Programiranje protokom podataka

U računarskom programiranju, programiranje protokom podataka je paradigma programiranja da su modeli programa usmereni ka grafiku podataka, da teku između operacija, čime sprovode principe protoka podataka i arhitekturu. Podatak-tok programski jezici dele neke karakteristike funkcionalnih jezika, i uglavnom su razvijeni da bi doveli neke funkcionalne koncepte na jezik pogodniji za numeričku obradu. Neki autori koriste termin parametara umesto podatak-tok da bi se izbegla konfuzija sa podatak-tok računarstvom ili podatak-tok arhitekturom, na osnovu indeterminističkih paradigmi mašina. Podatak-tok programiranje je osmislio Džek Denis i njegovi diplomirani studenati na MIT tokom 1960-ih.

Današnji procesori, sledeći Murov zakon, trebalo bi da imaju frekvenciju sata reda nekoliko desetina gigaherca, a time i veliku brzinu rada. Činjenica je, da takvu brzinu današnji računari nemaju. Razlog se može naći u enormnoj količini energije koju bi procesori takvog kapaciteta proizvodili, i velika količina resursa morala bi se koristiti na obezbeđivanje adekvatnog sistem hlađenja za takve sisteme. Performanse današnjih procesora su ograničene i zbog intenzivnog saobraćaja procesora i memorije, koji je veoma spor. Svaka instrukcija se mora dobaviti, dekodirati, izvršiti, što je vremenski zahtevno, tako da nezavisno od veličine ubrzanja koje se nastoji ostvariti unapređenjem tehnologije ili primenom paralelizama u izvršenju programa, performanse današnjih računara su ograničene. Navedena ograničenja dovela su do razvoja specijalizovane paradigme u računarstvu, poznatije kao paradigma protoka podataka. Ovaj u potpunosti drugačiji pristup, omogućava izvršenje programa za jedan, dva ili čak tri reda veličine (zavisno od specifičnosti aplikacije) brže u odnosu na izvršenje programa na uobičajenim arhitekturama.

Paradigma protoka podataka je nova programska paradigma koja modeluje program kao usmereni graf prenosa podataka između operacija, i na taj način implementira principe prenosa podataka i arhitekturu. Podaci su predstavljeni kao skup čvorova (takođe nazvanih blokovi) sa ulaznim „i/ili” portovima u njima. Čvorovi su povezani usmerenim granama koje definišu protok podataka kroz njih. Paradigma protoka podataka ima široku primenu, podržava bilo masivno izračunavanje podataka ili je osnova za vizuelne jezike, obezbeđujući mogućnost pogramiranja krajnjih (engl. end-user) korisnika. Koncepti protoka podataka su razvijeni kao rešenje za ograničenja i uska grla, koja se po pitanju performansi javljaju kod arhitektura upravljanja tokom. Kononcepti i ahitektura upravljanja protokom podataka imaju prednosti u odnosu na arhitekture upravljanja tokom po pitanju performansi i ekonomičnosti. Mašine protoka podataka (DFE) prema proceni stručnjaka iz ove oblasti, predstavljaju tehnologiju koja će sve više biti u upotrebi. Razlog tome leži u činjenici da je kao arhitekture veoma podesna za paralelno izvršavanje programa, veoma dobro se skalira i primenljiva je na probleme širokih namena. Posebnu namenu DFE ima u obradi velike količine podata, pa se primenljuje u oblasti velikih podataka. Iako su u osnovi zamišljeni kao akceleratori programa koji su prethodno bili sekvencijalne prirode, danas postoje algoritmi koji su pisani isključivo za njihovo izvršavanje na DFE, bez postojanja prethodnih sekvencijalnih pandana. Jedina poteškoća u radu sa ovim ahitekturama može biti u kreiranju visoko paralelizibilnih programa koji bi se mogli iskoristiti pune performanse ovakvih arhitektura.

Svojstva podatak-tok programskih jezika

Tradicionalno, program se modelira kao niz operacija koje se dešavaju u određenom redosledu; ovo može biti upućeno kao niz, proceduralno, kontrola protoka (što znači da program izabere određenu put), ili imperativno programiranje. Program se fokusira na komande, u skladu sa fon Nojman viziju sekvencijalnog programiranja, gde podaci obično "miruje".

Nasuprot tome, podatak-tok programiranje naglašava kretanje podataka i modela programa kao niz veza. Eksplicitno definisani ulazi i izlazi povezivanje operacija, koje funkcionišu kao crne kutije Operacija traje čim svi njeni ulaza postanu važeći. Tako podatak-tok jezici su suštinski paralelni i mogu raditi dobro u velikim, decentralizovanim sistema.

Stanje

Jedan od ključnih pojmova u programiranju je ideja stanja, u suštini snimak različitih uslova u sistemu. Većina programskih jezika zahtevaju značajnu količinu stanja informacija, koje su obično skrivene od programera. Često sam računar nema pojma koji podatak kodira trajno stanje. Ovo je ozbiljan problem, jer stanje informacija treba da se deli na više procesora u paralelnim obradama mašina. Većina jezika primora programera da bi dodali dodatni kod da ukaže koji podaci i delovi koda su važni za stanje. Ovaj kod ima tendenciju da bude skup u pogledu performansi, kao i teško čitljiv ili debagovan. Eksplicitni paralelizam je jedan od glavnih razloga za loše rezultate Enterprise Java Beans pri izgradnji data-intenzivne, ne-OLTP aplikacije.

Gde se linearni program može zamisliti kao jedan radnik koji se kreće između zadataka (operacije), a protok podataka programa je kao niz radnika na pokretnoj traci, svaki radi određeni zadatak kad god su materijali dostupni. Od operacije u pitanju je samo dostupnost ulaznim podacima, oni nemaju skrivena stanja da prate, i su svi "spremni" u isto vreme.

Reprezentacija

Podatak-tok programi su zastupljeni na različite načine. Tradicionalni program je obično predstavljen kao niz teksta uputstva, koji je osnovan za opisivanje serijskih sistema cevi podataka između malih, singl-svrha alata, procesa i povratka. Podatak-tok programi počinju na ulaz, možda komandne linije parametara, i ilustruju kako da se podaci koriste i modifikovani. Protok podataka je eksplicitan, često se vizuelno ilustruje kao linije ili cevi.

Što se tiče kodiranja, podatak-tok programa može se sprovesti kao heš tabela, sa jedinstveno identifikovanim ulazom, kao ključevi, koji se koriste da se vide saveti sa uputstvima. Kada se bilo koja operacija završi, program skenira spisak niza operacija dok ne pronađe prvu operaciju u kojoj su svi ulazi trenutno aktivni i vodi ga. Kada se operacija završi, obično će izlaziti podaci, čime druga operacija postaje važeća.

Za paralelni rad, samo spisak treba da se deli; to je stanje celog programa. Tako je zadatak održavanja stanja uklonjen od programera i dat jezičkoj komponenti. Na mašinama sa jednim procesorskim jezgrom gde bi implementacija dizajnirana za paralelni rad jednostavno uvela iznad, ovo iznad se može potpuno ukloniti pomoću drugačijih komponenti.

Istorija

Pionir podatak-tok jezika je BLODI (blok dijagram), razvijen od strane Johana Larri Kellia, Jr., Kerol Lochbauma i Viktora A. Vissotskija za određivanje semplovanih sistema podataka. BLODI specifikacija funkcionalnih jedinica (pojačala, Guja, linije za kašnjenje, itd) i njihove međusobne veze su sastavili u jednu petlju da ažurira ceo sistem za jedan sat.

Više konvencionalnih protoka podataka jezici su prvobitno razvili da bi paralelno programiranje olakšali. U Bert Sutherlandu je 1966. godine teza, on-line Grafička Specifikacija Računar procedura, Saterlend stvorena jedna od prvih grafičkih protoka podataka u programskim okvirima. Naknadni podaci-tok jezici su često razvijena u velikim superračunar laboratorijama. Jedan od najpopularnijih je SISAL, razvijen u Lavrenc Livermore nacionalnoj laboratoriji. SISAL liči na većiniujezika izveštaja pogona, ali promenljive treba dodeliti jednom. Ovo omogućava prevodiocu da lako identifikuje ulaze i izlaze. Razvijen je broj ogranaka Sisa, uključujući SAC, Singl Assignment C, koji pokušava da ostane što bliže popularnom C programskom jeziku ako je moguće.

Mornarica Sjedinjennih Američkih Država finansirala je razvoj ACOS i SPGN (obrada signala grafičkih oznaka) sa početkom u ranim 1980-ih. Ovo je u upotrebi na više platforma na terenu danas.

Više radikalni koncept je Prograph, u kome su programi izgrađena kao grafici na ekranu, a promenljive su u potpunosti zamenjene linijama koje povezuju ulaze u izlaze. Uzgred, Prograph je prvobitno napisan za Makintoš, koji je ostao jedinstven-procesor do uvođenja DaiStar Genesis MP 1996. godine.

Postoje mnoge hardverske arhitekture orijentisane ka efikasnom sprovođenju podatak-tok modela programiranja. MIT označen simbol protoka podataka arhitekture je dizajnirao Greg Papadopulos.

Protok podataka je predložen kao apstrakcija za određivanje globalnog ponašanja distribuiranih komponenti sistema: uživo distribuirani objekati programskog modela, distribuirani tokovi podataka se koristi za čuvanje i komuniciraju stanja, i kao takvi, oni igraju ulogu opisanu u varijablama, poljima i parametrima u Java programskim jezicima kao što su.

Jezici

• Agilent VEE
• Alterik
• ANI
• DARTS
• ASCET
• AviSinth skript jezik, za video obradu
• BLODI
• BMDFM Binarna Modularna podatak-tok mašina
• CAL
• [SPGN - obrada signala Grafik notacija]
• COStream
• Kasandra-vizija - Visual programski jezik sa OpenCV podrškom i C++ API dodatkom
• Sorezoid - oblak OS sa razvojnim okruženjem ambijenta za upravljanje poslovnim procesima u okviru svake kompanije
• Curin
• Hartmann cevovodi
• [[Hume]
• Džul
• Juttle
• KNIME
• Korduene Arhivirano na sajtu Wayback Machine (8. decembar 2015)
• LabVIEV G
• Linda
• Lucid
• Lustre
• M, koristi se kao pozadina za Majkrosoft Eksel je ETL plugin cnaga Upita.
• MakKompajler - Dizajniran od Makeler tehnologije i kompatibilan je sa OpenSPL
• Maks / MSP
• Visual programski jezik - Komponenta Majkrosoft Robotike Studija namenjen za robotsko programiranje
• Nektflov - pokretni podaci za računarske cevovode na osnovu modela programiranja podatak-tok
• OpenVire - dodaje mogućnosti vizuelnih protoka podataka programiranja u Delfi VCL putem ili FireMonkei komponenti i grafičkog urednika (istoimeni binarni protokol je povezan)
• OpenVire studio - razvojno okruženje ambijenta koji omogućava razvoj softverskih prototipova od programera.
• Oz sada takođe distribuiran od 1.4.0
• Pifagor
• Pipeline Pilot
• POGOL
• Prograph
• Čist podatak
• Pajtonnet
• Kvarc Kompozitor - Povered bi Epl; koristi za grafičke animacije i efekti
• SAC Singl Dodela C
• Skala (sa bibliotekom SinapseGrid)
• Signal (protok podataka orijentisan sinhronim jezikom omogućava više takta specifikacija)
• Simulink
• SIMPL
• SISAL
• stromk - Programsko okruženje vizuelno fokusiran na industrijskoj viziji (open source)
• SVARM
• Sistem Verilog
• Tersus - Vizuelna platforma programiranja (open source)
• Verilog
• VHDL
• Vinjeta je VBIS jezik za poslovne procese integracija
• vvvv
• VSXu Vidžet Radionica, "igra" namenjena deci koja je tehnički pojednostavljen protok podataka programskog jezika.
• XEE (Starlight) XML Inženjer okruženja
• XProc

Aplikacioni programski interfejs

• DC: Biblioteka koja omogućava ugrađivanje u jednom smeru podatak-tok ograničenja u C/C ++ programa.
• SistemC: Biblioteka za C ++, uglavnom usmerena na dizajn hardvera.
• MDF Biblioteka za pajton u cilju finansijskih modela

Protoka podataka naspram paradigme upravljanja tokom

Današnji CPU-vi spadaju u skupinu controlflow arhitektura. Controlflow arhitekture su u osnovi vrsta Von-Neumman-ovog tipa procesora, kod kojih se izvršenje programa svodi na njegovo prevođenje u listu instrukcija koje mu odgovaraju. Te instrukcije je potrebno dobaviti, dekodirati, izvršiti i rezultate zabeležiti u registre ili memoriju. Ovaj proces je vremenski zahtevan, pa se stoga koriste brojne tehnike kako bi se kašnjenje uzrokovano navedenim faktorima prikrilo (tehnike keširanja, prosljeđivanja, predikcije grananja). Izvršenje programa zahteva komunikaciju između komponenti računarskog sistema (npr. CPU i memorije) kako bi se obezbedilo izvršenje programa. Controlflow arhitekture za izvršenje programa podrazumevaju izvršenje instrukcija i odluku o tome kojom sekvencom će se pojedine instrukcije izvršavati, što se zapravo i naziva controlflow, kao i upravljanje podacima, poznatije kao dataflow. Pa se stoga osim problema komunikacije na relaciji procesor-memorija, javlja i problem sinhronizacije memorije, posebno izražen kod paralelnog izvršenja programa na controlflow arhitekturama. Programirati u navedenom okruženju se odnosi na pisanje programa kojim će se upravljati tokom podataka koji prolaze kroz hardver.

Obzirom da je kod controlflow arhitektura pojava overheada, koji se javlja u komunikaciji sa memorijom, i sinhronizacije veliki ograničavajući faktor, dataflow pristup nastoji to eliminisati. Eliminacija tih ograničenja se postiže uvođenjem sitnozrnastog (engl. Fine-grained) pristupa paralelizaciji pojedinih poslova. Takav pristup podrazumeva da se podela programa svede na poslove koji su veličinom jednaki jednoj instrukciji. Obzirom da je komunikacija veoma brza, to omogućava podelu, takvu da svaki deo dataflow mašine obavi taj mali posao. Hardver će u skladu sa postojanjem eventualnih zavisnosti između pojedinih instrukcija, doneti odluku o tome koje od tih instukcija može izvršavati paralelno. Naravno, ovakav pristup ima smisla isključivo ukoliko je program koji je potrebno izvršiti dovoljno paralelizibilan tako da može iskoristiti performane dataflow mašine. Izvršenje programa u dataflow okruženju odvija se na način da se program prevede u izvršnikod za dataflow mašinu, koji opisuje sve potrebne veze između jezgri, i izračunavanja, koje će pojedine jezgre implementirati. Po završetku svih izračunavanja dobiveni rezultat se upisuje u memoriju. Prednost ovog pristupa je u minimizaciji komunikacije između pojedinih delova računarskog sistema. Komunikacija se svodi samo na onu između susednih jezgra, tako da je vreme potrebno za komunikaciju gotovo zanemarivo, na taj način eliminišući kašnjenja uzrokovana komunikacijom CPU sa memorijom, kao što je slučaj kod rada controlflow arhitektura. Kod dataflow mašina ne postoje instrukcije, to je dataflow arhitektura sama za sebe.

Prednosti protoka podataka

Programiranjem hardvera, omogućava se izvršenje programa nad streamom podataka koji je preuzet iz memorije.

Dataflow pristup ima prednosti u vidu brzine, disipacije snage i veličine u odnosu na controlflow. Karakteristika dataflow arhitektura je u tome što se program prevodi sve do najnižeg nivoa, do nivoa logičkih kola i tranzistora, što ima direktnu posledicu u ubrzanju prilikom izvršenja programa u odnosu na contolflow arhitekture (program se prevodi do nivoa mašinskog koda). Također, već pomenuti saobraćaj između procesora i memorije, koji predstavlja usko grlo sa aspekta performansi sistema, te prenos podataka kroz memorijsku hijerarhiju je eliminisan, pa samim tim i overhead potreban za izvođenje takvih operacija. Uočava se da je dataflow koncept vođen razlikom napona koja se može postići između ulaza i izlaza iz pojedinih komponenti hardvera. Sa aspekta disipacije snage, prednost dataflow arhitektura se može uvidjeti iz relacije kojom je određena:

$P=f*U^{2}*k$

Ukoliko je napon potreban za dataflow i controlflow arhitekturu isti, kao i koeficijent k koji predstavlja konstantu, uočavamo da disipacija snage zavisi direktno od frekvencije sata. Frekvencija sata koja je karakteristična za dataflow arhitekture iznosi 200MHZ, dok za controlflow arhitekture iznosi oko 3GHZ. Ovaj izraz u potpunosti oslikava stanje zašto controlflow arhitekture oslobađaju više energije (toplote), tj. imaju veću disipaciju snage od dataflow arhitekura. Dok se prednost u veličini, može objasniti kroz zastupljenost ALU-a, kao osnovnih elemenata procesora koji izvode izračunavanja. ALU kod controlflow arhitektura zauzima približo 5% veličine celokupnog čipa, dok jedinice koje izvode operacije kod dataflow arhitektura zauzimaju približno 95% veličine čipa.

Dataflow pristup se najbolje može objasniti na primeru rada petlje, gde se petlja prebacuje, sa do tada uobičajenog softverskog izvšenja, na hardver. Hardverski, petlja se može izvršiti bez ikakvih vremenskih zavisnosti i potrošnje, praktično u jednom prolazu. Na tom prinicpu se zasniva ideja dataflow paradigme. Kao zaključak se može stanoviti da zapravno način izvršavanja programa zavisi direktno od karakteristikama programa, odnosno od njegove paralelizibilnosti. Ukoliko program nije paralelizibilan, performanse ovakvih arhitektura nije moguće postići, što je u saglasnosti sa Amdahlovim zakonom.

Vidi još

• Akter Model
• Programiranje pokretnih podataka
• Digitalna obrada signala
• Događaj-driven programiranje
• Protok na bazi programiranja
• Funkcionalno reaktivno programiranje
• Recčnik promenljivog računarstva
• Visoke performanse promjenljivog računarstva
• Postepeno računarstvo
• Paralelno programiranje model
• Podeljen globalni adresni prostor
• Programiranje signala
• Stream procesora
• Cevovod (Junik)
• Yahoo cevi

Literatura

• Wadge, William W.; Ashcroft, Edward A. (1985). Lucid, the Dataflow Programming Language (PDF) (illustrated izd.). Academia Press. ISBN 9780127296500. 

Spoljašnje veze

• Dataflow Analytics
• Dataflow and Reactive Programming Systems
• Basics of Dataflow Programming in F# and C#
• Dataflow Programming - Concept, Languages and Applications
• Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing
• Handling huge loads without adding complexity The basic concepts of dataflow programming, Dr. Dobb's, Sept. 2011