stringtranslate.com

Инкрементные вычисления

Инкрементные вычисления , также известные как инкрементные вычисления , — это программная функция , которая при изменении фрагмента данных пытается сэкономить время , пересчитывая только те выходные данные, которые зависят от измененных данных. [1] [2] [3] Когда инкрементные вычисления успешны, они могут быть значительно быстрее, чем наивное вычисление новых выходных данных. Например, пакет программного обеспечения для работы с электронными таблицами может использовать инкрементные вычисления в своих функциях пересчета, чтобы обновить только те ячейки, содержащие формулы, которые зависят (прямо или косвенно) от измененных ячеек.

Когда инкрементные вычисления реализуются с помощью инструмента, который может автоматически реализовать их для множества различных фрагментов кода, такой инструмент является примером инструмента анализа программы для оптимизации .

Инкрементные вычисления предоставляют средства вычисления новой пары вход/выход (I2,O2) на основе старой пары вход/выход (I1,O1). Ключевой метод представлен функцией ΔP, которая связывает изменения на входе с изменениями на выходе.
Инкрементальные вычисления выводят новую пару вход/выход из одного или нескольких старых отношений вход/выход. Для этого ΔP должен связать изменение на входе с изменением на выходе. Потребитель результата может быть заинтересован в полном обновленном выходе или в дельта-выходе, или в обоих.

Статика против динамики

Методы инкрементальных вычислений можно в целом разделить на два типа подходов:

Статические подходы пытаются вывести инкрементальную программу из обычной программы P, используя, например, либо ручное проектирование и рефакторинг, либо автоматические преобразования программы. Эти преобразования программы происходят до того, как будут предоставлены какие-либо входные данные или изменения входных данных.

Динамические подходы записывают информацию о выполнении программы P на определенном входе (I1) и используют эту информацию при изменении входа (на I2) для обновления выхода (с O1 на O2). На рисунке показана связь между программой P, функцией расчета изменений ΔP, которая составляет ядро ​​инкрементной программы, и парой входов и выходов, I1, O1 и I2, O2.

Специализированные и универсальные подходы

Некоторые подходы к инкрементальным вычислениям являются специализированными, в то время как другие являются универсальными. Специализированные подходы требуют от программиста явного указания алгоритмов и структур данных, которые будут использоваться для сохранения неизменных подвычислений. С другой стороны, универсальные подходы используют язык, компилятор или алгоритмические методы для придания инкрементального поведения в противном случае неинкрементальным программам. [4]

Статические методы

Производные программы

Учитывая вычисление и потенциальное изменение , мы можем вставить код до того, как произойдет изменение (предпроизводная) и после изменения (постпроизводная), чтобы обновить значение быстрее, чем перезапуск . Пейдж записал список правил для формальной дифференциации программ в SUBSETL. [5]

Посмотреть обслуживание

В системах баз данных, таких как DBToaster, представления определяются с помощью реляционной алгебры. Инкрементальное обслуживание представлений статически анализирует реляционную алгебру для создания правил обновления, которые быстро поддерживают представление при наличии небольших обновлений, таких как вставка строки. [6]

Динамические методы

Инкрементальное вычисление может быть достигнуто путем построения графа зависимостей всех элементов данных, которые могут нуждаться в пересчете, и их зависимостей. Элементы, которые необходимо обновить при изменении одного элемента, задаются транзитивным замыканием отношения зависимости графа. Другими словами, если есть путь от измененного элемента к другому элементу, последний может быть обновлен (в зависимости от того, достигнет ли изменение в конечном итоге элемента). Граф зависимостей может нуждаться в обновлении по мере изменения зависимостей или по мере добавления или удаления элементов в систему. Он используется внутри реализации и обычно не требует отображения пользователю.

Избежать фиксации зависимостей между всеми возможными значениями можно, определив подмножество важных значений (например, результаты агрегации), по которым можно отслеживать зависимости, и постепенно пересчитывая другие зависимые переменные, тем самым уравновешивая объем информации о зависимостях, которую необходимо отслеживать, с объемом пересчета, который необходимо выполнить при изменении входных данных. [7]

Частичную оценку можно рассматривать как метод автоматизации простейшего возможного случая инкрементальных вычислений, в котором делается попытка разделить данные программы на две категории: те, которые могут изменяться в зависимости от входных данных программы, и те, которые не могут (и наименьшей единицей изменения являются просто «все данные, которые могут изменяться»). Частичную оценку можно комбинировать с другими методами инкрементальных вычислений.

При наличии циклов в графе зависимости одного прохода по графу может быть недостаточно для достижения фиксированной точки. В некоторых случаях полная переоценка системы семантически эквивалентна инкрементальной оценке и может быть более эффективной на практике, если не в теории. [8]

Существующие системы

Поддержка компилятора и языка

Фреймворки и библиотеки

Приложения

Смотрите также

Ссылки

  1. ^ Карлссон, Магнус (2002). «Монады для инкрементальных вычислений». Труды седьмой международной конференции ACM SIGPLAN по функциональному программированию . Нью-Йорк: ACM . С. 26–35. doi :10.1145/581478.581482. ISBN 1-58113-487-8.
  2. ^ Умут А. Акар (2005). Самонастраивающиеся вычисления (PDF) (диссертация доктора философии).
  3. ^ Камил Деметреску; Ирен Финокки; Андреа Рибикини (2011). «Реактивное императивное программирование с ограничениями потока данных». Труды 26-й Международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования (OOPSLA 2011) . ACM . С. 407–426. arXiv : 1104.2293 . doi : 10.1145/2048066.2048100. ISBN 978-1-4503-0940-0.
  4. ^ Ян Чен; Джошуа Данфилд; Мэтью А. Хаммер; Умут А. Акар. Неявное самонастраивающееся вычисление для чисто функциональных программ. ICFP '11. С. 129–141. Архивировано из оригинала 2016-10-30 . Получено 2018-03-12 .
  5. ^ Пейдж, Роберт (1981). Формальное дифференцирование: метод синтеза программ . UMI Research Press. ISBN 978-0-8357-1213-2.
  6. ^ Ахмад, Яниф; Кеннеди, Оливер; Кох, Кристоф; Николич, Милош (2012-06-01). «DBToaster: Обработка дельта более высокого порядка для динамических, часто свежих представлений». Proc. VLDB Endow . 5 (10): 968–979. arXiv : 1207.0137 . doi :10.14778/2336664.2336670. ISSN  2150-8097.
  7. ^ Мугилан Мариаппан; Кевал Вора (2019). «GraphBolt: синхронная обработка потоковых графов на основе зависимостей». На Европейской конференции по компьютерным системам (EuroSys'19) . стр. 25:1–25:16. doi :10.1145/3302424.3303974.
  8. ^ Кимберли Берчетт; Грегори Х. Купер; Шрирам Кришнамурти (2007). «Понижение: метод статической оптимизации для прозрачной функциональной реактивности». В симпозиуме ACM SIGPLAN по частичной оценке и семантической манипуляции программами . стр. 71–80. CiteSeerX 10.1.1.90.5866 . ISBN  978-1-59593-620-2.
  9. ^ Хаммер, Мэтью А.; Акар, Умут А.; Чен, Ян (2009). "CEAL". Труды конференции ACM SIGPLAN 2009 года по проектированию и реализации языков программирования - PLDI '09 . стр. 25. doi :10.1145/1542476.1542480. ISBN 9781605583921. S2CID  11058228.
  10. ^ Репс, Томас; Тейтельбаум, Тим (1984). "Генератор синтезатора". Труды первого симпозиума по программной инженерии ACM SIGSOFT/SIGPLAN по практическим средам разработки программного обеспечения - SDE 1. стр. 42–48. doi :10.1145/800020.808247. ISBN 978-0897911313.
  11. ^ "Adapton: Абстракции языка программирования для инкрементальных вычислений". adaptation.org . Получено 2016-10-07 .
  12. ^ Saha, Diptikalyan; Ramakrishnan, CR (2005). "Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs". Практические аспекты декларативных языков . Конспект лекций по информатике. Том 3819. С. 215–229. CiteSeerX 10.1.1.111.7484 . doi :10.1007/11603023_15. ISBN  978-3-540-30947-5. ISSN  0302-9743.
  13. ^ Хаммер, Мэтью; Фанг, Ху; Хикс, Майкл; Фостер, Джеффри (2014). ADAPTON: Компонуемые, управляемые спросом инкрементальные вычисления (PDF) . PLDI.