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

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

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

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

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

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

Состояние

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

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

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

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

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

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

История

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

В 1966 году доктор философии. Тезис, он-лайн Графическое описание процедур Компьютер , Bert Сазерленд создал одну из первых графических основ программирования потоков данных для того , чтобы сделать параллельное программирование проще. Последующие языки потока данных часто разрабатывались в крупных суперкомпьютерных лабораториях. POGOL, в остальном обычный язык обработки данных, разработанный в NSA , компилировал крупномасштабные приложения, состоящие из нескольких операций «файл-файл», например слияния, выбора, суммирования или преобразования, в эффективный код, который исключал создание или запись промежуточных файлы в максимально возможной степени. SISAL , популярный язык потока данных, разработанный в Ливерморской национальной лаборатории Лоуренса , похож на большинство языков, управляемых операторами, но переменные следует назначать один раз . Это позволяет компилятору легко идентифицировать входы и выходы. Ряд отстоящих SISAL были разработаны, в том числе SAC , Single Assignment C , который пытается оставаться рядом с популярным языком программирования С , как это возможно.

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

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

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

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

Языки

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

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

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

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

использованная литература

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