В компьютерном программировании программирование потока данных — это парадигма программирования , которая моделирует программу как направленный граф данных, передаваемых между операциями, тем самым реализуя принципы и архитектуру потока данных . [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]
Первопроходцем в области потоков данных был язык BLOck DIagram (BLODI), опубликованный в 1961 году Джоном Ларри Келли-младшим , Кэрол Лохбаум и Виктором А. Высоцким для спецификации систем выборочных данных . [9] Спецификация функциональных блоков BLODI (усилители, сумматоры, линии задержки и т. д.) и их взаимосвязей была скомпилирована в единый цикл, который обновлял всю систему за один такт часов.
В докторской диссертации 1966 года « Онлайновая графическая спецификация компьютерных процедур » [10] Берт Сазерленд создал одну из первых графических структур программирования потоков данных, чтобы упростить параллельное программирование. Последующие языки потоков данных часто разрабатывались в крупных суперкомпьютерных лабораториях. POGOL, в остальном обычный язык обработки данных, разработанный в АНБ , компилировал крупномасштабные приложения, состоящие из нескольких операций «файл-файл», например, слияние, выбор, суммирование или преобразование, в эффективный код, который исключал создание или запись в промежуточные файлы в максимально возможной степени. [11] SISAL , популярный язык потоков данных, разработанный в Ливерморской национальной лаборатории имени Лоуренса , похож на большинство языков, управляемых операторами, но переменные должны быть назначены один раз . Это позволяет компилятору легко идентифицировать входы и выходы. Было разработано несколько ответвлений SISAL, включая SAC , Single Assignment C , который пытается оставаться как можно ближе к популярному языку программирования C.
ВМС США финансировали разработку нотации графа обработки сигналов (SPGN) и ACOS, начиная с начала 1980-х годов. Это используется на ряде платформ в этой области сегодня. [12]
Более радикальная концепция — Prograph , в которой программы строятся как графики на экране, а переменные полностью заменяются линиями, связывающими входы с выходами. Кстати, Prograph изначально был написан на Macintosh , который оставался однопроцессорным до появления DayStar Genesis MP в 1996 году. [ необходима цитата ]
Существует множество аппаратных архитектур, ориентированных на эффективную реализацию моделей программирования потоков данных. [ неопределенно ] Архитектура потока данных с тегами от Массачусетского технологического института была разработана Грегом Пападопулосом . [ чрезмерный вес? – обсудить ]
Поток данных был предложен [ кем? ] как абстракция для определения глобального поведения компонентов распределенной системы: в модели программирования живых распределенных объектов распределенные потоки данных используются для хранения и передачи состояния, и как таковые они играют роль, аналогичную переменным, полям и параметрам в языках программирования типа Java.
Языки программирования потоков данных включают в себя: