INFORMATICA 2/85 OSNOVNA NAČELA DF SI STEMOV J. ŠILCINB. ROBIČ UDK: 681.519.7 INSTITUT „JOZEF ŠTEFAN" LJUBLJANA Koncept krmiljenja s tokom podatkov predstavlja bistven^ spremembo v naClnu izvajanja instrukoij napram klasičnemu sekventinemu izvajanju. Ti sistemi ne delujejo na podlagi krmilnega toka, zato tudi ne potrebujejo programskega Števca in pomnilnika s klasiCno funkcijo. V DF računalnikih postanejo instrukoije izvrSljive v trenutku, ko prispe zadnji med zahtevanimi operandi, kar omogoBa vzporedno izvrševanje instrukcij. LogiCna posledica tega je visoka stopnja izkoriSCenosti inherentne paralelnosti, prisotne v algoritmih. Basic Principles ol Pata Flow svstems. The data flow concepts is a lundamentallv different way of looking at instruotion execution in machine- level prograras - an alternative to sequential instruotion executlon. In a data flow computer an instruotion is ready for execution when its operands have arrived. There is no ooncept of control flow, and data flou computers do not have program looation oounters. A oonsequenoe of data - activated instruotion execution is that many instruotions of a data flou program may be available for execution at onoe. Thus, highly ooncurrent computation is a natural consequenoe of the data flow concept. Uvod V Skih 5 ki. P nik, k vsebin jami progra naslad gramsk plicit instru poteka mannov proces se v iste rvie i po a se pogo niski nje i St no kci j pro ih a i ran on Ne mov i ima mni p v sk sto Štev instr evec alfuri , ki grama rhite uman ma jo jo g rogr ladu a2ur ec ukci se ra i se i je ktur nove dve loba ame s P ira kate je bodi n s zva j teme Se arhi pome In i n ter p rogra In rega ki na si i tem a jo. 1 jna pose tektur mbni k aslovl odatke mskimi drugi vsebin j se mplici dolo TakSno omeji bno pr e rafiun arakter jivi po in kat instr e, vseb a je n izvrSi. tno ali Ca sek krmil tev von i vzpor alni- isti- mnil- erega ukci- ujejo aslov Pro- eks- vence jenje Neu- ednem JU. DF računalniki tdata flow computers) ni­ majo nobene od obeh zgoraj omenjenih značilno­ sti. PrviC, njihova struktura je zasnovana tako, da poteka procesiranje na osnovi vredno­ sti in ne naslovov spremenljivk, kar pomeni, da ni potreben globalni naslovljivi pomnilnik, saj ni nikakršnega naslavljanja. DrugiC, v DF sistemih ni niCesar, kar bi bilo podobno pro­ gramskemu Števcu. Torej temeljijo ti sistemi na naCelih asinhronosti in funkcionalnosti, ki pravita, da so vse operacije funkcije (funkci­ onalnost), ki postanejo izvršljive takoj, ko so na voljo vrednosti vseh vhodnih operandov (asinhronost). Iz naCela funkcionalnosti sle­ di, da se katerikoli operaciji, ki sta Izvr­ šljivi, lahko izvrSita po kakršnemkoli zapore­ dju ali konkurenčno. skega rem povez rando lih Progr progr ge), (data vsega tem g Zgorn graf toCke ave v ter izraC amske ama v se d i f low inh raf om ji naCeli logiCno vodita do progran- a (data flou program graph), v kate- ponazarjajo operacije, usmerjene pa so nosilke vrednosti vhodnih ope- vCasih Se dodatnih informacij o de- unov, katerim pripadajo operandi. mu grafu, ki je rezultat prevajanja viSjem DF jeziku (data flou langua- namiCno prilagodi materialna oprema harduare), ki je sposobna izvajanja erentnega paralelizma, opisanega s , kar ponazarja slika 1 CID. DF jezik DF materialna oprema Raziskavo financira RS8 po pogodbi C2-012A- 106-8A Slika 1, 11 pi.r\anni.tir\& v z p oce ci nos-t. Veliko Število algoritmov (npr. pri NP problemih) vsebuje Inherentni paralelizem, ki pa v van Neuihannovlh arhitekturah ni izrabljen v naJvetSJi motini meri. Arhitekture, ki bi to omogofiale, bi npr. vse NP probleme prevedle na P,probleme, kar pomeni,^da bi se eksponentna Časovna kompleksnost zhi2ala na polinomsko. Zakaj 7 Eksponentna Časovna kompleksnost d'e- terministienih algoritmov za refievanje nekate­ rih NP problemov izvira iz Stavila potencial­ nih reSitev, katere mora algoritem sekvenOno genericatl in preveriti. S paralelnimi arhi­ tekturami pa bi bilo moti realizirati nedeter- ministiCne algoritme, ki bi bili sposobni sočasnega jgeneriranja potencialnih refiitev in izbire najustreznejše med njimi. V ta-' namen je potrebno definirati pro­ gramski jezik, ki bi dovolj eksplicitno izra- i!al inherentno paralelnost algoritma, defini­ rati strukturo (strojni Jezik), ki je rezultat prevajanja programa v tem jeziku in ki omogoCa dovolj enostavno realizacijo z. materialno opremoj predvsem pa naj ohranja vso inherentno paralelnost algoritma. Oglejmo si segment programa, zapisanega v enem od von Neumannovih jezikav. nivo O I 1 nivo 1 I 2,3 nivo 2 I ^,5 nivo 3 s 6. Zaporedje izvrševanja st 53,6 izkorifiCa inherentno par Cji meri. Operacije, ki so lahko kljub temu postanejo iz Cnih Časih - tedaj, ko so n vseh vhodnih operandov. Predp jata Dperaoijl seštevanja eno, mnoJfenja dve in deljenja te. Čeprav sta operaciji A in ju, torej se lahko izvajata,p tala operacija 4 izvršljiva cija 5 pa i!e po treh Časovnih izvajanje programskega graf hrano. avkov 1,C2,33,C4, alelnost v najve- na istem nivoju, vrSljive v razli- a voljo vrednosti ostavimb, da tra- in odštevanja po trt Časovne eno- 5 na istem nivo- aralelno, bo pos- pp Štirih, opera- enotah. Torej je a popolnoma asin- Pri datne tet! ke naleti raci Jami, dasiravno konCana, akumulira si primer programsk i! (slika cikličnih gr ave. Kadar v fflo na podatk to ne usta predhodna saj so vred ne v doloCeni intuitivno k ega grafa za 3). afih lahko nas posamezni pono ovne odvisnost vi nadaljnih ponovitev ni npsti vhodnih h vejah grafa onstruiranega izraCun funkci tanejo do- vitvi zan- i med ope- ponovitev, popolnoma operandov Oglejmo cikličnega je f(i) = 1) 2) 3) A) 5) 6) p 1= x+y i () i= p/y J r != x»p ) 6 1= r-q i t 1= r»p 5 rez 1= s/t J Stand ki ustreza menta, tor nekateri 1,C2,33,.4, izvrSitev to vsa inh menta. OCi pžralelnas ino progra ustreza z sliki 2 ardni prevajalniki generirajo kodo, zaporednemu Izvajanju stavkov seg- ej 1,2,3,A,B,6 , Vendar pa se lahko med njimi izvrSijo paralelno, npr. 5,6, kjer z 1:2,3] opiSemp paralelno stavkov 2 in 3. VpraSamo se, ali je erentna paralelnost zgornjega seg- tno je, da je iz sekvenCnega zapisa t teifko razvidna, zato se posluituje- mskih grafov. Programski graf, ki gornjemu segmentu, je prikazan na C'rež = s/t J Slika 2. ToCke programskega grafa ponazarjajo stavke (operacije), usmerjene povezave pa so­ vpadajo s prehajanjem vrednosti operandov* Ker Je graf na sliki 1 aoikliCen, se lahko opera­ cije, ki so na istem nivoju, izvajajo pafa~ lelno. Operacija u Je na nivoju i, Ce Je dollfina najdaljSe poti od zaCetne operacije do operacije w enaka i. V programskem grafu na sliki 1 so operacije porazdeljene po nivojih na sledeC naCin: Slika 3. Poseben sel se ob prvi izvr povezavi a in p njiju povezavi vrednost operand pomnoKi preJSnji je za operacij pol, operacijo s mnoifenja dve C funkcijske vred 1! , 2! , <,! .. 3! Je v tem, da bloka A vrednost e prekrije z nov uporabil predhod se blok B izvaja ista vrednost uporabila veCkr da bi se nekater ( panavi Jale, np ekci j Sitvi ,ob v r i a za rezu o ko eBtev asovn nosti Vzro se za vhod 0 vre no vr 1 hit vhodn at, k e f un r. 1 ski m blo saki n i. 1, s Itat. piran anja i en v t k za radi nega dnost ednos reje ega o ar bi koi js , 2 ehanizem posk kov A in B up naslednji pa Blok A inkre katerio nato Predpostavi ja (capy) p ena in za op oti. Tedaj oCki f zap izostanek re hitrejšega iz operanda v p jo, ne da bi t. V primeru kot blok A, p peranda v pov imelo za pos ke vrednosti 2! ,31 .. rbi, da orabita namesto roentira blok B mo, da otrebno eracijo bi bile čredama zultata vaJanja ovezavi blok B , ko bi a bi se e;avi e ledico, v toCkl 12 Tako ni maguBe s prisotnostjo katerekoli vrednosti vhodnega opsranda d8klarii:'ati vozli- Bda kot izvršljivega, saj lahko pripadajo vre­ dnosti vhodnih operandov popolnoma razliCnim delom IzcaHura. Obstaja nekaj razliflnih reSi- tev nastalega problema oziroma natiinov reali­ zacije DF sistema C23. (i) Ciklidni programski grat transiocmi- ramo v aoiklifini tako, da vsako ponovitev opi- Semo z aoiklitJnim podgrafom. Tako translormi- ran graf iz slike 3 ima obliko kot Je prikaza­ na na sliki >>. Ta refiltev zahteva velike koliCine pro­ gramskega pomnilnika, zahteva pa tudi dinaoi- Bno generiranje koda v primeru, ko je pogoj za izstop iz zanke izratiunan fiele v tlasu njenega izvajanja. Obe zahtevi se odraiiata kot pomem­ bna pomankljivost v praktiflnih sistemih. nosilka vrednosti aperanda nosilk^ potrditvenega signala Slika 5. Slika >>. (ii> Ponovitve opišemo z enim grafom, vendar se lahko ponovitev prlCne Šele tedaj, ko Je predhodna konOana. Taksna rešitev ne dovoljuje vzporednosti med ponovitvami in zahteva posebne ukaze ali posebno materialno opremo, ki testira koneo ponovitve. (iii> Uporaba grafov je omejena tako, da je v veji grafa prisotna istočasno samo ena vrednost operanda C33. To pomeni, da se opera­ cija lahko izvrši le tedaj, ko so prisotne vrednosti vseh vhodnih operandov in ni v izhodni veji nobene vrednosti. Torej vrednost spremenljivega operanda v neki povezavi ne sme biti spremenjena vse dokler ni uporablJenA. Ko pa je enkrat uporabljena, mora postati neupo- rabljiva. Kljub sekvendnosti izvajanja je prednost tega naCina pred prvima dvema v moiini izrabi cevljenja (pipelining). Vsaka operacija po svoji izvršitvi obvesti svoje "starSe", da je pripravljena od njih sprejeti naslednje vrednosti vhodnih operandov. To stori s pomo­ čjo dodatnih povezav - nosilk potrditvenih (aknculedge) signalov, kar kaife primer na sli­ ki 5. Z uvedbo potrditvenih signalov se Btevilo povezav, in s tem promet v grafu, podvoji. (iv) Poleg vrednosti operandov nosijo po­ vezave ee dodatna informacijo • delih izratiu- nov, katerim pripadajo operandi Cm. Pravima, da e.o povezave nosilke znakov (token). Znaki imajo dodatne labele, ki vsebujejo indeks in nivo ponovitve. Te labele obifiajno imenujemo barva. Operacije se lahko izvrSi le tedaj, ko imajo vsi vhodni znaki enako barvo. Ta metoda uporablja popolnoma statifino generiran kod in omogoOa maksimalna vzporednost izvajanja. TakSna rešitev zahteva povedan pretok in­ formacij po grafu in dodatna vozlifiCa za spre­ minjanje ter primerjanje label, kar ima za posledico bodisi dodaten Tudi tu so povezave nosilke znakov, poleg tega pa opravljajo Se funkcijo vrst (cjueue), kar pomeni, da so v njih znaki razvr- SBeni v istem vrstnem redu, kot so vanje pri­ hajali. Povezava E S slike 3 ima tedaj obli­ ko, kot Jo prikazuje slika 6. i + 2 i + 1 i J 1 1 + 2 U1 1 ? Slika 6. Ta reSitev omogoda enako stopnjo vzpored­ nosti kot pri labellranju, zahteva pa čakalne vrste, ki so prostorsko zahtevne. Programski graf, zgrajen po enem od zgor­ njih naSel, je struktura, ki utiifikovlta pove- ;:uj>.' visok programski Jezik z materialna opre­ mo in popolnoma ohranja inherentno paralel- nost (iiUkia 1). Primerjavo opisanih petih realizacij OF si:iteiiia si oglejmo na primeru naslednjega pro­ grama i 13 input d,e,f cCD3 = Q for i from 1 to 8 do beg in aCil = bCi3 = cCi3 = end output a,b,c dCi] / eCi3 aCi3 t Ki] hči] + cCi-n Predpostavimo, da zahteva deljenje tri, mnoitenje dve in seštevanje eno Časovno enoto. Namišljeni OF računalnik naj ima Štiri pro­ cesne enote P1, P2, P3 in P H 8 a 0 t- 5 1 •/O 1 4 i 1 - . 1 . . 1 iO iS _1_ 1,0 _1 _i H Q< fi, F\- • Q. b. ^ a,. k Cj Ov b> Ci ds b. Si Q, bs C a, b. C a, b, C, k y iO 1 . iO I IS 77 _l I P, p.' ft PH Q, Qt a Q, a, C. b, b. Ch o„ QQ b, QQ /A Q C/ b, A b, b, • ci,- C, •v Slika a 14 oierja. Le-ta z njihovo uporabo olajSa delo prevajalniku pri odkrivanju paralelnosti. Ve­ Čina teh Jezikov pa Je nenaravnih v smislu, da v preveliki meri odražajo arhitekturo, na pod­ lagi katere so oblikovani, manj pa naCin, ria katerega programer razmišlja pri reSevanJu nekega problema.. Tako kot ostale oblike paralelnih raču­ nalnikov zahtevajo tudi OF računalniki (zaradi CimboljSe izrabe svojih lastnosti) posebne vi­ soke programske jezike, t.i. DF jezike, ki pa ne sodijo med von Neumannove Jezike CS3. Za razliko od konvenoionalnih Jezikov, kateri delujejo nad podatki s pomoCJo stran­ skih uCinkov, DF Jeziki le-teh ne poznajo. Znana Je namreC zveza med učinkovitim paralel­ nim raCunanJero in odsotnostjo stranskih uCin­ kov. To lastnost imajo funkcionalni Jeziki, ki delujejo izklJuCno na podlagi uporab funkcij nad vrednostni Cb3. SledeCa lastnost, katero imajo DF jeziki. Je lokalnost uCinka, kar pomeni, da ukazi nimajo nepotrebnih, daleC segaJoCih podatkovnih odvisnosti. Omejitve glede izvajanja ukazov temeljijo izklJuCno na ''podatkovnih odvisnostih. Posledica te zahteve Je, da Je vsa informacija, potrebna za izva­ janje programa, vsebovana v programskem grafu. DF jeziki imajo v sintaksnem smislu veli­ ko skupnih lastnosti s konvencialniai jeziki, saj uporabljajo podobne programske konstrukte, kot so prireditev, aritmetiCne izraze, pogojne stavke, iteracije in rekurzijo. Bistvena pa ^f razlikujejo v semantiki. Za razliko od konvefi- oionalnih jezikov, pri katerih identifikatcijp predstavlja naslovijlvo enoto pomnilnika, p^ pr.i OF Jezikih predstavlja povezavo. Posledici takSne semantike DF Jezikov Je, da se lahko nekemu identifikatorju priredi vrednost samo enkrat, kar imenujemo pravilo o enkratni pri­ reditvi. 8 preimenovanjem identifikatorjev lahko v neiterativnih delih programa problem večkratne prireditve uspeSno reSimo. TeKava pa lahko nastopijo v zankah. Zato Je potrebno pri definiranju zanke navesti <1) vhodne vred­ nosti vseh zanCnih identifikatorjev, t2) pogoj ustavljanja, (3) vrednost, ki naj bo rezultat ob koncu izvajanja zanke in (4) pravila po ka­ terih se zanCnim identifikatorjem (ob vsaki izvreitvi telesa zanke) priredijo nove vredno­ sti. Za ilustracijo si oglejmo primer algorit­ ma za izraCun n!, zapisanega v DF jezikih VAL ( Value-orlented Algorithmlc Language ) for j,k 1= n,1 i l2 it j = O then k else iter j,k end end := j-1,k*j 1 in ID CS3 <- 1 (Initial j <• nj k vhile j O Q do neu j •*• J-1 t new k return k) k»J| (1) (2) (3) (A) (1) (2) (A) (3) DF računalniki nimajo centralnega proce­ sorja, temveC imajo procesni del, ki ga ses­ tavlja mnoiiica nekaj deset, sto ali tisoC pro­ cesnih enot. Vsaka procesna enota je enaka enostavni aritmetično logiCni enoti ali vho­ dno/izhodnemu procesorju. Nimajo niti pomnil­ nika, kakršnega uporabljajo von Neumannove arhlt ima p celic progr Cilno ci j6k Zato de iz proce sko v nllni prika ekture, z otencialn , v kate amskem g tudi to, e ure, pr pa ima ar cel ic sne enote ezje, ki Skimi cel zana na s ato p o ve rih raf u. da ogram bitra pomni proč povez icami liki a imajo pomni liko Število se nehajojo Za DF raCun ne uporablja skega Števca ifno vezje, ki IniSkega del esnega dela i uje procesne Arhitektura 9 C7J. InlSki del, ki pomnilniSkih vsi podatki o alnike je zna­ jo sinhroniza- in registrov. usmerja izho- a v ustrezna n distribuoij- enote s poo- DF sistema Je rtlOUMII UL -j ntOCtlHA EMOTA I«- i niOCItKA MSTA OMNU-NJKI ML PKTUmuCIJ. • Ponnii.. ceticA -J fOMNIL. CriKA I- AUiTa/tina vezjt Slika 9. Arbitrarno vezje ugotovi, katere operaci­ je so godne za izvršitev in Jih posreduje pro­ cesnemu delu. Le-ta Jih IzvrSi in poSlJe delne rezultate distribucijskemu vezju. To vezje pa ugotovi katere operacije iz poanilniSkega dela Čakajo na dobljene rezultate in Jim Jih posreduje v obliki vhodnih operandov. Sedaj zopet nastopi arbitralfno vezje s dimer se ci­ kel ponovi. Z 3 K 1 j,«-i ti&U Osnovne ideje, na katerih temelji DF kon­ cept, segajo v pozna Šestdeseta )eta. Z razvo­ jem sodobne VLSI tehnologije Je postala obsto­ ječa (von Neumannova) arhitektura glavna ovira pri izkoriščanju paralelnosti v algoritmih. VLSI tehnologija pa Je omogoCila smiselno upo­ rabo materialne opreme v arhitekturah non-von (ne von Neumannovlh) sistemov. DF koncept Šestdesetih let je tako postal uresničljiv, saj omagoCa ta tehnologija izdelavo integrira­ nih vezij s celo 100 noilioaml. TlsoC takih ve­ zij, ki opravljajo usmerJevalno-povezovalno funkcijo (router), omogoCa uporabo celo 512 procesnih enot ali celiCnih blokov (celi block). Ce vsaka od procesnih enot izvrili milijon InstrukciJ v sekundi, potem nove arhi­ tekture (ob pravilni izrabi paralelizmov) oao- goCajo skoraj milijardo inStrukoij v sekundi. VeCjl DF projekti v .svetu potekajo t - na MIT, kjer skupina pod vodstvom J.Oennisa razvija DF sistem z rezinastiml procesorji tipa Am2903, - tudi na niT, kjer skupina pod Arvindovim vodstvom gradi VLSI 6A procesorski OF raču­ nalnik z labellranlml znaki (tegged-token), -' na univerzi Utah deluje skupina pod vodstvo« A.Davisa, ki Je sestavil prvi deluJoCi OF računalnik. 16 - na CERT v Toulousu, kjer deluje skupina pod vodstvoin J.C.Syra na projektu LAU,, - na univerzi v nanohesteru gradijo eksperi­ mentalni fflultiprocesorki DF sistein z labeli- raniini znaki pod vodstvom J.Gurda in I. Uatsona in r- na univerzi Tokyo, raCunalnik Topstar, pod vodstvom T.Suzukija in J.Hotooke. Analize učinkovitosti, ki so jih izvrSili na realiziranih OF sistemih, so pokazale ob- fiutno Časovno izboljšanje pri reševanju neka­ terih znanih algoritmoVi kot sta FFT (40:1) in Gaussova eliminaciJska . metoda (S0:1>. Ker so ti sistemi Šele v razvoju, obstaja tudi ne­ kaj nereSenih problemov, kot sta problema vhodno/izhodnih aktivnosti in zadasnega pom- nenja C52. ce3 ca] CHD 151 Cbl p.D,6aJski, O.A.Padua, D.J.Kuck 4 R.H. Kuhn I 'A Second Opinion on Data Flow Machines and Languages', Computer,Vol.IS, No.2, Feb.1982, pp.B8-i9 J.B.Oennie t 'Data Flow Superoomputers', Computer,Vol. 13,No. 11,Nov. 1980, pp.'r8-S6 I.Uatson, J.Gurd I 'A Praotioal Data Flow Computer', Computer,Vol.15,No.2,Feb.1982, pp.51-57 U.B.Ackerman i 'Data Flow Languages', Computer,Vol.15,No.2,Feb.1982, pp.15-25 J.Backus : 'Can Programming Be Liberated from the von Neumann Style7 A Fuhotional Style and Its Algebra of Programa', Comm. of the ACH, Vol.21,No.5,Aug.1978, pp.613- 641 Lit^ir^atuiira Cll sT.Ageruala, Arvind i 'Data Flow Systems', Computer, Vol.15, No.2,Feb.1982, pp.10-13 C7] J.B.Dennis, H.V.-P.Lim & U.B.Ackerman : 'The HIT Data Flou Engineering Model', Information Processing 83, R.E.A.Mason (ed.), Elsevier Science Publishers B.V. (North-Holland), pp.553-560