Русская Википедия:Программирование потоков данных

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Парадигмы программирования Программирование потоков данных (Шаблон:Lang-en) — подход к программированию, при котором программа моделируется в виде орграфа потока данных между операциями, подобного диаграмме потока данных. Развивается в программной инженерии с 1970-х годов[1].

Естественное визуальное представление наряду с поддержкой параллелизма являются двумя привлекательными для разработчиков свойствами данной парадигмы[1]. Разумеется, программирование потоков данных необязательно сопряжено с инструментами визуального программирования.

Программисты Unix знакомы с программированием потоков данных, так как в командной оболочке этой системы применяются именованные каналы и другие подобные средства межпроцессного взаимодействия[2].

Описание

Основой работы программ потоков данных (dataflow) является активация вычислений на узлах (node), которые можно считать чёрными ящиками, вызываемая изменениями, обновлениями входных данных. Узел (в модели — вершина графа) представляет из себя элемент, который производит обработку данных на входе, преобразуя их в данные на выходе. Работа узла в течение периода активации считается единичным вычислением. Узлы посылают и принимают данные через порты (port) — точки соединения дуг (рёбер графа) и узлов. Порты — всё, что связывает узел с окружением. Для различения узлы могут иметь имена. Результат вычисления узла часто, но не обязательно, является функцией входных данных, то есть, результат может изменяться со временем. Вычислительная работа узла называется активацией (activation, firing). В активированном состоянии узел берёт входные данные, производит вычисления, отдаёт выходные данные в соответствующие порты. Передаваемые данные независимо от их типа называются токенами (token). Токены поступают по дугам (их можно называть рёбрами, связями, соединениями). Появление данных на входящей дуге может вызывать активацию узла. Обычно принято, что в дуге находится не более одного токена, но в теории можно создать и модели с неограниченной ёмкостью. В более разработанных моделях дуги могут сливаться в одну или разветвлятьсяШаблон:SfnШаблон:Sfn.

В результате программирования получается программа потоков данных — ориентированный граф. Все пути взаимодействия элементов явно задаются программистом. В простейшем случае конвейерной обработки (pipeline dataflow) элементы можно задать последовательностью единичных вычислений. Вычисления производятся по очереди, при поступлении токенов на вход. Такая схема называется выполнением, управляемым данными (data-driven execution)Шаблон:Sfn.

Характеристики

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

  • Push- или pull-дисциплины для дуг. В первом случае токены «выталкиваются» по инициативе производителя данных, а во втором инициатором запроса токена является потребитель. Два подхода также известны как вычисление, управляемое данными (data-driven computation) и вычисление, управляемое запросами (demand-driven computation)Шаблон:Sfn
  • Изменяемые (mutable) или неизменяемые (immutable) данные. Хотя неизменяемые данные — наиболее удачный подход для параллельной обработки, некоторые реализации, основанные на императивных языках программирования, могут требовать изменяемых данных со всеми необходимыми механизмами синхронизации.
  • Возможности слияния (join) и разветвления (split) дуг. В случае слияния, порт назначения дуги получает токены от любого из двух портов в начале дуги. При разветвлении токен обычно копируется двум получателям. Слияния и разветвления могут быть множественными.
  • Статическая или динамическая программа потока данных. Эта характеристика касается возможности изменений в графе потока данных. Аппаратные реализации, как правило, используют статические программы, но в общем случае структура графа может динамически изменяться. В динамической программе некоторая дуга может изменить порт назначения или узел обработки — свои характеристики.
  • Узел может быть функциональным или же хранить своё состояние (stateful) внутри.
  • Синхронная или асинхронная активация. Один из важнейших параметров классификации систем потоков данных. Синхронная активация подразумевает некоторый заранее зафиксированный и спланированный порядок активации, построенный с учётом всей программы в целом. В системе с асинхронной активацией каждый блок заботится о своём настоящем и активация происходит при удовлетворении условий, например, появлении данных на входе. Для систем с асинхронной активацией могут потребоваться дуги ёмкостью более одного токена. Схема активации может быть и смешанной (hybrid).
  • Множественные входные и выходные порты. Наличие нескольких портов может потребовать и изменения для условий активации. Например, активация может происходить, если хотя бы один из входов получил данные. В более сложных случаях могут использоваться схемы активации (fire pattern), в котором для каждого порта одно из четырёх отношений к активации: 1 — на входе есть данные, 0 — на входе нет данных, X — наличие данных безразлично, * — безусловная активация (независимо от условий для других портов). Узел может иметь несколько схем, которые проверяются одна за другой, пока схема не будет соответствовать текущему состоянию. Например, трёхпортовый узел со схемой «[1, 1, X], [0, X, 0]» будет активизирован, если первые два порта получили данные или на первом и третьем порту нет данных.
  • Обратные связи, или циклы, позволяют использовать выходной поток снова на входе вычислительного блока. При работе с циклами необходимо избегать тупиковых ситуаций (см. взаимная блокировка), при котором некоторый узел будет ждать данных на входе, которые зависят от его же выхода. Для работы с обратной связью может потребовать задание начальных токенов (ещё до запуска программы) для дуг обратной связи или использование одноразовых узлов (one-shot), которые активируются ровно один раз, в начале работы программы.
  • Составные узлы (compound node) позволяют пакетировать примитивные узлы в более крупные модули.
  • Рекурсивные узлы. Разновидность составного узла, содержащего копию самого себя.
  • Многоскоростное производство и потребление токенов. Для повышения производительности при активации может быть позволено получение и отправка нескольких токенов из порта сразу.
  • Узлы с принадлежащими им портами также называются акторами [3]. Классические акторы, предложенные Карлом Хьюиттом [4], являются частным случаем акторов потоков данных, а именно, имеющие ровно один входной порт и ни одного выходного.

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Tiago Boldt Sousa Dataflow Programming Concept, Languages and Applications Шаблон:Wayback
  2. ↑ Шаблон:Книга
  3. ↑ A Structured Description Of Dataflow Actors And Its Application [1] Шаблон:Wayback
  4. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Программирование_потоков_данных&oldid=10649747