Инкрементальные вычисления - Incremental computing

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

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

При инкрементных вычислениях новая пара ввода / вывода выводится из одного или нескольких старых отношений ввода / вывода. Для этого ΔP должно соотносить изменение входа с изменением выхода. Потребитель результата может быть заинтересован в полностью обновленном выводе или выводе дельты, или обоими.

Статический против динамического

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

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

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

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

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

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

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

Учитывая вычисление ${displaystyle C = f (x_ {1}, x_ {2}, dots x_ {n})}$ и потенциальное изменение ${displaystyle x_ {j}: = Delta _ {x_ {j}}}$ , мы можем вставить код перед изменением (предварительная производная) и после изменения (пост-производная), чтобы обновить значение ${displaystyle C}$ быстрее, чем повторный запуск ${displaystyle f}$ . Пейдж записала список правил формального разделения программ в SUBSETL.^[5]

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

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

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

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

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

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

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

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

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

Автоматическая инкрементализация (также называемая «самонастраивающимся вычислением» и «адаптивным функциональным программированием»),^[9] Delta ML, Haskell Adaptive
Корнеллский синтезатор-генератор^[10]
IceDust - пользовательский предметно-ориентированный язык.

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

Адаптон^[11] - с реализациями на нескольких языках
Ограничения одностороннего потока данных (реактивные вычисления в C ++)
Дифференциальный поток данных
Джейн Стрит Инкрементальный
Инкрементальный журнал данных (Logicblox)
Инкрементный пролог (XSB)^[12]
Доменные подходы:
- Инкрементальная проверка типа

Приложения

Базы данных (просмотр обслуживания)
Системы сборки
Таблицы^[13]
Среды разработки
Финансовые вычисления
Оценка грамматики атрибутов
Графические вычисления и запросы
GUI (например, React и DOM diffing)
Научные приложения

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

Рекомендации

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

[monads-for-incremental-1] Карлссон, Магнус (2002). «Монады для инкрементальных вычислений». Материалы седьмой международной конференции ACM SIGPLAN по функциональному программированию. Нью-Йорк: ACM. С. 26–35. Дои:10.1145/581478.581482. ISBN 1-58113-487-8.

[2] Умут А. Акар (2005). Самонастраивающееся вычисление (PDF) (Кандидатская диссертация).

[3] Камил Деметреску; Ирен Финокки; Андреа Рибичини (2011). «Реактивное императивное программирование с ограничениями потока данных». Материалы 26-й Международной конференции ACM по языкам и приложениям систем объектно-ориентированного программирования (OOPSLA 2011). ACM. С. 407–426. arXiv:1104.2293. Дои: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] Ахмад, Яниф; Кеннеди, Оливер; Кох, Кристоф; Николич, Милош (01.06.2012). «DBToaster: Дельта-обработка высшего порядка для динамических, часто свежих представлений». Proc. VLDB Endow. 5 (10): 968–979. arXiv:1207.0137. Дои:10.14778/2336664.2336670. ISSN 2150-8097.

[7] Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: управляемая зависимостями синхронная обработка потоковых графов». На Европейской конференции по компьютерным системам (EuroSys'19). С. 25: 1–25: 16. Дои:10.1145/3302424.3303974.

[8] Кимберли Берчетт; Грегори Х. Купер; Шрирам Кришнамурти (2007). «Понижение: метод статической оптимизации для прозрачной функциональной реактивности». В симпозиуме ACM SIGPLAN по частичной оценке и манипулированию программами на основе семантики. С. 71–80. CiteSeerX 10.1.1.90.5866. ISBN 978-1-59593-620-2.

[HammerAcar2009-9] Хаммер, Мэтью А .; Acar, Umut A .; Чен, Ян (2009). «CEAL». Материалы конференции 2009 ACM SIGPLAN по проектированию и реализации языков программирования - PLDI '09. п. 25. Дои:10.1145/1542476.1542480. ISBN 9781605583921.

[RepsTeitelbaum1984-10] Представители, Томас; Тейтельбаум, Тим (1984). «Синтезатор-генератор». Материалы первого симпозиума по разработке программного обеспечения ACM SIGSOFT / SIGPLAN по практическим средам разработки программного обеспечения - SDE 1. С. 42–48. Дои:10.1145/800020.808247. ISBN 978-0897911313.

[11] "Adapton: абстракции языка программирования для инкрементных вычислений". adapton.org. Получено 2016-10-07.

[SahaRamakrishnan2005-12] Саха, Диптикалян; Рамакришнан, К. Р. (2005). «Пошаговая оценка табличного пролога: помимо программ чистой логики». Практические аспекты декларативных языков. Конспект лекций по информатике. 3819. С. 215–229. CiteSeerX 10.1.1.111.7484. Дои:10.1007/11603023_15. ISBN 978-3-540-30947-5. ISSN 0302-9743.

[adapton-pldi2014-13] Хаммер, Мэтью; Пханг, Кху; Хикс, Майкл; Фостер, Джеффри (2014). ADAPTON: Составные инкрементальные вычисления по запросу (PDF). PLDI.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]