29 O PRESLIKAVI HADFG NA TAS INFORMATICA 3/92 Keywords: tree, network, allocation, network construction Peter Zaveršek*, Peter Kolbezen** * VELCOM d.o.o., Foitova 8, Velenje ** Institut Jožef Štefan, Jamova 39, Ljubljana POVZETEK. Delo obravnava preslikavo algoritma, ki je določen s hierarhičnim acikličnim grafom pretoka podatkov (HADFG), na drevesno avtomatno strukturo (TAS). Predlagani postopek preslikave upošteva prostorsko optimizacijo avtomata. Podana je primerjalna analiza med avtomatom z drevesno in avtomatom s toroidno strukturo. Na osnovi te analize so pokazane dobre in slabe strani obeh struktur avtomata. ALLOCATION OF HADF GRAPHS ONTO A TREE STRUCTURE. Hierarchical acyclic data flow graph (HADFG) tree-shaping form encouraged us in investigating a possibility of their allocation onto a tree-like automat structure (TAS). Various approaches can be used in order to obtain an appropriate structure. The paper proposes an analytical space-optimizing approach towards the network construction. Further, execution results on such a network are compared to the ones obtained by a torus-like network and the behaviour of each of them is discussed. 1. Uvod V delih [1, 2] je opisan večprocesorski sistem za učinkovito izvajanje hierarhičnih acikličnih grafov pretoka podatkov (HADFG). Sistem ima toroidno avtomatno strukturo. Preslikava HADFG na takšno strukturo je posredna. Mehanizem posredne preslikave s svojimi neželenimi vplivi podaljšuje čaš izvajanja HADF grafov, ker zahteva zase del procesorskih zmogljivosti. Tako si lahko upravičeno zastavimo vprašanje uspešnosti neposredne preslikave HADFG na avtomatno strukturo. Postopek preslikave, če naj bo uspešen, mora v povezavi z avtomatno strukturo čim manj obremenjevati procesorje. Preslikava naj bo zato neposredna, procesorji v strukturi pa statično povezani. Zaželena je avtomatna struktura, ki se povsem ujema s programskim grafom v času izvajanja grafa. Procesorji v dinamično rekonfigurabilnem polju, kot npr. [3] ali sistemi ParsyTec-a [6], bi poleg kompleksnejše strojne opreme zahtevali dodatne procesorske zmogljivosti za povezovanje v času izvajanja. Omenjene sisteme bi lahko uporabili kot osnovo statičnim sistemom, če bi procesorje v njih ustrezno povezali pred začetkom izvajanja programskih grafov. Procesorji v statični strukturi, ki jo zahtevamo, bodo predvidoma manj izkoriščena kot tisti v toroidnem sistemu, ker se statična struktura ne more prilagajati trenutnim razmeram v sistemu (zasedenost, razpoložljivost procesorjev). S transformacijo DFG v HADFG dobimo drevesni program- ski graf s korenom zgoraj, in vejami, ki se širijo od korena navzdol [1]. Kot je splošno znano, razlikujemo pri drevesnih grafih več tipov vozlišč. Koren grafa je vozlišče, ki nima predhodnika, in ima enega ali več naslednikov. Razvejišče je vozlišče, ki ima enega predhodnika in enega ali več naslednikov. Vozlišče grafa, ki ima le predhodnika in nima nobenega naslednika, imenujemo list grafa. Ce poskušamo takšen graf čimbolj neposredno preslikati v avtomat, lahko sklepamo da bo imela tudi avtomatna struktura drevesno obliko. To nas je vzpodbudilo k primerjalni raziskavi drevesne avtomatne stuk-ture in že v delih [1, 2, 4] obravnavane toroidne strukture. Pričakujemo, da bo neposredna preslikava na drevesno avtomatno strukturo (TAS) ponudila boljše rezultate glede na čas izvajanja vsaj za neko družino HADF grafov. Družino HADFG, ki se bo uspešneje izvajala, želimo tudi identificirati. Zato poskušamo v tem delu odgovoriti, ali je za izvajanje alogritmov, ki so predstavljeni v obliki HADF grafov, učinkovitejši toroidni sistem ali TAS. 2. Drevo in torus Predlagana toroidna struktura v delih [1, 2] je sestavljene. iz množice prepletenih zank (prstanov) trans-puterjev. Vsak transputer v avtomatni strukturi je fizično vezan na štiri sosede. Komunikacija med njimi je krožna po zankah, ki sestavljajo torus, in poteka eno- 30 smerno. Vsak procesor ima zato le dva logična soseda. Komunikacijske zanke ponujajo možnosti dvostranskih prenosov, ki jih izkoriščamo tako, da znotraj ene fizične zanke vzpostavimo dve logični komunikacijski zanki. Medtem, ko se po eni prenašajo podatki, ima druga funkcijo prenosa krmilnih sporočil in ukazov. Zasnova sistema podpira dinamično, "run-time" razporejanje procesov glede na proste vire v polju. Izbrana arhitektura, podprta s preprostimi mehanizmi optimizacije razporejanja, omogoča skupaj z uporabljeno arhitekturo sorazmerno učinkovito preslikavo programskega grafa na statično povezano polje procesorjev. Vsi procesorji v toroidnem polju imajo enako število sosedov, zato so si enakovredni ne glede na položaj v vezju. Ker imajo vsi procesorji logične naslednike, se polje navidezno nikjer ne zaključi. Izvajanje programskih algoritmov, ki so predstavljeni v obliki IIADFG, je, zahvaljujoč virtualni razširljivosti toroidnega polja, učinkovito in uspešno tako pri manjšem, kot pri večjem številu procesorjev. Drevesna struktura za razliko od toroidne ni virtu-alno razširljiva. Terminalni procesorji (listi drevesne avtomatne strukture) nimajo naslednikov. Širjenje HADF grafa po takšnem polju se zaustavi na terminalnih procesorjih, kjer se struktura zaključi. Zato drevo ne ponuja vsem procesorjem enakovrednega položaja v strukturi. Učinkovita preslikava HADF grafa na drevesno strukturo zahteva ustrezno razvejanost in globino strukture. Drevo torej ni tako prilagodljivo, kot je torus. Če želimo izvajati programski graf na statično povezani drevesni avtomatni strukturi, moramo ustrezno strukturo praviloma zasnovati vnaprej. Struktura je lahko predvidena ali za vsak HADF graf posebej ali za neko natančno določeno družino HADF grafov. 3. Določitev drevesne strukture Učinkovito izvajanje algoritma, ki ga predstavlja določen HADF graf, zahteva ustrezno drevesno av-tomatno strukturo. Razsežnost avtomata mora biti vsaj takšna, kot je razsežnost preslikave grafa. Globina avtomatne strukture mora biti vsaj enaka številu paralelnih nivojev HADF grafa, medtem ko mora širina na opazovanem delu ustrezati številu paralelnih vej v vozliščih grafa, ki se bodo preslikala na to avtomatno vozlišče. Zahtevamo, da je avtomatna struktura splošna. Ustrezati mora vsakemu HADF grafu dane oblike in mora zagotavljati neomejeno širjenje procesorskih aktivnosti v njej, neodvisno od časov izvajanja posameznih procesov. Posledica pogoja takšne časovne neodvisnosti je, daje tudi rezultat optimizacije skromnejši. Primer optimiranja avtomatne strukture je npr. sekvenčno izvajanje dveh kratkih paralelnih procesov ob tretjem zelo dolgem, s čemer lahko prihranimo kakšen procesor. V nadaljevanju bomo nakazali možne poti, ki nas pripeljejo do ustreznega avtomata. / . / . \ / , \ , \ (^©©©©(^(ii)©^®1 Slika 1: Izhodiščni HADF graf 3.1 Prekrivanje HADF graf natančno predpisuje način izvajanja posameznih vej v skladu s tipom veje (paralelna, sekvenčna). Možnost, ki se sama ponuja, je neposredna preslikava grafa v avtomatno strukturo. Glede na tip veje lahko zaključimo naslednje: • Paralelne veje: Vse paralelne veje, ki izhajajo iz istega (paralelnega) vozlišča, se izvajajo sočasno. Izvajanje ostalih paralelnih vej grafa glede na opazovano vejo je določeno z njihovo lego v grafu. Zaželeno je, da se paralelne veje znotraj enega paralelnega vozlišča, kot tudi vse njim paralelne veje drugod po grafu, izvajajo sočasno. Zajeti želimo ves ponujeni paralelizem in tako doseči največjo stopnjo paralelnosti izvajanja. S tem bo tudi hitrost izvajanja največja. Med izvajanjem moramo imeti vsak trenutek na razpolago zadostno število procesorjev, odgovarjajoče številu procesov, ki jih je v danem trenutku možno izvajati sočasno. Procesorji morajo biti medsebojno povezani tako, kot zahteva HADF graf, saj v nasprotnem primeru preslikava procesov nanje ne bi bila možna. • Sekvenčne veje: Sekvenčne veje se izvajajo druga za drugo. Pravimo, da so si tuje. Pri izvajanju izrabljajo isti del avtomatne strukture. Ivaskado večih zaporednih sekvenčnih procesov lahko obravnavamo kot en sam proces. Vse procese, ki sestavljajo kaskado, preslikamo na isti procesor. Podobno obravnavamo podgrafe, ki si sledijo drug za drugim. Tudi te preslikamo na isti del avtomatne strukture. Zavedati se moramo pomembne razlike med procesi in pod-grafi. Posamezni procesi zasedejo le en procesor, medtem ko je razsežnost in oblika zahtevanega avtomatnega polja za podgraf določena s pripadajočo globino in širino podgrafa. Potrebno globino podavtomata določa število paralelnih nivojev najglobjega. podgrafa. Število procesorjev na posameznem nivoju je enako številu paralelnih vej tistega peralelnega vozlišča nivoja, ki ima največje število vej. Gornje ugotovitve strnimo v preprost postopek, poimenovan prekrivanje. Z njim je že mogoče določiti 31 avtomat. Postopek prekrivanja na primeru grafa iz slike 1 prikazuje slika 2 in poteka takole : 1. postopek pričnemo izvajati na podgrafu, ki je določen s skrajnimi levimi sekvenčnimi vejami podgrafa (slika 2-1). 2. Preslikamo vozlišča v procesorje po naslednjem pravilu: • sekvenčna vejišča se preslikajo v procesorje, povezave med procesorji pa določajo paralelne povezave grafa • procesi (listi HADFG drevesa) se preslikajo v procesorje • če v avtomatni struktruri na mestu, kjer bi moral biti procesor slednjega še ni, ga dodamo (temnejši procesorji na sliki 2) • če ima avtomatna struktura več procesorjev, kot je potrebno, jih ne odvzemamo 3. Izberemo naslednjo sekvenčno vejo na najnižjem sekvenčnem nivoju (naslednji podgraf) in nadaljujemo od točke 2 dalje, dokler ni obdelan celoten graf (slike 2 II-IV). Metoda prekrivanja avtomatne strukture z ustreznimi deli grafa, nam omogoča enostavno konstruiranje avtomatne strukture. Tako pridobljena avtomatna struktura popolnoma ustreza danemu grafu, vendar je v splošnem predimenzionirana. Ugotovimo lahko, da je možno graf ustrezno preoblikovati in realizirati funkcionalno enakovredno strukturo z manjšim številom procesnih elementov. 3.2 Urejeno prekrivanje HADF graf ima v splošnem nesimetrično obliko. Ne-simetričnost se odraža v različnih globinah podgrafov istega nivoja, in v različnem številu vej, ki izhajajo iz posameznih paralelnih, vozlišč grafa. Vrstni red posameznih vej znotraj paralelnega vozlišča je funkcionalno nepomemben, saj se vse veje istega vozlišča izvajajo sočasno. Ta lastnost nam daje možnost, da veje med seboj kombinatorično permutiramo tako, da dosežemo kar najboljše prekrivanje nastajajoče drevesne avtomatne strukture z obravnavanim grafom. Originalni HADF najprej graf ustrezno preoblikujemo, nakar sestavimo avtomat z zgoraj opisanim prekrivanjem. Uspešnost postopka se kaže v prostorski optimizaciji ATS in je neposredno odvisna od preoblikovanja grafa. Iterativne metode (npr. simulirano ohlajanje) bi lahko bile zelo uspešne, vendar potrebujejo za svoje izvajanje več časa. Analitični pristop je hitrejši in zaradi drevesne strukture enostavno izvedljiv, zato smo ga uporabili tudi mi. Prvi korak do optimizacije je torej ureditev HADF grafa. Graf uredimo tako, da znotraj vseh paralelnih vozlišč razvrstimo skrajno levo najglobje in skrajno desno najplitvejše veje. V primeru enake globine 0A® Slika 2: Postopek prekrivanja dveh vej ima prednost tista, ki ima večje število procesov na najnižjem nivoju. Opisani postopek prevede drevo iz neurejene v urejeno strukturo, kar lahko shematično prikažemo na sliki 3. 3.2.1 Algoritem urejenega prekrivanja Algoritem deluje na principu utežitve vozlišč HADF grafa. Uteži, ki jih pripišemo vozliščem, so le računski pripomočki in nimajo nobene povezave s časovnimi utežmi grafa. Primerna utežitev nam olajša postopek urejanja grafa. Predpostavke za HADF graf: • začetno vozlišče HADF grafa je sekvenčno vozlišče, ki predstavlja ničti nivo v grafu (l = 0). V nasprotnem primeru govorimo o večih grafih, ki se lahko izvajajo paralelno. 32 Neurejena struktura Urejena struktura Slika 3: Struktura grafa • na koncih vej, ki izhajajo iz korenskega vozlišča, se nahajajo procesi ali paralelna vejišča. To je prvi nivo v grafu (/ = 1). • ko se spuščamo po grafu navzdol, se izmenjujejo sekvenčni in paralelni nivoji. Nivo v grafu se poveča z vsakim naslednjim vozliščem za ena (/j+1 = h + 1). Utežitev listov in vozlišč grafa ter urejanje Prvi, prioritetni kriterij pri urejanju grafa je globina. Širina predstavlja drugi kriterij. Utežitev vej mora zagotoviti globjim vejam večjo težo ne glede na širino primerjanih plitvejših vej. Uteži moramo izbirati tako, da ima utež na najnižjem nivoju večjo težo, kot je vsota vseh ostalih uteži na višjih nivojih. N-1 9n > 9i 1=0 Predno začnemo uteževati posamezne liste, moramo določiti težo uteži za liste HADF grafa po posameznih nivojih. Največje število paralelnih vej N, ki izhajajo iz katerega koli paralelnega vozlišča v grafu, je v skladu z gornjo zahtevo in mora biti znano. Enakovredno bi ustrezalo tudi poznavanje največjega števila paralelnih vej po posameznih paralelnih nivojih, vendar zaradi poenostavitve postopka gledamo na HADF graf kot celoto. Uteži določamo po naslednjem pravilu: Utež q0 {l = 0) qo ■ ■ ■ izberemo: qo 0 Utež qx (l - 1) qi ...izberemo: qi — 1 Utež q2 (/ = 2) N 91 > 9o 92 >J2qr=N-qi = N ¿=1 Najmanjša možna razlika za N ... <72 = N + 1 Utež 93 (/ = 3) N 93 v— 0 N3 - l >22<]2 = n ■ q-> = ;V(yV + l) = N2 + N = _ 1 -1 ¿=i 93 = 92 + 1 = N + N + 1 = /V3 - 1 N - 1 Utež qk (/ = k) N qk-1 = N ' qk~1 = 1 = 1 N(Nk~2 + Nk~3 +...+ N + 1) - Nh~l + Nh~- + ■ ■ ■ + N- + N = Nk - 1 N - 1 - 1 qk = q2 + 1 = Nk~l + Nk~2 + N2 + N + 1 = N _ 1 Pripisovanje uteži procesom HADF grafa Ko so uteži določene, utežimo z njimi liste grafa (procese) v skladu z njihovo lego v grafu. Paralelne in sekvenčne procese obravnavamo po ločenih kriterijih. Slika 4: Urejen HADF graf Paralelni procesi • obsegajo liste grafa na nivojih / = 2k - k = 1,2,... • iz posameznega vejišča izhaja največ N takšnih procesov • utež qn = 9>i|n=Jr = ^rfl1 => => 9I|,=2. 92|i=4" ■ ■■flk\tl=,k 33 Sekvenčni procesi • obsegajo liste grafa na nivojih /= 2k- 1 \k = 1,2,... • število vej iz posameznega vejišča ni omejeno • utež qn = qn\n=IDIV2 = T^fr => 9o|,=1, 92|,=3> ■ • Pripisovanje uteži razvejiščem grafa Paralelna razvejišča (/ = 2k — 1) Paralelnemu razvejišču pripišemo vsoto uteži vseh vej, ki iz njega izhajajo: mp