WikiSort.ru - Программирование

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

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

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

Описание

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

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

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

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

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

См. также

• Диаграмма потоков данных (DFD)

Примечания

Литература

• Van-Roy, P. and Haridi, S. Concepts, Techniques, and Models of Computer Programming. — Prentice-Hall, 2004. — 900 p. — ISBN 9780262220699.
• Sharp, J.A. Data Flow Computing: Theory and Practice. — Intellect, Limited, 1992. — 566 p. — ISBN 9780893919214.
• Carkci, M. Dataflow and Reactive Programming Systems: A Practical Guide. — CreateSpace Independent Publishing Platform, 2014. — 570 p. — ISBN 9781497422445.
• Gehani, N. Ada: Concurrent Programming. — Silicon Press, 1991. — P. xii. — 216 p. — ISBN 9780929306087.* Bebis, G. and Boyle, R. and Parvin, B. and Koracin, D. and Wang, S. and Kyungnam, K. and Benes, B. and Moreland, K. and Borst, C. and DiVerdi, S. and others. Advances in Visual Computing: 7th International Symposium, ISVC 2011, Las Vegas, NV, USA, September 26-28, 2011. Proceedings. — Springer Berlin Heidelberg, 2011. — P. 260. — ISBN 9783642240317.
• Gengnagel, C. and Kilian, A. and Nembrini, J. and Scheurer, F. Rethinking Prototyping: Proceedings of the Design Modelling Symposium Berlin 2013. — epubli GmbH, 2013. — P. 53-55. — 662 p. — ISBN 9783844268454.
• Kent, A. Dataflow languages // Encyclopedia of Library and Information Science: Volume 66 - Supplement 29 - Automated System for the Generation of Document Indexes to Volume Visualization. — Taylor & Francis, 2000. — P. 101-. — 500 p. — ISBN 9780824720667.
• Wesley M. Johnston, J. R. Paul Hanna, Richard J. Millar. Advances in Dataflow Programming Languages. ACM Computing Surveys, Vol. 36, No. 1, March 2004, pp. 1–34.

Ссылки

• Tiago Boldt Sousa Dataflow Programming Concept, Languages and Applications

Для улучшения этой статьи желательно: Добавить иллюстрации.