PODATKOVNO VODENE RABUNALNISKE ARHlTEKTURE Jurij Silc, Borut Robifi in Branko hihovilovifi Institut 'Jozef Stefan', Ljubljana UDK: 681.3.014 RaCunalniSke arhitekture lahko razvrstimo glede na podatkovni in krmilni mehanizem. Padatkavni meha- nizem doloCa natiin, kako se ukazom dodeljujejo argumenti, krmilni mehanizem pa dolotia vpliv izršitve enega ukaza na izvrSitev ostalih ukazav. Glede na podatkovni in krmilni mehanizem razvrstimo raCu- nalniSke arhitekture v pet kategorij. V podatkovnopretokovnih raBunalnikih je izvajanje instrukcij podatkovno vodeno; instrukcije postanejo izvrSljive takoj, ko so na valjo vrednosti vseh vhadnih ar- gumentov. Podatkovno vodenim arhitekturam pripadajo visoki programirni jeziki z enkratno prireditvi- jo Cld, Val, Lucid, Valid, SISAL) . Materiaino opremo podatkovnapretokonih raCunalnikov sestavljajo procesni, pomnilniSki in komunik aci jski del, ki 50 fned seboj kroino povezani. Konflno je prikazan tu- di naCin, kako lahko uporabimo podatkovno vadeno arhitekturo kot podporo logiflnemu programiranju. DATA-DRIVEN COMPUTER ARHITECTURES - Basically, computer architectures share two fundamental mechani- sms, these are 'data and control mechanisms. The data mechanism defines the uay a particular argument is coinmunicated by a number o( instructions. The control mechanism defines ho« one instruction cau- ses the execution of one or raore othecs. In each category of computer, data mechanisms and contral mechanisms ace largely incampatible sets ol alternative concepts. In data flow computer, instruotion execution is data driveni the availability Q( input operands triggers the exeGution ol the instruc- tion that consumes the inputs. Data flou computers are programmed in very high level single-assig- nment languages . - Program preveden iz jezika SISAL v zbirnik TASB. 374 Elementi programskega grafa ponazarjajo pretok podatkov med posameznimi ukazi. Tofike grafa ponazarjajo ukaze, usmerjene povezave pa so nosilke vrednosti argunentov ter obifiajno £e dodatnih informacij o delih izrafiunov katerim pripadajo argumenti. Torej so vhodne povezave nosilke operandov ukaza, ki ga tofika predstav- lja, izhodne povezave pa hranijo parcialne ce- zultate. Primer programskega grafa je prikazan na sliki 5. (imlial vaiues) inl (final value) Slika 5. - Podatkovno graf . pretoko.vni programski Programski graf je asinhron, kar pomeni, da postaneja ukazi izvršljivi- tedaj, ko imajo na voljo vse vhodne operande. Gibanje podatkov skozi programski graf pameni izvajanje progra- ma. Omeniti velja Se eno zelo pomembno last- nost programskih grafav in jasno s tem tudi podatkovno vadenih arhitektur; namrefl, ko je operacija oz. ukaz izvrSen, vhodni operandi oz. njihove vredndsti, niso vefl razpoloz'1 jivi . Pri cikliflnih programskih grafih se pojavijo dodatne tetave\ v doloCenih vejah grafa se la- hko zafino akumulirati vrednosti operandov, kar paoeni, da bi postal graf nedeterministifien. Tarej ni mo2no s prisotnostjo katerekoli vred- nosti vhodnega operanda deklarirati toHko kot izvrSljivo, saj lahko pripadajo operandi po- polnoma razliCnim delom izrattuna. Obstaja ne- kaj reSitev nastalega problena: * CikliCne programske grafe transformiramo v acikliCne. Ta re^itev je zelo nerodna v pri- ffleru, ko imano zanke, katerih pogaj za iz- stop iz zanke se izrafiuna Sele v Casu samega izvajanja. V teh primerih je potrebno dina- mifino generiranje koda. * V vejah dovoljujeroo prisotnost le ene vred- nosti. To izvedemo s pomočjo dodatnih povra- tnih povezav, ki nosijo potrditvene signale, kateri dovoljujejo ustvarjanje novih vredno- sti. Z uvedbo teh povezav se promet v grafu podvoji. * Naslednja reSitev je, da so povezave nosilke paketov, ki poleg vrednosti operandov nosijo Se dodatne informacije o delih izraCunov, katerim te vrednosti pripadajo. Te dodatne labele obifiajno imenujemo barve in toflka po- stane izvrSljiva, ko so v vseh vhodnih pove- zavah prisotni paketi enake barve. * Obstaja Se ena moSna reSitev; povezave lahko opravljajo (unkcijo vrste, kar pomeni, da so vrednosti razvrSCene tako, kot so v povezavo prihajale. Ce povzamemo, pragraoski graf je asinhron in deterministiCen, vse toCke imajo pomen iunkcij in vrednosti operandov po uporabi nisa več razpoloSljive CM3. § 3.3. Materialna oprema Materialna aprema podatkovno vodenih arhitek- tur mora blti zasnovana tako, da omogoCa uKin- kovito implementacijo programskega grafa. Tak sistem sestavljajo procesni, pomnilniSki in komunikacijski del, ki so raed seboj kro?no pa- vezani (slika 6). komunl kac i je C, ... Cn p omnilnik M, . . . Mm procesorji P, . . . Pk KJ Slika 6. - Podatkovno vodena arhitektura. Podatkovno pretokovni raflunalniki nimaja cen- tralnega procesorja, temvefi iraajo procesni del, ki ga sestavlja množica nekaj deaet, sto ali tisofi prooesnih enot. Nimajo niti pomnil- nika, kakrSnega uporabljajo von Neumannove ar- hitekture, zato pa imajo pomnilniSki del , ki ima potencialno veliko Stevila pomnilniških celic, v katerih se nehajojo vsi podatki o programskem grafu. Za podatkovno pretokovne računalnike je znafiilno tudi to, da ne uporab- ljajo sinhronizacijske ure, prograraskega Ste- vca in registrov. 2ato pa ioa arbitra?no vez- je, ki usmerja izhode iz celic pomnilniSkega dela v ustrezne procesne enote procesnega dela in distribucijsko vezje, ki povezuje procesne enote s pomnilniSkimi celicami. Osnovne ideje podatkovno vodenih arhitektur segajo v pozna Sestdeseta leta, ki pa so ob moSnosti VLSI implementaoije postale ponovno zelo aktualne. VLSI tehnologlja, ki omogoCd izdelavo mikrovezij s celo 100 pini, je po- trebna, saj bi tisofi takSnih vezij, ki bi opravljalo funkcijo usnerjanja in povezovanja, omogoCilo uporabo 512 procesorskega padatkov- no pretokovnega sisteoa. 375 S 4. LOGICNO PROGRAMIRANJE NA PODATKOVNO VODE- NIH ARHITEKTURAH Logiflna programiranje je matematieni formali- zem, s katerim lahko reSujemo probleme na ne- proceduralni naflin. Logiflni programi niso ve- zani na von Neumannove - sekvenflne arhitekturb in so zato primerni za izvajanje na paralelnih arhitekturah. Zato se samo po aebi postavlja vpraganje, kako je logode za njihovo izvajanje uporabiti podatkovno vodene arhitekture? 5 tem bi namreC dosegli, da bi te arhitekture podpi- rale tudi Prolog, ki je izbran za jejik 'pete' generacije. Odgovor je: narediti prevajalnik, ki bi logiCni program prevedel v programski graf , to je strojni jezik podatkovno pretoko- vnega raCunalnika 151. Prolog je nepostapkovni ali deklerativni je- zik, ki temelji na predikatnem raSunu prvega reda, ki tudi tvori njegovo sintakso. Omogofia enostavno detiniranje relacij med padatki in pa strukturiranje podatkov. § 4.1. LogiCni program Logifini program je mnozica stavkov, ki imajo obliko Po :" P| • • • • • Pm • Vsak p, , imenovan cilj (literal), ima obliko p(t| ,...,t,,), kjer je p predikatni simbol , ti tn pa so elementarni podatkovni abjekti (termi), ki so lahko konstante, spremenljivke ali funktorji. Privzemimo omejitev, da so vsi predikati binarne oblike, torej p't, ,tk). 5 to omejitvijo ne izgubima ntttesar na sploSnosti, saj lahko vsako n-mestno relacijo pretvarimo v n+1 binarnih relacij. Zaradi enostavnosti se omejimo le na' elementarne podatkavrn; oblike tipov konstanta in spremenljivka. p se ime- nuje glava stavka, p do pm pa tvorijo telo sfavka. Stavek brez ciljev je enotin stavek, ki izraza eksplicitno dejstvo, to je brejpo- gojno trditev QZ. dejstvo. V primeru programa s slike 7 so stavki, oznafieni z (1) da (5), ki podajajo relacije "vodja", "raziskovalec" in "programer" med asebarai in skupinami, enotim stavki. (1) vodja(sk1,peter). (2) vodja(sk2,gorazd). (3) razis(sk1,borut). <*) razis(sk1,jure). (5) prog(sk2,jure). (6) sodel(S,l) :- prog(S,I). (7) sodeKS.l) :- razis(S,I). (8) nad(l1,I2) :- sodel(S,11),vodja(S , 12) . (9) ?- nad(jure,12) . Slika 7. - Primer logifinega pragrama. vpraSalnega stavka prilagDdi na glavo enega izmed sploSnih stavkov. Na sliki 7 je vpraSal- ni stavek označen z <9), ki spraSuje "Kdo je Juretu nadrejen?". Cilj tega-stavka se pi-ila- godi z glavo stavka (8). Spremenljivka 11 v celem stavku pri tem zavzame vrednost jurt. Telo stavka (8) sestavljata cilja sodel(S,ju- re) in vodja(S,I2). V naslednjem koraku se sodel(S,jure) prilagodi eni od glav stavkov (6) ali (7), npr.(6>. Postopek se nadaljuje dokler ni cilj vpraSalnega stavka lzpolnjen. Kadar cilja ni vetS raogotte prilagaditi nober.i glavi, pride do vrafianja in ponavnega prilaga- janja z drugimi glavami ; npr. cilj sodel'S, jure) se prilagodi glavi stavka (7). fle niti prilagajanje niti vrafianje ni vefi mogoee, po- tem cilja ni mogoCe izpolniti. § H.B. Predstavitev logiflnega programa s po- datkovno pretokavnim grafom Kot retieno, logiCni program sestavljajo dej- stva in sploSni stavki. Vsako dejstvo vseLuje ime predikata p, ki mu sledita dva elementarna podatkovna objekta t, in tk . Mno^ici vseh dejstev logiflnega pragrama priredimo graf ta- ka, da predstavimo vsako dejstvo p(t, ,tk) & podgrafom oblike >0 grafa so elementarni podatkovni ob- jekti. Usmerjena povezava iz vozliSCa t v t obstaja in nosi oznako p natanka tedaj, ko je p(t ,t ) dejstvo. Dobljeni graf ioienujeino graf dejstev. Dejstva opisujejo relaoije med ele- mentarnimi podatkovnimi objekti, ki v splo£nein niso simetritne. Zato je graf dejstev usaer- jen. Za primer s slike 7 je gral dejstev pri- kazan na sliki S. vod ja ___--—""? azis •>0 peter ->0 borut prog sk2 0-- ->0 gorazd vod ja Slika 8. - Graf dejstev. SploSni stavki, ki imajo glava in telo, se «ed sebaj povezujejo s kazalci v usmerjeno struk- turo na sledeč nafiin: cilj v teleeu nekega stavka ka2e na vse stavke, katerih glave se z njim ujemajo. Takfino, vCasih celo ciklifino, strukturo imenujeao strukturo ciljev. Nek cilj L te strukture reSimo tako, da v grafu dejstev polSBemo dejstvo, ki se ujema s tem ciljem ali pa (Be to ni moKno) reSimo vsaj enega od stav- kov, na katere kaze ta cilj. Slika 9 prikazuje strukturo ciljev za primer logiCnega programa s slike 7. Stavki, ki inajo glavo in telo prinaSajo ioplicitno inforoacijo in se imenujejo splo^ni stavki. TakSni so stavki (6) do (8) v pnmeru s slike 7. Stavka (6) in (7) opisujeta dej- stvo, da oseba I, ki je "programer" ali "raz- iskovalec" skupine 5, tudi "sodelavec" te sku- pine. Stavek (8) pravi, da je oseba 12 v rela- ciji "vadja" z osebo 11, Be je 12 "vodja" sku- pine S, katere "sodelavec" - "programer" ali "raziskovalec" - je 11. Stavki, ki nimajo glave, so vpraSalni stavki. Sistem poiSBe odgovor nanje taka, da cilj ?- nad(jure,12) nad(H,I2) :- sodel D 12. S S tem, ko smo logiCni program prevedli v graf- no oblika, postane izvajanje programa ekviva- lentno problemu prilagajanja grafa. Potek je naslednji: vzorec se reSi tako, da se v grafu dejstev poiSCe dejstvo, ki se ujema z vzorcem. Npr. vpraSalni stavek v naSem primeru je vzo- rec nad 12 D >0 jure. V grafu dejstev poizkusimo paiskati povezavo z oznako "nadrejeni" in toCko "jure". Skratka vzorec poizkuSamo prllagoditi dejstvu. To pri- lagajanje ne uspe, ker v strukturi ciljev ni povezave "nadrejeni". Istofiasno se priflne pri- lagajati tudi vzorec sadel jure 0<- vod ja ->Q 12 na katerega kaS!e ciljni vzorec. Cilj "sodela- vec" kafe na naslednja dva vzorca S 0- in prog razis' ->0 jure S 0- ->0 jure, ki se tudi sottasno priSneta prilagajati grafu dejstev. Tu prilagajanje uspe. Spremenljivka S se veife na vrednosti "sk1" in "sk2". Po ponov- ne« prllagajanju vzorcev sodel vodja jure 0< 0 >0 12 sk1 in sodet vodja jure 0< 0 >0 12 sk2 dabimo iskani reSitvi, ki sta "peter" in "go- razd". 6ra( dejstev torej ustreza podatkovno preto- kovnemu grafu oz. strojnemu jeziku podatkovno vodene arhitekture. Vsaka tottka grafa je logi- Cno gledano ativni element, sposoben izirienjave paketov podatkav med tofikami. Paketi vsebujejo vzorce (vkljuCno s kazalci), ki se poizkuSajo prilagoditi grafu dejstev. § 5. ZAKLJUBEK Veflji projekti na podroflju podakovno vodenih sistemov potekajo: * Na MIT, kjer sta dve skupini; prva pod vod- stvom J. Dennisa razvija siste« z rezinasti - mi procesorji in druga po vodstvom Arvida, ki gradi VLSl 6A procesorski sistem. « Na univerzi Utah deluje skupina, ki jo vodi Davis. * Na CERT V Toulousu dela skupina pod vodstvom J. C. Syra na projektu LAU. t Na univerzi v Manohestru gradijo eksperioier,- talni podatkovno vadeni multiprooesoraki 51- stem pod vodstvotn J. Gurda in 1. Uatsuna. * Na univerzt Tokyo, kjer gradija raKutulnik Topstar pod vadstvom T. Suzukija in J. NulJ • oke. Analize uCinkovitosti, ki so jih izvrSili na realiziranih sistemih so pokazale obCutna fia- sovno izboljSanje. Ti sistemi so fiele v razvo- ju, zato obstaja tudi nekaj nereSenih proble- iiiov, kot npr. nereSen pcoblen vhodno/i zhodnih aktivnosti. Vsekakar pa postajajo podatkovnc vodene arhitekture tudi komercialno doseg- ljive. Pri firmi NEC so izdelali, tako lahko beremo v lanski oktoberski fitevilki revije Computer Design, prvi VLSI Cip pPD72S1, ki uporablja podatkovno vodena arhitekturo in je namenjen procesiranju slik Ct3. V referatu saio predstavili eno od mogofiih ar- hitektur pete generacije, ki bo morda prevla- dala na podrotiju superraCunalnikov. Tak£ne ar- hitekture imajo za cilj poveCati raeunalni«ko mofi sistenov, kar pomeni povettati njihovo zma- gljivost in hitrost pracesiranja ter odpravili ozka grla v procesu raCunanja, ki so posledica von Neumannovega ozkega grla. VeCje rafiunalni- Ske znag1jivosti potrebujemo zaradi naianlih potreb pri refievanju problemov na podrofju unetne inteligence, obdelave slik, razpoznava- nja govora, napovedovanja vremenskih situacij, avtomatskega prevajanja jezika, ipd. Obdelav« in reSevanje takSnih in podabnih problemov s 5pre jeml ji vo hitrostjo je itiagotta le ob uporabi novih paralelnih - deoentraliziranih rafiunal- nifikih arhitektur. § t. LITERATURA Cl] Treleaven P.C., Isabel Gouveira Lina: 'Fu- ture Computers: Logic, Data Flow, ..., Control Flow?', Computer. Vol.17, No.A, Har. 198*, pp.47-57 CH] Computer. Special Issue on Data Flou 5ys- teras, Vol.15, No.2, Feb. 1982 C3] Gurd J.R., C.C. Kirkham & I. Uatson: 'The Manchester Prototype Oataflou Coroputei-' , Conim. of the ACti. Vol.28, No.1, Jan. 1965, pp.3A-52 CO fiilc J., B. Robifi: 'Osnovna naflela DF sis- temov' , Informatica. 3t.2, 1985, str. 10-15 C53 Blc L.: 'Execution of Logic Programs an a Dataflou Architecture', The 11th Annual International Symposium on Computer Archi- tecture, Ann Arbor, Michigan, June 198A, pp.290-296 Ct: Chong Y. II.: 'Data Flou Chip Optimizes Iraage Processing', Computer Desion. Oct.15 1984, pp.97-103