46 SINHRONIZIRANA PODATKOVNO PRETOKOVNA INFORMATICA 3/92 RAČUNALNIŠKA ARHITEKTURA II Jurij Šile Laboratorij za računalniške arhitekture Inštitut Jožef Stefan, Ljubljana Keywords: parallel processing, dataflow Ludvik Gyergyek computing, scheduling, allocator, performance Fakulteta za elektrotehniko in računalništvo, evaluation, parallel computer architecture Ljubljana Delo obravnava problem časovne optimizacije asinhronega procesiranja na omejenem številu procesorjev. Predlagamo izvirno rešitev, ki temelji na uvedbi nekaterih mehanizmov sinhronizacije v asinhrono računanje. Graf pretoka podatkov, ki opisuje asinhrono procesiranje, opremimo s časovno optimalno sprožitveno funkcijo, ki služi tako pri vlaganju grafa v računalnik, kakor tudi pri njegovem časovno optimalnejšem izvrševanju. V ta namen smo razvili hevristična algoritma pOptSinh in TOptSinh za konstrukcijo optimalnih sprožitvenih funkcij, ki po pesimistični oceni vračata optimalno rešitev v 80% primerov. Nadalje predlagamo algoritma za dodeljevanje MinGlDol in MinGIGor, ki temeljita na optimizaciji medprocesorskih komunikacij. V primerjavi z znanimi razvrščevalnimi algoritmi dobimo s predlaganima algoritmoma boljše rezultate, kar potrjujejo analizirani primeri algoritmov za izračun hitre Fourierjeve transformacije, dinamične analize scene in LU razcepa matrike. Končno podajamo tudi zasnovo hibridne vzporedne arhitekture računalnika, ki podpira predlagano preoblikovanje asinhronega računanja. SYNCHRONOUS DATAFLOW COMPUTER ARCHITECTURE - We discuss the problem of time optimization of asynchronous processing on a limited number of processors. We present an original solution to the problem based on introduction of synchronization mechanisms into asynchronous processing. The dataflow graph describing asynchronous processing is associated with the corresponding time-optimal firing function. This function is used both for loading a dataflow graph into the computer and for time-optimal graph execution. In order to do this, we have developed two heuristic algorithms, pOptSinh and TOptSinh, which are used for optimal firing function construction. According to conservative estimates, these algorithms return optimal functions with 80% probability. Furthermore, we propose two scheduling algorithms, MinGlDol and MinGlGor, which are based on interprocessor communication minimization. These two algorithms give better results compared to some other well known scheduling algorithms. This fact is illustrated in Fast Fourier Transformation, Dynamic Scene Analysis, and LU matrix decomposition algorithms. Finally, \v„ present a design of hybrid parallel computer architecture capable of supporting modified asynchronous computing. 1. Asinhrono računanje V nadaljevanju bomo opisali način asinhronega računanja, ki ga bomo opisali s pomočjo GPP. Formalizirali bomo problema minimizacije časa oziroma procesorjev. Uvedli bomo pojem sprožitvene funkcije, ki nam bo v nadaljevanju omogočil vpeljati nekatere mehanizme sinhronizacije v asinhrono računanje. 1.1 Graf pretoka podatkov Graf G, ki ga sestavljata množici točk V in povezav £ C V X V, označimo z G{V,€). Število točk in povezav označimo z n = |V| oziroma m = |£|. Kadar je (u, v) 6 £, pravimo, da je točka v neposredni naslednik točke u, in to označimo z u i—► v. Kadar obstaja vsaj ena usmerjena pot iz točke u do točke v, pa pravimo, da je v naslednik točke u, kar označimo z u v. Relacija i—► je tranzitivna ovojnica relacije i—k Graf G je 47 acikličen, če ne vsebuje točke v z lastnostjo v v. Če je G acikličen, je i—> relacija stroge delne urejenosti v V, saj je irefleksivna, asimetrična in tran-zitivna. Vhodnja stopnja d+(v) točke v je število povezav, ki se stekajo v v, izhodnja stopnja d"(v) točke u pa je število povezav, ki točko v zapuščajo. Pravimo, daje G enostaven, če obstaja.med dvema točkama največ ena povezava v isti smeri. Naj bo G(V,£) acikličen. Tedaj zapišemo V kot: V = VZ UVWU VK. Vz, Vj\rin Vk se imenujejo množica začetnih, notranjih oziroma končnih točk. Velja naslednje: VveVz : d+(v) = 0Ad~(v) > 0, Vv£VN : d+(v) > 0 A d~(v) > 0, Vu G VK ■ d+(v) > 0 A d~(v) = 0. Če sta Vz in Vk končni, neprazni in nevezani množici, potem v G ni nobene izolirane točke. V nadaljevanju bomo obravnavali le grafe pretoka podatkov GPP, ki so v skladu s sledečo definicijo: Definicija: Par (G(V,£),t) je graf pretoka podatkov, če velja: (a) G je usmerjen, enostaven in acikličen; (b) Vz n Vtf = 0; (c) t : V —> IN. □ Če je v G V, pomeni t(v) čas izvrševanja točki v pridružene operacije1. 1.2 Najkrajši čas izvrševanja Naj bodo dani GPP = (G,t) ter točki u in v. Če velja u v, obstaja iz točke « do d vsaj ena pot p = u>2, ■ ■ ■, Wk, kjer je wi = u ter Wk = v. Tedaj definiramo dolžino poti p kot Kp) — SLi Kw*)- Dolžino najdaljše poti iz točke u v točko v pa označimo z i(u, v). Pot iz množice točk U v množico točk VV je vsaka pot, ki se prične v eni od točk množice U in se konča v eni od točk množice W. Dolžino najdaljše poti med množicama U in W pa označimo z i(U, VV). Če vsebuje kaka od množic U ali VV en sam element, pišemo namesto množice kar sam element; na primer, če je U = {u}, pišemo kar ¿(u, VV). 1 Operacij posebej ne navajamo, ker za samo analizo niso pomembne. Seveda je. 1{Vz,Vk) najkrajši možni čas, v katerem se še more izvršiti GPP. Označimo ga s Too, ker se GPP izvrši v najkrajšem možnem času le ob zadosti velikem (praktično "neskončnem") številu procesorjev. Če je na voljo le en procesor (zaporedno izvrševanje), pa označimo najkrajši možni čas za izvršitev GPP s T\. Seveda velja Ti = ZveVt(v). 1.3 Sprožitvena funkcija Naj bodo dani GPP = (G, t), naravno število T > Too ter funkcija s : V —► {0,1,.. .T}. Če je v G V, pišemo f(v) = s(i>) + t(v). Definicija: Funkcijo s imenujemo sprožitvena funkcija, če velja: (a) f(v) v => f(u) < s(v), Vu, u G V. □ Sprožitvena funkcija s priredi vsaki točki v trenutek sprožitve s(v), v katerem točka v zajame vhodne podatke in prične izvrševanje pridružene operacije. Posredno je s tem natanko določen tudi trenutek izstrelitve f(v), v katerem točka v konča svoje izvrševanje in pošlje podatke vsem neposrednim naslednikom. Zgornja definicija zagotavlja, da vsaka točka izstreli svoje rezultate pred trenutkom T; poleg tega pa proženje ter izstre-ljevanje spoštujeta relacijo i—Za dani GPP v splošnem obstaja več različnih sprožitvenih funkcij. Množico vseh sprožitvenih funkcij danega GPP označimo z S (T). Vsaka s G S (T) porodi pravilo, po katerem poteka računanje GPP. Kadar bomo želeli to pravilo posebej poudariti, bomo k oznaki s dodali ustrezni indeks. Sprožitveno funkcijo s imenujemo požrešna, če velja s(v) = l(Vz,v) — t(v), za vsak u G V, oziroma lena, če velja s(u) = T - l(v, Va-), za vsak v G V. Požrešno2 sprožitveno funkcijo bomo .označili s se, leno3 pa s si. Prva opisuje podatkovno vodeno računanje, druga pa računanje vodeno z zahtevo. 2 Požrešno iz angl. "eager". 3Leno iz angl. "lazy". 48 1.4 Kritične točke Naj bo dan GPP = (G, t). Poti z dolžino i{Vz, VK) so najdaljše poti v GPP. Definicija: Točko v imenujemo kritična, kadar se nahaja na kaki od najdaljših poti v GPP. Če je 0 < r < č(Vz,Vk.), imenujemo točko v kritična na globini t, kadar je kritična in velja £(Vz, v) — t(v) = t. □ Množico kritičnih točk označimo s IC, množico kritičnih na globini r pa s JC(t). Kritičnost je torej značilnost GPP samega, saj je moč enostavno pokazati, da je kritična natanko tista točka v £ V, za katero velja t(Vz, v) - t(v) = i{Vz, VK) - t(v, VK). V posebnem primeru smemo kritičnost točk opredeliti tudi z vidika sprožitvenih funkcij. Naj bo dan čas izvrševanja T. Opazimo, da je levi del zgornje enačbe enak se(t;). Desni del pa je enak ¿¡(v), vendar le, če je T = T^l V tem primeru je kritični točki možno prirediti le en in en sam trenutek za njeno sprožitev, neodvisno od izbrane sprožitvene funkcije s £ Too ter sprožitvena funkcija s £ S(T). Kadar je r £ {0,1,..., T}, definiramo PT,s(t) = {v e V I a(t>) r2jl -Ti I V nadaljevanju bomo to oceno označevali s pt^^fb-Računanje PTe^FB zajema obravnavo roo(Tco-)-l)/2 intervalov [rj,^], kar pomeni, da je časovna zahtevnost reda O(T^). Vidimo, da ima računanje PToo.FB relativno veliko časovno zahtevnost, zato si bomo v nadaljevnaju ogledali še nekatere manj natančne toda hitrejše metode za izračun pr«,- Chen - Epleyeva ocena. V [2]4 je vpeljana ocena za PToo» ki temelji na povprečni vzporednosti Soo = 4To oceno je dejansko prvi vpeljal McNaughton v [3] 49 rp j± in se glasi PToo = l^oo] • To oceno bomo označevali s pr^^E- Hujeva ocena. Hu je v [4] vpeljal oceno za p?^ na sledeč način. Naj bo £(t) = {»eV | fi(v) = r}, torej množica vseh točk, ki se morajo izstreliti najkasneje v trenutku r. Potem je w pT°° = n^r 7 S I I " 0 i—' r=1 Hujevo oceno bomo označevali s pr«,,// in jo imenovali tudi največja povprečna vzporednost. Ramamoorthy - Chandy - Gonzalezova ocena. Ramamoorthy et al. - so v [5] izboljšali PToo,H tako, da so upoštevali tudi kritično vzporednost, ki je vpeljana kot k = max I /C(t) I . 0 saJ se P" relativno velikih grafih njen vpliv izniči. Takrat postane pr^.R ~ PToo,//- Eden od načinov za izboljšanje natančnosti ocene je torej izostritev kritične vzporednosti k, kar bomo storili v nadaljevanju. Predpostavimo, da je v vseh trenutkih r intervala [ri,72] v vsaki množici /C(r) po k elementov. Zgodi se, da se mora v [t\ , r2] poleg kritičnih izvrševati tudi katera od nekritičnih točk. Kadar obstaja vsaj ena taka točka, potrebujemo dodatni procesni element, torej je potrebnih k + 1 procesorjev! Do podobne situacije pa seveda pogosto pride tudi v intervalih, kjer je število kritičnih točk sicer manjše od k, vendar se mora znotraj tega intervala (delno) izvrševati toliko nekritičnih točk, da skupno število potrebnih procesorjev preseže k. V nadaljevanju bomo zato vpeljali razširjeno kritično vzporednost k' in jo uporabili pri lastni oceni za px[6]. Na končnem intervalu [0,Too] poiščimo najmanjše končno zaporedje trenutkov 0 = tq < ti < ... < Tk = Too, in sicer takšno, da je na vsakem intervalu [rj_i, rj), j = 1,2,...,/; število kritičnih točk I /C(r) I stalno. To število krajše označimo s 1. Definirajmo množico Wj_i tistih nekritičnih točk, ki zahtevajo v intervalu [Tj-i,Tj) procesor vsaj za en trenutek: Wj-i = { veV-IC I (se(v) > Tj_i V fe(v) > Tj-i > 3e(v)) A (h(v) < r, V ft(v) > r-j > st(v))}. Izrševanje točke v € Wj_ 1 se časovno prekriva (v vsaj enem trenutku) z izvrševanjem kritičnih točk v časovnem intervalu [rj-i,Tj). To prekrivanje je v splošnem krajše od časa t(v), kajti točka se lahko sproži že pred trenutkom Tj_i in/ali konča izvrševanje po trenutku Tj. Zato upoštevamo pri izračunu skupnega prekrivanja v intervalu [rj_ 1, Tj) za vsako točko v G VVj-i le njeno minimalno prekrivanje cjj- 1(v), ki je Uj-l{v) = min{/e(u) - Tj-I, Tj - Sl(v), t(v)} Minimalno potrebno število dodatnih procesnih elementov v časovnem intervalu [t.,-1 , Tj) je tako: Vi =( £ ^-iM)/ \eWj_i ' max{r,_i, min se(t;)} — min{r;, max fi(v)}. «evvj.j v€Wj_i Končno je mogoče zapisati razširjeno kritično vzporednost k! kot k' = max [i/ij -f 1 Too, za katero je množica sprožitvenih funkcij 2. Mehanizmi sinhronizacije S(TP) ^ 0. Posledica pomanjkanja procesorjev je podaljšanje časa izvrševanja ATp, ki znaša A Ti Sprožitvene funkcije, ki minimizirajo zgornji izraz imenujemo časovno optimalne sprožitvene funkcije - krajše T-optimalne. Iskanje T-optimalnih Sedaj bomo opisali hevristična algoritma za konstrukcijo T- in p-optimalnih sprožitvenih funkcij, ki ju bomo uporabili v dveh hevrističnih algoritmih za dodeljevanje; z njima dani GPP porazdelimo med procesorje [9]. 51 vhod: GPP, p. izhod: SGPP(p,Tp), oz. s(u), za vsak v G V. r := 0; Tp := 0; q := 0; W := V repeat if q > 0 then V, := {v e V\f(v) = r}; W := W - Vp; 9 := g - |VP| endif V, := {v G V|t> ima vse vhodne podatke}; — Množica izvršljivih točk je V,- = /C(r) U Vn, kjer sta /C(r) in Vn — množici kritičnih oz. nekritičnih točk na globini r. if q < p then if p — q < |/C(r)| then bodi Vd C IC(t), kjer je |Vd| < p — q else if p - q > | V,-| then Vd := V; else Bodi Vd C Vn, kjer je |Vd| < p - q - |£(r)|; Vd := Vd U IC{t) endif q := q + |Vd| J— Sproži se nekaj dodatnih, naključno izbranih točk. endif forall v G Vd do s(v) := r endforall Tp := r; r := r + 1 until W = 0; Algoritem TOptSinh: Konstruiranje T-optimalne sprožitvene funkcije. 2.1 Sinhronizacija Algoritma za konstrukcijo optimalnih sprožitvenih funkcij, kiju bomo opisali v tem poglavju, temeljita na spoznanju, da si moremo izvrševanje GPP predočiti s pomočjo prehajanja točk iz ene množice (stanja) v drugo. Že v prej smo vpeljali eno takšnih množic - množico IC(t) kritičnih točk v trenutku r. Nadalje za vsak trenutek r vpeljemo še množici: V,-izvršljivih točk, tj. točk, ki so zbrale vse vhodne podatke, a se še niso sprožile in Vp = {v G V| f(v) = r} pozabljenih točk, tj. točk, ki so se izstrelile v tem trenutku. V splošnem so poleg kritičnih v množici V,- tudi točke, ki smejo svojo sprožitev odložiti, ne da bi to nujno vplivalo na najkrajše izvrševanje GPP. Te točke imenujemo nekritične v trenutku r in jih zberemo v množico Vn. Par {GPP, s), kjer je s sprožitvena funkcija, ki posredno določa tudi p in T, imenujemo sinhro-nizirani graf pretoka podatkov ter ga označimo z SGPP(p,T). Torej T-optimalna sprožitvena funkcija določa SGPP(p,Tp), medtem ko p-optimalna funkcija določa SGPP(pr00,T). 2.1.1 T-optimalna sprožitvena funkcija Za konstruiranje T-optimalne sprožitvene funkcije smo razvili algoritem, ki smo ga imenovali TOptSinh. Ta nam za dani GPP ter vnaprej določeno število p procesorjev vrne takšno sprožitveno funkcijo 5, ki zagotavlja čas izvrševanja Tp, ki je kar se da blizu oceni Tp. Kvaliteto algoritma smo ocenjevali z odstotkom primerov, ko je čas Tp dosegel oceno TPih, saj natančne vrednosti Tp ne poznamo. Algoritem je bil preverjen6 nad 500 GPP in je v 75.6 % dosegel Tp = TptH- Obenem smo merili tudi upad idealne popospešitve Dp v odvisnosti od pomanjkanja procesorjev. Primerjava med asinhronim podatkovno vodenim računanjem (sprožitvena funkcija se) in sinhroniziranim podatkovno vodenim računanjem (T-optimalna sprožitvena funkcija) je prikazana v tabeli 4, kjer so podani povprečni rezulati. Ključni del algoritma TOptSinh je v konstruiranju množice Vj, tj. v sprožanju dodatnih izvršljivih točk, kadar so na voljo prosti procesorji. Absolutno prednost pri sprožanju imajo kritične točke v danem trenutku (zaradi omejenega števila procesorjev seveda v splošnem pride do odloga sprožitve celo pri nekaterih kritičnih točkah). Uvrščanje nekritične točk v množico Vd pa smo izvajali v skladu z naslednjimi strategijami: naključno izbiranje (v vrstnem redu, kot prihajajo 12 V ta namem smo uporabili računalnik IBM PC in razvili ustrezna programska orodja. 52 vhod: GPP,T0G. izhod: 5GPP(pr00,roo), oz. za vsak v e V. Izračunaj pr^; r := 0; pToo : = 0; q := 0 repeat if ^ > 0 then Vp:={t>eF|/(*) = r}; g:=g-|Vp| endif V,- := {v G V|t> ima vse vhodne podatke); — Množica izvršljivih točk je V,- = fC(r) U V„, kjer sta /C(r) in Vn — množici kritičnih oz. nekritičnih točk na globini r. q := q + |£(r)| — Sprožijo se vse kritične točke, if q < pToo then Bodi Vd C Vn, kjer je | < pr«, - q; q := q + |Vd| — Sproži se nekaj dodatnih, naključno izbranih točk. endif forall v G K.{r) U Vd do := r endforall PToo := max(g,pToo); r := r + 1 until r = T,»; Algoritem pOptSinh: Konstruiranje p-optimalne sprožitvene funkcije. PToo p = 3/4prm | p = 1/2pro» | p = 1/4pt«, Sprožitvena funkcija se 4 0.030 0.223 1.232 5 0.016 0.121 0.454 6 0.006 0.205 0.621 7 0.004 0.104 0.761 8 0.015 0.147 0.883 9 0.006 0.071 0.397 10 0.003 0.100 0.464 E 0.011 0.139 0.687 T-optimalna sprožitvena funkcija 4 0.011 0.211 1.079 5 0.002 0.048 0.375 6 0.002 0.117 0.537 7 0.000 0.029 0.718 8 0.000 0.044 0.789 9 0.000 0.001 0.324 10 0.000 0.018 0.311 E 0.002 0.067 0.590 Tabela 4: Upad idealne pospešitve Dp. v V,-), po naraščajočih t(v) in po padajočih t(v). Poskusi so pokazali, da nobena od strategij ni bila izrazito boljša od ostalih. 2.1.2 p-optimalna sprožitvena funkcija Algoritem pOptSinh za dani GPP ter pripadajoči najkrajši čas izvrševanja T^ vrne sprožitveno funkcijo s, ki zagotavlja izvrševanje GPP na številu procesorjev, ki je kar se da blizu ocene Pt^- Algoritem v vsakem trenutku r poskuša sprožiti čimveč, toda kvečjemu izvršljivih točk. V vsakem trenutku r sprožimo vse točke iz IC(t). Če je zasedenih procesorjev še vedno manj kot Pt ♦ O O o O 0 O o -e—©~ o ... sprožitvena funkcija sE • ... p-optimalna sprožitvena funkcija J_i_1_i_I_i_I_i_l_i_l_L_ 0 20 40 60 80 100 120 Število točk n Slika 1: Izkoriščenost procesorjev Ep. PToo P1-i s = p-optimalna 6l ( 1 0 ' I 0 ( O 1 0 J_l_L 0 2 4 6 8 .10 PTCo pn s = se Slika 2: Potrebe po procesorjih. 1 prikazuje izkoriščenost procesorjev Ep v odvisnosti od velikosti GPP za asinhro podatkovno vodeno računanje (sprožitvena funkcija se) in sinhronizirano podatkovno vodeno računanje (p-optimalna sprožitvena funkcija). Računanje, ki sledi p-optimalni sprožitveni funkciji, ima mnogo manjše zahteve po procesorjih kot računanje, ki sledi se sprožitveni funkciji, kar potrjujejo rezultati, prikazani na sliki 2. Tudi tu smo analizirali 1.500 GPP, pri čemer smo spreminjali število točk n < 120 in čas njihovega izvrševanja t(v) < 10. 2.2 Dodeljevanje Po končani fazi sinhroniziranja je GPP pridružena sprožitvena funkcija s in skupaj tvorita SGPP(p,T). S tem so vse t; £ V urejene po trenutkih sprožitve s(v). Takšna urejenost zagotavlja, da se GPP izvrši na p procesorjih v času T ob uporabi najsplošnejšega algoritma za dodelje- vanje (algoritem NakljDod) [7], ki točko v dodeli naključno izbranemu prostemu procesorju. • vhod: SGPP(p,T). izhod: 7r(t>), za vsak v £ V. Razvrsti pare (u,5(u)) po naraščajočih s(u) in jih shrani v sklad S. for q := 1 to p do F[q\ := 0 endfor repeat Vzemi iz S vse pare z enakim 5 in jih shrani v W. P {q\ ^[9] < 5} forall v € >V do Naključno izberi q £ P. %(v):= q; F[q) := /(«); P := P - {q} endforall W := 0; P := 0 until 5 = 0; Algoritem NakljDod: Naključno dodeljevanje. Po končanem dodeljevanju je vsaki točki v £ V pridružen procesor z indeksom 7r(v), kjer je 1 < w(v) < p. V vsakem trenutku je na voljo vsaj toliko prostih procesorjev, kot je točk, ki se morajo tedaj sprožiti. Dodeljevanje teh točk je poljubno, kar pomeni, da moremo v splošnem dani SGPP(p,T) porazdeliti na več načinov. Vse dodelitve so enakovredne, saj vse zagotavljajo, da se GPP izvrši na p procesorjih v času T. Točki a in » iz V sta ločeni, če sta dodeljeni različnima procesorjema. Povezavo med ločenima točkama imenujemo globalna povezava. V primeru hibridne arhitekture poteka komunikacija med ločenima točkama preko nadzorno-povezovalne enote in v splošnem zahteva čas tc > 0. V takšnem primeru najsplošnejši algoritem torej ne vrača več enakovrednih dodelitev, saj se število globalnih povezav spreminja. Že prej smo videli, da število globalnih povezav vpliva na čas izvrševanja GPP. Zato se bomo osredotočili na konstruiranje takšnih algoritmov za dodeljevanje, ki bodo mini-mizirali število globalnih povezav v dodelitvah [8]. Točneje: trivialni kriterij naključnega dodeljevanja prostih procesorjev bomo nadomestili s kompleksnejšim, ki se glasi: Dodeli točke w množice W procesorjem q množice P tako, da bo ^ c(u>, q) maksimalna, kjer je c(w, q) število sosednjih točk točke w, ki so bile doslej dodeljene procesorju q. 54 vhod: SGPP(p,T). izhod: 7r(v), za vsak v £ V. Razvrsti pare (u,s(i;)) po naraščajočih s(v) in jih shrani v sklad S. for q := 1 to p do := 0 endfor repeat Vzemi iz S vse pare z enakim s in jih shrani v W. P :={q | F[q) < forall v £ W do forall q£ P do c(v,q) = število neposrednih predhodnikov od v, ki so bili dodeljeni v g-ti procesor, endforall endforall Reši problem WBM za graf (VV U P, W X P). forall pare (v,q), ki so del rešitve do tt(v) := q\ := f(v) endforall := 0; P := 0 until S = 0; Algoritem MinGlDol: Minimizacija globalnih povezav (navzdol). Dodeljevanje, ki poteka v skladu z zgornjim pravilom, je v nekem smislu konservativno, saj poskuša točko pridružiti procesorju, v katerem je največ njenih sosedov. Opisano pravilo je primer znanega problema uteženega dvodelnega ujemanja (WBM8) [10, 11]: Naj bo dan dvodelni graf G = (W U P,E), kjer je E C W x P ter cenovna funkcija c : E —► IN. Iščemo ujemanje MCE (množico povezav M, v kateri noben par povezav nima skupne točke) tako, da Je £(tu,q)€Mc(w>Q) maksimalna. Problem WBM znamo rešiti v času č?(nelog n/ max(l,log kjer je e = | E | in n =| W | + | P | . V algoritmu MinGlDol poteka dodeljevanje od začetnih točk proti končnim, medtem ko poteka dodeljevanje v algoritmu MinGIGor v nasprotni smeri. V obeh algoritmih se pojavlja problem WBM, pri čemer v prvem primeru določajo ceno c(w, q) neposredni predhodniki točke w, v drugem pa njeni neposredni nasledniki. 2.3 Primeri Z nekaterimi primeri bomo pokazali učinkovi- 8 Weighted Bipartite Matching tost časovne optimizacije asinhronega računanja s pomočjo mehanizmov sinhronizacije. Obravnavali bomo naslednje primere: hitro Fourierjevo transformacijo (FFT), dinamično analizo scene (DAS) in LU razcep matrike (LU). Privzeli bomo hibridno arhitekturo s p = 3 procesorji (P\,P2 in P3), katere medprocesorsko komunikacijo tc bomo ustrezno spreminjali. Kvaliteto naših rezultatov, ki jih dobimo z uporabo sinhronizacijskega algoritma TOptSinh ter dodeljevalnih algoritmov MinGlDol in MinGIGor, bomo primerjali z naslednjimi znanimi razvrščevalnimi algoritmi: CPM9 [12], HNF10 [13] in WLn [13]. 2.3.1 FFT: Hitra Fourierjeva transformacija Povrnimo se na primer izračuna hitre Fourierjeve transformacije na 8 točkah, ki smo ga že obravnavali v prvem delu. Predpostavimo, da se točke A, C, E, G, I, J, M, N, Q, R, S in T izvršujejo eno časovno enoto, točke B, D, F, H, K, L, O, P, U, V, W in X pa pet časovnih enot. CPM, HNF in WL algoritmi. Za primer FFT algoritma dajejo vse tri metode (CPM, HNF, WL) 9 Critical Path Method 10 Heavy Node First "Weighted Length 55 vhod: SGPP(p,T). izhod: za vsak v € V. Razvrsti pare (t>,s(t>)) po padajočih s(v) in jih shrani v sklad S. for q := 1 to p do := T endfor repeat Vzemi iz S vse pare z enakim / in jih shrani v W. P-= Uim >7); forall v 6 W do forall q 6 P do = število neposrednih naslednikov od v, ki so bili dodeljeni v g-ti procesor, endforall endforall Reši problem WBM za graf (WU?,WxP). forall pare (v,q), ki so del rešitve do 7r(u) := q F[q} ':= s(v); endforall VV := 0; P:= 0; until 5 = 0 Algoritem MinGIGor: Minimizacija globalnih povezav (navzgor). Pi i—T P? i D" P3 I—F -LIL IT1RIQI "ETeT ■ K ' _hj IEEE inijm 10 15 20 25 30 35 v v v A 6 1 15 Q 23 B 5 J 13 R 22 C 5 K 12 S 22 D 0 L 10 T 21 E 6 M 14 U 16 F 0 N 12 V 15 G 5 O 7 W 20 H 0 P 7 X 17 Slika 3: FFT: Razvrstitev po CPM, HNF in WL. enakovredne rezultate. Točke se dodelijo procesorjem, kot je prikazano na sliki 3. Razvidno je, da dobimo v tem primeru 22 globalnih povezav. Upad idealne pospešitve Dp se pri tc > 0 poveča, tako dobimo pri tc = 10 čas izvrševanja Tp — 43, kar se odraža tudi v povečanju upada idealne pospešitve Dp = 1.87. Podrobnejši rezultati CPM, HNF in WL dodeljevanja v odvisnosti od časa tc so prikazani v tabeli 6. tc TP Sp Ep Dp 0 2 4 10 25 27 31 43 2.88 2.67 2.32 1.67 0.96 0.89 0.77 0.56 0.67 0.80 1.07 1.87 Tabela 6: FFT: CPM, HNF in WL dodeljevanje pri različnih tc. MinGlDol in MinGIGor algoritma. GPP FFT Tabela 7: FFT: T-optimalna sprožitvena funkcija. algoritma najprej sinhroniziramo, za kar uporabimo algoritem TOptSinh, ki vrne T-optimalno sprožitveno funkcijo. Rezultat je prikazan v tabeli 7. 1 H 1 B 1 L III U h-lRßl 1 D IGIEI O INI J MI V 1 W 1 1 F ICIAI P 1 K 1 X ISI : i_■ ■_i_i_i_i_ 0 5 10 15 20 25 • 30 35 Slika 4: FFT: Razvrstitev po MinGlDol. V drugem koraku uporabimo dodeljevalni algoritem MinGlDol oz. MinGIGor. Razvrstitev točk po MinGlDol algoritmu je prikazan na sliki 4, medtem ko je razvrstitev po MinGIGor algoritmu prikazana na sliki 5. 56 p\ I H IGIEI O INI J Ml V I W ~| r\ I F ICIAI P I K I X klgl j p3 I D I B I L lil U iTlsl | i-1-1-1-1-i-1—-V- 0 5 10 15 20 25 30 35 Slika 5: FFT: Razvrstitev po MinGIGor. Z uporabo algoritmov MinGlDol in MinGIGor dobimo pri tc = 0 enake rezultate kot pri algoritmih CPM, HNF in WL (Tp = 25, Sp = 2.88, Dp = 0.667 in Ep = 0.96). Pri tc > 0 pa naša algoritma vračata rezultate z manjšim upadom idealne pospešitve Dp. Tako je pri tc = 10 čas izvrševanja Tp = 40 (v prejšnjem primeru 43), kar pomeni, da je Dp le 1.67. Podrobnejši rezultati MinGlDol in MinGIGor dodeljevanja v odvisnosti od časa tc so prikazani v tabeli 8. tc TP Sp Ep £>p 0 2 4 10 25 25 28 40 2.88 2.88 2.57 1.80 0.96 0.96 0.86 0.60 0.67 0.67 0.87 1.67 Tabela 8: FFT: MinGlDol in MinGIGor dodeljevanje pri različnih tc. Oba algoritma občutno zmanjšata število globalnih povezav, tako dobimo pri MinGlDol algoritmu 16 globalnih povezav, algoritem MinGIGor pa nam število globalnih povezav zmanjša celo na 15. 2.3.2 DAS: Dinamična analiza scene Za naslednji primer vzemimo algoritem za dinamično analizo scene. Algoritem DAS se uporablja pri izločanju ■ podob gibljivih objektov in je podrobneje opisan v [14]. Pripadajoči GPP prikazuje slika 6. Točke A, B, C in D se izvršujejo 345 časovnih enot, točke E, F, G in H 259 časovnih enot, točki I in J 190 časovnih enot, točki K in L 241 časovnih enot in točka M 69 časovnih enot. CPM, HNF in WL algoritmi. Tudi v primeru DAS algoritma dajejo metode (CPM, HNF in WL) enakovredne rezultate (slika 7). MinGlDol in MinGIGor algoritma. Oba algoritma vračata enake rezultate kot algoritmi CPM, HNF in WL, torej pri tc = 0 dobimo Tp = 1449, Sp - 2.31, Dp = 0.31 in Ep = 0.77 ter 12 globalnih povezav. Z algoritmom MinGIGor dobimo tudi enako dodelitev med procesorje (slika 7), medtem ko dobimo z al- Slika 6: GPP DAS algoritma. Pi i r. i s—i 1 B 1 F 1 P- II I 1 1, 1 1 A 1 D 1 H 1 i 1 K IMl i_i_i_i_i_i_:_j_i_ O 500 1.000 1.500 Slika 7: DAS: Razvrstitev po CPM, HNF, WL in MinGIGor. goritmom MinGlDol sicer drugačno dodelitev med procesorje (slika 8), ki pa, kot rečeno, rezultira v enako število globalnih povezev. Podrobnejša analiza pri 0 < tc < 300 je prikazana v tabeli 9. tc Tp sp Bp Dp 0 100 200 300 1449 1649 1849 2049 2.31 2.03 1.81 1.63 0.77 0.68 0.60 0.54 0.31 0.49 0.68 0.86 Tabela 9: DAS: CPM, HNF, WL, MinGIGor in MinGlDol dodeljevanje pri različnih tc. 2.3.3 LU: LU razcep matrike Za zadnji primer vzemimo algoritem za LU razcep matrike [15], ki je eden od najpogosteje uporabljenih algoritmov za reševanje sistema linearnih enačb. GPP LU algoritma je podan na sliki 9. Točke A, F, K in P se izvršujejo 4 časovne enote, točke B, C, D in E 5 časovnih enot, točke G, L in Q 9 časovnih enot, točke H, I in J 10 časovnih enot, 57 Slika 9: GPP algoritma za LU razcep matrike. Pi C Pi C G l n p3 c 500 UZD cmzD h i t i K—m 1.000 1.500 pl UlPIhl T. I T I ft p2 I !•' I H I P. I U I .) I p3 1 t_ 0 25 50 75 100 Slika 12: LU: Razvrstitev po MinGlDol. Fj ifibi a i 0 dosežeta obe metodi enak upad idealne pospešitve, ki je boljši od upada idealnih pospešitev metod CPM, HNF in WL (tabela 12). 2.3.4 Primerjava rezultatov Na osnovi povedanega sledi, da algoritma MinGlDol in MinGIGor dodeljujeta GPP ob manjšem (kvečjemu enakem) številu globalnih povezav. Analiza FFT, DAS in LU algoritmov je potrdila našo domnevo, da je število globalnih povezav v tesni zvezi z upadom idealne pospešitve. S tem je upravičena naša odločitev, da smo se pri oblikovanju algoritmov za dodeljevanje osredotočili na minimizacijo števila globalnih povezav. To minimizacijo opravljata algoritma MinGlDol in MinGIGor, ki za svoje delo potrebujeta sinhro-niziran GPP. Slednjega pa konstruiramo z enim od naših algoritmov TOptSinh oz. pOptSinh. S takšno minimizacijo je dosežen zastavljeni cilj, tj. časovna optimizacija asinhronega procesiranja. Algoritma MinGlDol in MinGIGor sta bila preizkušena nad 500 GPP, pri čemer smo spreminjali: število točk n < 120, čas njihovega izvrševanja Tabela 12: LU: MinGlDol in MinGIGor dodeljevanje pri različnih tc. tc MinGIGor (Dp/Dl) MinGlDol (Dp/DL) 5 1.3729 1.3623 10 1.2216 1.2199 20 1.1260 1.1187 Tabela 13: Relativna kvaliteta MinGlDol in MinGIGor algoritmov. t{v) < 10 in medprocesorsko komunikacijo tc < 20. Število procesorjev smo omejili na p = l/2pr00. Kvaliteto algoritmov MinGlDol in MinGIGor smo ocenjevali12 glede na algoritem NakljDod. Rezultati so zbrani v tabeli 13, kjer so Dv, Dl in Dp upadi idealne pospešitve pri algoritmih NakljDod, MinGIGor in MinGlDol. 3. Organizacija stroja Končno bomo predstavili še računalniško arhitekturo, ki učinkovito podpira podatkovno vodeno računanje, oplemeniteno s sinhronizacijskimi mehanizmi, kot so bili vpeljani v prejšnjem poglavju. Takšna arhitektura v popolnosti izkorišča rezultate časovne optimizacije asinhronega procesiranja. 3.1 Funkcionalni opis Že uvodoma smo opozorili na problem kopičenja podatkovnih paketov v vrsti pred procesno enoto, ki je posledica omejenega števila procesorjev v procesni enoti. Nakazali smo tudi eno od možnih rešitev, ki temelji na pravilnem vstopanju paketov v vrsto oz. izstopanju paketov iz nje. Na osnovi vpeljanih sinhronizacijskih mehanizmov je to rešitev možno uresničiti z vzporedno računalniško arhitekturo, kot bo opisana v nadaljevanju; poimenovali jo bomo sinhronizirana podatkovno pretokovna arhitektura (SPPA) [7, 16]. SPPA sodi v družino hibridnih arhitektur. Ses- 12 V ta namem smo uporabili računalnik IBM PC in razvili ustrezna programska orodja. 59 tavlja jo množica enakih podatkovno pretokovnih procesorjev (PPP) ter nadzorno-povezovalna enota (NPE), ki so krožno povezani, kot kaže slika 14. Vhodno/izhodna komunikacija z gostiteljskim računalnikom poteka preko NPE. Slika 14: SPPA. Preden se lotimo podrobnejšega opisa enot, na kratko opišimo potek reševanja danega problema na SPPA. Reševanje si lahko predstavljamo kot zaporedje treh faz: prevajanje programa ter optimizacija GPP, nalaganje SGPP v SPPA in izvrševanje v SPPA. Prevajanje ter optimizacija. Naj bo dan nek poljuben algoritem, zapisan v kakem od visokih podatkovno pretokovnih jezikov. Z ustreznim prevajalnikom se algoritem prevede v strojni kod, tj. GPP. Prevajanje poteka na gostiteljskem računalniku. V naslednjem koraku GPP optimiziramo, tj. konstruiramo p- ali T-optimalnO sprožitveno funkcijo (pOptSinh in TOptSinh) ter z uporabo algoritmov MinGIGor oz. MinGlDol določimo procesorske indekse 7r. Ti indeksi so pomemebni za samo nalaganje GPP v SPPA. Poleg tega pa so ob koncu optimizacije znane še vse globalne povezave ter trenutki sprožitve vseh tistih točk (vhodne ločene točke), v katere vstopajo globalne povezave. Ti podatki imajo pomembno vlogo pri izvrševanju GPP v SPPA. Nalaganje. Kot bomo videli v nadaljevanju, ima vsak PPP svoj grafni pomnilnik, v katerem hrani podatke o delu GPP. V fazi nalaganja se vsaka točka v iz GPP naloži v PPP z indeksom i, če je ir(v) — i. V PPP s tem indeksom se implicitno vpišejo tudi vse povezave, katerih začetna in končna točka sta dodeljeni procesorju z indeksom i, kot narekuje logična zgradba grafnega pomnilnika. V NPE pa se shranijo globalne povezave ter trenutki sprožitve vseh vhodnih ločenih točk. Pri nalaganju sodelujeta gostiteljski računalnik ter NPE. Izvrševanje. Po fazi nalaganja vsak PPP hrani ustrezen podgraf od GPP. Vse točke v PPP, ki za svojo izvršitev potrebujejo vsaj en podatkovni paket iz drugega podgrafa, se imenujejo vhodne ločene točke. Podobno pa so izhodne ločene točke vse tiste točke podgrafa, ki vsaj en svoj rezultat posredujejo v drug podgraf. Vse ostale točke v podgrafu imenujemo notranje točke. Izmenjava podatkov med notranjimi točkami poteka asinhrono, zato je podgraf čisti graf pretoka podatkov brez vnaprej določenih trenutkov sprožitve. Tudi izhodna ločena točka posreduje svoj rezultat takoj, ko se le ta izračuna. Izmenjava podatkovnih paketov med PPP poteka posredno preko NPE. Vsaka izhodna ločena točka torej pošlje svoj paket v NPE. Ta enota prebere iz seznama globalnih povezav, kateri vhodni ločeni točki je paket namenjen. Poleg tega pa iz seznama sprožitvenih trenutkov ugotovi, kdaj mora ta paket poslati ustreznemu PPP. Vidimo, da NPE deluje popolnoma sinhrono na osnovi globalne ure. 3.2 Nadzorno-povezovalna enota NPE opravlja naslednje funkcije: skrbi za vhodno/izhodno komunikacijo z gostiteljskim računalnikom, omogoča nalaganje delov GPP v ustrezne PPP in skrbi za posredovanje paketov med ločenimi točkami. Logično si NPE predstavljamo kot tabelo Globalna povezava Procesorski indeks Podatkovno polje Trenutek sprožitve . U l—► v P kjer je u i—► v globalna povezava iz točke u v v, tt(v) indeks PPP, v katerem je vhodna ločena točka v, p podatkovno polje, ki ga točka u pošilja točki v, ter ¿(v) trenutek sprožitve točke v. Podatkovno polje p je par p = (d, a), kjer je d vrednost, a pa določa, kateri od argumentov točke v bo sprejel vrednost d. Tabela se pred začetkom izvrševanja uredi po naraščajočih vrednostih ¿(u), ki so bile določene 60 v fazi optimizacije. Delovanje NPE opišimo na primeru. Naj bo A i—► B globalna povezava. Točka A naj bo dodeljena procesorju i, točka B pa procesorju j. Točka B se mora sprožiti v trenutku t. V nekem trenutku r < t točka A pošlje podatkovno polje p v izhodnem paketu oblike NPE I A i—► B I p v NPE. Ta na osnovi globalne povezave A >—>.B poišče v tabeli vrstico s to globalno povezavo ter v podatkovno polje vpiše vrednost p. S tem je sprejem izhodnega paketa končan. Sočasno globalna ura enote NPE šteje čas r. Ko postane r = i, NPE tvori vhodni paket oblike i I B I p in ga pošlje verigi PPP, kjer ga jF-ti PPP sprejme. 7r(v) I v I p kjer je v točka, ki (v procesorju z indeksom 7r(t>)) čaka na podatkovno polje p = (d, a). Iz indeksa 7r(v) krmilnik ugotovi, če je prispeli paket namenjen njemu. Če ni, ga vhodno-izhodni krmilnik nespremenjenega v istem ciklu posreduje naslednjemu PPP. Procesorje tako za tuje pakete transparenten. Če pa se ir(v) ujema z indeksom danega procesorja, se paket sprejme. V tem primeru enota za ažuriranje in dostavo iz paketa izloči indeks tt(v), preostanek v I d I a pa pošlje grafnemu pomnilniku. Grafni pomnilnik hrani opise točk in povezav podgrafa G P P. Opis točke v se nahaja v tabeli 3.3 Podatkovno pretokovni procesor Podatkovno pretokovni procesor omogoča hranjenje in izvajanje podgrafov GPP ter hkrati učinkovito komuniciranje s svojo okolico. Arhitektura je zasnovana tako, da je uporabljen sinhro-nizacijski mehanizem, ki temelji na shranjevanju paketov. Procesor sestavljajo vhodno-izhodni krmilnik, grafni pomnilnik, enota za ažuriranje in dostavo, čakalna vrsta, procesna enota ter izhodna vrsta (slika 15). paketi Točka Op St. Operandi Točke čakajoče na rezultat v op c d\ dm "M .«i t"n> /n, «n kjer je op operacija, ki jo mora točka v izvršiti nad operandi di, d2, • • •, dm ter rezultat poslati točkam wi,w2,..., wn\ rezultat mora biti shranjen v točko W{ kot argument z zaporedno številko a,. Zastavica fi zavzame vrednost L ali G glede na to, ali je točka to, v istem (lokana točka, f = L) ali drugem PPP (globalna točka, / = G). Števec c manjkajočih vhodnih operandov se ob nalaganju postavi na vrednost m. Enota za ažuriranje in dostavo vpiše vrednost d paketa v grafni pomnilnik v vrstico z oznako točke v na mesto operanda da ter hkrati zmanjša števec c za eno. Takoj po vpisu enota za ažuriranje in dostavo preveri, če je vrednost števca c enaka nič. Če je temu tako, posreduje paket oblike op dx v čakalno vrsto, kjer se paketi kopičijo in čakajo na Slika 15: Zgradba PPP. sprostitev procesne enote. Sočasno pa na osnovi v- te vrstice grafnega pomnilnika tvori v izhodni vrsti Vhodno-izhodni krmilnik skrbi za komunicajo naslednjo tabelo med PPP in okolico. Vhodni podatkovni paketi, ki vstopajo v krmilnik, imajo obliko 61 Ko procesna enota izračuna rezultat r — op(d\,..., dm), tvori paket v | r in ga pošlje izhodni vrsti. Ta vpiše vrednost r v polja za rezultat vseh vrstic, ki ta rezultat pričakujejo. Enota za ažuriranje in dostavo na osnovi zastavice /, tvori lokalni paket, če je /,• = L oz. izhodni paket, če je fi = G. Lokalni paket ima obliko W{ | r | a,i izhodni paket pa obliko NPE j t;-» w{ j d kjer je d = (r,o,). Vrednost r lokalnega paketa se preko enote za ažuriranje in dostavo vpiše v grafni pomnilnik v vrstico z oznako W{ na mesto operanda dai. Izhodni paket pa se preko vhodno-izhodnega kr. milnika posreduje NPE. 3.4 Izvedba Zadnji korak do končne izvedbe SPPA predstavlja razvoj strojne opreme NPE in PPP. V začetni fazi je moč NPE relativno preprosto emulirati s kakim od obstoječih mikroračunalnikov; končni cilj pa je izvedba NPE v obliki VLSI čipa. Tudi PPP je smiselno zasnovati kot VLSI vezje, vendar pa že danes obstajajo na tržišču procesorji, ki bi v prvi fazi zadovoljivo opravljali funkcijo PPP. Najbliže temu je podatkovno vodeni mikroprocesor /iPD7281 [17, 18]. Primeren kandidat, ki bi v prvi fazi prevzel funkcijo PPP, je transputer (npr. T9000) [19]. Za konec omenimo še možnost, da bi PPP nadomestili tudi s podatkovno vodenim procesorskim poljem. Se posebej so zanimiva heksag-onalna procesorska polja, ki so trenutno še predmet raziskav [20]. Zgradbo procesorskega polja prikazuje slika 16. Podatkovno vodene celice (procesorji) so organizirane v vrstice. Med vsakim parom vrstic je speljano komunikacijsko vodilo, ki omogoča vhodno/izhodno komunikacijo z NPE ter porazdelitev delov GPP med celice. Vsaka celica je točkovno povezana s šestimi sosednjimi celicami. Slika 16a prikazuje povezanost celice 0 s sosedami 1, 2, 3, 4, 5 in 6. Iz tehnoloških razlogov je število celic v polju omejeno (trenutno do nekaj 100 [20]). Zato moramo v splošnem GPP porazdeliti po več poljih. Na primer, slika 16b prikazuje rezultat nalaganja tistega dela GPP za FFT, ki je ga je algoritem MinGlDol priredil procesorju P2. 4. Zaključek Povrnimo se ponovno na nalogo, ki smo si jo zastavili. Predpostavimo, da je na voljo podatkovno pretokovni računalnik s potencialno neskončnim številom procesorjev ter izberimo poljuben graf pretoka podatkov. Denimo, da je za najhitrejšo asinhrono izvršitev izbranega grafa potrebnih vsaj m procesorjev. Tedaj označimo s Tm najkrajši čas, v katerem se ta graf izvrši na m procesorjih. Na računalniku z n < m procesorjev pa bi se v splošnem isti graf asinhrono izvršil v času Tn = Tm + ATn, kjer ATn > 0. Za nalogo si zadajmo minimizirati podaljšek izvrševanja ATn, tj. časovno optimizirati asihrono procesiranje pri n danih procesorjih. Časovno optimizacija asinhronega procesiranja se rešuje bodisi dinamično, tj. med izvrševanjem grafa pretoka podatkov, ali pa statično, tj. med prevajanjem programa v graf. Dinamično dodeljevanje je obremenjeno z "overheadom" ter zaradi lokalne optimizacije redko vodi v globalno (časovno in/ali prostorsko) optimalno izvrševanje grafa pretoka podatkov. Zato je smiselno čim večji del optimizacije prenesti v fazo prevajanja. K razrešitvi opisanega problema smo pristopili po izvirni poti. Rešitev, ki jo predlagamo, temelji na uvedbi nekaterih mehanizmov sinhronizacije v asinhrono procesiranje. Graf pretoka podatkov s predhodno analizo opremimo z dodatno informacijo, ki bo koristila pri vlaganju grafa v računalnik ter med njegovim izvrševanjem. Postopek, imenovan statično dodeljevanje, poteka v dveh korakih: Sinhronizacija: Naj bo V množica točk danega grafa pretoka podatkov ter označimo s t(v) čas 62 ■ C i < i i l Comun: kac jsk a vc dilc ) > < -o ( ) ) o- -o z C ¿ ¿ < Komuni kacijsko vodik (a) o o— o G o o o o O E o o o O d o O O Kon Lunikac ijsko ve dilo 6 O o -M- o <*> -e-J J o o o o W ° o o <5 O O V GO O Komunikacijsko vodilo (b) Slika 16: Heksagonalno procesorsko polje. izvrševanja točke v £ V. Vsaki točki v € V hevristično priredimo trenutek njene sprožitve s(v) tako, da minimiziramo ATn, kjer je n < m. K hevrističnim metodam se zatečemo zaradi NP-polnosti opisanega problema. Graf, katerega točke so opremljene s trenutki sprožitve, imenujemo sinhronizirani graf pretoka podatkov. Sinhro-nizirani graf je torej oplemeniten graf, v katerem je znano, kdaj oziroma v kakšnem vrstnem redu se morajo točkam pridruženi ukazi pričeti izvrševati, da se bo celoten graf izvršil na n < m procesorjih v najkrajšem času. Dodeljevanje: Vsaki v G V priredimo indeks 7r(v), 1 < 7r(u) < n, ki pove, kateremu od n procesorjev se bo točka dodelila. Torej razbijemo V v n particij Vi,V2,-..Vn, kjer je V,- množica točk, ki se bodo izvrševale na ¿-tem procesorju. Točki imenujemo ločeni, če sta dodeljeni različnima procesorjema. Povezavo med ločenima točkama imenujemo globalna povezava. Množico V je v splošnem moč razbiti na več načinov, seveda pa se omejimo le na konstrukcijo dopustnih particij, ki omogočajo izvršitev grafa v skladu z določenimi trenutki sprožitve s(u). Med dopustnimi partici-jami iščemo optimalno, tj. takšno, pri kateri bo najmanj globalnih povezav. Tako bo zagotovljena tudi najmanjša medprocesorska komunikacija. Rezultat dodeljevanja je, da imamo za vsako v E V določen indeks n(v) ter "označene" globalne povezave. 63 Sinhronizirani graf pretoka podatkov dobimo s pomočjo hevrističnih algoritmov pOptSinh in TOptSinh, za konstrukcijo optimalnih sprožitvenih funkcij. Po pesimistični oceni vračata predlagana algoritma optimalno rešitev v 80% primerov. V algoritmu pOptSinh je uporabljena izvirna ocena za spodnjo mejo potrebnih procesorjev, ki temelji na razširjeni kritični vzporednosti grafa. Ta ocena je po svoji natančnosti v povprečju le za 6.52% slabša od optimalne Fernandez-Bussellove ocene, hkrati pa je njeno določanje za red velikosti hitrejše. Za dodeljevanje predlagamo algoritma MinGlDol in MinGIGor, ki temeljita na optimizaciji medpro-cesorskih komunikacij. V primerjavi z znanimi razvrščevalnimi algoritmi dobimo s predlaganima algoritmoma boljše rezultate, kar potrjujejo analizirani primeri algoritmov za izračun hitre Fourier-jeve transformacije, dinamične analize scene in LU razcepa matrike. Končno je predlagana tudi organizacija računalnika, ki podpira asinhrono procesiranje z elementi sinhronizacije. Nakazane so možnosti realizacije z VLSI podatkovno pretokovnimi mikroprocesorji in podatkovno pretokovnimi polji. Zahvala Raziskavo je finančno podprlo Ministerstvo za znanost in tehnologijo Republike Slovenije po pogodbi C2-0521-106-92. Za strokovno pomoč pri nastanku pričujočega dela gre zahvala mag. Borutu Robiču, sodelavcu Laboratorija za računalniške arhitekture IJS. Literatur a [1] E. B. Fernandez and B. Bussell. Bounds on the Number of Processors and Time for Multiprocessor Optimal Schedules. IEEE Trans. Computers, C-22(8):745—751, August 1973. [2] Y. E. Chen and D. L. Epley. Bounds on Memory Requirements of Multiprocessing Systems. In Proc. 6th Annu. Allerton Conf. Circui and Syst. Theory, pages 523-531, 1968. [3] R. McNaughton. Scheduling with Deadlines and Loss Functions. Management Sei., 6, October 1959. [4] T. C. Hu. Parallel Sequencing and Assembly Line Problems. Oper. Res., 9(6):841-848, November 19.61. [5] C. V. Ramamoorthy, K. M. Chandy, and M. J. Gonzalez. Optimal Schedulling Strategies in a Multiprocessor System. IEEE Trans. Computers, C-21(2):137—146, February 1972. [6] J. Silc, B. Robič, and L. M. Patnaik. Performance Evaluation of an Extended Static Dataflow Architecture. Computers and Artificial Intelligence, 9(l):43-60, 1990. [7] J. Silc and B. Robič. Synchronous Dataflow-Based Architecture. Microprocessing and Microprogramming, 27(l-5):315-322, August 1989. [8] J. Silc and B. Robič. Program Graph Partitioning for Macro-Dataflow. In Proc. ISSM Int'l Workshop on Parallel Computing, pages 327-330, September 1991. [9] J. Silc. Časovna optimizacija., asihronega procesiranja z uvedbo nekaterih mehanizmov sinhronizacije. Doktorska disertacija, Fakulteta za elektrotehniko in računalništvo, Ljubljana, junij 1992. 10] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976. 11] K. Mehlhorn. Graph Algorithms and NP-Completeness. Springer-Verlag, 1984. 12] E. G. Coffman et al. . Computer and Job-Shop Scheduling Theory. Wiley-Interscience, 1976. 13] B. Shirazi, M. Wang, and G. Pathak. Analysis and Evaluation of Heuristic Method for Static Task Schedulling. Journal of Parallel and Distributed Computing, 10(3):222-232, November 1990. 14] G. Pathak and D. P. Agrawal. Task Division and Multicomputer System. In Proc. 5th Int'l Conf. on Distributed Computing System, page 273, May 1985. 15] G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1989. 16] J. Šile and B. Robič. MADAME - Macro-Dataflow Machine. In Proc. Mediterranean Electrotechnical Conference - MELECON'91, pages 985-988, May 1991. 17] T. JefTery. The /¿PD7281 Processor. Byte, pages 237-246, November 1985. 18] J. Silc in B. Robič. Procesor s podatkovno pre-tokovno arhitekturo. Informática, 10(4):74—80, 1986. 19] D. Pountain. The Transputer Strikes Back. Byte, 16:265-275, August 1991. 20] S. Weiss, I. Spillinger, and G. M. Silberman. Architectural Improvements for Data-Driven VLSI Processing Arrays. In Proc. Functional Programming Languages and Computer Architecture, pages 243259, September 1989.