В компьютерном программировании программирование потоков данных — это парадигма программирования , которая моделирует программу как ориентированный граф данных, передаваемых между операциями, тем самым реализуя принципы и архитектуру потока данных . [1] Языки программирования потоков данных имеют некоторые общие черты с функциональными языками и обычно разрабатываются для того, чтобы перенести некоторые функциональные концепции в язык, более подходящий для числовой обработки. Некоторые авторы используют термин «поток данных» вместо «поток данных» , чтобы избежать путаницы с вычислениями потоков данных или архитектурой потоков данных , основанной на недетерминированной машинной парадигме. Программирование потоков данных было впервые разработано Джеком Деннисом и его аспирантами Массачусетского технологического института в 1960-х годах.
Традиционно программа моделируется как серия операций, выполняемых в определенном порядке; это можно назвать последовательным, [2] : стр.3 процедурным, [3] потоком управления [3] (указывающим, что программа выбирает конкретный путь) или императивным программированием . Программа фокусируется на командах, в соответствии с концепцией фон Неймана [2] : стр.3 последовательного программирования, где данные обычно «находятся в состоянии покоя». [3] : стр.7
Напротив, программирование потоков данных подчеркивает движение данных и моделирует программы как серию связей. Явно определенные входы и выходы соединяют операции, которые функционируют как черные ящики . [3] : стр.2 Операция запускается, как только все ее входные данные становятся действительными. [4] Таким образом, языки потоков данных по своей сути параллельны и могут хорошо работать в больших децентрализованных системах. [2] : стр.3 [5] [6]
Одной из ключевых концепций компьютерного программирования является идея состояния , по сути, моментального снимка различных состояний в системе. Большинство языков программирования требуют значительного объема информации о состоянии, которая обычно скрыта от программиста. Часто компьютер сам понятия не имеет, какая часть информации кодирует постоянное состояние. Это серьезная проблема, поскольку информация о состоянии должна распределяться между несколькими процессорами в параллельных вычислительных машинах. Большинство языков вынуждают программиста добавлять дополнительный код, чтобы указать, какие данные и части кода важны для состояния. Этот код имеет тенденцию быть дорогим с точки зрения производительности, а также трудным для чтения и отладки. Явный параллелизм — одна из основных причин низкой производительности Enterprise Java Beans при создании приложений, не поддерживающих OLTP , с интенсивным использованием данных . [ нужна цитата ]
Если последовательную программу можно представить как одного работника, перемещающегося между задачами (операциями), то программа потока данных больше похожа на группу рабочих на сборочной линии , каждый из которых выполняет определенную задачу всякий раз, когда доступны материалы. Поскольку операции касаются только доступности входных данных, у них нет скрытого состояния, которое нужно отслеживать, и все они «готовы» одновременно.
Программы потока данных представлены по-разному. Традиционная программа обычно представляется как серия текстовых инструкций, что приемлемо для описания последовательной системы, которая передает данные между небольшими специализированными инструментами, которые принимают, обрабатывают и возвращают данные. Программы потока данных начинаются с входных данных, например параметров командной строки , и иллюстрируют, как эти данные используются и изменяются. Поток данных является явным, часто визуально иллюстрируется в виде линии или канала.
С точки зрения кодирования программа потока данных может быть реализована в виде хеш-таблицы с уникальными входными данными в качестве ключей, используемых для поиска указателей на инструкции. Когда какая-либо операция завершается, программа просматривает список операций, пока не находит первую операцию, все входные данные которой в данный момент действительны, и запускает ее. Когда эта операция завершается, она обычно выводит данные, тем самым делая другую операцию действительной.
Для параллельной работы требуется общий доступ только к списку; это состояние всей программы. Таким образом, задача поддержания состояния снимается с программиста и передается среде выполнения языка . На машинах с одним процессорным ядром, где реализация, предназначенная для параллельной работы, просто приведет к накладным расходам, эти накладные расходы можно полностью устранить, используя другую среду выполнения.
Некоторые недавние библиотеки потоков данных, такие как Differential/Timely Dataflow, использовали инкрементные вычисления для гораздо более эффективной обработки данных. [1] [7] [8]
Пионером языка потоков данных был BLODI (BLOck DIAgram), опубликованный в 1961 году Джоном Ларри Келли-младшим , Кэрол Лохбаум и Виктором А. Высоцким для определения систем выборочных данных . [9] Спецификация BLODI функциональных блоков (усилителей, сумматоров, линий задержки и т. д.) и их взаимосвязей была скомпилирована в единый цикл, который обновлял всю систему за один такт.
В 1966 году доктор философии. диссертация «Онлайн-графическая спецификация компьютерных процедур» [ 10] Берт Сазерленд создал одну из первых сред графического программирования потоков данных, чтобы упростить параллельное программирование. Последующие языки потоков данных часто разрабатывались в крупных суперкомпьютерных лабораториях. POGOL, традиционный язык обработки данных, разработанный в АНБ , компилировал крупномасштабные приложения, состоящие из множества операций между файлами, например, слияния, выбора, суммирования или преобразования, в эффективный код, исключающий создание или запись в промежуточный код. файлы в максимально возможной степени. [11] SISAL , популярный язык управления потоками данных, разработанный в Ливерморской национальной лаборатории имени Лоуренса , похож на большинство языков, управляемых операторами, но переменные следует назначать один раз . Это позволяет компилятору легко идентифицировать входные и выходные данные. Был разработан ряд ответвлений SISAL, в том числе SAC , Single Assignment C , который пытается оставаться как можно ближе к популярному языку программирования C.
ВМС США финансировали разработку ACOS и SPGN (обозначение графа обработки сигналов), начиная с начала 1980-х годов. Сегодня это используется на ряде платформ. [12]
Более радикальная концепция — Prograph , в которой программы создаются в виде экранных графиков, а переменные полностью заменяются линиями, связывающими входные данные с выходными данными. Между прочим, Prograph изначально был написан на Macintosh , который оставался однопроцессорным до появления DayStar Genesis MP в 1996 году .
Существует множество аппаратных архитектур, ориентированных на эффективную реализацию моделей программирования потоков данных. [ неопределенно ] Архитектура потока данных с тегированными токенами MIT была разработана Грегом Пападопулосом . [ чрезмерный вес? ]
Поток данных был предложен [ кем? ] как абстракция для определения глобального поведения компонентов распределенной системы: в модели программирования живых распределенных объектов распределенные потоки данных используются для хранения и передачи состояния и, как таковые, играют роль, аналогичную переменным, полям и параметрам в Java-подобные языки программирования.
Языки программирования потоков данных включают в себя: