RAZVRSTITEV NOVOGENERACIJSKIH RAČUNALNIŠKIH ARHITEKTUR INFORMATtCA 4/86 UDK: 681.3.02 Borut Robič in Jurij Šilc Institut Jožef Stefan, Ljubljana V Clanku predstavljava razvrstitev rafiunalnifikih arhitektur, porojeno iz treh naflinov vodenja raCunanja: krmilnega, podatkovnega in vodenja z zahtevo. Opisani so ustrezni raflunsto modeli ter njihove rsalizacije na razlifinih organizacijah stroja. Classification of New Generation Computer Architectures - Classifioation o( neu generation computer architectures based an control driven, data driven, and deaand driven camputation is described. Also, we present several simple operational models and their implementatians on diftecent oachine organizations. 1- Pc-olog Ideja o raCunalnikih pete generacije je bila prvie predstav1jena na nednarodni konfe- renci v Tokyu oktobra 1981. Peta generacija bo zdruSevala rezultate raziskav na podroBjih uaetne inteligence, prograairnega inzeniringa, VLSI (ULSI) tehnologije ter predvsem raCunal- niSkih arhitektur. Slednje bodo zanesljivo preSle od zaporednega na soCasno izvrSevanjt. Na resnost teh raziskav kaie tudi dejstvo, da so od tokijske konference pa do leta 1934 ustanovili pet velikih nacionalnih ozirodia regionalnih raziskovalnih programov: - japonski, katerega usmerja ICOT (Institute for New Generation Coaputer Tschnology), - aaeritika DARPA (Defense Advanced Research Project Agency) in HCC (Hlcroelectronic and Computer Technology Corporation) , - britanski Alveyjev progran in - ESPRIT (European Btrategic Research Prograaae in Infornation Technology) v EG5. Raziskave novogeneraciJskih raCunalniSkih arhitektur so intenzivne in so porodile vrsto novih, ne-von Neunannovih principov raCunanja ter pridruženih organizacij stroja. V filanku prikazujeva eoKno razvrstitev arhitektur, kot je bila predlagana v delu CTrel82a3. ARHITEKTURA II KRMILNO VODENJE 3.1 VODENJE Z ZAHTEVO 3.3 PODATKOVNO VODENJE = 3.2 VODENJA RACUNANJA 3 ZAPOREDNI KRHILNI TOK 4.1 SOCASNI KRMILNI TOK 4.2 TOK KRNILNIH PAKETOV 4.3 / REDUKCIJA 1ZRAZ0V 4.5.1 \ REDUKCIJA GRAFOV 4.5.2 TOK PODATKOVNIH - PAKETOV 4.4 MODELI RACUNANJA 4 CENTRALIZIRANA 0R6ANIZACIJA 5.1 ORGANIZACIJA ZA OBRAVNAVO IZRAZOV 5.3 ORSANIZACIJA ZA POSREDOVANJE PAKETOV 5.2 0R6AN1ZACIJA STROJA 5 Slika 1. Elementt rafiunalni^ke arhitekture. 19 2 . Uvod Rezultat raziskav na podrottju novej£ih raCunalniSkih arhitektur so tri osnovne dmifine arhitektur, ki se razlikujeja po nafiinu vodenja raflunanja CTrelBI], CTrel82aD. Ustrežne arhi- tekture se imenujejo kroilno vodene, podatkovno vodene ozirooa arhitekture, vodene z zahtevo. Znotraj vsake druiine pa se arhitekture lofiijo Se po izbranen oodelu rafiunanja ter seveda po organizaciji stroja. Izraz rafiunalniška arhi- tektura je torej doloflen s treni elenenti :: = ( , ). DruZina kroilno vodenih arhitektur zdruzuje tradicionalne von Neumannove raCunalnike skupaj z njihovioi paralelnioi razliCicami, kot sta na priaer SIMO In HIHO arhitektura. Ostali dve dru?ini pa zdrufujeta novejSe, visoko paralelne ne-von Neumannove arhitekture. V nadaljevanju bo prikazana podrobnejSa razdelitev raCunalniSkih arhitektur ter razlike med njimi. Bralcu bo v poooC slika 1, kjer se oznake ab posameznih elementih arhitekture nanašajo na ustrezna poglavja v tilanku. Vodenja rafiunanja RaCunanje lahko smatramo kot zaporedno ponavljanje treh faz: . a) izbiranja /selection/, b) preverjanja /e«amination/ ter c) izvrSevanja /execution/. a) Izbiranje: v tej fazi se dolotl skupina ukazov prograaa, ki so mozni kandidati za izvrSitev. izvrSijo se lahko le izbrani ukazi, vendar izbor ukaza Se ne zagotavlja njegove takojSnje izvrSitve. Pravilo, po katerem se ukazi izbirajo, imenujema pravilo izbiranja. Lofiioia tri pravila izbiranja: - brezpogojno /iraperative selection/, - notranje /inneraost selection/ ter - zunanje /outermost selection/. Pri brezpogajneoi izbiranju se izbere ukaz ne glede na njegovo lego v progranu. Izbor se izvrSi na podlagi posebnega registra (program- skega Stevca) ali pa na podlagi prisotnosti vseh krnilnih paketov. Notranje izbiranje lzbere najgloblje gnezdene ukaze izraza, zunanje izbiranje pa ukaze, ki ne gnezdijo v nobeneo izrazu. b) Preverjanje: v tej fazi se ugotovi, Ce sa izbrani ukazi izvr^ljivi, kar pDmeni, da se preveri, Ce sa prisotne vse potrebne vrednosti aperandov v izbranih ukazih. Pravilo, po kate- rea poteka preverjanje, inenujaoo pravilo izvrSitve /finng rule/. IzvrSljive ukaze prev- zaae tretja faza ratiunanja, izvrSevanje. Ce ukaz ni izvrSljiv, pa ga faza preverjanja bodi- si odlozi, dokler ga neka kasnejSa laza izbiranja zopet ne izbere, ali pa ga poskuSa napraviti izvrSljivega s teia, da zahteva dolo- Citev vrednosti njegovih argumentov. o) IzvrSevanje: v tej fazi se izvrSljvi ukazi dejansko izvrSe. LoCiao krmilno vodeno /control driven/ raCunanje, podatkovno. vodeno /data driven/ rattunanje ter raCunanje vodeno z zahtevo /deaand dnven/. fieprav bodo vsa tri vodehja raflunanja podrobno opisana v nadaljevanju, te tu omenimo, da pri podatkovneoi vodenju prisotnDst vseh potrebnih operandov sprozi izvrSevanje ukaza, oedtea ko prl vodenju na zahtevo zahteva po rezultatu sprolfi izvrfievanje tistega ukaza, ki ta rezultat lahko priskrbi. 3.1. Krmilno vodenie Krailno vodeno raflunanje ina tledeCe zna- Cilnostli - izbiranje ukazov je brezpogojno, - preverjanje ukazov se ne izvaja in - izvrSevanje ukazov sledi neposredno po izbiranju. Torej se ukazi izvrSe takoj, ko so izbrani. 3.2. Podatkovno vodenie ZnaBilnasti podatkovnega vodenja lahko strneoo v naslednjei - izbiranje poteka tako, da se vsakenu ukazu dodeli procesor, - preverjanje sestoji iz sprotnega ugotav- ljanja prisotnasti vseh vhodnih aperandav ukaza, - izvrSsvanje pa sestoji iz izvrSitve vseh ukazov, katerih vsi potrebni operandi so prisotni. ToreJ pri podatkovno vodenem raCunanju ukazi pasivno tiakajo na svoje vhadne operande. 3.3. Vodenie z zahtevo Vodenje nostii - ukaz z zahtevo pa ima sledefie znafiil- se izbere (navadno po pravilu zu- nanjega izbiranja) tedaj, ko nek prej izbrani ukaz zahteva njegov .rezultat, - v fazi preverjanja se ugotovi, Ce so izbrani ukazi izvrfiljivi, torej fie so znane vrednosti njihovih operandov. če vradnost operanda Se ni znana, sa posre- duja zahteva tisteau ukazu, ki ga lahko izraCuna, - lzvrSevanje js sestavljeno iz izvrSitve vseh tistih ukazov, katerih potrebni operandi BO znanl. Torej se pri vodenju na zahtevo ukaz izvrSi tedaj, ko je bila podana zahteva po njegovem rezultatu. Modeli raBunanja Vodenja rafiunanja realiziramo z razliCnini nodeli raBunanja. Krmilno vodenemu rattunanju pripadajo sle- defii modeli: - z zaporednln krnilnio tokon /sequential control flow/, - s sofiasnim krnilnin tokon /parallel control flow/, - s tokom krmilnih paketov /control (lou uith control tokens/. Podatkovno vodenemu rafiunanju pripada le model: - s tokom podatkovnih paketov /data flov/. Rafiunanje, ki je vodeno z zahtevo pa je aoC realizirati z dvema modeloma: - z redukcljo izrazov /string reduction/, - z redukcijo grafov /graph reduction/. 20 V vsakem modelu rafiunanja se zrcali izvirni naCin vodenja rafiunanja v obliki sproSitvenega ter podatkavnega mehanizma. Spraiitveni mehanizem /control mechanism/ dolofia naCin, kako izvršitev nekega ukaza vpliva na izvrSitev ostalih ukazov in s tem vodenje izvrSevanja programa. SproJitveni nehanizea je lahko: - zaporeden /sequential/: ukazi se izbira- jo drug za drugia in se po vrsti izvrSu- - sofiasen /parallel/i kjer se na nek naBin ugotavlja prisotnost vhodnih operandov ter povzrotii zafletek izvrSevanja tistih ukazov, ki imajo na voljo vse potrebne operande, - rekurziven /reoursive/: kjer se posredu- je zahtevo po operandih ter spraži izvrfievanje tistega ukaja, katerega rezultat je bil zahtevan. S podatkovnim inehanizmoai /data mechanism/ pa je dolofien naKin, pa katerem si ukazi delijo skupne operande. Pri tem si lahko ukazi deiijo operand 5 pomoCjo: - vstavljene vrednosti /literal/: fle je vrednost operanda znana !!e pped prieetkotn rafiunanja, se takaj vpifie v vse ukaze, ki jo uporabljajo, - sprotne vrednosti /value/: kopije operan- da, ki se je izrafiunal, se posredujejo vsea ukazom, ki jim je operand skupen, - reference /reference/1 tu vsebujejo vsi ukazi referenco (naslov) na skupen ope- rand. Zvezo med obena mehanizmoma tei- raz liflnimi nodeli raflunanja prikazuje tabela 1. PODATKOVNI MEHANIZEM vstavljene in sprotne vred. vstavljene vred. in reference S P H R E 0 H i! A 1 N T 1 V l E E N H zaporeden zaporedni kr0i1ni tok sofiasen tok podatkovnih paketov suttasni krmilni tok tok krmilnih paketov rekurziven redukcija izrazov redukcija grafov Tabela 1. Modeli raCunanja glede na sproJitveni in podatkovni mehanizem. .1. Zaporedni krmilni tok Model z zaporednim krmilnim tokoo iraa naslednje znadilnosti: - kroilno vodenje raCunanja, - zaparedni sprožitveni mehanizem, - podatkovni oehanizen s pomofijo vstavlje- nih vrednosti in refereno. Model z zaporednim kroilnim tokora uporablja en saa procesor za rafiunanje in programski Stevec, s katerin se izbere nasledrtji ukaz. Torej obstaja en saa krmilni tok, ki prehaja z ukaza na ukaz in temelji na zaporednem sproiitvenem mehanizemu. Ko krmilni tok daseSe ukaz, se razreSijo vse reference, kar pomeni, da se dostavijo vrednosti operandov i; naslovljenih pomnilniSkih lokacij. V .nodelu z zaporednim krrailnim tokara se torej uporablja podatkovni oiehanizem 2 vstavl jenimi vrednostmi in referencami. Ukaz se nato takoj izvrSi, saj (azi (brezpogojnega) izbiranja neposredno sledi faza izvrSevanja - raBunanje je torej krsilno vodeno. Rezultat izvrSitve sa vpifie v skupno lokacijo. Po izvrSitvi ukaza se prograoski ittevBC bodisi neposredno ali posredno aJurira, s Cimer krmilni tok preide na naslednji ukaz. lzvr€evanje v oiodelu z zapoi-ednim knailnim tokom ponazoriao na stavku z := (K+2)»(x-y) ,. ki je predstavljen z zaporedjes ukazov, pri tte«er vsak vsebuje operaoijo, kateri sledijo operandi (Slika 2). Ti 50 bodisi vstavljene vrednosti ali pa naslovi lokacij, kjer so shranjene vred- nosti operandov. PrenaSanja vrednosti raed ukazi se vrSi s poeofijo skupnih lokacij v pomnilniku. I + x 2 t1 I - x y t2 I * 11 t2 z I 2 t1 I - x y t2 I * t1 t2 z xi(3) x 2 t1 I - x y t2 I • t1 t2 z I . . xi<3> krnilni tok podatkovni tok Slika 2. Ra«3unanja v modelu z zaporedni« krailnio tokoo. Soliasni krmilni tok Model soBasnega krmilnega toka ima sledefie znafiilnostii - kcailno vodenje raCunanja, - saCasni sproiitveni nehanizen, - padatkovni mehanizeoi s pomoejo vstavlje- nih vrednosti in referenc. V aodelu s soflasnim kroiilnim tokom uporab- ljaao ukaza FORK za zafletek sofiasnega rafiunanja ter JOIN za sinhronizacijo. Ukaz FORK i povzro- Ci nastanek novega zaparednega krmilnega toka s priCetkom pri ukazu z naslovom i. Ukaz na naslovu i iraa tedaj na voljo le vse potrebne vhodne operande. Sobasni sproiitveni »ehanizem v tem modelu ne zahteva preverjanja prisatnosti potrebnih operandov, saj je prifletek novega kmilnega toka eksplicitno dolofien z ukazom FORK. Krailni tok, ki je izvrSil ukaz FORK i, nadaljuje z izvrSevanjeo naslednjega ukaza Uaplicitni kroilni tok). Ukaz JOIN n zaustavi prvih n-1 krailnih takov, ki sa prispeli do njega; ko prispe do tega ukaza zadnji, n-ti krrailni tok, nadaljuje z izvrSevanjea nasled- njega ukaza. KBC se v tem oodelu soBasno vrSi nekaj zaporednih krnilnih tokov, je njegov podatkovni nehanizea enak nehaniznu v modelu z zaporednia kroiilnim tokom. Seveda zahteva tak model uporabo vefijega fitevila prooesorjev. Primer izrafluna stavka z 1= (x+2)*(x-y) opisuje slika 3. 21 I FORK i I + x 2 t1 I 60TO j I - x y t2 I JOIN 2 I • t.1 t2 z I K: (3) y: (1) t1 : < ) t2: ( ) z: < ) 2 t1 I 60T0 j I - x y t2 I JOIN 2 I * t1 t2 z I I FORK i I + x:(3) y:(iftii*!S) t2:C2) z:C I i: Ji . + + + 1 + + » + +- I FORK i I + x 2 t1 I GOTO j I - x y t2 I JOIN 2 I * t1 t2 z I x:<3) t2:(2) . + + + + + 1 • +- I FORK i I + x 2 t1 I GOTO j I - x y t2 I JOIN 2 I * t1 t2 z I x:(3) t2:(2) I FORK i I + x 2 t1 I 60TO j I - x y t2 I JOIN 2 I » t1 t2 z I x;(3) krmilni tok podatkovni tok Slika 3. Raflunanje v modelu s sotiasnim krmilnim tokom. A.3. ToK krmilnih paketov Tok podatkovnih paketov Hodel toka s krmilnini paketi ima sledefie jnatilnosti: - krnilno vodenje raCunanja, - soCasni sprozitveni nehanizem, - padatkovni mehanize« s pomaCjo vstavlje- nih vfednasti in refernec. Tudi pri modelu s tokom krmilnih paketov pateka raCunanje sotasno, zato ta model zahteva vefije Stevilo procesorjev. Vsak ukaz hrani poleg operacije ter operandov 5e naslov svojega naslednika, ki bo uporabil njegov rezultat, ter prostore za krmilne pakete, ki jih prejme od svojih predhodnikav po njihovl izvr^itvi. Ko ukaz zbere vse krmilne pakete, se sproSi njegova izvr5evanje, pri Cemer se najprej . razreSijo vse reference ter nato izvrSi opera- cija. Na kancu se rezultat shcani v skupno lokacijo, krmilni paket pa se posreduje vsem naslednikoo ukaza. Vidimo, da je izvrSevanje krmilno vodeno s soCasniin sproSitvenim mehaniz- moa, ki ugotavlja prisotnost patrebnih krrailnih paketov. Podatkovni nehanizem pa temelji na vstavljenih vrednostih in relerencah. Potek raflunanja stavka z := (x+2)*fx-y) je opisan na sliki i,. Model s tokou podatkovnih paketov ima na- slednje znatfilnosti: - podatkovno vodenje rafiunanja, - sotiasni sproifitveni mehanizem, - podatkovni mehanizera s pomoejo vstavlje- nih in sprotnih vrednosti. Ta model je podoben roodelu s tokoit krrailnih paketov, le da se tu izvrSevanje odvija s pomoCjo podatkavnih paketov. Ukazi sestojijo iz operacij, mest za operande ter oznak vseh uka- zov, kamor naj se posreduje rezultat. Operandi so bodisi vstavljene ali pa sprotne vrednosti, s Cimer je dolaCen podatkovni raehanizera. Ukaz se lahko prifine izvrSevati takoj, ko mu je zadnji izmed njegovih neposrednih predhodnikov posredoval podatkovni paket E sprotno vrednost- jo, na katero tiaka. IzvrSevanje je podatkovno vodeno, saj soCasni sproiitveni mehanizem v tem modelu ugotavlja pcisotnost vseh potrebnih vrednosti vhodnih operandov. V primeru toka -podatkovnlh paketov so programi navadno predstavljeni s pomofijo usmer- jenih grafov, s katerimi je opisan tok podatkov nied ukazi. ToBke programskega grafa SQ ukazi, 22 I a + x 2 t1 kC13 I • • - x y t2 kC23 I o o * t1 t2 z 1C13 I ... - + + + + x:C3) y: (1) t1i< ) t2: ( ) zi( ) i: j: . k: 1: I • + x 2 t1 kC13 I i i - K y t2 kC23 I o o « t1 t2 z 1C13 I x:<3) V!C1) tUCS) t2:(2) ziC [f .tl 1U1___ .....lUiiJj1 li I o + x 2 t1 kM3 I o o - x y t2 kC23 I • • * t1 t2 z 1C13 I ... xt(3) y:(1) t1»(5) t2i<2> z:( ) i: J: kt 1: I o + x 2 t1 kC13 I o o - x y t2 kC23 I i i < tU2 z 1C13 I ... 1 x:(3) t2:(2) zs(10) i: ... I o + x 2 t1 kC13 I o o - x y t2 kC23 I o o * t1 t2 z 1C13 I x:(3) y:C1) tok krmilnih paketov podatkovni tok t2:C2) zs(1O> Slika 4. Računanje v modelu s tokom krmilnih paketov. povezave pa skrbijo za prenos vrednosti (podat- kovnih paketov) ned njicni. Toflka se lahko prifine izvrSevati Sele tedaj, ka so prisotni podatkovni paketi v vseh njenih vhodnih poveia- vah. Ob prittetku izvrfievanja toEka absorbira vse svoje vhodne podatkovne pakete (s Cimer ti izginejo iz vhodnih povezav), po izvrSitvi pa postavi rezultat (izhodni paket) istofiasno v vse svoje i2hodne povezave. Izhodni paketi toCke so hkrati vhodni paketi neposrednih nas- lednikov. Pri nodelu raBunanju s tokom podatkovnih paketov je k vsakenu ukazu pridružen procesor, ki pasivno Caka na potrebne vhodne vrednosti. Faza izbiranja je torej kar pridruZitev procesorjev vseo ukazao. Faza preverjanja ses- toji iz ugotavljanja, Oe BO prisotne vrednosti vseh vhodnih operandov. Ce te vrednosti niso prisotne, ostane procesor neaktiven, v nasprot- ne« pa jih sprejme, preide v fazo izvrSevanja ter zatea posreduje rezultate vsem svojim naslednikom. IzvrSitev Etavka z := , kje so tako [unkcija kot njeni argusenti bodisi ataai (npr. + ali 2) ali pa izrazi, sestavljeni iz atonov in izrazov. Uporaba funkclje je sestav- ljena iz dveh korakov: - zahtevs za dadelitsv vrednosti njenim neznania argumentoo ter - izrafiuna funkcije nad njlai. IzraBun funkcije se torej odlozi, dokler niso dodeljane vrednosti vsea argumenton. Na priner, zahteva za dodelitev vrednostl arguaentu a1, kjer je a1 dsflniran z a1 = , sproJfi nadaljno uporabo funkaije g nad arguinen- ti b1,...,bM. TakSne zahteve po uporabi (unkcij lahko porodijo nove zahteve, s fiioier je doloCeri rekurziven sprolitveni aahanizea. OCitno Je, da noca biti vsak arguaent definiran i eno saao definicijo, kar imenujeao pravilo o enkratnl prireditvi /single assigne- nent rule/. Pravimo, da se dani argunent tkli- CUJB /reference/ na svojo definicijo. Poleg tega definicija vrna pri vsaki uporabi vedno enako vrednost kar lasnujeno referenCna trans- parentnost rsdukcija. Pri redukciji poteka faza izbiranja navadno 23 < + C 3 2 z/1 i2i (-[][] :/2 ) ( + C3] 2 z/1 ) i2: ( - C33 [1] z/2 ) iti ( • [ : 2 1/1 ) i2i ( • [ ] N i/2 ) iii ( t [ ] 2 1/1 ) i2: ( - C 3 C 1 z/2 ) i1 : ( + z/2 ) 4.5.1. Redukciia izrazov Model z redukcijo izrazov ima sledede znatfilnostii - vodenje rafiunanja z zahtevo, - rekurzivni sproKitveni mehanizem, - podatkovni oehanizem s pooiofijo vstav- 1jenih in sprotnih vrednosti. Zahteva za dodelitev vrednosti argumentoro poteka tako, da se neatomarni argument nadomes- ti s kopijo definlcije, na katero se sklicuje. Podatkavni mehanizen zato temelji na vstavlje- nih in sprotnih vrednostih. Ce lunkcija vsebuje vett neatomarnih argumentov, se vsi nadomeste sotiasna. Be so arguaienti lunkcije atomarni, se funkcija izrabuna in nadomesti z rezultatom. Izrattuni funkcij potekajo sofiasno. V ten rnodelu je zelo ponenbno dejstvo, da se postopek nadomeSflanja izvrSi vsakokrat, ko se zahteva izraCun argunenta. Priner redukcije izrazov pri izvrSevanju stavka z != (x+2)«(x-y) je opisan na Bliki 6. def inicije x: (3) y: (1) 2) i2: <- x y) z: (* -> (. . .z.. .) -> -> (...<• i1 i2) . . .) -> > C. . .<• (+ x 2) t- x y>>...)-> >(...<*<+ 3 2) (- 3 1)>. ..) -> -> (...(• 5 2) . . .) -> -> <. .. 10 ...) -> Slika 6. RaCunanje v modelu z redukcijo izrazov. Slika 5. Rafiunanje v sodelu s tokoro podatkovnih paketov. A.S.2. Redukciia oratov po pravilu zunanjega izbiranja. Procesorji se pridru2ijo ukazom v čitsu iaze izbiranja. Faza preverjanja pregleda argumente ukaza ter ugotovi, Ce je izrattun ntozen. tte je, preide ratlunanje v (azo izvrSevanja, v kateri se ukaz izvrSi ter nadauesti s svojiro rezultatora. V nasprotnea primeru pa faza preverjanja izda zahtevo po nadomestltvi neznanih argumentuv : znanimi vrednostmi. TakSna zahteva povzroKi nastanek novih faz izbiranja, preverjanja in izvrSevanja tistih ukazov, ki lahko vrnejo zahtevane vrednasti. Vsaka taka nova iaza pre- verjanja seveda lahko porodi zopet nove faze rafiunanja. Ko se vsa ta povzrofiena raflunanja konCajo in vrnejo prvotno zahtevane vrednosti, zaCetni ukaz kDnflno preide v fazo izvr^evanja. Lofiimo dve vrsti redukcije, ki se razliku- jeta po naCinu obravnavanja argumentov. Pripa- dajofia sodela raCunanja se ioenujeta redukcija izrazov oziroma redukcija grafov. Model z redukcijo grafov pa ina sledefie znaCilnosti: - vodenje raCunanja z zahtevo, - rekurzivni sproiitveni aehanizem, - podatkovni mehanizeo s pomottjo vstav- ljenih vrednosti in refereno. Pri redukciji grafa se definiciji, na katero se sklicuje argunent, doda oznaka tega argumenta. To pomeni, da podatkovni mehanizetn temelji na vstavljenih vrednostih in referen- cah. Po uporabi funkcije v tej definiciji se njena vrednost posreduje eakajoeemu argumentu, hkrati pa se tudi definicija nadomesti s to vrednostjo. Ob kasnejSem sklicevanju na tako definicijo se takoj vrne njena vrednost. To je temeljna prednost redukoije grafa napram redukciji izrazov. Primer izrafluna stavka z := <:x+2)*(x-y) je opisan na sliki 7. 24 x: (3) : (+ x 2) y: (1) i2: (- x y) z: <* j : (. . . z*. . > x: <3 K'2 y: (1 i2/2) 2rY-^x y_.z/2) i2 ji (. . . z7. . > z/2'J x: (3) 11: (5 z/1) z : i2 j/ j : C. . . z"?..) x: (3) y; < 1) : (2 z/2> r. (1) x : (3) i1i (5) ys (2) t.h, Povzetek lastnosti modelov raCunan.ia Zaporedni in sotfasni kroilni tok inata sle- defie skupne znaCilnosti: - prenos podatkov ined ukazi poteka preko referenc na skupns poenilniSke lokacije, - vrednosti operandov so lahko shranjene v sanBO ukazu (vstavljene vrednosti); s ten se pohltri njegova izvrSitev, - krnilni tok je po svoji nac-avi zaporeden, vendar tahko kreiramo sodasne krmilne tokove z uporabo posebnih uka2ov FORK in JOIN, - krmilni tok in tok podatkov sta lofiena, - potek rafiunanja je popolnona določen s krailnin tokoa. rattunanja s tokom podatkovnih se posredujejo med v obliki podatkovnih Lastnosti paketov soi - sprotne vrednosti ukazi neposredno paketov, - noifna je uporaba vstavljenih vrednosti , - ob pritietku izvr^evanja prevzane ukaz svoje vhodne pakete, s Ciner ti izginejo iz vhodnih pavezav, zato jih kasneje ne more vefi uporabiti, - pri izvrSevanju se ne uporabljajo nika- krttne skupne pomnilniSke lokacije za pranos podatkov, kot je to priuer pri krailnea vodenju, - izvrfievanja prograoa je popolnoma dolofie- no s tokoo podatkov. Redukcija pa ima sledefie znatiilnosti: - vse progranske strukture, (unkcije in argumenti 50 gnezdeni izrazi, - pri prenaSanju vrednosti se ne uporablja- jo nikakrSne skupne pomnilniške lokacije, - izvrSitev ukaza vrne bodisi atooaren ili pa sestavljen izraz, - po izvrSitvi definicije se le-ta lahko nadamesti z izraOunano vrednostjo, - potek raflunanja je popolnona definiran s tokom zahtev po izvrSitvah. Vsa opisane nodele raflunanja in njihov odnos glede na nafiin vodenja opisuje tabela 2. krtllno NACINI VODENJA podatkovno 2 zahtevo R M A 0 e D U E N L A 1 N J A zaporedni tok podatkovnih redukcija krailni tok paketov izrazov sotiasni redukcija krailni tak grafov tok kroilnih paketov z: (10 j/1) Tabela 2. NatUni vodenja in ustrezni nodeli ratiunanja. i: (...z.. .) Org«nizaoijs x: (3) 11: (5) tak zahtev = j: z: (.. tok y i (10) * .10...) podatkov - : (1) 2: (2) sklic Slika 7. RaCunanje v madelu z redukcijo grafav. Kot je bilo uvodona onenjeno, pripadajo naCinoo vodenja rabunanja ustrezne druzine rafiunalnlSkih arhltaktur, ki se imenujejo krmilno vodene arhitekture, podatkovno vodene arhitekture tac arhitekture, vodene z zahtevo. Omenjene druzine izvirajo Iz načinav vodenja rafiunanja, vendar pa 1ahko posanezne druJine razdeliao m poddruzine gleds na izbrani roodel rattunanja ter organlzaoijo stroja /nachine organization/. Pod izrazom organizacija stroja razumemo naflin sestavljanja in nedsebojnega povezDvanja osnovnih raflunalniSkih naterialnih 25 virov /resources/, kot so procesorji, poronilni- ki in konunikacijske enote. Razlikujeino tri osnovne organizacije stroja in sicer: - centralizirano organizacijo /centrali- zed organization/, - organizacijo za posredavanje paketov /package communioation arganization/, - organizacija za obrsvnavo izrazov /en- pression manipulatian organization/. V nadaljevanju boreo najprej opisali vse tri oaenjene organizacije stcoja. 5.1. Centralizirana ordani. ? aci ia Centralizirano arganizaoijo sestavljajo en procesor, pomnilnik ter vodilo med njima (Slika S). Takfina organizaoi. ja iaa v danea trenutku v progranu en sam izvrSujoC se ukaz. Po izvrSltvi takSnega ukaza se prifine izvrSevanje njegavega natanfina doloCenega naslednika, izbranega s progranskim Stevcem. To je v resnici tradicio- nalna von Neuoannova arhitektura. c p M P ••• procesor C ... konunikacijska enota M .. . ponni lnik Slika S: Centralizirana organizacija stroja. 5.2. Oroanizaciia za posredovanie paketov Orgamzacijo sestavljajo tri glavne enote: procesna enota, ki zdrutiuje vefije Stevilo procesarjev, pamnilniSka enota ter komunika- cijska enota. Enote so krozno povezane, kot to prikazuje slika 9. Med enotami se nahajajo 6e vrste /pools ol work/, ki apravljaja nalogo zafiasnega skladijfienja paketov, kadar je to potrebno. IzvrSevanje pragrana v takSni organizaciji poteka v obliki enosmernega krolnaga toka paketov skozi njene enote. Enote delujejo soiiasno, torej je izvr&evanje programa cevljeno /pipelined/. Paketi, ki so pripravlje- ni za obdelavo v eni izmed enot, flakajo v ustrezni vrsti, vee dokler jih ustrezna enota ni pripravljena sprejeti. Ko jih ta enota obde- la, shrani tako sprenenjene pakete v vrsto pred naslednjo enoto. 5.3. Organizaciia za obravnavp izrazov TakSno organizacijo sestavljajo enaki osnovni gradniki, med seboj povezani v pravilno strukturo /regular structure/. Vsak gradnik sestavljajo tn enote: procesor, pommlnik in koaunikacijska enota. Slednja skrbi za puvezavo aed procesorjem, ponnilnikara tec sasednjimi gradniki. Dve znaflilni strukturi tak^ne organi- zacije, vektorsko in drevesno, prikazuje slika 10. V tak^ni organizaciji se obravnava progran kot gnezden izraz. Podizrazi so pridru- 2eni gradnikoa, pri Cemer se podizraz pridru^i tistenu gradniku, ki zrcali lego podizraza v izrazu. Med izvrševanjem vsak gradnik pregleda svoj pndruSfeni podizraz ter ugotovi, kaj mu je stonti. P . . . procesor C ... koounikacljska enota M ... poanilnik Q ... vrsta Slika 9. Organizacija stroja za posredovanje paketov. P ... procesor C ... koaunikacijska gnota H ... poanilnik Slika 10. Organizacija stroja za obravnavo izrazov; a) vektorska, b) drevesna. 26 V tem poglavju bomo pokaiali, kako 1ahko razlifine organizacije stroja podpirajo posaoiez- ne aodele raCunanja. Povedano drugafie, tri os- novne družine arhitektur bomo razdelili na pod- družine, kot je prikazano v tabeli 3. družine arhitektur model raCunanja organizacija stroja zaporedni krmilni tok centralizirana krailna vodene soCasni krmilni tok obravnava izra2ov I tok kroilmh I paketov posredovanje paketov podatkovna vodene I tok podatkavnih I paketov posredovanje paketav I tak podatkovnih I paketov obravnava izrazov 1 redukcija I izrazov obravnava izrazov vodene z zahtevo I redukcija I gratov + I redukcija I izrazov obravnava izrazov centralizirana redukoija grafov posredovanje paketov Tabela 3. Razdelitev rattunalniSkih arhitektur. lastnin krmilnim takon. Gradnik, v kateren je kmilni tok prispel do ukaza JOIN n, se zaustavi vse dotlej, dokler se v n-1 gradnikih ne iztefia zadnji ead porojeniai kmilnini toko- vi. 6.1.3. Tok krntilnlh paketov posredovanie paketov na organizacl ii za Kroilno voden nodel ratiunanja s tokos krnilnih paketov pa je fioC realizirati na organizaciji za pasredovanje paketov. Arhitek- tura i«a zgradbo, kot jo prikazuje slika 11. Slika 11. Tok krnilnlh paketov na organizaciji za posredovanje paketov 6.1. Krmilnp vodene arhitekture 6.1.1. Zaporedni krailni tok na centralizirani oroanizaclii NajnaravnejSi kandidat za podporo zapored- nega krailnega toka je centralizirana organi- zacija stroja. Kroilni tok dolofia prograoski Stevec v procesorju, ki zaporedno naslavlja ukazs, ki so na vrsti za izvrSitev. Procesar takSne ukaze drugega za drugia, tj. zaporedno, izvrSuje. Ker ta zveza doloCa znano von Neuaannovo arhitekturo, je na tera oestu ne botno podrobneje opisovali. 6.1.2. SoKasni krroilni tok na organlzaciii za obravnavo izratov Sodasni krmilni tok, pri katerem uporablja- 00 ukaza FORK.in JOIN, podpira organizacija za obravnavo lzrazov. Zaparedni krnilni takovi, ki BB vrfiijo sofiasno, potekajo v razliCnih gradnikih te organizacije. Krmilnl tok, ki poteka v eneo gradniku, lahko porodi nov krailni tok v nekea drugem gradniku. Ko gradnik A prifine izvrSevati ukaz FORK i, sporo&i (preko koaunikacijske enote) tisteau gradniku B, v katerega poanilniku se nahaja ukaz z naslovom i, naj prifine z izvrSevanjem svojega programa pri taa ukazu. V prisec-u, ko v B !e poteka nek krailni tok, A odlozi izvrSitev operacije FORK i, dokler se krmilni tok v B ne lztette. Tedaj se lahko izvr^i ukaz FORK i, torej se prifine krmilni tok v B pri ukazu i, gradnik A pa lahko nadaljuje uvrSevanje, narekovano z Program se nahaja v poanilniSki enoti /meoory unit/. Enota za zbiranje /aatching unit/ hrani za vsak ukaz prograna: - nnoZico doslej zbranih krailnih paketav ukaza - naslov ukaza v po«nilni«ki enoti. Ko enota za zbiranje zbera vse potrebne krailne pakete danega ukaza, poilje njegov naslov preko vrste naslovov ukazov /instruction address pool/ v enoto za dostavo in vpis /fetch & update unit/. Ta snota prenese iz poanilnittke enote naslovljeni ukaz, razreSt reference ter sestavi ukazni paket. Le-ta vsebuje operacijo, vrsdnosti operandov ter naslove ukazov, ki prlbakujejo rezultat. Ukazni paket se preko vrste ukaznih paketov /executable instc-uctions pool/ prenesa v procesno enoto. Ko se ukaz izvrBi, se sestavijo podatkovni ter krmilni paketi. Podatkovni paketi nosijo rezultat ter naslov ukaza, ki tiaka nanj in se preko vrste podatkovnih paketov /data pool/ poSljejo v enoto za dostavo in vpis, ki razultat« vpitte v naslovljene lokacije poanilniSke enote. Krailni paketi pa se preko vrste krnilnih paketov /control token pool/ posrodujejo enoti za zbiranje. 6.2. Podatkovno vodene arhitekture 6.2.1. Tok podatkovnih oaketov na oroanizaciii ža posredovanie paketov Modal rafiunanja s tokon podatkovnih paketov obitfajno realizirano na organizaciji z> posredovanja paketov. Takfino arhitekturo iaenujeao podatkovno pretokovna arhitektura /data flaw archi tecture/. LotSiao dve vrsti podatkovno pretokovnih arhitektur: 27 - arhitektura s shranjevanjem paketov /token store/, - arhitektura 2 zbiranje« paketov /token •atching/. Prikazani sta na sliki 12 in sliki 13. 6.2.1.1. Podatkovno cretokovna shranievaniem paketov arhitektura s Projektii Podatkovno pretpkovno arhitekturo s shranjevanjem paketov so realizirali na MIT-ju pod vadstvo« J.B. Dennisa CDenn833. Druga realizacija te arhitekture je ODP (Ols- tributed Data Processor), izdelan v Tenas Instruments CCorn793. Zanioivo je, da podpira DDP programirni jezik Fortran 66. Omenioo Se francoski projekt LAU (Language a Assignation Unique), ki poteka v CERT laboratoriju, Toulou- se CCorat79, ComtBO]. POMNILNISKA ENOTA 6.2.1.2. Podatkovno pretokovna arhitektura—z. zbiranien paketov ENOTA ZA VPIS K VRSTA NASUV0»/\ | UKAZNIH I 1 —- . PAKETOV \J ENOTA ZA DOSTAVO PROCESNA ENOTA P, . . . Po VRSTA UKAZNIH PAKETOV Slika 12. Podatkovno pretokovna arhitektura s shranjevanjem paketov. PomnilniSka enota /me«ory unit/ vsebuje ukazne pakete, ki vsebujejo operacijo, prostare ZJ operande ter naslove na njegov rezultat CakajoCih ukaznih paketov. Enota za vpis /update unit/ hrani naslov vsakega ukaznega paketa ter Stevilo operandav, ki jih moca Se prejeti, da bo postal izvrSljiv. Pri tej arhitekturi se podatkovni paketi, ki jih sesta- vi procesna enota /processing unit/, posreduje- ja preko vrste s podatkovnimi paketi /data token pool/ v enoto za vpis. Vsak podatkovni paket vsebuje poleg rezultata tudi naslov CakajoCega ukaznega paketa v pomni.lni.5ki enoti. Enota za vpis shrani rezultat pnspelega podatkovnega paketa v Cakajofii ukazni paket v po»nilni*ki enoti ter zmanjSa Stevilo operan- dov, ki jih mora ta paket Se prejeti. fie enota za vpis ugotovi, da je ukazni paket prejel zadnjega izned potrebnih operandov, poSlje naslov paketa preko vrste naslavov ukaznih pjketov /instruction address pool/ enoti za dostavo /fetch unit/. Ta enota nato takoj pranese ukazni paket preka vrste ukaznih paketov /enecutable instruction pool/ v proces- no enoto, kjer se ukaz izvrSi. Podatkovni paksti, ki so rezultat izrSitve ukaza, se nato zopet posredujejo enoti za vpis. Opooba: lzvrSevanje, pri katerem enota ia dpstavo prenese izvrSljiv ukazni paket v procesno enoto takoj, ka iz enote za vpis prejme njegov naslov, imenujemo takojSnje izvrSevanje. S predhodno analizo programskega grafa pa lahko dabiao določeno informacija, ki slufi enoti za dostavo pri izbiranju in prenaSanju izvrSljivih paketov v procesno enoto. Enota za dostavo lahko tedaj poCaka s prenosoa r\a trenutek, ki je najbolj ugoden. S ten je lahko omogočeno izvrSevanje dosti 'veCjih' prograaov, ne da bi se minimalni morni Cas, potreben za njihovo izvrSevanje, podalj- fial. Oaenjena analiza je podrobno opisana v CRobi86a, Robi86b]. ENOTA ZA ZBIRANJE VRŠTA MN0ŽIČ7 PODATKOVNIH I PAKETOV PROCESNA ENOTA VRSTA UKAZNIH PAKETOV Slika 13. Podatkovno pretokovna arhitektura z zbiranjem pakstov Pri tej arhitekturi se podatkovni paketi, ki so prispeli iz procesne enote, ne shranijo neposredno v ukazni paket, katererau so naaenjeni. Naoesto tega se podatkovni paketi nalagajo v mnoiice, ki se nahajajo v enoti za zbiranje /matching unit/ paketov. Vsaka mnoXica je preko pridruzenega naslava prirejena ukazneou paketu, ki se nahaja v poanilniSki enoti /meaory unit/. Ko se nnoZica napolni (prejme zadnjl potrebni podatkovni paket), se preko vrste onoZic podatkovnih oaketov /token sats poot/ prenese v enoto za doetavo in vpis /fetch & updata unit/. Ta enota prenese iz poanilniSke enote kopijo naslovljenega ukaznega pakata, ga dopolnl s prispelo onol^ico podatkovnih paketov, ter ga preko vrste ukaznih paketov /executable instruction pool/ poSlje v procesno enoto /processing unit/. Tu se ukaz izvrfii, podatkovni paketi, ki so rezultati izvr«itve, pa se zopet prenesejo v enoto za zbiranje paketov. Opoobai Podobno kot v prejSnji arhitekturi, lahko tudi tu izvrSljive ukazne pakete zadrKu- jeao, le da v tea prioeru vrSi zadriievanje enota za zblranje. Projektii Realiziranih je vefl projektov, med katerioi onenimo Hanchester Data Flow Conputer, ki so ga izdelali pod vodstvon I. Uatsona in J.R. Gurda na univerzi v Manchestru CWats79, Gurd 83, Gurd85]. RazSirjena razliCica EXMAN (EXtended MANchester Data Flow Cooputer) je predlagana v CPatn863. Tretji projekt poteka na univerzl v Neucastlu, kjer gradijo rafiunal- nik JUMBO CTrel82o]. Ooenino fie Id (Irvin Data- flow Machine) projekt, zaBet na kalifornijski univerzl v Irvinu, kl se trenutno nadaljuje na MIT-Ju CArviBOD in ga vodi Arvind. 28 6.2.2. Tok podatfcovnih paketov na organizaci.ii za obravnavo izrazov 6.3.2. Redukciia arafov na organizaciii obravnavo izrazov Tok podatkovnih paketov je aoC realizir«- ti tudi na organizaciji za obravnavo izrazov. Ko procesor v nekem gradniku prejme podatkovni paket preko komunikacijske enote iz drugega gradnika, vstavi vrednost, ki jo nosi paket v ukaz, kateremu je namenjena. V naslednjem koraku procesor ugotovi, de je ukaz izvrSljiv, ter ga v tera primeru izvrSi ter poSlje podatkovni paket, v katerem se nahaja rezultat, Dreko koaunikacijske enote tistemu gradniku. v katerea se nahaja ukaz, ki ta rezultat priCaku- je. Ce pa ukaz Se ni izvrSljiv, se procesor povrne v stanje Cakanja. Projektis Oata-Oriven Machine »1 ]. Pojavljajo se tudi komp leksnejSe arganizacije stroja. Kot llustracijo navedino le dva najnovejSa podatkavno pretokovna caču- nalnika: SI6HA-1 CShi«86] in veCprocesorski podatkovno pretokovm sistem na osnovi proce- sorjev JJPO7281 CJelf85, Silc863. V obeh pri- nerih gre za organizacijo stroja, ki je podobna organizaciji za obravnavo izrazov, le da so gradniki podatkovno pretakovni procesorji, katerih organizacija temelji na posredovanju paketov. RaCunalni^ke arhitekture je mofl razdeliti tudi z dveh drugih, dia»etralnih zornih kotov: z vidika jezikov oziroma strojne opreme. Tako obstaja razdelitev novejSih radunalni- Skih arhitektur, temeljeCih na visokih programirnih jezikih /high level language computer architectures/. TakSna cazdelitev je podana v ChiluS6D in ja prikazuje slika 1A. Ceprav ni nanen Clanka predstdvitev tak^ne razdelitve arhitektuc, pa vendarle omenimo sku- pino reduciranih arhitektuc, itied katere sodijo IBM 801, RISC et ooaputer/, 7 sklad /staok/, 6.3.4 - konflni /sink •/, 6.3.4 - vnesni /intermediate •/, 6.3.4 - zaCetni /souroe •/, 6.3.4 sklic /reference/, 4.S paket /token/ - krailni /cantrol •/, 6.1.3 - podatkovni /data */, 4.4, 6.1.3, 6.2.1.1, 6.2.1.2, 6.2.2 - ukazni /instruction */, 6.1.3, 6.2.1.1, 6.2.1.2 - z rszultaton /result t/, 4.4, 6.3.3 - z zahtevo /demand •/, 6.3.3 pravilna struktura /regular structure/, 5.3 - vektorska /array */, 5.3 - drevesna /tree t/, 5.3 pravilo /rule/ - izvrSitve /(iring */, 3 - o enkratni prireditvi /single as5ignement »/, 4.5 tok /flow/ - krmilni /oontol «/, 4 - s krailniai paketi /*• with control tokans/, 4, 4.3 - sofiisni /parallel •*/, 4, 4.2 - zaporedni /seqjential *t/, 4, 4.1 - podatkovnih paketov /data •/, 4, 4.4 U uporaba (unkcljs /function aplication/, 4.5 V vrsta /pool ol uork/, 5.2 - krmilnih paketov /control token */, 6.1.3 - ranoilo podatkovnih paketov /token sets «/, 6.2.1.2 - naslovov ukazov /instruction address «/, 6.1.3, 6.2.1.1 31 - podatkovnih paketov /data token */, 6.1.3 6.2.1.1, 6.2.1.2 - ukaznih paketov /enecutable instruction */, 6.1.3, 6.2.1.1., 6.2.1.2 Pnpis: Pn prevajanju angleSkih izrazov sva nekajkrat ubrala nekoliko svobodnejSo pot, predvse« takrat, ko bi dobesedni prevod slabo opisoval dotittni predmet. Upava, da sva ioiela pri lzbiri slovenskih izrazov sreBno roko. L ± CArvi803 Arvind, Kathail V., Pingali K. "A Processing Element for a Large Multiprocessar Datallow Machine", Proc. Int'l. Conf . Circuits and Conputers, New York, Oct. 198Q. CBack783 Backus J. "Can prograrcning be libera- ted froa the von Neumann style? A functional style and its algebra of pragramms", Camm. ACM Vol.21, No.8, Aug. 1978, pp.613-641. CBerk713 Berkling K.J. "A computing machine based an tree structure", IEEE Trans. Computer, Vol.C-20, Na.4, Jan. 1971, pp.404-418. CBish863 Bishop P. Fifth 5eneration Computers, Concepts, imp lementations and uses, Ellis Horuood, 1986. CBrajB63 Brajak P. "Paralelno procesiranje: arhitektura 90-tih godina, Zbornik jugoslaven- skog savjetovanja o novin generacijana raCuna- la, MIPRO 86, Rijeka, Maj 1986, str.33-46. CCorn793 Cornish M. "The TI Data Flou Archite- ctures: The Pouer of Concurrency for Avionics", Proc. 3rd Canf. Oigital Avionics S/stems, Fort Uorth, Texas, Nov. 79, pp.19-25. CComt79] Coote 0., Hifdi N. "LAU Mul tipi-oces- sor: Microiunctional Oescription and Technalo- gical Choices", Proc. 1st European Conf. Parallel and Distributed Processing, Toulause, France, Feb. 1979, pp.8-15. CCoatSCn Comte D., Hifdi N., Syre J.C. "The D*ta Drlven LAU Multiprocessor System: Results and Perspectives", Proc. IFIP 80 Cangress, Oct. 1980. CDavi78D Oavis A.L. "The Architeoture and System Method of DDM1: A Recursively Struotured Oata Driven Machine", Proc. Sth Ann. Symp. Conp. Arch., Palo Alto, Calif., April 3-5, 1978, pp.210-215. C0avi823 Davis A.L., Keller R.M. "Data Flou Prograo Graphs", Computer, Vol.15, No.2, Feb. 1982, pp.26-*l. CDarlBID Darlmg J., Reeve n. "ALICE: A Multi- processor Reduction Machine lor the Parallel Evaluation of Applicative Languages", Prac. Int'1 Sy»p. Functional Programming Languages and Computer Architecture, June 1981, Gotebacg, Sweden, pp.32-62. CDenn7*] 0ennis,J.B., Misunas.D.P. "A Computer Architecture for highly parallel signal pi-aces- sing", Proc.197A Nat. Coraputer Conl., AFIPS Press, Arlington, Va.,1974,pp.402-409. CDenn833 Dennis J.B., Lim W.Y-P., Ackerman U.B. "The HIT Data Flow Engineering Model", Informatian Pracessing 83, R.E.A. liason (ed.?, Elsevier Scince Publishers B.V.