Програмування потоків даних

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

Природне візуальне подання разом з підтримкою паралелізму є двома привабливими для розробників властивостями цієї парадигми. Проте, програмування потоків даних не обов'язково пов'язане з інструментами візуального програмування.

Програмісти Unix знайомі з програмуванням потоків даних, оскільки в командній оболонці цієї системи застосовуються іменовані канали й інші подібні засоби взаємодії між процесами.

Опис

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

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

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

У програмуванні потоків даних можна застосовувати і складніші конфігурації, ніж конвеєр. Зокрема, такі можливості можна додати до найпростішої моделі (в тій чи іншій комбінації):

• Push- або pull-дисципліни для дуг. У першому випадку токени «виштовхуються» з ініціативи виробника даних, а в другому ініціатором запиту токена є споживач. Два підходи також відомі як обчислення, кероване даними (англ. data-driven computation) і обчислення, кероване запитами (англ. demand-driven computation)
• Змінні (англ. 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. — 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. — 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-. — ISBN 9780824720667. to Volume Visualization 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-. — ISBN 9780824720667.
• Wesley M. Johnston, JR 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