Програмування потоків даних (англ. 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) дозволяють пакетувати примітивні вузли в більші модулі.
- Рекурсивні вузли. Різновид складеного вузла, що містить копію самого себе.
- Багатошвидкісне виробництво і споживання токенів. Для підвищення продуктивності при активації може дозволятися отримання і відсилання з порту кількох токенів відразу.
- Вузли з належними їм портами також називають акторами. Класичні актори, запропоновані [en], є окремим випадком акторів потоків даних, а саме, мають рівно один вхідний порт і жодного вихідного.
Див. також
- Діаграма потоків даних (DFD)
Примітки
- Tiago Boldt Sousa Dataflow Programming Concept, Languages and Applications
- Jon Orwant. Computer Science & Perl Programming: Best of The Perl Journal. — O'Reilly Media, Incorporated, 2002. — P. 146. — .
- Carkci, 2014, 2. Dataflow Explained.
- Sharp та 1992, 293.
- A Structured Description Of Dataflow Actors And Its Application
- ; Bishop, Peter; Steiger, Richard. A Universal Modular Actor Formalism for Artificial Intelligence. — IJCAI, 1973. — 7 July.
Література
- Van-Roy, P. and Haridi, S. Concepts, Techniques, and Models of Computer Programming. — Prentice-Hall, 2004. — 900 p. — .
- Sharp, J.A. Data Flow Computing: Theory and Practice. — Intellect, Limited, 1992. — 566 p. — .
- Carkci, M. Dataflow and Reactive Programming Systems: A Practical Guide. — CreateSpace Independent Publishing Platform, 2014. — 570 p. — .
- Gehani, N. Ada: Concurrent Programming. — Silicon Press, 1991. — P. xii. — . * 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. — .
- 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. — .
- 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-. — . 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-. — .
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Programuvannya potokiv danih angl dataflow programming pidhid do programuvannya za yakogo programa modelyuyetsya u viglyadi oriyentovanogo grafu potoku danih mizh operaciyami podibnogo do diagrami potokiv danih Rozvivayetsya v programnij inzheneriyi vid 1970 h rokiv Prirodne vizualne podannya razom z pidtrimkoyu paralelizmu ye dvoma privablivimi dlya rozrobnikiv vlastivostyami ciyeyi paradigmi Prote programuvannya potokiv danih ne obov yazkovo pov yazane z instrumentami vizualnogo programuvannya Programisti Unix znajomi z programuvannyam potokiv danih oskilki v komandnij obolonci ciyeyi sistemi zastosovuyutsya imenovani kanali j inshi podibni zasobi vzayemodiyi mizh procesami OpisOsnovoyu roboti program potokiv danih dataflow ye aktivaciya obchislen na vuzlah node yaki mozhna vvazhati chornimi yashikami sho viklikayetsya zminami onovlennyami vhidnih danih Vuzol u modeli vershina grafu ye elementom yakij opracovuye dani na vhodi peretvoryuyuchi yih na dani na vihodi Robota vuzla protyagom periodu aktivaciyi vvazhayetsya odinichnim obchislennyam Vuzli posilayut i prijmayut dani cherez porti port tochki z yednannya dug reber grafu i vuzliv Porti vse sho pov yazuye vuzol z otochennyam Dlya rozriznennya vuzli mozhut mati nazvi Rezultat obchislennya vuzla chasto ale ne obov yazkovo ye funkciyeyu vhidnih danih tobto rezultat mozhe zminyuvatisya z chasom Obchislyuvalna robota vuzla nazivayetsya aktivaciyeyu angl activation firing V aktivovanomu stani vuzol bere vhidni dani vikonuye obchislennya viddaye vihidni dani u vidpovidni porti Peredani dani nezalezhno vid yih tipu nazivayutsya tokenami angl token Tokeni nadhodyat po dugah yih mozhna nazivati rebrami zv yazkami z yednannyami Poyava danih na vhidnij duzi mozhe viklikati aktivaciyu vuzla Zazvichaj prijnyato sho v duzi mistitsya ne bilshe odnogo tokena ale v teoriyi mozhna stvoriti i modeli z neobmezhenoyu yemnistyu U bilsh rozroblenih modelyah dugi mozhut zlivatisya v odnu abo rozgaluzhuvatisya Vnaslidok programuvannya vihodit programa potokiv danih oriyentovanij graf Vsi shlyahi vzayemodiyi elementiv yavno zadaye programist U najprostishomu vipadku konveyernoyi obrobki angl pipeline dataflow elementi mozhna zadati poslidovnistyu odinichnih obchislen Obchislennya provodyatsya po cherzi pri nadhodzhenni tokeniv na vhid Taku shemu nazivayut vikonannyam kerovanim danimi angl data driven execution HarakteristikiU programuvanni potokiv danih mozhna zastosovuvati i skladnishi konfiguraciyi nizh konveyer Zokrema taki mozhlivosti mozhna dodati do najprostishoyi modeli v tij chi inshij kombinaciyi Push abo pull disciplini dlya dug U pershomu vipadku tokeni vishtovhuyutsya z iniciativi virobnika danih a v drugomu iniciatorom zapitu tokena ye spozhivach Dva pidhodi takozh vidomi yak obchislennya kerovane danimi angl data driven computation i obchislennya kerovane zapitami angl demand driven computation Zminni angl mutable abo nezminni angl immutable dani Hocha nezminni dani najvdalishij pidhid dlya paralelnogo opracyuvannya deyaki realizaciyi zasnovani na imperativnih movah programuvannya mozhut vimagati zminyuvanih danih z usima neobhidnimi mehanizmami sinhronizaciyi Mozhlivosti zlittya angl join i rozgaluzhennya angl split dug U razi zlittya port priznachennya dugi otrimuye tokeni vid bud yakogo z dvoh portiv na pochatku dugi Pri rozgaluzhenni token zazvichaj kopiyuyetsya dvom oderzhuvacham Zlittya i rozgaluzhennya mozhut buti mnozhinnimi Statichna abo dinamichna programa potoku danih Cya harakteristika stosuyetsya mozhlivosti zmin u grafi potoku danih Aparatni realizaciyi yak pravilo vikoristovuyut statichni programi ale v zagalnomu vipadku struktura grafu mozhe dinamichno zminyuvatisya U dinamichnij programi deyaka duga mozhe zminiti port priznachennya abo vuzol obrobki svoyi harakteristiki Vuzol mozhe buti funkcionalnim abo zh zberigati svij stan angl stateful useredini Sinhronna abo asinhronna aktivaciya Odin z najvazhlivishih parametriv klasifikaciyi sistem potokiv danih Sinhronna aktivaciya maye na uvazi deyakij zazdalegid zafiksovanij i splanovanij poryadok aktivaciyi pobudovanij z urahuvannyam vsiyeyi programi v cilomu V sistemi z asinhronnoyu aktivaciyeyu kozhen blok pikluyetsya pro svoye sogodennya i aktivaciya vidbuvayetsya pri zadovolenni umov napriklad poyavi danih na vhodi Dlya sistem z asinhronnoyu aktivaciyeyu mozhut znadobitisya dugi yemnistyu bilshe odnogo tokena Shema aktivaciyi mozhe buti i zmishanoyu angl hybrid Mnozhinni vhidni i vihidni porti Nayavnist dekilkoh portiv mozhe vimagati i zmin dlya umov aktivaciyi Napriklad aktivaciya mozhe vidbuvatisya yaksho hocha b odin z vhodiv otrimav dani U skladnishih vipadkah mozhut vikoristovuvatisya shemi aktivaciyi angl fire pattern v yakih dlya kozhnogo portu priznacheno odne z chotiroh vidnoshen do aktivaciyi 1 na vhodi ye dani 0 na vhodi nemaye danih X nayavnist danih bajduzha bezumovna aktivaciya nezalezhno vid umov dlya inshih portiv Vuzol mozhe mati kilka shem yaki pereviryayutsya odna za odnoyu poki shema ne vidpovidatime potochnomu stanu Napriklad triportovij vuzol zi shemoyu 1 1 X 0 X 0 bude aktivizovano yaksho pershi dva porti otrimali dani abo na pershomu i tretomu portu nemaye danih Zvorotni zv yazki abo cikli dozvolyayut vikoristovuvati vihidnij potik znovu na vhodi obchislyuvalnogo bloka Pri roboti z ciklami slid unikati tupikovih situacij div Vzayemne blokuvannya za yakih deyakij vuzol bude chekati danih na vhodi yaki zalezhat vid jogo zh vihodu Dlya roboti zi zvorotnim zv yazkom mozhe znadobitisya zadannya pochatkovih tokeniv she do zapusku programi dlya dug zvorotnogo zv yazku abo vikoristannya odnorazovih vuzliv angl one shot yaki aktivuyutsya rivno odin raz na pochatku roboti programi Skladeni vuzli angl compound node dozvolyayut paketuvati primitivni vuzli v bilshi moduli Rekursivni vuzli Riznovid skladenogo vuzla sho mistit kopiyu samogo sebe Bagatoshvidkisne virobnictvo i spozhivannya tokeniv Dlya pidvishennya produktivnosti pri aktivaciyi mozhe dozvolyatisya otrimannya i vidsilannya z portu kilkoh tokeniv vidrazu Vuzli z nalezhnimi yim portami takozh nazivayut aktorami Klasichni aktori zaproponovani en ye okremim vipadkom aktoriv potokiv danih a same mayut rivno odin vhidnij port i zhodnogo vihidnogo Div takozhDiagrama potokiv danih DFD PrimitkiTiago Boldt Sousa Dataflow Programming Concept Languages and Applications Jon Orwant Computer Science amp Perl Programming Best of The Perl Journal O Reilly Media Incorporated 2002 P 146 ISBN 9780596003104 Carkci 2014 2 Dataflow Explained Sharp ta 1992 293 A Structured Description Of Dataflow Actors And Its Application Bishop Peter Steiger Richard A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973 7 July LiteraturaVan 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 amp 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 amp 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 PosilannyaTiago Boldt Sousa Dataflow Programming Concept Languages and Applications