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

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

В компьютерное программирование, программирование потока данных это парадигма программирования который моделирует программу как ориентированный граф данных, передаваемых между операциями, таким образом реализуя поток данных принципы и архитектура. Поток данных языки программирования поделитесь некоторыми особенностями функциональные языки, и, как правило, были разработаны для того, чтобы привнести некоторые функциональные концепции в язык, более подходящий для обработки чисел. Некоторые авторы используют термин поток данных вместо поток данных чтобы избежать путаницы с вычислением потока данных или архитектура потока данных, основанный на парадигме недетерминированных машин. Программирование потока данных было впервые предложено Джек Деннис и его аспиранты Массачусетского технологического института в 1960-х годах.

Свойства языков программирования потоков данных

Традиционно программа моделируется как серия операций, выполняемых в определенном порядке; это можно назвать последовательным,[1]:стр.3процедурный,[2]поток управления[2] (указывая, что программа выбирает определенный путь), или императивное программирование. Программа ориентирована на команды в соответствии с фон Нейман[1]:стр.3 видение последовательного программирования, при котором данные обычно находятся в состоянии покоя.[2]:стр.7

Напротив, программирование потока данных подчеркивает движение данных и моделирует программы как серию соединений. Явно определенные входы и выходы соединяют операции, которые работают как черные ящики.[2]:стр.2 Операция запускается, как только все ее входные данные становятся действительными.[3] Таким образом, языки потоков данных по своей сути параллельны и могут хорошо работать в больших децентрализованных системах.[1]:стр.3[4][5]

Состояние

Одна из ключевых концепций компьютерного программирования - идея государственный, по сути, снимок различных состояний в системе. Большинство языков программирования требуют значительного количества информации о состоянии, которая обычно скрыта от программиста. Часто сам компьютер не знает, какая часть информации кодирует устойчивое состояние. Это серьезная проблема, так как информация о состоянии должна совместно использоваться несколькими процессорами в параллельная обработка машины. Большинство языков заставляют программиста добавлять дополнительный код, чтобы указать, какие данные и части кода важны для состояния. Этот код имеет тенденцию быть дорогим с точки зрения производительности, а также сложен для чтения и отладки. Явный параллелизм является одной из основных причин плохой работы Корпоративные компоненты Java при создании ресурсоемких, неOLTP Приложения.[нужна цитата ]

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

Представление

Программы потока данных представлены по-разному. Традиционная программа обычно представлена ​​в виде серии текстовых инструкций, что разумно для описания последовательной системы, которая передает данные между небольшими одноцелевыми инструментами, которые получают, обрабатывают и возвращают. Программы потока данных начинаются с ввода, возможно, командная строка параметры и проиллюстрировать, как эти данные используются и изменяются. Поток данных явный, часто визуально показан в виде линии или конвейера.

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

Для параллельной работы требуется общий доступ только к списку; это состояние всей программы. Таким образом, задача поддержания состояния снимается с программиста и передается языку. время выполнения. На машинах с одним ядром процессора, где реализация, предназначенная для параллельной работы, просто привела бы к накладным расходам, эти накладные расходы можно полностью устранить, используя другую среду выполнения.

История

Пионерский язык потока данных был BLODI (BLOck DIagram), разработанная Джон Ларри Келли младший, Кэрол Лохбаум и Виктор Александрович Высоцкий для уточнения системы выборочных данных.[6] Спецификация BLODI функциональных блоков (усилители, сумматоры, линии задержки и т. Д.) И их взаимосвязей была скомпилирована в один цикл, который обновлял всю систему за один такт.

В 1966 году доктор философии. Тезис, Он-лайн графическая спецификация компьютерных процедур,[7] Берт Сазерленд создал одну из первых сред программирования с графическим потоком данных, чтобы упростить параллельное программирование. Последующие языки потока данных часто разрабатывались суперкомпьютер лаборатории. POGOL, традиционный язык обработки данных, разработанный в АНБ, скомпилировал крупномасштабные приложения, состоящие из нескольких операций преобразования файлов, например объединять, выбирать, резюмировать или преобразовывать в эффективный код, который исключает создание или запись в промежуточные файлы в максимально возможной степени.[8] СИЗАЛ, популярный язык обработки данных, разработанный в Национальная лаборатория Лоуренса Ливермора, похоже на большинство языков, управляемых операторами, но переменные должны быть назначается один раз. Это позволяет компилятор чтобы легко идентифицировать входы и выходы. Был разработан ряд ответвлений SISAL, в том числе SAC, Однократное присвоение C, который старается максимально приблизиться к популярным Язык программирования C насколько возможно.

ВМС США финансировали разработку ACOS и SPGN (обозначение графа обработки сигналов), начиная с начала 1980-х годов. Сегодня это используется на многих платформах.[9]

Более радикальная концепция Prograph, в котором программы построены в виде графиков на экране, а переменные полностью заменены линиями, связывающими входы с выходами. Между прочим, Prograph изначально был написан на Macintosh, который оставался однопроцессорным до появления DayStar Genesis MP в 1996 г.

Существует множество аппаратных архитектур, ориентированных на эффективную реализацию моделей программирования потоков данных. Архитектура потока данных с тегированным токеном MIT была разработана Грег Пападопулос.

Поток данных был предложен как абстракция для определения глобального поведения компонентов распределенной системы: в живые распределенные объекты модель программирования, распределенные потоки данных используются для хранения и передачи состояния, и поэтому они играют роль, аналогичную переменным, полям и параметрам в языках программирования, подобных Java.

Языки

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

Интерфейсы прикладного программирования

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

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

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

  1. ^ а б c Джонстон, Уэсли М .; J.R. Пол Ханна; Ричард Дж. Миллар (март 2004 г.). «Достижения в языках программирования потоков данных» (PDF). Опросы ACM Computing. 36: 1–34. Дои:10.1145/1013208.1013209. Получено 15 августа 2013.
  2. ^ а б c d е Уэдж, Уильям У .; Эдвард А. Эшкрофт (1985). Lucid, язык программирования потоков данных (Иллюстрированный ред.). Academia Press. ISBN  9780127296500. Получено 15 августа 2013.
  3. ^ а б «Основы программирования потока данных». Начало работы с продуктами NI. National Instruments Corporation. Получено 15 августа 2013.
  4. ^ Хартер, Ричард. «Языки потока данных и программирование - Часть I». Мир Ричарда Хартера. Архивировано из оригинал 8 декабря 2015 г.. Получено 15 августа 2013.
  5. ^ «Почему языки программирования потока данных идеально подходят для программирования параллельного оборудования». Серия информационных документов по основам многоядерного программирования. National Instruments Corporation. Получено 15 августа 2013.
  6. ^ Джон Л. Келли-младший; Кэрол Лохбаум; В. А. Высоцкий (1961). «Компилятор блок-схемы». Bell System Tech. J. 40 (3): 669–678. Дои:10.1002 / j.1538-7305.1961.tb03236.x.
  7. ^ У. Р. Сазерленд (1966). «Он-лайн графическая спецификация компьютерных процедур». Массачусетский технологический институт. Цитировать журнал требует | журнал = (помощь)
  8. ^ Глория Ламберт (1973). «Масштабная обработка файлов: ПОГОЛ». POPL '73: Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования. ACM. С. 226–234.
  9. ^ Обработка подводных акустических данных, Ю.Т. Чан

внешняя ссылка