Программирование потоков данных

В компьютерном программировании программирование потоков данных — это парадигма программирования , которая моделирует программу как ориентированный граф данных, передаваемых между операциями, тем самым реализуя потока данных . принципы и архитектуру ^[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. - как языки программирования.

Языки

Языки программирования потоков данных включают в себя:

Сеу (язык программирования)
АСКЕТ
AviSynth для обработки видео. Язык сценариев
BMDFM Бинарная модульная машина потока данных
CAL
Cuneiform — функциональный язык рабочих процессов.
Конвейеры CMS
Хьюм
Джоуль
Keysight VEE
KNIME — бесплатная платформа для анализа данных, отчетности и интеграции с открытым исходным кодом.
ЛабВЬЮ , Г ^[4]
Линда
Ясный ^[3]
Блеск
Макс/MSP
Microsoft Visual Programming Language — компонент Microsoft Robotics Studio, предназначенный для робототехники. программирования
Nextflow : язык рабочего процесса
Orange — инструмент визуального программирования с открытым исходным кодом для интеллектуального анализа данных , статистического анализа данных и машинного обучения .
Oz теперь также распространяется с версии 1.4.0.
Пилот трубопровода
Програф
Чистые данные
Quartz Composer — разработан Apple ; используется для графической анимации и эффектов
SAC Одно назначение C
СИГНАЛ (синхронный язык, ориентированный на потоки данных, позволяющий использовать многотактовые спецификации)
Симулинк
СИЗАЛЬ
SystemVerilog — язык описания оборудования.
Verilog — язык описания оборудования, включенный в стандарт SystemVerilog в 2009 году.
VisSim — язык блок-схем для моделирования динамических систем и автоматической генерации прошивки.
VHDL — язык описания оборудования.
Wapice IOT-TICKET реализует безымянный язык программирования визуальных потоков данных для анализа данных Интернета вещей и составления отчетов.
XEE (Starlight) Среда разработки XML
XPoc

Библиотеки

Apache Beam : Java/Scala SDK, который унифицирует потоковую (и пакетную) обработку с поддержкой нескольких механизмов выполнения (Apache Spark, Apache Flink, Google Dataflow и т. д.).
Apache Flink : библиотека Java/Scala, которая позволяет выполнять потоковые (и пакетные) вычисления поверх распределенного кластера Hadoop (или другого).
Апач Спарк
SystemC : библиотека для C++, в основном предназначенная для проектирования аппаратного обеспечения.
TensorFlow : библиотека машинного обучения, основанная на программировании потоков данных.

См. также

Ссылки

^ Jump up to: ^а ^б Шварцкопф, Мальта (7 марта 2020 г.). «Замечательная полезность вычислений с потоками данных» . АСМ СИГОПС . Проверено 31 июля 2022 г.
^ Jump up to: ^а ^б ^с Джонстон, Уэсли М.; младший Пол Ханна; Ричард Дж. Миллар (март 2004 г.). «Достижения в языках программирования потоков данных» (PDF) . Обзоры вычислительной техники ACM . 36 : 1–34. дои : 10.1145/1013208.1013209 . S2CID 5257722 . Проверено 15 августа 2013 г.
^ Jump up to: ^а ^б ^с ^д ^и Уодж, Уильям В.; Эдвард А. Эшкрофт (1985). Lucid, язык программирования потоков данных (иллюстрированное издание). Академия Пресс. ISBN 9780127296500 . Проверено 15 августа 2013 г.
^ Jump up to: ^а ^б «Основы программирования потоков данных» . Начало работы с продуктами NI . Национальная корпорация инструментов . Проверено 15 августа 2013 г.
^ Хартер, Ричард. «Языки потоков данных и программирование. Часть I» . Мир Ричарда Хартера . Архивировано из оригинала 8 декабря 2015 года . Проверено 15 августа 2013 г.
^ «Почему языки программирования потоков данных идеальны для программирования параллельного оборудования» . Серия технических документов «Основы многоядерного программирования» . Национальная корпорация инструментов . Проверено 15 августа 2013 г.
^ МакШерри, Фрэнк; Мюррей, Дерек; Айзекс, Ребекка; Айсард, Майкл (5 января 2013 г.). «Дифференциальный поток данных» . Майкрософт . Проверено 31 июля 2022 г.
^ «Дифференциальный поток данных» . Своевременный поток данных. 30 июля 2022 г. Проверено 31 июля 2022 г.
^ Джон Л. Келли младший; Кэрол Лохбаум; В. А. Высоцкий (1961). «Компилятор блок-схем». Белл Систем Тех. Дж . 40 (3): 669–678. дои : 10.1002/j.1538-7305.1961.tb03236.x .
^ Сазерленд, Уильям Роберт (январь 1966 г.). Он-лайн графическая спецификация компьютерных процедур (кандидатская диссертация). Массачусетский технологический институт . hdl : 1721.1/13474 . Проверено 25 августа 2022 г.
^ Глория Ламберт (1973). «Масштабная обработка файлов: ПОГОЛ». POPL '73: Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования . АКМ . стр. 226–234.
^ Обработка подводных акустических данных, Ю.Т. Чан

Внешние ссылки

Книга: Потоки данных и системы реактивного программирования.
Основы программирования потоков данных на F# и C#
Программирование потоков данных — концепция, языки и приложения
Статическое планирование программ синхронного потока данных для цифровой обработки сигналов
Обработка огромных нагрузок без усложнения. Основные концепции программирования потоков данных, доктор Доббс, сентябрь 2011 г.

[sigops-1] Jump up to: ^а ^б Шварцкопф, Мальта (7 марта 2020 г.). «Замечательная полезность вычислений с потоками данных» . АСМ СИГОПС . Проверено 31 июля 2022 г.

[advances-2] Jump up to: ^а ^б ^с Джонстон, Уэсли М.; младший Пол Ханна; Ричард Дж. Миллар (март 2004 г.). «Достижения в языках программирования потоков данных» (PDF) . Обзоры вычислительной техники ACM . 36 : 1–34. дои : 10.1145/1013208.1013209 . S2CID 5257722 . Проверено 15 августа 2013 г.

[lucid-3] Jump up to: ^а ^б ^с ^д ^и Уодж, Уильям В.; Эдвард А. Эшкрофт (1985). Lucid, язык программирования потоков данных (иллюстрированное издание). Академия Пресс. ISBN 9780127296500 . Проверено 15 августа 2013 г.

[labview-4] Jump up to: ^а ^б «Основы программирования потоков данных» . Начало работы с продуктами NI . Национальная корпорация инструментов . Проверено 15 августа 2013 г.

[5] Хартер, Ричард. «Языки потоков данных и программирование. Часть I» . Мир Ричарда Хартера . Архивировано из оригинала 8 декабря 2015 года . Проверено 15 августа 2013 г.

[6] «Почему языки программирования потоков данных идеальны для программирования параллельного оборудования» . Серия технических документов «Основы многоядерного программирования» . Национальная корпорация инструментов . Проверено 15 августа 2013 г.

[differential-paper-7] МакШерри, Фрэнк; Мюррей, Дерек; Айзекс, Ребекка; Айсард, Майкл (5 января 2013 г.). «Дифференциальный поток данных» . Майкрософт . Проверено 31 июля 2022 г.

[differential-github-8] «Дифференциальный поток данных» . Своевременный поток данных. 30 июля 2022 г. Проверено 31 июля 2022 г.

[Kelly1961-9] Джон Л. Келли младший; Кэрол Лохбаум; В. А. Высоцкий (1961). «Компилятор блок-схем». Белл Систем Тех. Дж . 40 (3): 669–678. дои : 10.1002/j.1538-7305.1961.tb03236.x .

[sutherland1966-10] Сазерленд, Уильям Роберт (январь 1966 г.). Он-лайн графическая спецификация компьютерных процедур (кандидатская диссертация). Массачусетский технологический институт . hdl : 1721.1/13474 . Проверено 25 августа 2022 г.

[11] Глория Ламберт (1973). «Масштабная обработка файлов: ПОГОЛ». POPL '73: Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования . АКМ . стр. 226–234.

[12] Обработка подводных акустических данных, Ю.Т. Чан

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Типы языков программирования
Level	Machine Assembly Compiled Interpreted Low-level High-level Very high-level Esoteric
Generation	First Second Third Fourth Fifth