Програмирање протоком података

(преусмерено са Data Flow paradigma)

У рачунарском програмирању, програмирање протоком података је парадигма програмирања да су модели програма усмерени ка графику података, да теку између операција, чиме спроводе принципе протока података и архитектуру. Податак-ток програмски језици деле неке карактеристике функционалних језика, и углавном су развијени да би довели неке функционалне концепте на језик погоднији за нумеричку обраду. Неки аутори користе термин параметара уместо податак-ток да би се избегла конфузија са податак-ток рачунарством или податак-ток архитектуром, на основу индетерминистичких парадигми машина. Податак-ток програмирање је осмислио Џек Денис и његови дипломирани студенати на МИТ током 1960-их.

Данашњи процесори, следећи Муров закон, требало би да имају фреквенцију сата реда неколико десетина гигахерца, а тиме и велику брзину рада. Чињеница је, да такву брзину данашњи рачунари немају. Разлог се може наћи у енормној количини енергије коју би процесори таквог капацитета производили, и велика количина ресурса морала би се користити на обезбеђивање адекватног систем хлађења за такве системе. Перформансе данашњих процесора су ограничене и због интензивног саобраћаја процесора и меморије, који је веома спор. Свака инструкција се мора добавити, декодирати, извршити, што је временски захтевно, тако да независно од величине убрзања које се настоји остварити унапређењем технологије или применом паралелизама у извршењу програма, перформансе данашњих рачунара су ограничене. Наведена ограничења довела су до развоја специјализоване парадигме у рачунарству, познатије као парадигма протока података. Овај у потпуности другачији приступ, омогућава извршење програма за један, два или чак три реда величине (зависно од специфичности апликације) брже у односу на извршење програма на уобичајеним архитектурама.

Парадигма протока података је нова програмска парадигма која моделује програм као усмерени граф преноса података између операција, и на тај начин имплементира принципе преноса података и архитектуру. Подаци су представљени као скуп чворова (такође названих блокови) са улазним „и/или” портовима у њима. Чворови су повезани усмереним гранама које дефинишу проток података кроз њих. Парадигма протока података има широку примену, подржава било масивно израчунавање података или је основа за визуелне језике, обезбеђујући могућност пограмирања крајњих (енгл. end-user) корисника. Концепти протока података су развијени као решење за ограничења и уска грла, која се по питању перформанси јављају код архитектура управљања током. Кононцепти и ахитектура управљања протоком података имају предности у односу на архитектуре управљања током по питању перформанси и економичности. Машине протока података (ДФЕ) према процени стручњака из ове области, представљају технологију која ће све више бити у употреби. Разлог томе лежи у чињеници да је као архитектуре веома подесна за паралелно извршавање програма, веома добро се скалира и применљива је на проблеме широких намена. Посебну намену ДФЕ има у обради велике количине подата, па се применљује у области великих података. Иако су у основи замишљени као акцелератори програма који су претходно били секвенцијалне природе, данас постоје алгоритми који су писани искључиво за њихово извршавање на ДФЕ, без постојања претходних секвенцијалних пандана. Једина потешкоћа у раду са овим ахитектурама може бити у креирању високо паралелизибилних програма који би се могли искористити пуне перформансе оваквих архитектура.

Својства податак-ток програмских језика

уреди

Традиционално, програм се моделира као низ операција које се дешавају у одређеном редоследу; ово може бити упућено као низ,[1] процедурално,[2] контрола протока[2] (што значи да програм изабере одређену пут), или императивно програмирање. Програм се фокусира на команде, у складу са фон Нојман[1]:p.3 визију секвенцијалног програмирања, где подаци обично "мирује".[3]

Насупрот томе, податак-ток програмирање наглашава кретање података и модела програма као низ веза. Експлицитно дефинисани улази и излази повезивање операција, које функционишу као црне кутије[4] Операција траје чим сви њени улаза постану важећи.[5] Тако податак-ток језици су суштински паралелни и могу радити добро у великим, децентрализованим система.[1]:p.3[6] [7]

Стање

уреди

Један од кључних појмова у програмирању је идеја стања, у суштини снимак различитих услова у систему. Већина програмских језика захтевају значајну количину стања информација, које су обично скривене од програмера. Често сам рачунар нема појма који податак кодира трајно стање. Ово је озбиљан проблем, јер стање информација треба да се дели на више процесора у паралелним обрадама машина. Већина језика примора програмера да би додали додатни код да укаже који подаци и делови кода су важни за стање. Овај код има тенденцију да буде скуп у погледу перформанси, као и тешко читљив или дебагован. Експлицитни паралелизам је један од главних разлога за лоше резултате Ентерприсе Јава Беанс при изградњи дата-интензивне, не-ОЛТП апликације.

Где се линеарни програм може замислити као један радник који се креће између задатака (операције), а проток података програма је као низ радника на покретној траци, сваки ради одређени задатак кад год су материјали доступни. Од операције у питању је само доступност улазним подацима, они немају скривена стања да прате, и су сви "спремни" у исто време.

Репрезентација

уреди

Податак-ток програми су заступљени на различите начине. Традиционални програм је обично представљен као низ текста упутства, који је основан за описивање серијских система цеви података између малих, сингл-сврха алата, процеса и повратка. Податак-ток програми почињу на улаз, можда командне линије параметара, и илуструју како да се подаци користе и модификовани. Проток података је експлицитан, често се визуелно илуструје као линије или цеви.

Што се тиче кодирања, податак-ток програма може се спровести као хеш табела, са јединствено идентификованим улазом, као кључеви, који се користе да се виде савети са упутствима. Када се било која операција заврши, програм скенира списак низа операција док не пронађе прву операцију у којој су сви улази тренутно активни и води га. Када се операција заврши, обично ће излазити подаци, чиме друга операција постаје важећа.

За паралелни рад, само списак треба да се дели; то је стање целог програма. Тако је задатак одржавања стања уклоњен од програмера и дат језичкој компоненти. На машинама са једним процесорским језгром где би имплементација дизајнирана за паралелни рад једноставно увела изнад, ово изнад се може потпуно уклонити помоћу другачијих компоненти.

Историја

уреди

Пионир податак-ток језика је БЛОДИ (блок дијаграм), развијен од стране Јохана Ларри Келлиа, Јр., Керол Лоцхбаума и Виктора А. Виссотскија за одређивање семплованих система података.[8] БЛОДИ спецификација функционалних јединица (појачала, Гуја, линије за кашњење, итд) и њихове међусобне везе су саставили у једну петљу да ажурира цео систем за један сат.

Више конвенционалних протока података језици су првобитно развили да би паралелно програмирање олакшали. У Берт Сутхерланду је 1966. године теза, он-лине Графичка Спецификација Рачунар процедура,[9] Сатерленд створена једна од првих графичких протока података у програмским оквирима. Накнадни подаци-ток језици су често развијена у великим суперрачунар лабораторијама. Један од најпопуларнијих је СИСАЛ, развијен у Лавренц Ливерморе националној лабораторији. СИСАЛ личи на већиниујезика извештаја погона, али променљиве треба доделити једном. Ово омогућава преводиоцу да лако идентификује улазе и излазе. Развијен је број огранака Сиса, укључујући САЦ, Сингл Ассигнмент C, који покушава да остане што ближе популарном C програмском језику ако је могуће.

Морнарица Сједињенних Америчких Држава финансирала је развој АЦОС и СПГН (обрада сигнала графичких ознака) са почетком у раним 1980-их. Ово је у употреби на више платформа на терену данас.[10]

Више радикални концепт је Програпх, у коме су програми изграђена као графици на екрану, а променљиве су у потпуности замењене линијама које повезују улазе у излазе. Узгред, Програпх је првобитно написан за Макинтош, који је остао јединствен-процесор до увођења ДаиСтар Генесис МП 1996. године.

Постоје многе хардверске архитектуре оријентисане ка ефикасном спровођењу податак-ток модела програмирања. МИТ означен симбол протока података архитектуре је дизајнирао Грег Пападопулос.

Проток података је предложен као апстракција за одређивање глобалног понашања дистрибуираних компоненти система: уживо дистрибуирани објекати програмског модела, дистрибуирани токови података се користи за чување и комуницирају стања, и као такви, они играју улогу описану у варијаблама, пољима и параметрима у Јава програмским језицима као што су.

Језици

уреди

Апликациони програмски интерфејс

уреди
  • DC: Библиотека која омогућава уграђивање у једном смеру податак-ток ограничења у C/C ++ програма.
  • СистемC: Библиотека за C ++, углавном усмерена на дизајн хардвера.
  • MDF Библиотека за пајтон у циљу финансијских модела

Протока података наспрам парадигме управљања током

уреди

Данашњи ЦПУ-ви спадају у скупину controlflow архитектура. Controlflow архитектуре су у основи врста Von-Neumman-овог типа процесора, код којих се извршење програма своди на његово превођење у листу инструкција које му одговарају. Те инструкције је потребно добавити, декодирати, извршити и резултате забележити у регистре или меморију. Овај процес је временски захтеван, па се стога користе бројне технике како би се кашњење узроковано наведеним факторима прикрило (технике кеширања, просљеђивања, предикције гранања). Извршење програма захтева комуникацију између компоненти рачунарског система (нпр. ЦПУ и меморије) како би се обезбедило извршење програма. Controlflow архитектуре за извршење програма подразумевају извршење инструкција и одлуку о томе којом секвенцом ће се поједине инструкције извршавати, што се заправо и назива controlflow, као и управљање подацима, познатије као датафлоw. Па се стога осим проблема комуникације на релацији процесор-меморија, јавља и проблем синхронизације меморије, посебно изражен код паралелног извршења програма на controlflow arhitekturama. Програмирати у наведеном окружењу се односи на писање програма којим ће се управљати током података који пролазе кроз хардвер.

Обзиром да је код цонтролфлоw архитектура појава overheada, који се јавља у комуникацији са меморијом, и синхронизације велики ограничавајући фактор, датафлоw приступ настоји то елиминисати. Елиминација тих ограничења се постиже увођењем ситнозрнастог (енгл. Fine-grained) приступа паралелизацији појединих послова. Такав приступ подразумева да се подела програма сведе на послове који су величином једнаки једној инструкцији. Обзиром да је комуникација веома брза, то омогућава поделу, такву да сваки део датафлоw машине обави тај мали посао. Хардвер ће у складу са постојањем евентуалних зависности између појединих инструкција, донети одлуку о томе које од тих инстукција може извршавати паралелно. Наравно, овакав приступ има смисла искључиво уколико је програм који је потребно извршити довољно паралелизибилан тако да може искористити перформане датафлоw машине. Извршење програма у датафлоw окружењу одвија се на начин да се програм преведе у извршникод за датафлоw машину, који описује све потребне везе између језгри, и израчунавања, које ће поједине језгре имплементирати. По завршетку свих израчунавања добивени резултат се уписује у меморију. Предност овог приступа је у минимизацији комуникације између појединих делова рачунарског система. Комуникација се своди само на ону између суседних језгра, тако да је време потребно за комуникацију готово занемариво, на тај начин елиминишући кашњења узрокована комуникацијом ЦПУ са меморијом, као што је случај код рада controlflow архитектура. Код датафлоw машина не постоје инструкције, то је датафлоw архитектура сама за себе.

Предности протока података

уреди

Програмирањем хардвера, омогућава се извршење програма над стреамом података који је преузет из меморије.

Датафлоw приступ има предности у виду брзине, дисипације снаге и величине у односу на controlflow. Карактеристика датафлоw архитектура је у томе што се програм преводи све до најнижег нивоа, до нивоа логичких кола и транзистора, што има директну последицу у убрзању приликом извршења програма у односу на contolflow архитектуре (програм се преводи до нивоа машинског кода). Такођер, већ поменути саобраћај између процесора и меморије, који представља уско грло са аспекта перформанси система, те пренос података кроз меморијску хијерархију је елиминисан, па самим тим и оверхеад потребан за извођење таквих операција. Уочава се да је датафлоw концепт вођен разликом напона која се може постићи између улаза и излаза из појединих компоненти хардвера. Са аспекта дисипације снаге, предност датафлоw архитектура се може увидјети из релације којом је одређена:

 

Уколико је напон потребан за датафлоw и controlflow архитектуру исти, као и коефицијент k који представља константу, уочавамо да дисипација снаге зависи директно од фреквенције сата. Фреквенција сата која је карактеристична за датафлоw архитектуре износи 200MHZ, док за controlflow архитектуре износи око 3GHZ. Овај израз у потпуности осликава стање зашто controlflow архитектуре ослобађају више енергије (топлоте), тј. имају већу дисипацију снаге од датафлоw архитекура. Док се предност у величини, може објаснити кроз заступљеност АЛУ-а, као основних елемената процесора који изводе израчунавања. АЛУ код цонтролфлоw архитектура заузима приближо 5% величине целокупног чипа, док јединице које изводе операције код датафлоw архитектура заузимају приближно 95% величине чипа.

Датафлоw приступ се најбоље може објаснити на примеру рада петље, где се петља пребацује, са до тада уобичајеног софтверског извшења, на хардвер. Хардверски, петља се може извршити без икаквих временских зависности и потрошње, практично у једном пролазу. На том приницпу се заснива идеја датафлоw парадигме. Као закључак се може становити да заправно начин извршавања програма зависи директно од карактеристикама програма, односно од његове паралелизибилности. Уколико програм није паралелизибилан, перформансе оваквих архитектура није могуће постићи, што је у сагласности са Амдахловим законом.

Види још

уреди

Референце

уреди
  1. ^ а б в Johnston, Wesley M.; J.R. Paul Hanna; Millar, Richard J. (2004). „Advances in Dataflow Programming Languages” (PDF). ACM Computing Surveys. 36: 1—34. doi:10.1145/1013208.1013209. Приступљено 15. 8. 2013. 
  2. ^ а б в Wadge, William W.; Ashcroft, Edward A. (1985). Lucid, the Dataflow Programming Language (PDF) (illustrated изд.). Academia Press. ISBN 9780127296500. Приступљено 15. 8. 2013. 
  3. ^ Wadge & Ashcroft 1985, стр. 7. sfn грешка: више циљева (2×): CITEREFWadgeAshcroft1985 (help)
  4. ^ Wadge & Ashcroft 1985, стр. 2. sfn грешка: више циљева (2×): CITEREFWadgeAshcroft1985 (help)
  5. ^ а б „Dataflow Programming Basics”. Getting Started with NI Products. National Instruments Corporation. Приступљено 15. 8. 2013. 
  6. ^ Harter, Richard. „Data Flow languages and programming - Part I”. Richard Harter's World. Архивирано из оригинала 08. 12. 2015. г. Приступљено 15. 8. 2013. 
  7. ^ „Why Dataflow Programming Languages are Ideal for Programming Parallel Hardware”. Multicore Programming Fundamentals Whitepaper Series. National Instruments Corporation. Архивирано из оригинала 21. 12. 2018. г. Приступљено 15. 8. 2013. 
  8. ^ Kelly, John L. Jr., Carol Lochbaum, V. A. Vyssotsky (1961). „A block diagram compiler”. Bell System Tech. J. 40: 669—678. doi:10.1002/j.1538-7305.1961.tb03236.x. 
  9. ^ W.R. Sutherland (1966). „The On-line Graphical Specification of Computer Procedures”. MIT. 
  10. ^ Underwater Acoustic Data Processing, Y.T. Chan

Литература

уреди

Спољашње везе

уреди