Information Technology | Computer architectures » Szisztolikus rendszerek

7. Szisztolikus rendszerek (Eberhard Zehendner) A szisztolikus rács – a speciális feladatot ellátó számítógépek legtökéletesebb formája – legegyszerubb  esetben csupán egyetlen számítási muvelet  ismételt végrehajtására alkalmas.  alkalmazási területe van, foként  Ennek ellenére számos, gyakorlati szempontból is jelentos az iteratív módszereket alkalmazó numerikus matematika, kombinatorikus optimizálás, lineáris algebra, algoritmikus gráfelmélet, kép- és jelfeldolgozás, nyelv- és szövegfeldolgozás stb. területén  egy végrehajtásra Egy szisztolikus rács felépítése egészen pontosan megfeleltetheto  váró algoritmus szerkezetének úgy, hogy minden egyes számítás helye és idopontja egyszer és mindenkorra meghatározott, az egymással kommunikáló cellák közvetlenül és permanens módon egymáshoz vannak kapcsolva, így kommunikációs csatornák létrehozása feleslegessé válik. Az algoritmust közvetlenül hardver

valósítja meg Emiatt a szisztolikus algoritmusokat ebben az összefüggésben hardver-algoritmusként” is szokták emlegetni. ” szisztolikus algoritmusok” kifejezés tehát nem egy bizonyos, jól körülhatárolt szᔠmítási feladatra adott megoldások sokaságát jelenti (mint például a rendezési algoritmusok A esetében), hanem sokkal inkább egy sajátos feladatmeghatározási-, programozási-, illetve  felhasználási területhez tartozó alszámítási stílust határoz meg. Igen sokféle, különbözo goritmus lehet szisztolikus jellegu”,  ami nem jelenti feltétlenül azt, hogy ezen területek ” összes ismert algoritmusa szisztolikus feldolgozásra alkalmas alakra hozható lenne. Ennek a fejezetnek nem célja, hogy a szisztolikus algoritmusokat”, vagy akár csak a ” legfontosabb szisztolikus algoritmusokat” bemutassa. A cél az, hogy néhány egyszeru,  de ” tipikus példa segítségével megalapozzuk a szisztolikus algoritmusok általános

megértését.  áll. Az alapfogalmak (71 alfejezet) után a térido  leképezést A fejezet öt alfejezetbol (7.2 alfejezet), majd a be/kiviteli sémát (73 alfejezet) mutatjuk be A 74 alfejezetben a vezérlési szempontokat, a 7.5 alfejezetben pedig a lineáris szisztolikus rácsokat tárgyaljuk 7.1 A szisztolika alapfogalmai  származik. Maga a szisztolikus elnevezés a szisztolikus architektúrák muködési  elvébol Szisztolikus munkamódon a futószalag-elv, illetve a térbeli párhuzamosság intenzív együttes alkalmazását kell értenünk, melyet egy globális, és teljes mértékben szinkronizált órajel irányít. Ez eredményezi az adatfolyamoknak az összekapcsolt cellák hálózatán keresztül tör ritmikus áramlását, az emberi szervezetben keringo  vérhez hasonlóan, melyet a szív a téno  pontjai felé küld. A futószalag-elv nem csupán egyetvérereken keresztül a test különbözo 269 7.1 A szisztolika alapfogalmai b41 b31 b21 b11 0 0 a14 a13

a12 a11 c11 b42 b32 b22 b12 b43 b33 b23 b13 b44 b34 b24 b14 b45 b35 b25 b15 B c12 c13 c14 c15 + * A 0 a24 a23 a22 a21 0 a34 a33 a32 a31 0 0 c21 c22 c23 c24 c25 c31 c32 c33 c34 c35 (a) C (b) 7.1 ábra Téglalap alakú szisztolikus rács mátrixszorzáshoz: (a) A rács felépítése és a beviteli séma; (b) cellaszerkezet  irányba haladó, a szisztolikus rács celláiban len irányban érvényesül, hanem a különbözo  adatfolyamok mindegyikére vonatkozik. egymást keresztezo Egy szisztolikus rendszer általában egy gazdagépbol,  illetve a tulajdonképpeni szisztolikus rácsból áll. A gazdagépnek elvileg alárendelt szerepe van; csupán a szisztolikus rács muködésbe  hozatalára, továbbá adatokkal való ellátására szolgál. A szisztolikus rács egy sajátos, cellákból álló hálózatként is felfogható, mely a masszív párhuzamosságnak köszön hetoen az adatorientált muveleteket  igen nagy sebességgel hajtja végre. Egy

szisztolikus rács celláinak egységes muködése  révén végrehajtott program adja magát a szisztolikus algoritmust. Bármennyire is különböznek egymástól a szisztolikus rácsok, mégis jó néhány közös  tulajdonsággal rendelkeznek: ezek a diszkrét idoséma, a szinkron munkamód, a szabályos (általában két dimenziós) mértani felépítés, csak közvetlenül szomszédos cellák között fennálló kommunikáció, valamint a legegyszerubb  vezérlési mechanizmusok alkalmazása.  jelenségeket A fejezet további részében a szisztolikus rácsokkal kapcsolatos alapveto  példán keresztül bemutatni és megvilágítani. Egy számítási feladatra fogjuk egy jellemzo  szisztolikus rácsokat találhatunk, gyakran többféle megoldás kínálkozik, azaz különbözo melyek közül a legjobbak általában igen bonyolultak. A továbbiakban ezért nem a legjobb változat bemutatását tuztük  ki célul, hanem a legfontosabb elvek tömör és intuitív módon való

bemutatását. 7.11 Bevezet® példa: mátrixok szorzása A 7.1 ábrán egy 15 cellából álló, téglalap alakú szisztolikus rács látható, amely egy 3 méretu  A mátrixnak egy N ×5 ×N méretu  B mátrixszal való összeszorzására alkalmas. Az N paraméter a 7.1 ábrán látható szisztolikus rács felépítése szempontjából semmiféle szerepet nem játszik, viszont lényeges a beviteli séma, valamint az algoritmus futási ideje szempont- 270 jából. 7. Szisztolikus rendszerek (Eberhard Zehendner) 271 7.1 A szisztolika alapfogalmai A beviteli séma az N =  konkrét feladat 4 értéknek felel meg. A 71 ábra a következo megoldását mutatja: A ·B=C , ahol    A =       B =   C    =       , a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 b11 b12 b13 b14 b15 b21 b22 b23 b24 b25 b31 b32 b33

b34 b35 b41 b42 b43 b44 b45 c11 c12 c13 c14 c15 c21 c22 c23 c24 c25 c31 c32 c33 c34 c35     ,       , továbbá ci j = 4 X aik · bk j (1 ≤ i ≤ 3, 1 ≤ j ≤ 5) . k=1   kapcsolaA szisztolikus rács cellái adatokat cserélhetnek egymás között az oket összeköto  nyilakkal jelöltünk. A szisztokon keresztül, melyeket a 71(a) ábrán a cellákat összeköto tolikus rács a peremcelláin keresztül kommunikál a külvilággal. A szisztolikus rács minden egyes cellája ugyanazt a kapcsolódási mintát követi a környezettel való kommunikáció során. A szisztolikus rács teljesen szabályos felépítése (a cellák elhelyezése, illetve a kapcsola kapcsolódási tengelyek tok szerkezete) szabályos adatfolyamokat eredményez a különbözo mentén. A 7.1(b) ábra egy cella belso  szerkezetét szemlélteti. Egy cella egy szorzóból, egy összeadóból, három

regiszterbol  és négy csatornából, illetve az ezeket összekapcsoló vezetékek áll. Minden cellának ugyanolyan a felépítése bol Az A, B és C regiszterek mindegyike egy szám tárolására képes. A regiszterek jelölését  itt értelem szerint választottuk meg, de tulajdonképpen tetszés szerint jelölhetjük oket. Az A, illetve B regiszterek az ún. bemeneti csatornáktól kapják értékeiket A 71(b) ábrán a  szélén található apró körökkel jelöltük ezeket. Egy ilyen csatorna cella bal, illetve felso  illeszkedo  kapcsolathoz. csatlakozási felületet képez a cellához kívülrol Az A, illetve B regiszterek aktuális értékét a szorzó operandusként fogja felhasználni,  ezzel egyidoben az értékek továbbadódnak a cella kimeneti csatornáin keresztül (lásd az  köröket). A szorzás eredményét az összeadó ábra jobb, illetve alsó szélén elhelyezkedo  kapja. Az összeadás eredménye felül veszi át, mely második paraméterét a C

regisztertol fogja írni C korábbi értékét. 272 7. Szisztolikus rendszerek (Eberhard Zehendner) 7.12 A feladat és a rács paraméterei A 7.1 ábrán bemutatott szisztolikus rács 15 cellája 3 sorból és 5 oszlopból álló téglalap alakú mintát alkot (akárcsak a C mátrix). Ennek méretei megegyeznek az A mátrix sorainak, illetve a B mátrix oszlopainak számával. Tehát esetünkben a szisztolikus rács mérete a meg adatszerkezetek méretéhez igazodik Általános esetben, ha oldásra váró feladatban szereplo egy N1 × N3 méretu A mátrixot egy N3 × N2 méretu  B mátrixszal kellene összeszoroznunk,  szisztolikus rácsra lenne szükségünk. egy N1 sorral, illetve N2 oszloppal rendelkezo A 7.1 ábrán látható felépítés természetesen azt is megengedi, hogy egy több, mint N1  szisztolikus rácsot használjunk. Ez abban az sorral vagy több, mint N2 oszloppal rendelkezo esetben lényeges, amikor egy rögzített méretu  szisztolikus rácsot

szeretnénk használni kü méretu lönbözo  mátrixok összeszorzására. Ekkor minden esetben csupán azt az N1 sorból,  illetve N2 oszlopból álló téglalap alakú részt használnánk, mely a példában a rács bal felso sarkában található. Jóllehet a többi cella is ugyanúgy fog muködni,  ám a feladat megoldásához nem járulnak hozzá (de hibát sem okoznak). Az N1 , N2 , N3 méretek a megoldásra váró feladat paramétereit képezik, mivel a megol függ; ezek tehát a feladat dás során végrehajtott muveletek  száma mind a három értéktol paraméterei. Ellenben a szisztolikus rács mérete, illetve felépítése csak az N1 és N2 mére függ, ezek tehát egyúttal a rács paraméterei is lesznek tektol Megjegyzés. A 72 alfejezetben a mátrixok szorzását megvalósító újabb szisztolikus  függráccsal ismerkedhetünk meg, melynek méretei mindhárom (N1 , N2 , N3 ) paramétertol nek. 7.13 Térbeli koordináták A továbbiakban a szisztolikus rács

minden egyes cellájához szeretnénk egy egyértelmu  térbeli koordinátát hozzárendelni, ennek segítségével jellemezve a cella mértani elhelyezkedését a rács egészéhez képest. Egy téglalap alakú szisztolikus rács esetén legegyszerubb,  ha  sor-, illetve oszlopszámokat használjuk. A 71 ábrán c11 -gyel jelölt erre a célra a megfelelo cella tehát az (1, 1) koordinátákat kapja, a c21 -gyel jelölt pedig a (2, 1) koordinátákat, és így  részében adottnak tovább. Az így meghatározott térbeli koordinátákat a fejezet hátralevo tekintjük.  Elvileg lényegtelen, hogy hol helyezkedik el a koordinátarendszer kezdopontja, milyen  és melyik irányban helyezkednek el a koordinátatengelyek, melyik irány felel meg az elso, a második koordinátának. A példában a mátrix komponenseinek jelölésére a megadott szá koordináta a fentrol  lefelé, 1-gyel kezdod  oen  mozást választottuk, ennek alapján az elso számozott soroknak felel meg, míg

a második komponens a balról jobbra, szintén 1-gyel  oen  kezdod számozott oszlopoknak. Természetesen másképp is megválaszthattuk volna a koordinátarendszert. A fenti séma  azonban kitun  oen megfelel az alábbi szisztolikus rácsnak: az egy adott cellában kiszámított ci j mátrixkomponens indexei pontosan megegyeznek a cella koordinátáival. Az A mátrix  koorbeviteli adatként megadott sorainak száma pontosan ugyanaz, mint azon cellák elso dinátája, amelyeken ezek az adatok keresztülhaladnak; ugyanez érvényes a második koordinátára, a B mátrix oszlopaival kapcsolatban. Az összes kapcsolat (és ezzel együtt a rajtuk  irányába keresztülhaladó összes adatfolyam) tengelypárhuzamos és a koordináták növekvo mutat. 273 7.1 A szisztolika alapfogalmai  térbeli koordinátákat Nem mindig ennyire egyértelmu,  hogyan rendelhetünk megfelelo a cellákhoz; példaként álljon itt a 7.3(a) ábrán látható szisztolikus rács A koordinátarend

módon tükszer megválasztásától függetlenül fontos, hogy a cellák koordinátái szembeötlo rözzék a szisztolikus rács szabályos felépítését. Emiatt használunk tulajdonképpen mindig  cellák egész koordinátákat. Ezért jó, ha az egymástól minimális euklideszi távolságra fekvo koordinátái csupán egyetlen komponensben különböznek, és a különbség értéke 1. 7.14 Generikus operátorok sorba fejtése Minden, a 7.1 ábrán látható aktív (i, j) cella pontosan a C eredménymátrix ci j elemét számolja ki Tehát a cellának az alábbi skalárszorzatot kell kiértékelnie: 4 X aik · bk j . k =1 Ez iteratív módon történik: minden lépésben egy újabb aik · bk j szorzatot számítunk ki, ami hozzáadódik az addigi részösszeghez. A részösszeget a számítások elején természete sen nulláznunk kell (vagy egy tetszés szerinti kezdoértéket határozhatunk meg). Az impera tív programozási nyelvek klasszikus jelölésmódját

követve a következoképpen írhatjuk le, hogy mi történik. M́́(N1 ,N2 ,N3 ) 1 for i 2 3 4 5 6 ← 1 to N1 ← 1 to N2 do c(i, j) ← 0 for k ← 1 to N3 do c(i, j) ← c(i, do for j j) + a(i, k) · b(k, j) return C = Ha N1 dást, Θ(N 3 P = N3 , akkor ennek az algoritmusnak a végrehajtása során ) szorzást és futási ideje A N2 Θ(N 3 Θ(N 3 ) összea- ) értékadást kell végrehajtani, ezért egy soros processzoron a Θ(N 3 ).  operátor az úgynevezett generikus operátorok közé tartozik, melyekösszegzo   A 7.1 ábrán látható szisztolikus rács esetén hez tetszoleges számú operandus rendelheto. minden egyes összeadás, mely ugyanannak az összegnek a kiszámításához tartozik, ugyanabban a cellában hajtódik végre. Ugyanakkor sok olyan példa is van, melyben egy generikus  cellák közt oszlanak meg (lásd például a 7.3 ábrán beoperátor egyes muveletei  különbözo mutatott szisztolikus

rácsot). Megjegyzés. Néhány további példa generikus operátorokra: szorzat, minimum, maximum, továbbá az ́, , illetve ́́- logikai muveletek.   a végrehajtandó muSzükség van tehát a generikus operátorok sorba fejtésére, mielott  veleteket hozzárendelhetnénk a szisztolikus rács celláihoz. Ezeket az operátorokat azonban  opemásképp kell kezelnünk, mint a megszokott, rögzített számú operandussal rendelkezo rátorokat – ilyen például a két operandusú összeadás – mivel ezek beosztásánál bizonyos fokú szabadsággal rendelkezünk. 274 7. Szisztolikus rendszerek (Eberhard Zehendner) 7.15 Értékadásmentes jelölés A szisztolikus programok leírására az imperatív forma helyett, akárcsak a M́́ algoritmus esetében, inkább egy értékadásmentes jelölést használunk, mely egy egyenlet megoldásán alapszik. Ily módon elkerüljük a mellékhatásokat

és közvetlen módon ki tudjuk fejezni a párhuzamosságot. Az alábbi esetben zavaró a c(i, j) változó értékének felülírása Ezért bevezetjük helyette a c(i, j, k) példányok sorozatát, mely a c(i, j) változónak a M́́ algoritmus lépéseinek végrehajtása során felvett értékeit jelöli. Ezáltal egy úgynevezett rekurzív egyenlet jön létre. A M́́ algoritmusban bemutatott mátrixszorzást például a kö módon lehet értékadásmentes alakban kifejezni: vetkezo Bemeneti muveletek  c(i, j, 0) =0 1 ≤i≤ N1 , 1 ≤ j≤ N2 . 1 ≤i≤ N1 , 1 ≤ j≤ N2 , 1 1 ≤i≤ N1 , 1 ≤ j≤ N2 Számítások c(i, j, k) = c(i, j, k − 1) + a(i, k) · b(k, j) ≤k≤ N3 . (7.1) Kimeneti muveletek  ci j = c(i, j, N3 ) . A (7.1) rendszer leírja a végrehajtott szisztolikus algoritmus pontos felépítését A leg egyenlet az összes bemeneti adatot jellemzi, a legalsó

pedig az összes kimeneti adatot; felso a szisztolikus rácsban ezek az egyenletek nem számítási, hanem ki/bemeneti muveleteknek   egyenlet írja le a tulajdonképpeni számításokat. felelnek meg. A középso A rendszer minden egyes egyenletéhez hozzátartozik egy, az egyenlet jobb oldalán látható kvantikálás, mely az i és j iterációs változók által felvett értékek halmazát határozza  egyenlet esetében k változóét is). Minden ilyen halmazt értéktartománynak meg (a középso  egyenlet i, j, k iterációs változói egy (i, j, k) iterációs vektort alkotnevezünk. A középso nak. A ki/bemenet esetében az iterációs vektoroknak csupán i és j komponense van Ahhoz, hogy egy zárt jelölésmódot kapjunk, kiegészíthetjük ezeket a vektorokat egy k komponenssel, melynek rögzített az értéke. A bemeneti adatokat k pedig k = = 0-val jelöljük, a kimeneti adatokat  N3 -mal. A következoket kapjuk: Bemeneti muveletek  c(i, j, k) =0 1 ≤i≤

N1 , 1 ≤ j≤ N2 , k =0. 1 ≤i≤ N1 , 1 ≤ j≤ N2 , 1 ≤k≤ 1 ≤i≤ N1 , 1 ≤ j≤ N2 , k = Számítások c(i, j, k) = c(i, j, k − 1) + a(i, k) · b(k, j) N3 . (7.2) Kimeneti muveletek  ci j = c(i, j, k) N3 . Figyeljük meg, hogy a be/kimeneti adatokhoz tartozó értéktartományok formálisan szintén háromdimenzióssá váltak ugyan, a megszokott értelemben azonban csak kétdimenziósak. 275 7.1 A szisztolika alapfogalmai 7.16 Elemi számítások  közvetlen módon leolvashatók azok az elemi, azaz tovább A (7.2) rendszer egyenleteibol már nem osztható muveletek,  melyeket a szisztolikus rács cellái fognak elvégezni. Ezek pontosan azok – a rendszer valamely egyenletében leírt – muveletek,  melyek az egyenlethez rendelt kvantikálás egy rögzített pontjára vonatkoznak. Amennyiben egy egyenletben  ezeket együvé tartozónak, azaz egyetlen összetett muveletnek több részmuvelet  fordul elo,   tekintjük, és

ugyanabban a lépésben, ugyanaz a cella fogja oket együttesen végrehajtani.  egyenletében két muvelet A (7.2) rendszer középso  jelenik meg: az a(i, k) · b(k, j) szorzás, illetve a hozzá tartozó c(i, j, k) = c(i, j, k − 1) + · · · összeadás. Az együvé tartozó egyes muveleteket,  vagyis az összeadást és szorzást a 7.1(b) ábrán látható szisztolikus rács cellája egy összetett szorzás-összeadás” muvelet  során fogja elvégezni. ” Minden egyes ilyen elemi számításhoz hozzárendelhetünk egy jelet. Nyugodtan nevez-  koordinátákat kapjunk, kézenfekvo  meghetjük ezeket is koordinátáknak. Hogy megfelelo oldásnak kínálkozik az adott értéktartományból vett (i, j, k) iterációs vektorok használata. − 1) + a(i, k) · b(k, j) számításhoz például az (i, j, k) koordinátahármast rendelhetjük hozzá. Ugyanígy a c(i, j, k) A fentieket alkalmazva a (7.1) rendszerre, a c(i, j, k) = c(i, j, k = 0 bemeneti muvelethez  is

ugyanazt az (i, j, k) koordinátahármast rendelhetjük hozzá; persze itt minden esetre érvényes, hogy k = 0. Egyébként a példában szereplo értéktartományokat úgy választottuk meg, hogy azok diszjunkt halmazok legyenek. Mivel a számítások, illetve a ki/bemeneti muveletek  jelölésére is ugyanúgy iterációs vektorokat használunk, nincs többé szükség arra, hogy ezt a két fogalmat megkülönböztessük. Ez egyúttal azt is jelenti, hogy az értelmezési tartomány valamely pontjához tartozó  egyenlemuveletek  ismét egy összetett muveletet  képeznek – akkor is, ha ezek különbözo  származnak, és lehet, hogy semmi közük egymáshoz. A továbbiakban az egyszeruség tekbol  kedvéért koordinátaként mindig iterációs vektorokat fogunk használni. 7.17 Diszkrét id®szeletek A szisztolikus cellák által végzett egyes elemi számítási folyamatok mindig diszkrét idosze  letekben mennek végbe. Egy szisztolikus rács esetében minden ilyen

idoszelet ugyanolyan hosszú. Ezen felül a szisztolikus rács minden egyes cellája teljes mértékben szinkron módon  muködik,  azaz mindegyikük egyidoben fejezi be az adott lépéshez tartozó kommunikációs,  illetve a számítási muveleteket.  Az egyes cellák egyes idoszeletei megszakítás nélkül követik egymást. Megjegyzés. Természetesen Albert Einstein felismerései óta tudjuk, hogy zikailag nem tudunk igazi egyidejuséget  létrehozni. A valóságban itt arról van szó, hogy a szisztolikus  rács cellái idoben egymáshoz igazodva dolgoznak. Technikailag ez úgy valósítható meg, hogy a cellákat egy közös ütemjel vézérli, mely a rács összes regiszterét összeköti. Az  ilyen módon elért egyidejuség  keretében a cellák közti kommunikáció eléggé egyidoben megy végbe ahhoz, hogy az egymáshoz kapcsolódó írási, illetve olvasási folyamat során ne vesszenek el adatok. Ennélfogva mindenképpen az a helyénvaló, ha az elméleti

fejtegetések során elvi egyidejuséget  tételezünk fel.  diszkrét idoszeletekre  Emiatt a zikai idot oszthatjuk, folytatólagosan megszámozva az    idoszeleteket. Nem lényeges, hogy az idotengely kezdopontja hol helyezkedik el, hiszen  múlása minden egyes cella számára szinkron módon történik. Kézenfekvo  a t az ido = 0 276 7. Szisztolikus rendszerek (Eberhard Zehendner)  úgy megválasztani, hogy ez éppen annak az idoszeletnek  idot feleljen meg, melynek so bemeneti adat elérkezik valamely cellához. Ezt az egyezményt használva, a rán a legelso (7.1) rendszer (i, j, k)-val jelölt összetett muveletének  elvégzése az i  + j + k − 3 idopontban  + j + k ido- történik. Másrészt ugyanúgy megfelelne az is, ha az (i, j, k) koordinátákat az i ponthoz rendelnénk hozzá; a különbség az eddigiekhez képest csupán annyi, hogy ekkor az  globálisan három egységgel lenne eltolódva. ido Tételezzük tehát fel a továbbiakban, hogy

egy bizonyos (i, j, k) számítás az i + j+k  = 3 idopontban kerül sor, a legutolsó   pedig a t = N1 + N2 + N3 idopontban. A teljes végrehajtási ido  tehát N1 + N2 + N3 −2 idoszeletet   számításra ekkor a t idopontban megy végbe. A legelso tesz ki. 7.18 Küls® és bels® kommunikáció Szisztolikus rácsok esetén a számításokhoz szükséges adatok a számítás kezdetén általában még nincsenek a rács celláiban. Ezeket a rácsba a külvilágból kell betölteni A külvilág egy  gazdagépbol  központi memóriához való hozzáféréssel rendelkezo  áll, melyet egy vezérlo  idopontban  egység vezérel. A vezérloegység a megfelelo kiolvassa a memóriából a szüksé módon továbbítja azokat a szisztolikus rácsnak, illetve a kiszámolt ges adatokat, megfelelo eredményeket visszaírja a memóriába.  idoszeletben  A k-nak megfelelo az aik és bk j operandusoknak minden egyes (i, j) cella rendelkezésére kell állniuk. De a 71 ábrán

látható szisztolikus rács esetén mindössze az  oszlop cellái kapják az A mátrix elemeit közvetlenül a külvilágtól bemeneti adatként. elso Az összes többi cella arra van utalva, hogy a szükséges aik értékeket egy szomszédos cel vízlától kapja meg. Ez, ahogy a 71(a) ábrán is látható, a szomszédos cellák között levo szintes kapcsolatokon keresztül történik. Az aik érték rendre keresztülhalad az (i, 1), (i, 2),  . , (i, N2 ) cellákon Ennek megfeleloen a bk j érték az (1, j) cellán keresztül kerül a rácsba,  onnan pedig a függoleges összeköttetéseken keresztül halad tovább a (2, j), (3, j), . cellákon át, egészen az (N1 , j) celláig Az ábrán látható nyilak hegye azt mutatja, hogy egy ilyen kapcsolat milyen irányban muködik.  Az osztott/párhuzamos architektúrák esetén gyakorta gondot okoz, hogy egy értéket   következik, hogy a mi esetünkben egy idoegység alatt nagy távolságra továbbítsunk. Ebbol  az aik

érték továbbítása az (i, j) cellától az (i, j + 1) cella felé nem ugyanazon az idoszeleten belül történik, melyben az (i, j) cella ezt az értéket az (i, j − 1) cellától vagy a külvilágtól   átvette, hanem egy idoszelettel késobb. Ugyanez érvényes a bk j érték továbbítására is. Ez a késleltetés a részletes cellaszerkezetet bemutató 7.1(b) ábrán világosan látható: minden bemeneti adattól kiinduló útvonal, mely egy cellán vezet keresztül, áthalad egy regiszteren,  és minden egyes regiszter pontosan egy idoszeletnyi késleltetést eredményez.  van írva, hogy a különMegjegyzés. Szisztolikus architektúrák esetében általában elo  cellákat összeköto  útvonalak mindig legalább egy regiszteren keresztül vezessenek bözo  van szó. A szisztolikus rács – akkor is, ha csupán szomszédos cellák közti adatátvitelrol globális ütemjele összekapcsolja a cellák regisztereit. Mindez a szisztolikus rács kapcsola tain

keresztüláramló, jellemzoen ritmikus adatforgalomhoz vezet. A szisztolé” (magyarul ”  vérerekkel szemben fennálló szívösszehúzódás) orvosi kifejezés pontosan emiatt, a lükteto képi rokonság okán vált e fogalom névadójává.  Hogy az adatoknak ezt a késleltetett továbbadását szemléltessük, tovább bovítjük a (7.1) rendszert úgy, hogy a többszörösen olvasott értékek – mint például az aik – számára külön- 277 7.1 A szisztolika alapfogalmai  példányokat vezetünk be (ez egy, a szisztolikus algoritmusok tervezésére alkalmas bözo tipikus eljárásmód): Bemeneti muveletek  a(i, j, k) = aik = bk j c(i, j, k) = 0 b(i, j, k) ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 . 1 i Számítások a(i, j, k) = a(i, j − 1, k) b(i, j, k) = b(i − 1, j, k) c(i, j, k) = c(i, j, k − 1) + a(i, j − 1, k) · b(i − 1, j, k) . ≤i≤ 1 ≤ i ≤ 1 ≤ i ≤ N1 , 1

≤ j≤ N1 , 1 ≤ j ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤i≤ N1 , 1 N2 , k 1 ≤k≤ N2 , 1 ≤ k ≤ N2 , 1 ≤ k ≤ N3 N3 , , (7.3) N3 Kimeneti muveletek  ci j = c(i, j, k) 1 ≤ j≤ = N3 .  A ci j kiszámítását célzó minden egyes c(i, j, k) részösszeg egy bizonyos idoszelet során  idoszeletben,  számítódik ki, és azt csupán egyetlen alkalommal, ti. a következo használjuk.  Az (i, j) cellának tehát szüksége van egy regiszterre (a 7.1(b) ábrán ez a C), amely megorzi  a c(i, j, k) értéket egy idoszelet erejéig. A c(i, j, k) értékre a továbbiakban nem lesz szükség,  regiszter tartalma felülírható a c(i, j, k + 1) értékkel. A skalárszorzat kiszáezért a megfelelo mításának végeztével a regiszterben a c(i, j, N3 ) érték, azaz a kiszámításra váró ci j eredmény  marad meg. A számítások kezdetén a regisztert nulláznunk kell (vagy egy tetszoleges kez doértéket adhatunk neki). Az aik és bk j értékeket ezzel

szemben nem szükséges az (i, j) cellában tárolnunk. Amint a 7.1(a) ábrán vázolt adatbeviteli sémán látható, az A mátrix minden sorának bevitele egy   ohöz  idoegységgel késleltetve van az eloz képest. Ugyanúgy, a B mátrix minden egyes osz  ohöz  lopa egy idoegységgel késleltetve van az eloz képest. Így az a(i, j − 1, k) és b(i − 1, j, k)  értékek pontosan abban az idoszeletben érkeznek az (i, j) cellához, amikor ott a c(i, j, k) érték kiszámítása történik, értékük az A, illetve B regiszterbe íródik, innen viszont azonnal  felhasználjuk oket a szorzás elvégzésére, illetve értékük továbbadódik a szomszédos celláknak. Amint az (i, j) cellában megtörtént az aik és bk j értékek összeszorzása, ebben a cellában  már nincs szükség az értékükre. Emiatt nem fontos az értéküket a cellában tovább orizni,  idoszelet  így az A és B a következo során új értéket fog kapni.  a fejtegetésekbol  máris

kiderül, hogy ahhoz, hogy egy cella tárolókapacitását Ezekbol a minimálisra csökkentsük, ügyelnünk kell arra, hogy a számítási, illetve kommunikációs  folyamatokat úgy irányítsuk térben és idoben, hogy az azonnali felhasználás, illetve tovább legrövidebb ideig kelljen csupán tárolni. A szisztolikus rács adás révén az adatokat a leheto  ki/beviteli séáltalános felépítésén túl ezt lényegében azzal érhetjük el, hogy egy megfelelo  módon állapítjuk meg a cellákon belüli késleltetési idoket.  mát választunk, illetve megfelelo A példában látható ki/beviteli séma geometriai elrendezése az A és B mátrixok szétdarabolásának eredményeként született. A bemeneti adatfolyamokban ezáltal szabaddá vált helyeket null-értékekkel töltjük fel, különben elrontanánk a ci j értékek kiszámítását.  függ. A bemeneti adatfolyamok hossza a feladat N3 paraméterétol 278 7. Szisztolikus rendszerek (Eberhard Zehendner) A

C mátrix elemeinek kiszámítása a 7.1 ábra alapján stacionárius módon történik, ami azt jelenti, hogy valamely mátrixelem végleges értéke kiszámításának lépései ugyanabban a cellában mennek végbe. A stacionárius változók egyáltalán nem mozdulnak a számítások során a szisztolikus rácson belül. Az eredményeket végül továbbítanunk kell a rács pere cellákhoz, mivel csak ezeken keresztül tudjuk átadni oket  mén levo a külvilágnak. Ráadásul  gyelembe kell vennünk azt is, hogy a ci j kiszámítására szolgáló regisztereket kezdoérték feladat megoldása elég nagy idobeli,  kel kell ellátnunk. E két különleges kiegészíto illetve anyagi ráfordítást igényel, de ezt a 7.4 alfejezetben még pontosabban megvizsgáljuk majd 7.19 Futószalag-elv¶ feldolgozás  módon diszkrét, egyforma hosszúságú, globálisan szinkronizált idoszeletekkel  A jellemzo  szigorú ido való munkamódnak, illetve a cellák egymástól

regiszterek segítségével történo  beli elszigeteltségének köszönhetoen, a szisztolikus rácsokat a futószalag-elvu  feldolgozás egy sajátos alkalmazásának tekinthetjük. A cellák regiszterei ez esetben a jól ismert futószalag-regisztereknek felelnek meg. A klasszikus értelemben vett futószalag kétségkívül mindig lineáris felépítésu,  míg a szisztolikus rácsok szerkezete (amint az a példából is látszik) gyakorta kétdimenziós. Egy többdimenziós szisztolikus rácsot felfoghatunk úgy,  áll. Természetesen egyértelmu, mint ami több, egymásba fonódó futószalag szövedékébol   sajátosságok a többhogy az egydimenziós futószalagelvu  feldolgozásra érvényes alapveto  dimenziós szisztolikus rácsoknál ugyanúgy fellelhetoek. A futószalagelvu  feldolgozás egyik tipikus velejárója, hogy a hatékonyság kisebb a számítások kezdetén, illetve végén. Eleinte a futószalag üres, egyetlen fokozata sem dolgo  fokozat

rendelkezik adatokkal és ez végez számításokat; zik. Ezt követoen csupán az elso  idoszeletben  az összes többi fokozatnak továbbra sincs semmi tennivalója. A következo az  fokozat adatokat ad át a következonek,  elso ugyanakkor maga is újabb adatokat kap; csak ez a két fokozat dolgozik. Ez így megy tovább mindaddig, amíg végül minden fokozat  ízben állíthatjuk a futómegtelik adatokkal, és a futószalag dolgozza fel ezeket, vagyis elso  hogy teljes hatékonysággal dolgozik. Néhány ilyen teljes telítettségu szalagrol,  lépés után,   függ, egyszer csak elfogy a bemeneti adat, melynek idotartama az adatfolyamok méretétol  fokozata tehát abbahagyja a muködést.  idoszeletben  a futószalag elso  A következo a második fokozat is abbahagyja a munkát, majd ugyanígy tovább, míg legvégül egyetlen fokozat  illetve végso  munkaszakasz csökkenti a teljes futószalag átlagsem dolgozik már. A kezdo, teljesítményét, és ennek a

teljesítménycsökkenésnek a viszonylagos értéke annál nagyobb, minél több fokozata van a futószalagnek az adatfolyamok hosszához képest.  Ugyanezt a jelenséget a maga sajátos mivoltában kitun  oen vizsgálhatjuk a 7.1 ábrán bemutatott szisztolikus rács esetében. Itt is találunk a számítások kezdetén, illetve végén  idoszeletben  szinte tétlenül álló cellákat. Az elso csupán az (1, 1) cella végez hasznos munkát; az összes többi cella is dolgozik ugyan, de csak üresjáratban. A második lépésben eh hez hozzáadódnak még az (1, 2) és (2, 1) cellák; ezt az idoszeletet szemlélteti a 7.2(a) ábra Mindez ugyanígy folytatódik, míg végül az (N1 , N2 ) cella is hozzá nem járul a számításokhoz. Amint a legutolsó tényleges adat elhagyta az (1, 1) cellát, ez többé nem járul hozzá a számításokhoz, csupán a már kiszámolt c11 értéket fogja újra és újra reprodukálni. Lé lépésre egyre több cella hagyja abba az aktív

tevékenységet, míg legvégül már csak pésrol  az (N1 , N2 ) cella végzi el az utolsó fontos számítást; a 7.2(b) ábra szemlélteti ezt a végso  idoszeletet. 279 7.2 Tér-ido-leképezés  és szisztolikus rács b41 b32 b23 b31 b22 b13 x a14 a13 a12 ∗ b21 a11 ∗ b12 a23 a22 a21 ∗ b11 x a32 a31 x c15 c33 (a) c24 c25 c34 a34 ∗ b45 (b) 7.2 ábra Két kiragadott helyzetkép a 71 ábrához (részletek) Megjegyezzük, hogy a képletekben a szorzás jelölésére pontot használunk, az ábrákon azonban csillagot. Gyakorlatok 7.1-1 Hogyan kellene módosítani a 71(a) ábrán bemutatott beviteli adatsémát, ha ugyanazon szisztolikus rács segítségével egy (2 × 6)-os és egy (6 × 3)-as mátrixot szeretnénk  összeszorozni? Átszervezhetok-e a számítások oly módon, hogy az eredménymátrix a szisztolikus rács jobb alsó sarkába kerüljön? 7.1-2 Miért fontos a 71 ábra szerinti mátrixszorzás szempontjából, hogy a

beviteli folyamokban a nem használt helyekre 0 értékeket helyezzünk? Miért nem lényeges ugyanez a B mátrix esetében? 7.1-3 Ha a 71 ábrán látható szisztolikus rácsot futószalagként kellene értelmezzük, hány  fokozatra lenne szükségünk ahhoz, hogy megfeleloképpen tudjuk leírni ennek viselkedését? 7.2 Tér-id®-leképezés és szisztolikus rács  o  alfejezetben leírt bevezeto  elegendo  ugyan egy egyszeru Az eloz  fogalom megalkotásához, de akkor már nem elég, ha a szisztolikus rács tulajdonságait mennyiségileg pontosan szeretnénk megragadni és értékelni. Különösen a paraméteres feladat-meghatározás bevezetése igényel matematikai segédeszközöket Ezért ez az alfejezet az egyenletes szisztolikus algoritmusok lineáris leképezésekre alapozó elméletének központi kérdéseivel foglalkozik. 280 7. Szisztolikus rendszerek (Eberhard Zehendner) C * + B A (a) (b) 7.3 ábra Hexagonális szisztolikus rács mátrixszorzáshoz:

(a) a rács felépítése és az adatok bevitelének/kivitelének elve; (b) cellaszerkezet. 7.21 Példa: mátrixszorzás stacionárius változók nélkül A (7.3) rendszer nem csak a 71 ábrán bemutatott szisztolikus rács segítségével számolható ki, hanem sok más szisztolikus ráccsal is. A 73 ábra példa egy ilyen szisztolikus rácsra Bár ugyanazt a függvényt értékeli ki, mint a 7.1 ábrán látható rendszer, a képi megjelenése teljesen más: • a cellák száma itt lényegesen nagyobb, 15 helyett összesen 36; • a rács körvonala hexagonális, téglalap alakú helyett; • minden cellának három bemenete és három kimenete van; • az adatok bevitele lényegesen másképp történik, mint a 7.1(a) ábrán; • végül: itt a C mátrix elemei is végighaladnak a rácson.  látásra nem tunik  A 7.3(b) ábrán látható cellaszerkezet elso  lényegesen különbözonek  a 7.1(b) ábrához képest A különbségek azért mégis jelentosek: az új

cellában nincs cikli kus út, így stacionárius változók itt nem jelennek meg. Ehelyett a cellának három bemeno,  csatornája van, melyeken keresztül a három mátrix elemei haladnak. illetve három kimeno  kommunikáció iránya a cella jobb és bal oldalán megváltoA csatornákon keresztül történo zott, a mátrixok csatornákhoz való hozzárendelése úgyszintén. 281 7.2 Tér-ido-leképezés  és szisztolikus rács 7.22 A tér-id® leképezés, mint globális szemléletmód Hogyan függ tehát össze a (7.3) rendszer és a 73 ábra? A 71 fejezetben bemutatott szisztolikus rács muködését  minden segítség nélkül jól tudtuk követni. Az alábbi példa esetén ez azonban lényegesen nehezebb – így sokkal inkább indíttatást érzünk egy matematikai segédeszköz használatára. Ahhoz, hogy le tudjuk írni a szisztolikus rácson belül végzett muveleteket,  minden ilyen  mértéket rendelhetünk hozzá: az idoszeletet,  muvelethez  két alapveto

melyben a muvelet   végrehajtásra kerül, illetve a cellát, amely a muveletet  végrehajtja. Amint ez a késobbiekben még inkább nyilvánvalóvá lesz, a tér-ido-leképezés  megválasztásával tulajdonképpen ki is merítettük a tervezéssel kapcsolatos szabadságunkat; szinte minden további elem kényszeru    módon következik a tér-ido-leképezésb ol. Akárcsak a 7.1 ábra szisztolikus rácsa esetében, a 73 ábrán látható szisztolikus rácsban is a t  = i + j + k idopontban történik az (i, j, k) elemhez kapcsolódó számítások elvégzése.   π= 1 1 1 (7.4) Ugyanezt egy idovektor  és egy v = (i, j, k) iterációs vektor skalárszorzataként is leírhatjuk, t =π·v ,    ·   esetünkben tehát t =  1 1 1 i j k (7.5)     = i + j + k . (7.6) = (x, y) térkoordinátáit, a 7.13 = (i, j, k) iterációs vektorokból következtethet3 az R tér k tengely menti projekcióját végzi

el. ! A 7.1 ábrán látható példában végrehajtott muveletek  z pontban leírt egyezményünk alapján a v jük ki. Az itt megválasztott leképezés Ez a lineáris leképezés egy P = 1 0 0 0 1 0 (7.7) projekciós mátrix segítségével írható le. A térkoordinátákat úgy kapjuk, hogy a projekciós mátrixot megszorozzuk a v iterációs vektorral, amit az alábbi módon írhatunk le: z = P ·v . (7.8) A projekció irányát az a vektor adja, amely ortogonális a projekciós mátrix minden sorára nézve: P · u = ~0. (7.9)  P projekciós mátrix számára például u A (7.7)-ben szereplo = (0, 0, 1) egy lehetséges pro- jekciós vektor. Szisztolikus rácsok tervezésénél gyakran alkalmaznak projekciókat a térkoordináták meghatározására. A 73(a) ábrán látható példánkban is az iterációs vektorokra alkalmazott projekció útján kapjuk a térkoordinátákat. Tekintsük adottnak az alábbi projekciós mátrixot: P = 0 −1 1 −1 1

0 ! . (7.10) 282 7. Szisztolikus rendszerek (Eberhard Zehendner) Egy hozzá tartozó lehetséges projekciós vektor u = (1, 1, 1).  A projekciós mátrixot és az idovektort összegezhetjük egy T mátrix segítségével, mely magát az úgynevezett tér-ido-leképezést  írja le: z t ! = P π ! ·v=T ·v . (7.11) 283 7.2 Tér-ido-leképezés  és szisztolikus rács  két sorát a P projekciós mátrix adja, a harmadikat pedig a T elso  π idovektor.  példa esetén a tér-ido-leképezés   A 7.1 ábrán szereplo T mátrixa a következo: T    =   1 0 0 0 1 0 1 1 1     , (7.12)  példa esetén pedig a 7.3 ábrán szereplo T   0  =  −1  1 −1 1 1 0 1 1     . (7.13)  A tér-ido-leképezést a szisztolikus rácsra vonatkozó globális szemléletmódként is fel foghatjuk. Amennyiben egy (esetünkben lineáris,

T -vel jelölt) tér-ido-leképezést alkalma iszunk egy rekurzív egyenletrendszerre, máris láthatóvá válnak a szisztolikus rács külso mérvei, azaz a felépítése (térkoordináták, kapcsolatrendszer, cellaszerkezet). Megjegyzés. Tisztán lineáris leképezések helyett affin leképezések is szóba jöhetnek, melyeknek egy vektor-komponensük is van, például T · v + h. Affin leképezésekre vi-  szont nincs feltétlenül szükségünk, amíg minden iterációs vektort ugyanazzal a tér-idoleképezéssel kezelünk. 7.23 A térkoordináták szimbolikus meghatározása Amikor az értéktartományok számszeruen  adottak, és eléggé kicsik, a (7.11) összefüggés segítségével könnyuszerrel  kiszámíthatjuk a térkoordináták konkrét halmazát. Amennyiben az értéktartományok paraméteresek, mint a (7.3) rendszer esetében, a cellák helyzetét szimbolikusan kell meghatároznunk Az alábbiakban leírtak e feladat megoldását célozzák Minden egyes

cellát egy z = (x, y) térkoordinátájú pontnak tekintünk az R2 kétdimen- ziós térben. Az S értéktartomány minden egyes iterációs vektorából a (78) kifejezés segítségével egy-egy processzor (cella) z térkoordinátáit kapjuk, z = P · v, így a v-vel jelölt muvelet  a z cellára lesz rávetítve. Az így kapott térkoordináták halmaza P(S ) = {P · v : v ∈ S } adja meg a szisztolikus rács muködése  szempontjából fontos összes cella helyzetét.  melyek egy konvex terület (itt Általában olyan értéktartományok fordulnak elo, R3 -ból)  meg (sur összes egész koordinátájú pontjának halmazaként jeleníthetok  u  konvex értéktartományok). Egy ilyen (véges számosságú) értéktartomány konvex burka egy politóp, melynek  csúcsai az értéktartomány pontjai. A politópokat tetszoleges lineáris leképzés újabb politóppá alakítja. Kihasználhatjuk tehát, hogy minden projekció lineáris leképezés Az újonnan 

politóp csúcsai az eredeti politóp csúcsainak projekciói. keletkezo Megjegyzés. Nem szükséges, hogy a projekció során az eredeti politóp minden csúcsa az új politópnak is csúcsa legyen. Lásd például a 74 ábrát A Z3 rács projekciója egy egész számú P projekciós mátrix által a amennyiben a P-t egy Z2 rácshoz vezet,  π egész számú idovektor megválasztásával egy unimoduláris T mát- rixra egészítjük ki. Ez egy sur  u  konvex értéktartományt (néhány, az alkalmazás szempontjá eltekintve) a koordináták sur ból lényegtelen kivételtol  u  konvex halmazává alakítja, melyet az ezt burkoló politóp csúcsai teljes mértékben jellemeznek. 284 7. Szisztolikus rendszerek (Eberhard Zehendner) (1 − N2 , N2 − N1 ) (1 − N2 , N2 − 1) (N3 − N2 , N2 − N1 ) (0, 1 − N1 ) (N3 − N2 , N2 − 1) (0, 0) (N3 − 1, 1 − N1 ) (N3 − 1, 0) 7.4 ábra Egy téglalap alakú értéktartomány projekciójának eredménye

Megjegyzés. Egy mátrixot unimodulárisnak nevezünk, amennyiben négyzetes, csak egész számú bemenetei vannak és a determinánsa ±1. Az unimoduláris mátrixok inver- tálhatók, és inverzük szintén unimoduláris. Alkalmazzuk ezt a módszert a (7.3) rendszer S = [1, N1 ] × [1, N2 ] × [1, N3 ] (7.14) egész számokat tartalmazó értéktartományára. A konvex burok csúcsai esetünkben (1, 1, 1), (N1 , 1, 1), (1, N2 , 1), (1, 1, N3 ) , (1, N2 , N3 ), (N1 , 1, N3 ), (N1 , N2 , 1), (N1 , N2 , N3 ) . (7.15) A (7.10)-beli P projekciós mátrix esetén a projekció csúcsainak helyzete − 1, 0), (N3 − 1, 1 − N1 ), (0, 1 − N1 ) , − N2 , N2 − N1 ), (1 − N2 , N2 − 1), (N3 − N2 , N2 − N1 ) . (N3 (1 (7.16) Mivel S -nek nyolc csúcsa van, a P(S ) képének viszont csupán hat, világos, hogy az S  részébe fog vetítodni,  két csúcsa a terület belso tehát a mértékek meghatározásában nem játszik szerepet; ezek az (1, 1, 1) és az (N1 , N2 ,

N3 ) csúcsok. Konkrétan N1 = 3, N2 = 5 és N3 = 4 esetében a (3, 0), (3, −2), (0, −2), (−4, 2), (−4, 4) és (−1, 4) csúcsok adódnak. Láthatjuk, hogy nem kell minden térkoordinátának feltétlenül  pozitívnak lennie. A koordinátarendszer kezdopontjának megválasztása, mely esetünkben a politóp belsejében helyezkedik el, szintén nem nyilvánvaló.  oldalai párA projekció eredményeként egy hatszöget kapunk, melynek szembefekvo huzamosak. Ennek peremén mindig N1 , N2 vagy N3 egész számú pont helyezkedik el Az  példával ellentétben itt tehát a feladat minden paramétere egyúttal a rács paramétere is. elso Ennek a szisztolikus rácsnak a körvonalát hexagonálisnak nevezzük. 285 7.2 Tér-ido-leképezés  és szisztolikus rács N3 N2 N1 7.5 ábra A térkoordináták halmazának részekre bontása Ennek a tartománynak az F felülete Θ(N1 N2 + N1 N3 + N2 N3 ), mely egyformán függ  Itt tehát egészen más helyzettel

találkozunk, mint a 7.1(a) ábrán, mindhárom mátrixmérettol. ahol (ugyanennek a feladatnak!) a bonyolultsága csupán Θ(N1 N2 ) volt.  Ezután a hozzávetoleges számolás után most megszámoljuk egész pontosan a cellákat. Ehhez a számoláshoz célszeru  az egész tartományt résztartományokra bontani, melyekben a cellák száma könnyuszerrel  meghatározható (lásd 7.5 ábra) A (0, 0), (N3 − 1, 0), (N3 − − N1 ) és (0, 1 − N1 ) pontok egy N1 N3 cellát tartalmazó téglalapot határolnak körül. Ha eltoljuk ezt a ponthalmazt N2 − 1 cellával feljebb és N2 − 1 cellával jobbra, végigjárjuk 1, 1 ezzel a teljes tartományt. Minden alkalommal azonban, amikor a téglalapot egy cellával + N3 − 1 új cella jön hozzá az eddigiekhez. Ez összesen + (N2 − 1)(N1 + N3 − 1) = N1 N2 + N1 N3 + N2 N3 − (N1 + N2 + N3 ) + 1 cellát tesz ki. Például N1 = 3, N2 = 5 és N3 = 4 esetében 36 cellát kapunk, amint az a 7.3(a) ábrán feljebb és jobbra

toljuk, csupán N1 N1 N3 látszik is. 7.24 A teljes végrehajtási id® szimbolikus kiszámítása Egy szisztolikus algoritmus teljes végrehajtási idejének szimbolikus kiszámítása a 7.23  pontban leírtakhoz hasonló módon történik. Az idoleképezés a (7.5) összefüggés alapján  illetve utolsó számításnak megfelelo  idoszeletet  szintén lineáris leképezés. Az elso, a szá mítási idopontok π(S ) = {π · v : v ∈ S } halmazának minimuma, illetve maximuma adja. A  ha az S konvex burkának v csúcsait vesszük gyelembe. fentebb leírtak alapján elegendo,  képlet alapján számíthatjuk ki: A teljes végrehajtási idot  a következo tΣ = 1 + max P(S ) − min P(S ) . (7.17)  és a legutolsó számítás idopontja  Az 1 hozzáadása mindenképpen fontos, mert a legelso is számít. 286 7. Szisztolikus rendszerek (Eberhard Zehendner) A 7.3 ábrán látható példa esetében a (76) összefüggést alkalmazva a (715)-ben kiszá képek

halmazát kapjuk: {3, 2 + N1 , 2 + N2 , 2 + N3 , 1 + N1 + molt politópcsúcsokra, a következo N2 , 1 + N1  mely szerint N1 , N2 , N3 ≥ 1 + N3 , 1 + N2 + N3 , N1 + N2 + N3 }. Az alapfeltevésbol, + N2 + N3 , a teljes végrehajtási ido  pedig N1 + N2 + N3 − 2 idoegységet tesz ki (akárcsak a 7.1 ábrán látható szisztolikus rács következik, hogy a minimum 3, a maximum pedig N1  esetén – elvégre az értéktartomány és az idovektor megegyezik a két példában). = 3, N2 = 5 és N3 = 4 konkrét értékeket adva a  − 3 + 1 = 10 idoszeletet tesz ki. 2 Ha N1 = N2 = N3 , akkor a szisztolikus algoritmus egy Θ(N ) cellát tartalmazó rend alatt határozza meg két, N × N méretu szerrel Θ(N) ido  mátrix szorzatát. A feladat paramétereinek az N1  12 kiszámolt teljes végrehajtási ido 7.25 A kapcsolatszerkezet levezetése  A szisztolikus rács kapcsolatszerkezetét úgy kapjuk, hogy a tér-ido-leképezést alkalmazzuk  a feladat adatfüggoségeire.  Minden

egyes adatfüggoség abból adódik, hogy egy változó bizonyos példányát közvetlen módon felhasználjuk ugyanazon vagy egy másik változó egy példányának kiszámolására. Megjegyzés. A szisztolikus rácsoknál – az imperatív programnyelven megírt programok  párhuzamos párhuzamos végrehajtásánál szükséges adatfüggoség vizsgálatok helyett, melyeket vagy a párhuzamosan optimalizáló fordító és/vagy a processzor végez el – csupán   van szó. Ez az általunk használt hozzárendelésmentes jelölés követfolyamfüggoségekr ol kezménye.  Az adatfüggoségeket úgy tudjuk leolvasni, hogy az értékadásmentes jelölés kvantikált  egyenletének egyszerre szemléljük a jobb és bal oldalát. Mindenekelott a (7.3) rendszer c(i, j, k) = c(i, j, k − 1) + a(i, j − 1, k) ∗ b(i − 1, j, k) egyenletét vizsgáljuk. A c(i, j, k) érték kiszámítása a c(i, j, k − 1), a(i, j − 1, k) és b(i − 1, j, k) értékek segítségével történik.

Van tehát egy adatfolyamunk c(i, j, k a(i, j  c(i, j, k) irányában, egy adatfolyam − 1)-tol − 1, k)-tól c(i, j, k) irányában és egy adatfolyam b(i − 1, j, k)-tól c(i, j, k) felé. Egy ilyen adatfolyam számunkra fontos sajátosságait egy függoségi  vektor segítségével írhatjuk le. Ezt a kiszámolt változópéldány iterációs vektora, illetve az ennek kiszámításához éppen használt változópéldány iterációs vektora közti különbségvektor adja A c(i, j, k) iterációs vektora (i, j, k), a c(i, j, k különbségvektor pedig dC    =          −  i j k  kapott − 1)-é pedig (i, j, k − 1). Az ebbol i j k −1        =  0 0 1     . (7.18)  módon kapjuk: Ugyanúgy, megfelelo dA és dB    =      = 

 i j k i j k        −  i j −1 k     i − 1    −  j k        =         =  0 1 0 1 0 0         . (7.19) (7.20) 287 7.2 Tér-ido-leképezés  és szisztolikus rács A (7.3) rendszer a(i, j, k) = a(i, j − 1, k)  hogy egyenletében közvetlenül felismerheto, melyik a kiszámolt változópéldány, és melyik a kiszámításához szükséges változópéldány. Itt láthatjuk tehát a különbséget egyenlet és értékadás között. Tekintve, hogy a(i, j, k)-t a(i, j  − 1, k)-ból másolás révén kapjuk, ugyanazt a függoségi vektort kapjuk, mint a (7.19) = b(i − 1, j, k) egyenletre is. Amennyiben egy változópéldány a v iterációs vektorral

rendelkezik, azt a P · v cellában kifejezésben. Ugyanez érvényes a b(i, j, k) 0  váltoszámítjuk ki. Ha ennek kiszámításához egy másik, v iterációs vektorral rendelkezo 0  = v − v0 függoségi 0 v cellától a z = P · v cella zópéldányra is szükség van, akkor ez a P · v cellában számítódott ki és d 0  vektor jellemzi a köztük fennálló adatfüggoséget. Ez a z = P ·  kommunikációt feltételez. Szisztolikus rácsok esetében ezt a kommunikációt a felé történo kommunikáló cellák közti közvetlen, statikus kapcsolat biztosításával oldják meg. A (78) leképzés lineáris voltából következik, hogy z Amennyiben P ·d = ~0, − z0 = P · v − P · v0 = P · (v − v0 ) = P · d.  cellán belül történik, ami a kommunikáció a számítást végzo   azt jelenti, hogy az csak idoben, de nem térben zajlik. Az értékek továbbadása idoben a  cella regiszterein keresztül valósul meg. számítást végzo · d ,

~0, akkor két különbözo cella közötti kommunikációra lesz szükség. Ekkor a szisztolikus rács összes cellájához hozzá kell rendelni egy P · d irányú kapcsolatot.  cella z térkoordinátájától a vektor irányításával Meghúzzuk a P · d vektort a számítást végzo Ha viszont P 0 ellentétesen haladva, és a z-t ellátó, z térkoordinátájú cellához jutunk.   Ha több ilyen d függoségi vektorunk van, mindegyikhez tartozik egyegy neki megfelelo kapcsolat. Tekintsük például a (718), (719), (720) és (710) összefüggéseket A követke állnak fenn: P · dA zok = (−1, 1), P · dB = (0, −1) és P · dC = (1, 0). A három P · d vektornak  kapcsolatokat a 7.3(a) ábrán minden egyes cellánál meggyelhetjük Ez egy hemegfelelo xagonális kapcsolatszerkezetet eredményez (az eddig ismert ortogonális helyett). 7.26 A cellaszerkezet meghatározása  Most átvisszük a 7.25 pontban tárgyalt, térrel kapcsolatos fejtegetéseket az idobeli

össze változópéldány kiszámítására a függésekre. Egy v iterációs vektorral rendelkezo 0 szeletben kerül sor. Amennyiben ennek kiszámításához egy másik, v  változópéldány szükséges, akkor ez utóbbi értéke a rendelkezo π· π·v  ido- iterációs vektorral 0  v idoszeletben került 0 = v−  π · v − π · v0 idoszeletet vesz igénybe. kiszámításra. A d   kommunikáció tehát pontosan v függoségi vektornak megfelelo Mivel a (7.6) leképezés lineáris, fennáll π· v −π· 0 v = π· (v − 0 v ) = π· d. Mivel a szisztolikus alapelv szerint minden egyes kommunikáció legalább egy regiszteren vezet   keresztül, a d függoségi vektorok pedig rögzítettek, az idovektor megválasztását a π·d ≥1 (7.21) feltétel korlátozza. P · d = ~0 esetén az éppen szükséges érték tárolása céljából egy regiszterre van szükség  idoszeletben  minden egyes cellában. Mivel egy ilyen regiszter tartalma

a következo máris felülíródik egy újabb értékkel, a régi értéket egy további regiszterbe kell átmentenünk, amennyiben π·d ≥ 2 fennáll. Mivel mindez   π · d idoszeleten belül megismétlodik minden π · d regiszterre van szüksége, melyeken az egyes tárolt érték esetén, a cellának pontosan  értékük a következo  cellának adódik át. Az elobb  értékek rendre keresztülhaladnak, mielott  vázolt helyzetnek megfeleloen, P · d , ~0 esetében az adatátvitel ugyancsak π·d regiszte- 288 7. Szisztolikus rendszerek (Eberhard Zehendner)  cellában ren keresztül történik, itt azonban nem fontos, hogy ezek mind a számítást végzo legyenek elhelyezve.   regiszterekre. A 73(b) Minden egyes d függoségi vektor esetén szükség van megfelelo  ábrán a cellához rendelt három bemenetet láthatjuk, melyek a dA , d B és dC függoségi vektoroknak felelnek meg. Mind a három vektor esetében fennáll, hogy a P és (7.4)

összefüggések következtében π·d = · d , ~0, illetve (7.6)  1. Tehát minden egyes d függoségi vektor- hoz egyetlen regiszterre van szükség. A (73) rendszer szabályos volta miatt a cella három bemenetéhez ugyanakkor három kimenet tartozik, a cella középpontjához képest egymással ellentétes pozícióban.  Mivel a d függoségi vektorok száma egy (7.3)-hoz hasonló rendszer által statikusan  π·d érték rögzített és többnyire kicsi, egy cellának általában korlátozott, és a nekik megfelelo kevés regiszterre van szüksége.  A cella három be-, illetve kimenete három dinamikus mátrix használatát teszi lehetové. A 7.1 ábrával ellentétben egy P4 k=1 aik · bk j skalárszorzat kiszámítása itt nem egyetlen cellá- ban történik, hanem a szisztolikus rács cellái közt felosztva. Itt tehát feltétlenül szükséges, hogy az összeget részösszegek sorozatára bontsuk. Ez tehát példa egy szétosztott generikus operátorra. A három

bemeneten, a hozzátartozó regisztereken és a három kimeneten kívül a 7.3(b) ábrán egy szorzót láthatunk egy sorosan hozzákapcsolt összeadóval. A (78) leképezés alkalmazása a (73) rendszer c(i, j, k) = c(i, j, k − 1) + a(i, j − 1, k) ∗ b(i − 1, j, k) egyenletének S értéktartományára a fent említett két egység összes cellában való jelenlétét eredményezi. Mivel az egyenlet alapján az összeg felépítése csakis a szorzat sikeres végrehajtása után  következik a két operátor 7.3(b) ábrán látható sorrendje lehetséges, ebbol  operandusok honnan származnak, az a hozzájuk tartozó függoségi  Hogy a megfelelo vektorok projekciójából olvasható le. Így például a(i, j − 1, k)-hoz a dA vektor tartozik. Ennek projekciója, P · dA  = (0, 1, 0) függoségi = (−1, 1), az A mátrix haladási irányát mutatja. A  processzor szemszögébol  nézve az ezzel ellenbeolvasandó adatot ezért, a számítást végzo tétes (1, −1)

irányból kell várni, vagyis a cella bal alsó sarkához kapcsolódó csatornából (de − 1, j, k) jobb oldalról jön (a B regiszteren keresz (a C regiszteren keresztül). A megfelelo  a(i, j, k), b(i, j, k) és − 1) pedig fentrol az A regiszteren keresztül). Ugyanígy b(i tül), c(i, j, k c(i, j, k) értékek a szemközti irányba csatornákon keresztül továbbítódnak: jobbra, felfelé, bal alsó irányba. Másrészt, a (7.7)-beli P projekciós mátrixot alkalmazva a dC -re a (0, 0) projekciót kapjuk Mivel ugyanakkor π · dC = 1, következik, hogy pontosan egy C regiszterre van szükség a C mátrix minden egyes eleme számára. Ez a regiszter szolgáltatja a c(i, j, k) érték kiszá mítására a c(i, j, k − 1) értéket, majd a számítást követoen felveszi a c(i, j, k) értékét. Mindez  A 7.1(a) ábra ennek megfeleloen  a 7.1(b) ábrán jól követheto azt mutatja, hogy a C mátrix számára nincs szükség cellák közti kapcsolatra: a mátrix

stacionárius. Gyakorlatok  P projekciós mátrixot találunk. 7.2-1 Egy u projekciós irányhoz mindig több különbözo a. Mutassuk meg, hogy a P = 0 1 −1 ! −1 0 1 projekciós mátrix is megfelel az u = (1, 1, 1) projekciós iránynak. 289 7.3 A be/kiviteli séma levezetése b. Számítsuk ki ennek a projekciós mátrixnak a segítségével a (7.3) rendszer értéktartományát c. Az így kapott térkoordináták különböznek a (7.23) pontban adottaktól Miért mondhatjuk mégis, hogy a két esetben kapott ponthalmazok topológiai szempontból ekvivalensek? d. Tanulmányozzuk a cellák elhelyezkedését a két esetben, hasonlóságokat és különbségeket keresve. 7.2-2 Végezzük el a 72 alfejezetben leírt számításokat a (73) rendszerrel és a T    =   1 0 1 0 1 1 1 1 1      tér-ido-mátrixszal kapcsolatban. 7.3 A be/kiviteli séma levezetése A 7.3(a) ábrán a be/kiviteli

séma az A, B, C mátrixokhoz tartozó adatfolyamok irányával van csupán megadva. Az adatok be/kivitelével kapcsolatos folyamatok megértéséhez szükséges részleteket a 7.6 ábra tartalmazza A 7.6 ábrán látható be/kiviteli séma a 71(a) ábrához képest egy sor új mozzanatot tartalmaz. Itt is egy bemeneti, illetve kimeneti adatfolyam áramlik keresztül mindegyik közönséges peremcellán, a szisztolikus rács sarkaihoz pedig két-két adatfolyam tartozik Az egy mátrixhoz tartozó beviteli cellák persze itt már nem egy egyenes vonal mentén helyezkednek el, hanem két, egymással határos perem mentén.  A 7.6 ábrán látható adatszerkezeteknek ugyanakkor más a dolésszögük, mint a 7.1(a) ábrán. Ezen kívül a 76 ábrán az A és B mátrix a 71(a) ábrához viszonyítva adatfolyamonként kétharmaddal csökkentett sebességgel érkezik Kevés fáradozással alapjában véve itt is lehetséges az, hogy az adott szisztolikus rácshoz elemi szinten próbáljunk

találó ki/beviteli sémát építeni.  út. A következo  Sokkal biztosabb azonban egy formális levezetésen keresztül vezeto pontokat az eljárás egyes lépéseinek bemutatásának szenteljük. 7.31 Az adatszerkezetek indexeit®l az iterációs vektorokig  az absztrakt adatszerkezetek és az értékadásmentes jelölésmód konkrét válMindenekelott tozópéldányai közti összefüggést kell megvilágítanunk. Az A mátrix minden eleme egy i sorindexszel és egy k oszlopindexszel van ellátva. = Ezt a két indexet egy w (i, k) adatszerkezet-vektorral foghatjuk össze. Az aik elem a  (7.3) rendszer a(i, j, k) példányának felel meg, tetszoleges j-vel. E példány koordinátái nek elemei, és mind egy egyenesen helyezkednek el a q R3 = (0, 1, 0) irány mentén. Az (i, k) adatszerkezet vektortól az (i, j, k) koordinátákra való átmenetet az alábbi leképezés írja le:     i j k      

 =  1 0 0 0 0 1     · i k !    + j ·   0 1 0        +  0 0 0     . (7.22) 290 7. Szisztolikus rendszerek (Eberhard Zehendner) c35 c25 c34 c15 c24 c33 c14 c23 c13 c32 c22 c12 c31 c21 c11 b15 b25 b14 b24 b35 b13 b45 b12 b23 b34 b11 b22 b33 b44 b43 b21 b32 b31 b42 b41 a11 a21 a12 a31 a22 a32 a13 a23 a33 a14 a24 C B A a34 7.6 ábra Részletes be/kiviteli séma a 73(a) ábrához A (7.3) rendszerben használt alak esetén minden egyes változópéldány (i, j, k) koordináta vektora pontosan megegyezik az értéktartomány azon iterációs vektorával, melynek kap változópéldány kiszámítása történik. Ezért a (722) képletet az adatszerkezet csán az illeto vektorok és az iterációs vektorok között fennálló összefüggésként is felfoghatjuk. Absztrakt  v iterációs vektorokat

megkaphatjuk a módon kifejezve, a megfelelo v = H ·w+λ·q+ p (7.23) képlet segítségével a w adatszerkezet vektorból. A p affin vektor a mi példánk esetén mindig a nullvektor, általános esetben viszont szükség lesz rá. Mivel b(i, j, k) = bk j , a B mátrixnak megfelelo megjelenítés az alábbi:         !  1   0   i   0 0  k      j  =  0 1  · + i ·  0  +  0  .     j     k 1 0 0 0 (7.24) 291 7.3 A be/kiviteli séma levezetése Ami a C mátrixot illeti, minden c(i, j, k) változópéldány szükséges egy másik érték  c(i, j, k) példányt kiszámításához. Viszont az összes rögzített (i, j) indexpárral rendelkezo tekinthetjük úgy, mint ami a ci j mátrixelemhez tartozik, mivel ezek közvetlenül a ci j

ki operátor sorba fejtésébol  származnak. A (723) képletnek számítására használt összegzo   megfeleloen tehát C-re a következoket kapjuk:     i j k        =  1 0 0 1 0 0     · i    + k ·   ! j 0 0 1        +  0 0 0     . (7.25) 7.32 Adatszerkezetekr®l készült helyzetképek Az A, B és C mátrixok mindegyike az adatszerkezet két indexének iránya mentén jött létre: egy sor, illetve egy oszlop mentén. A (0, 1) különbségvektor írja le az átmenetet  a másikra ugyanazon a soron belül, azaz a következo  oszlopbeli elemet adja: egyik elemrol (0, 1) = (x, y + 1) − (x, y). Ugyanígy az (1, 0) különbségvektor az ugyanabban az oszlopban, = (x + 1, y) − (x, y).  helyzetképeket mutatnak A 7.1(a)

és 76 ábrákon látható be/kiviteli sémák különbözo  sorban levo  elemhez vezeto  átmenetet írja le: (1, 0) és a következo  be: az adatok szisztolikus rácshoz viszonyított helyzete ugyanarra az idopontra vonatkozik. Amint a 7.6 ábrán látható, az absztrakt adatszerkezetek téglalap alakú mátrixformái  ebben a helyzetképben parallelogrammává alakulnak. Ez az alkalmazott tér-ido-leképezés lineáris voltának tulajdonítható. Ezeket a paralelogrammákat is ki lehet fejezni a peremek mentén kiszámolt különbségvektorok segítségével. Most az adatszerkezetek ∆w különbségvektorait ∆z térbeli különbségvektorokká sze- 0 retnénk alakítani. Ehhez olyan konkrét v, v iterációs vektor párokat kell meghatároznunk, a (7.23) összefüggésbeli λ paraméterek megválasztása révén, melyeket a megválasztott tér-    ido-leképezés ugyanarra az idopontra képez le. Hogy pontosan melyik idopontról is van szó, az itt most nem

lényeges. Tehát a v = H π · v = π · v0 ·w+λ·q+ p és  egyenloséget összevetjük azzal, hogy 0 v = H · w 0 + λ0 · q + p . (7.26) Ez azt eredményezi, hogy π · H · (w − w0 ) + (λ − λ0 ) · π · q = 0 , azaz ∆λ = (λ − λ0 ) = −π · H · (w − w0 ) . π·q (7.27) (7.28) A keresett ∆z térbeli különbségvektor tehát a használt leképezések lineáris voltából adó dóan a következoképpen számítható ki az adatszerkezet ∆z = P · ∆v = P · H · ∆w + ∆λ · P · q , tehát ∆z = P ∆w = w − w0 különbségvektorából: · H · ∆w − π · H · ∆w ·P·q . π·q (7.29) (7.30) 292 7. Szisztolikus rendszerek (Eberhard Zehendner)  a Most meghatározzuk a (7.30) képletbol ∆z térbeli különbségvektorokat az A mátrix  számára. A fentiek alapján érvényes a következo: H Mivel    =   1 0 0 0 0 1     , 

  q =   0 1 0     , P π · q = 1, következik ! 0 1 ∆z = · ∆w + ∆λ · −1 0 A sorok esetében a = −1 0 −1 1 −1 1 0 ! , π= ! ahol 1 ∆λ = −   1 1   1 1 1 . · ∆w .  a ∆z = (2, −1) térbeli ∆w = (0, 1) különbségvektorunk van, melybol ∆w = (1, 0)-ból következik a különbségvektor következik. Ugyanígy az oszlopok esetében ∆z = (1, −2). Egyeztessük ezt most a 76 ábrával, és láthatjuk, hogy az A sorai valóban a (2, −1) vektor mentén helyezkednek el, az oszlopok pedig a (1, −2) vektor mentén. Ugyanígy kapjuk a B sorai esetében, hogy ∆z = (−1, 2), illetve ∆z = (1, 1) a B osz lopaira. Megfeleloképpen ∆z = (−2, 1) a C sorai esetén, és ∆z = (−1, −1) a C oszlopai esetében. Ezzel tehát most már meg tudjuk szerkeszteni a be/kiviteli sémát minden egyes mátrixra külön-külön. 7.33 A be/kiviteli séma megszerkesztése Az A,

B, C mátrixok megjelenési formája a helyzetkép számára adott ugyan, de még meg kell határozzuk a szisztolikus rácshoz (és egyúttal egymáshoz) viszonyított elhelyezkedésüket. Ennek megvalósítására létezik egy egyszeru  grakus módszer.  Kiválasztunk egy tetszoleges iterációs vektort, legyen ez v = (1, 1, 1). A P projekciós  számítások törmátrix segítségével levetítjük ezt arra a cellára, melyben a neki megfelelo ténnek. z = 0 −1 1 −1 1 0  !   ·   1 1 1     = 0 0 ! . Az (1, 1, 1) iterációs vektorhoz az a(1, 1, 1), b(1, 1, 1) és c(1, 1, 1) számítások vannak hozzárendelve, melyek viszont a a11 , b11 és c11 mátrixelemeknek felelnek meg. Helyezzük az A, B, C mátrixok esetén kapott be/kiviteli sémát a szisztolikus rácsra úgy, hogy a megfe a11 , b11 és c11 bemenetek mind a z lelo = (0, 0) cellában legyenek. Ezzel tulajdonképpen már készen is volnánk.

Ez a be/kiviteli séma azonban átfedi a  Ezért minden mátrix szisztolikus rács celláit, és emiatt nem elég világosan felismerheto. be/kiviteli sémáját egy-egy pozícióval tovább toljuk az adatfolyamok haladásával ellentétes irányba mindaddig, amíg nem áll fenn többé átfedés. Ezzel pontosan a 76 ábrán bemutatott be/kiviteli sémát kapjuk.  Ezen elegáns grakus módszer mellett itt is megvan a lehetoségünk arra is, hogy az átfedésmentes elhelyezkedést formálisan számoljuk ki.  Csak a be/kiviteli séma megadása után tudjuk a szükséges idoszeletek számát megha lényeges idoszelet   adat bevitelével kezdodik.  tározni. Az elso a legelso Az utolsó lényeges   idoszelet az utolsó adatkivitellel végzodik. A 7.6 ábrán látható példa esetén a számítások 293 7.3 A be/kiviteli séma levezetése   bevitelétol  számítjuk, a számítások befejeztékezdetét a b11 elem 0 idoszeletben történo  nek pedig a 14. idoszeletet

tekintjük, miután a c35 eredmény kiszámítása megtörtént. Ez  összesen 15 idoszeletet tesz ki – ami öttel több a tulajdonképpeni számítások elvégzéséhez  szükséges idoszeletek számánál. 7.34 Tér-id®-leképezés által el®idézett adatsebesség Az A és B mátrix 7.1(a) ábrán látható beviteli sémája kompakt felépítésu:  ha megrajzoljuk az ábrán a mátrix széleit, ennek belsejében nem találunk kihasználatlan helyet. Más a helyzet a 7.6 ábrán Bármelyik adatfolyamot tekintjük, mindegyik elemet két kihasználatlan hely követ. A beviteli mátrixok esetében ez azt jelenti, hogy: a szisztolikus  rács peremcellái csak minden harmadik idoszeletben kapnak valódi adatot.  Ez a tulajdonság az éppen alkalmazott tér-ido-leképezés egyenes következménye. Maguk az absztrakt adatszerkezetek mind a két esetben kompaktak Azonban, hogy milyen sur  un  helyezkednek el az adatok a be/kiviteli sémában, az a T transzformációs mátrix de

függ: minden egyes be/kiviteli adatfolyamban a tényleges terminánsának abszolút értékétol értékek pontosan |det(T )| pozíciónyi távolságra követik egymást. Míg a 71 ábra esetében |det(T )| = 1 érvényes, addig a 7.6 ábra esetében a | det(T )| = 3 értéket állapíthatjuk meg, melynek most már gyakorlati jelentése is ismert. Mi történik vajon a ki nem használt helyekkel, mint amilyeneket a 7.6 ábrán is láthatunk? Annak ellenére, hogy a 73 ábra szisztolikus rácsának minden cellája tulajdonképpen  csak minden harmadik idoszeletben végez értelmes munkát, nincs sok értelme annak, hogy  lépés után két idoszelet   minden munkát végzo erejéig szüneteltessük oket. Ha pontosab értéban meggyeljük, megállapíthatjuk, hogy a 7.6 ábrán pontokkal jelölt helyeken lévo keknek semmiféle befolyásuk nincs a ci j elemek kiszámítására, mivel egy c(i, j, k) változó   cellában. A nem kiszámításának idopontjában soha nincsenek

ott a számításnak megfelelo  használt helyeket tehát egyszeruen  tetszoleges, akár véletlenszeru  értékekkel is feltölthetjük anélkül, hogy a végeredményt elrontanánk ezzel. Ráadásul az is lehetséges, hogy a 73 ábra   mátrixszorzást elvégezzünk, szisztolikus rácsának segítségével egyidoben három különbözo anélkül, hogy ezek zavarnák egymást. A 737 pontban ezt még pontosabban kifejtjük 7.35 Be/kivitel kiterjesztése és a b®vített be/kiviteli séma A 7.6 ábrát alaposabban tanulmányozva egy újabb kérdés merül fel Tekintsük példaként  a c22 útját a szisztolikus rács celláin keresztül. A tér-ido-leképezés alapján a számítások a (−1, 0), (0, 0), (1, 0) és (2, 0) cellákban mennek végbe. A 76 ábrán látható be/kiviteli séma  szerint természetesen elobb a (−2, 0) cellán, illetve legvégül a (3, 0) cellán is keresztülhalad a c22 .  Ezt értelmezhetjük úgy, hogy a választott tér-ido-leképezés révén a

(7.3) rendszerbe ktív számítások kerülnek be, itt például az értéktartomány új (2, 2, 0) és (2, 2, 5) pontjai kapcsán. Ennek a jelenségnek az alapja az a tény, hogy a be/kimeneti muveletek  értéktartományai nem a megválasztott u projekciós iránnyal párhuzamosan helyezkednek el. En nek következtében egyes be/kimeneti muveletek  olyan cellákra vetítodnek, amelyek nem a szisztolikus rács peremén vannak. Itt viszont a be/kimeneti muveletre  közvetlen módon nem kerülhet sor. Az útvonalat az adatfolyamok iránya mentén meghosszabbítva, illetve ezekkel  a belso  celláktól a szisztolikus rács pereméig, kiküszöbölhetjük ellentétes irányban ezektol 294 7. Szisztolikus rendszerek (Eberhard Zehendner) c35 c25 c34 c15 c24 c33 c14 c23 c32 c13 c22 c31 c12 c21 c11 b15 b14 b25 b35 b13 b24 b12 b23 b34 b45 b44 b11 b22 b33 b21 b32 b43 b31 b42 b41 0 0 0 a11 a21 a12 a31 a22 a13 a32 a23 a33 a14 a24 C B A a34 0 0 0  7.7 ábra Bovített be/kiviteli

séma a 7.6 ábrához  ezt a problémát. Ezzel viszont új számítások jönnek be, esetleg újabb pontokkal bovül az értéktartomány (be/kivitel kiterjesztése).  mellékes száVigyáznunk kell arra, nehogy a (−2, 0) és (3, 0) cellákban végbemeno, mítások elrontsák a c22 tulajdonképpeni értékét. A mátrixszorzás esetében ezt elég könnyu   elérni (az általános esetben viszont sokkal nehezebb). A generikus összegzooperátornak van egy semleges eleme, éspedig a nulla. Tehát ha elérjük, hogy a kiegészítés révén bekerült számításokban mindig csak a nullát adjuk hozzá az eddigiekhez, ez semmiféle kárt nem okoz.  A 7.7 ábra egy alkalmas bovített be/kiviteli sémára ad példát. Az A mátrix elé és mögé hozzá vannak fuzve  a szükséges null-elemek. Mivel a bevitt null értékeket adatnak kell 7.3 A be/kiviteli séma levezetése tekintenünk, a 7.6 ábra be/kiviteli sémája még egy pozícióval visszatolódik 295 296 7.

Szisztolikus rendszerek (Eberhard Zehendner)    A számítások tehát már a -1. idoszeletben megkezdodnek, viszont ugyanúgy a 14. ido  16 idoszelet  szelettel végzodnek, mint korábban. A teljes végrehajtási ido lesz. 7.36 A stacionárius változók kezelése Térjünk vissza a 7.1(a) ábra példájához Az A és B elemeinek beviteléhez nincs szükség  semmiféle kiterjesztésre, mivel ezekre mindig a peremcellákban van legeloször szükség. Más a helyzet viszont a C mátrixszal. Ennek elemeit stacionárius változókban számítjuk ki, vagyis mindvégig ugyanabban a cellában. A ci j eredmények tehát a szisztolikus rács belse jére esnek, ahonnan a kiszámításukat követoen egy további folyamatban a szisztolikus rács  peremcelláihoz kell továbbítanunk oket, mert csak ezeken keresztül férhetünk hozzájuk. Annak ellenére, hogy a megoldandó feladatot felületesen szemlélve úgy tunik,  mintha az a 7.35 pontban leírthoz nagyon hasonló lenne, és

emiatt igen egyszerunek  látszik, mégis  van itt szó. Nem arról van szó ugyanis, hogy a meglévo  adategy teljesen más helyzetrol  folyamokat elore vagy visszafelé a szisztolikus tömb pereméig meghosszabbítsuk. Hiszen  stacionárius változók esetében a függoségi vektor a nullvektor. Így ez semmiféle térbeli  adatfolyamot nem eredményezhet. Egy ilyen adatfolyamot nekünk kell elobb felépítenünk,  egységre is szükségünk van amiben igen nagy a szabadságunk. Alapjában véve egy vezérlo a cellákban. Ezt a kérdést a 74 alfejezetben tárgyaljuk tovább 7.37 Számítások összekapcsolása Amint az könnyen belátható, a 7.3 ábra szisztolikus rácsának kihasználtsága a 77 ábra   szakaszt be/kiviteli sémájával meglehetosen csekély. Anélkül, hogy a betöltési vagy a végso  tanulmányoznánk, máris észrevesszük, hogy a rács átlagos kihasználtsága keközelebbrol vesebb, mint egyharmadot tesz ki – hiszen valódi számítást minden

cella legfeljebb minden  harmadik idoszeletben végez. Egy egyszeru  eszköz ennek a viselkedésnek a javítására a számítások összekapcsolása.  mátAmennyiben három egymástól független, ugyanazokkal a paraméterekkel rendelkezo  rixszorzást kell elvégeznünk, ezek adatait bevihetjük egymástól csupán egy idoszeletnyi távolságban, anélkül, hogy a szisztolikus rácson vagy annak celláin bármit is változtatnánk. A  a be/kiviteli séma megfelelo  7.8 ábra helyzetképet mutat a szisztolikus rács egy részletérol, részeivel.  odni  Szeretnénk egyúttal valamilyen formális levezetésen keresztül meggyoz arról, hogy ez az ötlet valóban muködik.  Ennek érdekében módosítjuk a (7.3) rendszert úgy, hogy a vál tozókat és az értéktartományt egy negyedik dimenzióval bovítjük ki, mely csupán a három mátrixszorzás megkülönböztetésére szolgál: Bemeneti muveletek  a(i, j, k, n) = anik n b(i, j, k, n) = b kj c(i, j, k, n) = 0 ≤ i

≤ N1 , j = 0, 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 , = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 , 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0, 1 ≤ n ≤ 3 . 1 i 297 7.3 A be/kiviteli séma levezetése a132∗ b121 a222∗ b221 a312∗ b321 a113∗ b132 0 * b322 a322 a223 ∗ 0 a231 ∗ b131 a213∗ b231 0 * b313 b142 a331 a232 ∗ 0 a133 ∗ 0 a114∗ b141 b241 a233 a124 a142 b332 7.8 ábra Három mátrixszorzás összekapcsolt kiszámítása a 73 ábra szisztolikus rácsával (részlet) Számítások a(i, j, k, n) = a(i, j − 1, k, n) b(i, j, k, n) = b(i − 1, j, k, n) c(i, j, k, n) = c(i, j, k − 1, n) + a(i, j − 1, k, n) · b(i − 1, j, k, n) ≤i≤ 1 ≤ i ≤ 1 ≤ i ≤ N1 , 1 ≤ j≤ N1 , 1 ≤ j ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤i≤ N1 , 1 N2 , k 1 ≤k≤ N2 , 1 ≤ k ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤n≤3, N3 , 1 ≤ n ≤ 3 , N3 , 1 ≤ n ≤ 3 . Kimeneti muveletek  n ci j = c(i, j, k, n) 1 ≤ j≤ = N3 , 1 ≤n≤3.

(7.31)  n értékekhez tartozó feladatoknak Nyilvánvaló, hogy a (7.31) rendszerben a különbözo semmi közük egymáshoz. Ennek tehát a szisztolikus rácsban is így kell lennie Egy erre  tér-ido-mátrix   vonatkozó, az ábrának megfelelo a következo T   0  =  −1  −1 1 0 1 0 0 1 1 1 1     . (7.32) A T mátrix itt már nem négyzetes, de ez nem tesz semmit. A térkoordináták kiszámításának  két sorának utolsó szempontjából a negyedik dimenzió teljesen jelentéktelen; ezért a T elso  null-értékek segítségével egyszeruen  oszlopában levo  eltüntetheto. T utolsó sora újraépíti a π  idovektort. A π  megválasztásával a három megmegfelelo  oldásra váró feladat átfedésmentesen ágyazható be a tér-ido-szerkezetbe. A három feladat  iterációs vektorainak példányai egymástól egy idoegységnyi  egymásnak megfelelo távol ságban ugyanarra a

cellára lesznek vetítodnek, mivel π negyedik bemenete 1. 298 7. Szisztolikus rendszerek (Eberhard Zehendner) = = 5 és N3 = 4 konkrét feladat paraméterei esetében. Egyetlen mátrixszorzás esetén N1 · N2 · N3 = 60 számítást kell elvégezni. Ilyenkor egy szorzás és a hozzá tartozó összeadás összetett muveletnek  számít, azaz együtt csupán egyetlen számítást jelent; a be/kimeneti Kiszámítjuk most az átlagos kihasználtságot összekapcsolással, illetve e nélkül az N1 3, N2 muveleteket  nem számítjuk hozzá. A szisztolikus rács 36 cellával rendelkezik  Összekapcsolás nélkül a szisztolikus rácsunknak 16 idoszeletre van szüksége egy mát átlagos kihasználtságát eredményezi: rixszorzás elvégzéséhez. Ez a cellák következo 60/(16 · 36) ∼  0.104 számítás idoszeletenként és cellánként. A leírt összekapcsolási technika alkalmazása esetén mindhárom mátrix kiszámítása csu  pán két idoszelettel igényel

többet, tehát 18 idoszeletet tesz ki. Ám a végrehajtott számítások  száma megháromszorozódott, a cellák átlagos kihasználtsága tehát a következo: 3 · 60/(18 · 36) ∼  0.278 számítás idoszeletenként és cellánként. Az összekapcsolással tehát körülbelül 167 százalékkal sikerült növelnünk a kihasználtságot. Gyakorlatok 7.3-1 Vezessük le formálisan a B és C mátrix térbeli különbségvektorait a 76 ábrán látható be/kiviteli séma esetén a (730) összefüggés alapján  7.3-2 Vázoljuk a bovített be/kiviteli sémát a 7.6 ábrához, arra az esetre, amikor a többlet szorzásmuveletek  mindkét operandusát nullára kell állítanunk. 7.3-3 Alkalmazzuk a 73 alfejezetben bemutatott módszereket a 71 ábra szisztolikus rácsára  7.3-4? Igazoljuk a (732) sajátos tér-ido-leképezés 7.37 pontban leírt tulajdonságait a (7.31) rendszerre vonatkozóan 7.4 Vezérlési szempontok Mindeddig abból indultunk ki, hogy egy szisztolikus

rács cellái teljesen egyformán visel kednek minden idoszeletben. Érdekes példákat találhatunk ilyen szisztolikus rácsokra. Álta muködési lában azonban vezérlés segítségével a cellákat különbözo  módokba lehet állítani.  A következokben néhány tipikus helyzetet fogunk tanulmányozni. 7.41 Vezérlésmentes cellák A 7.3(b) ábrán látható cella az A, B, C regisztereket tartalmazza, amelyek egy globális órajel  jeleket, majd a aktivál annak érdekében, hogy átvegyék a mindenkori bemenetükön levo  a globális aktiválástól eltekintve azonban, a sejtek kimenetükre továbbítsák ezeket. Ettol   operandusra egy szorzásmuködése  minden idoszeletben ugyanaz: a három, A, B, C bemeno összeadás muvelet  hajtódik végre, melynek az eredménye egy szomszédos cellába kerül; ezzel párhuzamosan az A és B operandusok két másik szomszédos cellának továbbítódnak. Következésképpen ez a cella semmiféle vezérléssel nem rendelkezik.

 operátor végrehajtásához szükséges c(i, j, 0) kezdoértékek,  A generikus összegzo melyeknek itt nem kell feltétlenül nullértékeknek lenniük, a 7.6 ábra alapján bemeneti adatfo- 299 7.4 Vezérlési szempontok B + * A C (a) (b) 7.9 ábra Regiszterek visszaállítása globális vezérléssel: (a) rácsszerkezet; (b) cellaszerkezet lyamként kerülnek a szisztolikus rácsba, a c(i, j, N3 ) eredmények pedig a rács peremén keresztül, ugyanabban az irányban áramlanak kifelé. A 73(b) ábra szerint tehát a be/kimenet implicit módon része a cellák muködésének.  Ennek a nagyon egyszeru,  vezérlésmentes sejtmuködésnek  az ára mindhárom mátrixméret korlátozása: (M1 × M3 )-as A mátrix csak akkor szorozható össze a 7.3 ábra szisztolikus rácsán keresztül egy (M3 × M2 )-es B mátrix-  feltételek érvényesülnek: szal, ha a rács meghatározott N1 , N2 , N3 paramétereire a következo M1 ≤ N1 , M2 ≤ N2 és M3 ≤ N3 .

7.42 Globális vezérlés¶ cellák  A 7.1 ábrán látható szisztolikus rács esetén az eloírások erre vonatkozóan kevésbé szigorúak: bár M1 és M2 itt is korlátozva van M1 ≤ N1 és M2 ≤ N2 által, az M3 -ra viszont nincs  semmi korlátozás. A feladat azon paraméterei, melyeket a rács elore meghatározott para méterei nem korlátoznak, csak idoben tudnak megnyilvánulni, térben azonban nem. Ezáltal stacionárius változók használatára kényszerülünk. Egy új számítás kezdetén minden egyes stacionárius változóhoz rendelt regisztert a  o  számításoktól független alapállapotba kell hozni. A 73(b) ábrán látható szisztolimegeloz kus cella esetében ez a regiszter a C. Egy, az órajelhez hasonlítható globális jel segítségével  azaz lenullázható. A 79 ábra egy ezen az az összes cella C regisztere egyszerre törölheto, ötleten alapuló rácsszerkezetet, illetve cellaszerkezetet mutat be. 7.43 Helyi vezérlés  csupán a

globális vezérlés elve. A 71 ábrán Sajnos a mátrixszorzáshoz nem elegendo bemutatott szisztolikus rácsból ugyanis két lényeges tulajdonság is hiányzik: egyrészt a  c(i, j, 0) változóknak nincs kezdoértékük, másrészt a ci j eredmények sem a rács peremén jelennek meg.  Eloször az eredmények perem felé vezérlése valóban egyszeru  feladatnak tunik:  egy ci j 300 7. Szisztolikus rendszerek (Eberhard Zehendner) c13 c23 c33 c12 c22 c32 c11 c21 c31 c15 c25 c35 c14 c24 c34 7.10 ábra Be/kiviteli séma késleltetett eredménymegadás esetén elem kiszámításának befejeztével már nincs szükség arra, hogy az (i, j) cellának a szomszédos (i, j + 1) és (i + 1,  kapcsolatait az A és B mátrix elemeinek j) cellák felé vezeto  továbbadására használjuk. Használhatjuk tehát más célokra oket Például a C összes elemét  kapcsolatokon keresztül a szisztolikus rács alsó pereméhez vezethetjük. a lefelé vezeto Sajnos kiderül

azonban, hogy a rács alsó részén még be nem fejezett számítások akadá Ha az i + j + N3 idoszeletben  lyozzák az eredmények átvezetését a fenti részbol. kiszámított  idoszeletben  ci j eredményt a következo az (i zéshez vezetne: mivel az (i + 1, + 1, j) cellának továbbítanánk, ez értékütkö-  j) cella idoszeletenként csak egy értéket bocsáthat ki az alsó csatornán keresztül, vagy a ci j -nek kellene várnia, vagy az (i + 1, j) cellában kiszámolt eredménynek. Ugyanez a probléma lefelé az összes további cellát érintené Megoldásképpen késleltethetjük a ci j továbbadását. Ha ci j -nek egy cellán való keresz tülhaladáshoz nem egy, hanem két idoszeletre van szükség, akkor az ütközések elmarad nak. Az eredmények így egymástól egy idoszeletnyi eltéréssel haladnak egymást követve,   oszugyanazon a kapcsolaton keresztül. Egy oszlop alsó peremcelláján legeloször az illeto   Tehát a 7.10 lop utolsó

sorának eleme jelenik meg, majd az utolsó elotti, legvégül az elso. ábrán látható be/kimeneti sémát kapjuk. Honnan tudja egy cella, mikor kell az alsó csatornán keresztül továbbítania, ahelyett hogy a B mátrix elemeit a C mátrix elemeivel együtt adná tovább? Ezt a feladatot a cella globális és lokális vezérlésének kombinált alkalmazásával, véges áéllapotú automaták segítségével oldhatjuk meg: 301 7.4 Vezérlési szempontok Amikor az A és B utolsó értékeit is bevisszük az (1, 1) cellába, egy globális jelet küldünk az összes cellának, ami jelzi, hogy minden cellában elindíthatunk egy számlálót, amely a  számítási lépések számát adja meg. Az (i, j) cellában még i + j − 1 további még elvégzendo  a sima továbbvezetésre kapcsolnánk át. A korábban említett lépést kell elvégezni, mielott  globális visszaállító jel késobb ismét visszakapcsol majd a számítási üzemmódba.  szisztolikus rács látható

a 7.11 ábrán A rács felépítése, Egy ilyen elv alapján muköd  o valamint a kapcsolatszerkezet lényegében változatlanok maradtak. Viszont minden cella  melyek között az átkapcsolást egy vezérlologika  kétféle üzemmódban muködtethet  o, végzi: 1. Számítási üzemmódban az összeadás eredménye (akárcsak eddig) az C regiszterbe író  a cella alsó dik. Ezzel egy idoben a szorzásra használt operandus az B regiszterbol csatornáján keresztül átadódik. 2. Adattovábbító üzemmódban az B és C regiszterek sorba lesznek kapcsolva. Ebben az  csatornán kiolvasott üzemmódban a cellák egyetlen feladata az, hogy minden, a felso  értéket két idoszeletnyi késleltetéssel továbbítson az alsó csatorna felé.  elso  érték a legutoljára kiszámíAdattovábbító üzemmódban az (i, j) cellából kilépo tott, majd az C regiszterben elhelyezett érték lesz, azaz a ci j eredmény. A továbbiakban  összes érték a fentebb elhelyezkedo 

cellákban kiszámolt, majd innen továbbvezetett kilépo eredmény. A 711 ábrán megvalósított algoritmus formális leírása a (733) értékadásmentes rendszert eredményezi. Bemeneti muveletek  a(i, j, k) = aik b(i, j, k) = bk j c(i, j, k) = 0 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , i = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 . 1 Számítások a(i, j, k) = a(i, j − 1, k) b(i, j, k) = b(i − 1, j, k) c(i, j, k) = c(i, j, k − 1) + a(i, j − 1, k) · b(i − 1, j, k) . ≤i≤ 1 ≤ i ≤ 1 ≤ i ≤ N1 , 1 ≤ j≤ N1 , 1 ≤ j ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤i≤ ≤i≤ N1 , 1 N2 , 1 1 ≤k≤ N2 , 1 ≤ k ≤ N2 , 1 ≤ k ≤ N3 N3 , , (7.33) N3 Átvezetés b(i, j, k) c(i, j, k) = c(i, j, k − 1) = b(i − 1, j, k) 1 1 N1 , 1 ≤ j≤ ≤ j≤ N2 , 1 + N3 ≤ k ≤ i + N3 , + N3 ≤ k ≤ i − 1 + N3 , Kimeneti muveletek  c1+N1 +N3 −k, j = b(i, j, k) i = N1 , 1 ≤ j≤ N2 , 1 + N3 ≤ k ≤ N1 +

N3 .  Tisztáznunk kell még, hogy hogyan hozzuk létre egy cella vezérlojeleit ebben a modell egy ipop állapotkapcsolóval kell rendelkeznie, mely az ben. A cellának mindenekelott éppen bekapcsolt üzemmódot adja meg. Ezen ipop kimenete hozzákapcsolódik a 711(b)  ábrán látható mindkét multiplexer vezérlobemenetéhez. A globális visszaállító jel nem csak a cella C regiszterét állítja vissza, hanem a ipop állapotkapcsolót is: a cella tehát számítási üzemmódban fog dolgozni. 302 7. Szisztolikus rendszerek (Eberhard Zehendner) B * counter + i+j −1 A C (a) Q S Q R (b) 7.11 ábra A helyi és a globális vezérlés kombinált alkalmazása: (a) a rács felépítése; (b) cellaszerkezet Amikor a globális végjel megérkezik, a cellában egy visszaszámláló indul el, amely    minden idoszeletben eggyel csökken. A számláló kezdoértéke – cellától függoen –i+ j−1 értékre lesz állítva. Amikor a számláló eléri a nulla

értéket, a ipop ismét átáll: a cella adattovábbító üzemmódba megy át.  A visszaállítás elotti utolsó, egy cella C regiszterébe továbbított érték felhasználható  skalárszorzat szabadon választható kezdoértékeként,  a cellában kiszámítandó következo ha az C regiszter közvetlen visszaállításáról lemondunk. Ezután, akárcsak a 73 ábrán látható szisztolikus rács esetében, az általános C = A ·B+D , (7.34) 303 7.4 Vezérlési szempontok  képletek segítségével oldjuk meg: feladatot a következo Bemeneti muveletek  a(i, j, k) 1 b(i, j, k) = aik = bk j c(i, j, k) = di j i ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 . Számítások a(i, j, k) = a(i, j − 1, k) = b(i − 1, j, k) c(i, j, k) = c(i, j, k − 1) + a(i, j − 1, k) · b(i − 1, j, k). b(i, j, k) 1 ≤i≤ ≤i≤ 1 ≤ i ≤ N1 , 1 ≤ j≤ ≤ j≤ N1 , 1 ≤ j ≤ N2 , 1 N3

1 N1 , 1 N2 , 1 ≤k≤ ≤k≤ N2 , 1 ≤ k ≤ N3 ≤i≤ ≤i≤ N1 , 1 N2 , 1 , , (7.35) N3 Átvezetés b(i, j, k) c(i, j, k) = c(i, j, k − 1) = b(i − 1, j, k) 1 1 N1 , 1 ≤ j≤ ≤ j≤ N2 , 1 + N3 ≤ k ≤ i + N3 , + N3 ≤ k ≤ i − 1 + N3 . Kimeneti muveletek  c1+N1 +N3 −k, j = b(i, j, k) i = N1 , 1 ≤ j≤ N2 , 1 + N3 ≤ k ≤ N1 + N3 . 7.44 Osztott vezérlés  hátrányai vannak: A 7.11 ábrán bemutatott módszernek a következo 1.  Globális vezérlojeleket használunk. Ez magas fokú technikai pontosságot igényel 2. Minden cellának egy számlálóra van szüksége, mely igen nagy ráfordítást igényel. 3.  A számlálók kezdoértéke nem azonos minden cella esetében. Ezért minden cellát egyénileg kell megtervezni és megvalósítani 4. Egy új feladat bevitelével meg kell várni, amíg az utolsó eredmény elhagyja a szisztolikus rácsot.  Ezek a hátrányok eltunnek,  ha a vezérlojeleket az adatokhoz

hasonlóan továbbítjuk, te- hát osztott vezérlést alkalmazunk. Megtartjuk ugyan a 711(b) ábrán látható módon az B és  C regiszterek multiplexerekhez való kapcsolását, nem hozunk viszont létre vezérlojeleket a  is eltekintünk. Ehelyett kívülrol  vezetjük be a cellákon belül; a globális visszaállító jeltol  cellákba a szükséges vezérlojeleket, egy (csupán 1 bit szélességu)  S pótregiszterben tárol módon továbbítjuk. A tulajdonképpeni juk, majd onnan a szomszédos cellákba megfelelo  vezérlojel létrehozását a gazdagép veszi át, a betáplálás kizárólag a peremcellákon keresztül történik. A 712(a) ábra az ehhez szükséges rácsfelépítést, a 712(b) ábra pedig a módosított cellaszerkezetet mutatja be. Az adattovábbító üzemmódba való átkapcsolás egy oszlop cellái esetén lefele haladva   csupán az S regiszter egy-egy idoszeletnyi különbséggel következik be. Ezért elegendo okozta késleltetés. A számítási

üzemmódba való visszaállítás ugyanazon vezérfonal mentén következik be,  tehát ugyanúgy cellánként egy idoszeletnyi késleltetéssel történik. Mivel a ci j eredmények 304 7. Szisztolikus rendszerek (Eberhard Zehendner) b41 0 b31 0 b21 0 b11 0 d11 1 d21 1 d31 1 b42 0 b32 0 b22 0 b12 0 d12 1 d22 1 d32 1 b43 0 b33 0 b23 0 b13 0 d13 1 d23 1 d33 1 b44 0 b34 0 b24 0 b14 0 d14 1 d24 1 d34 1 b45 0 b35 0 b25 0 b15 0 d15 1 d25 1 d35 1 B S * + a14 a13 a12 a11 A a24 a23 a22 a21 C a34 a33 a32 a31 (a) (b) 7.12 ábra Mátrixszorzás téglalap alakú szisztolikus ráccsal, az eredmények kivitelével és osztott vezérléssel: (a) a rács felépítése; (b) cellaszerkezet.  ideig csak fele akkora sebességgel mozognak lefelé, a cellák visszaállításával megfelelo  várni kell: ha egy cella a t idoszeletben lett számítási üzemmódba állítva, akkor a t  idoszeletben kapcsol át adattovábbító üzemmódba, és a t + N1 + + N3  N3 idoszeletben

ismét visszakapcsol számítási üzemmódba.  makAmint látjuk, a szisztolikus rácsok osztott vezérlése a lokális/globális vezérléstol   roszkopikus idotényez oben különbözik. Míg a 712 ábrán látható szisztolikus rács minden  + N3 idoszeletben egy új (7.34) feladat megoldásába kezdhet, ugyanez a 711 ábrán lát + N2 + N3 − 2 idoszeletben lehetséges. Az  N1 + N3 , illetve 2N1 + N2 + N3 − 2 idokülönbséget periódusnak nevezzük, inverzét pedig N1 ható szisztolikus rács esetében csak minden 2N1 teljesítménynek. A (7.36) rendszer az osztott vezérlés és számítás közötti formális összefüggéseket írja   legszorosabban egymást követo  mátrixszorzásokból le. Egy tetszoleges hosszúságú, leheto álló sorozatból indulunk ki, a bevezetett n iterációs változó ezért korlátlan. 305 7.4 Vezérlési szempontok Vezérlés s(i, j, k, n) =0 =1 s(i, j, k, n) = s(i − 1, j, k, n) = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 . = 0,

1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ N1 + N3 . 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 . i s(i, j, k, n) i Adatbevitel a(i, j, k, n) = anik n b(i, j, k, n) = bk j n+1 b(i, j, k, n) = dN +N 1 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , i = 0, 1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ 1 i 3 +1−k, j N1 + N3 . Fedonévvel  rendelkezo  változók c(i, j, k, n) = c(i, j, N1 + N3 , n − 1) 1 ≤i≤ N1 , 1 ≤ j≤ N2 , k =0. 1 ≤i≤ N1 , 1 ≤ j≤ N2 , 1 ≤k≤ N1 + N3 , 1 ≤i≤ N1 , 1 ≤ j≤ N2 , 1 ≤k≤ N1 + N3 . 1 ≤i≤ N1 , 1 ≤ j≤ N2 , 1 ≤k≤ N1 + N3 , Adatokkal végzett muveletek  a(i, j, k, n) = a(i, j − 1, k, n) ( b(i − 1, j, k, n) : b(i, j, k, n) = c(i, j, k − 1, n) :   c(i, j, k − 1, n)       + a(i, j − 1, k, n) c(i, j, k, n) =    · b(i − 1, j, k, n)    b(i − 1, j, k, n) − 1, j, k, n) = 0 s(i − 1, j, k, n) = 1 s(i

− 1, j, k, n) = 0 s(i − 1, j, k, n) = 1 : s(i : Adatkivitel n c1+N +N −k, j 1 3 = b(i, j, k, n) i = N1 , 1 ≤ j≤ N2 , 1 + N3 ≤ k ≤ N1 + N3 . (7.36)  A (7.37) képlet a hozzátartozó tér-ido-mátrixot mutatja, amelyben az egyik elem nem  függ. konstans, hanem a feladat paramétereitol T    =   1 0 0 0 1 0 1 1 1 0 0 N1 + N3     . (7.37)  Feltunik,  hogy az egy sorhoz tartozó cellák esetében jobbra haladva szintén egy idoszeletnyi különbséggel kell átkapcsolni ezeket. A szisztolikus rács teljes szabályosságának  követelményét gyelembe véve, ez a körülmény felhasználható arra, hogy a vezérlojeleket csak az (1, 1) cellán keresztül tápláljuk be, felszabadítva ezáltal a gazdagépet. Ekkor a  vezérlést a következoképpen módosítanánk: 306 7. Szisztolikus rendszerek (Eberhard Zehendner) B * + A C S b41 b31 b21 b11 d11 d21 d31 a14 a13 a12 a11 0

0 0 0 1 b42 b32 b22 b12 d12 d22 d32 b44 b34 b24 b14 d14 d24 d34 b43 b33 b23 b13 d13 d23 d33 b45 b35 b25 b15 d15 d25 d35 (b) B S * + 1 1 A a24 a23 a22 a21 C a34 a33 a32 a31 (a) (c) 7.13 ábra Mátrixszorzás téglalap alapú szisztolikus ráccsal, eredménytovábbítással és osztott vezérléssel: (a) A  perem cellái; (c) a fennmaradó területek cellái. rács felépítése; (b) a felso Vezérlés s(i, j, k, n) =0 =1 s(i, j, k, n) = s(i − 1, j, k, n) s(i, j, k, n) = 1, j = 0, 1 ≤ k ≤ N3 , = 1, j = 0, 1 + N3 ≤ k ≤ N1 + N3 , 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 , i i (7.38) . Fedonévvel  rendelkezo  változók s(i, j, k, n) = s(i + 1, j − 1, k, n) i = 0, 1 ≤ j ≤ N2 , 1 ≤k≤ N1 + N3 . . A 7.13 ábra e módosítás eredményét mutatja Két cellatípus létezik tehát: a szisztolikus  szélén található cellák (7.13(b) ábra), és az összes többi cella (713(c) ábra) A rács felso  szélén, a

kapcsolatszerkezet is csupán igen csekély eltérést mutat s szisztolikus rács felso szabályos területhez képest. 307 7.4 Vezérlési szempontok 7.45 A cellaprogram, mint lokális szemléletmód Egy cella muködését  egy cellaprogrammal is kifejezhetjük. Ez különösen akkor érdekes, ha rendelkezésünkre áll egy programozható szisztolikus rács, melynek celláit valójában egy ismételt módon végrehajtott program vezérli. Akárcsak a globális nézetet, azaz a szisztolikus rács architektúráját, a lokális nézetet, azaz a cellaprogramot is a tér-ido-leképezés  határozza meg. Ez azonban csak implicit  alakban adódik, ezért eloször matematikai transzformációval explicit alakra kell átalakítani, amely aztán alkalmas lesz cellaprogramnak. A programváltozók példányait általános alakban indexkifejezések írják le, melyek az  egyenletet a (7.3) renditerációs változókra hivatkoznak Tekintsük például a következo  szerbol: c(i, j, k)

= c(i, j, k − 1) + a(i, j − 1, k) · b(i − 1, j, k) A c programváltozók c(i, j, k − 1) példánya az i, 1 j és k ≤i≤ N1 , 1 ≤ j≤ N2 , 1 ≤k≤ N3 . − 1 indexkifejezésekkel rendelkezik, melyek az i, j, k iterációs változók függvényeiként is felfoghatók.  Amint láthattuk, a (7.11) tér-ido-leképezését alkalmazva a (7.13)-beli T transzformá ciós mátrixszal, az értéktartomány (i, j, k) iterációs vektorainak halmaza az (x, y, t) tér-idokoordináták halmazába megy át:     x y t     = T    ·   i j k     0 −1   1  =  −1 1 1 1 0 1        ·  i j k     . (7.39) Mivel minden cellát az (x, y) térbeli koordinátája jellemez, és a hozzá tartozó cellaprogram  nak a múló t

idore is hivatkoznia kell, a programváltozók indexkifejezéseiben eloforduló  i, j, k iterációs változók nem használhatók többé, és át kell írni oket az új, x, y, t koordiná tákra. Ehhez az i, j, k iterációs változókat a (739)-beli tér-ido-leképezés inverzének segítsé gével fejezzük ki, az (x, y, t) tér-ido-koordináták függvényében.     i j k      −1   = T ·   x y t     = 1 3   −1 −2  1 ·  −1  2 1 1 1 1        ·  x y t     . (7.40)  Egy ilyen inverz leképezés akkor létezik, ha a tér-ido-leképezés injektív az értéktarto mányon – és ennek mindig igaznak kell lennie, mert különben ugyanabban az idoszeletben egyetlen cellában egyszerre több számítást kellene

végrehajtani. A példában az invertálhatóságot a négyzetes, nem szinguláris T mátrix az értéktartományra való hivatkozás nélkül  π idovektorra π · u , 0. is biztosítja. A tulajdonság:  a következo  és u projekciós irányra vonatkozóan elegendo  Az iterációs változók tér-ido-koordinátákkal való lecserélésével, mely az értéktartomá általában kevésbé szép, új index-kifejezéseket nyok transzformációjaként is értelmezheto, kapunk. A c(i, j, k − 1) tehát így alakul: c((− x − 2 · y + t)/3, (− x + y + t)/3, (2 · x + y + t)/3) . Az indexhalmazok egy utólagos transzformációjával viszont átnevezhetjük a programvál  hivatkozások tisztábban kivehetok  tozók példányait úgy, hogy a cellára illetve idore történo 308 7. Szisztolikus rendszerek (Eberhard Zehendner) legyenek. Különösen ajánlatos az egyenletrendszert ismét kimeneti normál formába hozni,  azaz a t idoszeletben az (x, y) cellában

kiszámított eredményeket a programváltozók (x, y, t) példányaiként jelölni. Ennek az eljárásnak a megértését leginkább egy absztrakt matematikai formalizmussal érhetjük el, melyet végül a mi speciális helyzetünkre alkalmazunk. Legyen egy kvantikált  egyenlet r és s programváltozókkal, valamint S értéktartománnyal a következoképpen adott: r(ψr (v)) A ψr , valamint ψs = F (. , s(ψ s (v)), ), v ∈S . (7.41) indexfüggvények a programváltozók példányait indexkifejezés-  párokként állítják elo. Az értéktartomány egy S -en injektív ϕ függvény segítségével történo transzformációja  által a (7.41) a következoképpen alakul át: r(ψr (ϕ −1 (e))) = F (. , s(ψ s (ϕ−1 (e))), ), e ∈ ϕ(S ) , (7.42) ϕ−1 egy függvény, amely ϕ(S )-en a ϕ inverz függvényét képezi. Az új indexfüggvények ψr ◦ ϕ−1 , valamint ψ s ◦ ϕ−1 . ahol Az indexhalmazok transzformációinak nincs közük

az értéktartományokhoz és minden egyes programváltozóra külön végrehajthatók, mivel csak ennek az egy programváltozónak a példányait nevezik át következetes módon. A ϑr és  ϑ s átnevezésekkel (7.42) a következo- képpen alakul: r(ϑr (ψr (ϕ −1 (e)))) = F (. , s(ϑ s (ψ s (ϕ−1 (e)))), ), Amennyiben a kimeneti normál formát szeretnénk megkapni, a e ∈ ϕ(S ) . (7.43) ϑr ◦ ψr ◦ ϕ−1 -nek az identi- tásfüggvénynek kell lennie. A (példában látható) legegyszerubb  esetben ψ s (v) = v −d ψr mindig az identitásfüggvény és ψs egy  alakú affin leképezés, konstans d-vel, a már ismert függoségi vektorral.  ki d ugyanúgy fejezheto = ~0-ral. Az értéktartományok transzformációja a ϕ(v) = T ψr · v tér-  ido-leképezéssel történik, ahol T invertálható mátrix. Minden indextranszformáció esetében egyértelmuen  (ϑ  = ϕ)-t választjuk. Tehát a (743) a következoképpen alakul: r(e)

= F (. , s(e − T · d), ), e ∈ T (S ) . (7.44)  Egy cellaprogram eloállításakor a végrehajtandó muveleteknek,  az adatok forrásának, valamint az eredmények rendeltetési helyének (az assembly programokból ismert  src, dst) minden egyes idoszeletben pontosan adottnak kell lennie.  Az éppen végrehajtandó muvelet  (opc) közvetlenül az F függvénybol opc, adódik. A ve-  zérléssel ellátott cellák esetében meg kell még állapítani azt az idotartamot is, mely alatt ez a speciális F végrehajtódik. Ez meghatározható a térkoordináták függvényében, a T (S )  idotengelyre való levetítéssel, egy általános poliéderes S esetében például egy Motzkin elimináció” útján.  adódik az új T A (7.44) rendszerbol Fourier”   áll, · d függoségi vektor, amely két komponensbol ∆z térbeli rész, mint különb-   A egy térbeli (vektoriális), és egy idobeli (skaláris) részbol. ségvektor leírja, hogy a szomszédos

cellák melyikében számítottuk ki az operandust. Ezt az  bevitelével kapcsolatos információt közvetlenül átalaoperandusoknak a z cellába történo kíthatjuk egy  −∆z pozíciójú csatorna-jelöléssé (src). Ennek megfeleloen az operandusokat 309 7.4 Vezérlési szempontok kiszámító z − ∆z cella ezt az értéket egy ∆z pozíciójú csatornán keresztül adja át (dst).   A T · d idobeli része a ∆t idokülönbség által megadja, hogy mikor történt az operandusok kiszámítása. Ez az információ az olvasó z cella számára jelentéktelen, mivel a szomszédos  o  idoszelet  cellákból mindig a közvetlenül megeloz kimenetét olvassa ki. Azonban ha ∆t >  1, akkor az operandust abban a z−∆z cellában, amelyben kiszámították, ∆t −1 idoegyszeleten keresztül tárolni kell. Ez megoldható például úgy, hogy a z − ∆z cella programja másolási muveletet  hajt végre, melynek során az operandusok értékei ∆t

− ∆t − 1 1 regiszteren haladnak keresztül, míg a cella tényleges kimenetéhez érnek.  Ezt a módszert alkalmazva a (7.36)-re, a (737)-beli T -t használva a következoket kapjuk: s(x, y, t) = s(x − 1, y, t − 1) . a(x, y, t) = a(x, y − 1, t − 1) . ( b(x − 1, y, t − 1) : b(x, y, t) = c(x, y, t − 1) :   c(x, y, t − 1)       + a(x, y − 1, t − 1) c(x, y, t) =    · b(x − 1, y, t − 1)    b(x − 1, y, t − 1) s(x s(x − 1, y, t − 1) = 0 − 1, y, t − 1) = 1 , : s(x : s(x (7.45) − 1, y, t − 1) = 0 − 1, y, t − 1) = 1 .  Az n iterációs változónak itt csupán a be/kiviteli séma szempontjából van jelentosége és a transzformáció számára egy rögzített értékre állíthatjuk. A hozzá tartozó cellaprogram,   mely minden idoszeletben lefut, a következo. C 1 2 3 4 5 6 7 8 9 10 S ← C(−1, 0)(0) A ← C(0, −1) B ← C(−1, 0)(1 : N)

C(1, 0)(0) ← S C(0, 1) ← A if S = 1 then C(1, 0)(1 : N) ← C C←B else C(1, 0)(1 : N) ← B C←C+A·B A csatornajelölések a cella lokális be/kimeneteire vonatkoznak. Alakjukat a csatorná- C(0, −1) a cella bal szélén heC(−1, 0) fent van, C(1, 0) pedig lent. A csatornajelölés után megadható még egy bit-tartomány: C(−1, 0)(0) kizárólag a csatorna 0. bitjét jelenti,  N-ig terjedo  bitjeit. Az A, B, jelöléC(−1, 0)(1 : N) ugyanannak a csatornának az 1-tol  kapják. nak a cella középpontjához viszonyított helyzetébol lyezkedik el, C(0, 1) a jobb szélen, sek a cella regisztereit jelentik. 310 7. Szisztolikus rendszerek (Eberhard Zehendner)   A (7.12)-beli T -t (735)-re megfeleloen alkalmazva a következoket kapjuk: a(x, y, t) = a(x, y − 1, t − 1) b(x, y, t) = b(x − 1, y, t − 1) c(x, y, t) = c(x, y, t − 1) + a(x, y − 1, t − 1) · b(x − 1, y, t − 1) . b(x, y, t) = c(x, y, t − 1) c(x, y, t) = b(x − 1, y, t − 1) +

x + y ≤ t ≤ x + y + N3 , 1 + x + y ≤ t ≤ x + y + N3 , 1 + x + y ≤ t ≤ x + y + N3 1 (7.46) + y + 1 + N3 ≤ t ≤ 2 ∗ x + y + N3 , x + y + 1 + N3 ≤ t ≤ 2 ∗ x + y −1 + N3 . x  Szépen kidomborodnak tehát az osztott vezérlés elonyei. A (7.45)-ben leírt cellapro   gram egy tetszoleges t idoszeletre vonatkozik, nem kell tehát globális vezérlojelekre reagáljon, nincs szüksége számlálóregiszterre, nincsenek számlálómuveletek  és a helyi cellakoordinátákat sem kell kódolni. Gyakorlatok  legszorosabban egymást követo  szá7.4-1 Adjuk meg a be/kimeneti sémákat két, leheto mítás végrehajtására a (7.35) rendszer alapján, a 711, illetve 712 ábrán bemutatott szisztolikus rácsokra 7.4-2 Hogyan kellene a 712 ábrán látható szisztolikus rácsot módosítani ahhoz, hogy hatékonyan támogassa a mátrixszorzatok kiszámítását M1 < N1 vagy M2 < N2 paraméterek esetén? 7.4-3 Hogy néz ki a cellaprogram a 73 ábrán

látható szisztolikus rács esetében? 7.4-4? Mekkora teljesítményt ér el a 73 ábrán látható szisztolikus rács N1 , N2 , N3 konkrét értékeire? Hát általános N1 , N2 , N3 -ra? 7.4-5? Módosítsuk a 71 ábrán látható szisztolikus rácsot úgy, hogy a stacionárius változók a számítás befejezése után jobb-alsó irányba (azaz a (i, j) cellától a (i + 1, j + 1) cella felé)  járulékos kapcsolatokon keresztül legyenek kivezetve. Adjunk meg egy, a (735)-nek vezeto  értékadásmentes rendszert, mely leírást ad a hozzá tartozó viselkedésrol.  Hogyan megfelelo  el? néz ki a be/kimeneti séma? Milyen periódus érheto 7.5 Lineáris szisztolikus rácsok A fenti alfejezetekben leírt megfontolások kétdimenziós szisztolikus rácsokra vonatkoznak.  Azonban egydimenziós szisztolikus rácsokra is átültethetjük oket. A két forma közötti lényeges különbség a szisztolikus rács peremére vonatkozik. Az egydimenziós szisztolikus rácsokat

egyrészt felfoghatjuk úgy, mint amelyek kizárólag pe illetve a kimenetek továbbítása a gazremcellákból állnak, az adatbevitel a gazdagéprol, dagépnek minden további intézkedés nélkül lehetséges. Másrészt rendelkeznek egy teljes dimenzióval és egy csupán formális dimenzióval. A lineáris szisztolikus rács muködési  iránya menti kommunikációjában adott esetben hasonló kérdések merülnek fel, mint a 7.35 pontban. Végül, a lineáris szisztolikus rács pereme teljesen másként is deniálható, mégpe cellából áll dig úgy, mint ami csak a két végen elhelyezkedo 311 7.5 Lineáris szisztolikus rácsok 7.51 Mátrix és vektor szorzása Ha a 7.1 ábrán az N1 vagy N2 feladat-paraméterek egyikének értéke 1, a mátrixszorzás átalakul mátrix és vektor közötti szorzássá: balról N1 = 1-re, illetve jobbról N2 = 1-re. A kétdimenziós szisztolikus rács ekkor egydimenzióssá fajul el. A szorzandó vektort, mint bemeneti

adatfolyamot, a lineáris szisztolikus rács egyik végcelláján keresztül vezetjük be.  Ezzel egy idoben a mátrix elemei a rács hosszanti oldalán kerülnek be. Akárcsak a teljes mátrixszorzás esetében, az eredmények stacionárius módon jönnek létre. Ezeket viszont kivezethetjük a rács hosszában az egyik végcelláján keresztül, vagy  cellákból a gazdagépnek. Ez különbözo  vezérlo átadhatjuk közvetlenül a számítást végzo   mechanizmusokat, idosémákat és teljes futási idoket eredményez. Lehetséges lett volna-e az összes bemeneti adatot a végcellákon keresztül bevezetni?  Semmiképp sem, ha a teljes futási idonek eleme van, tehát Θ(N) Θ(N)-nek kell lennie. A beviteli mátrixnak Θ(N 2 )   elemet kell idoszeletenként bevinni. Egy idoszeleten belül a vég-  adatok száma azonban korlátozott. Az esetünkben cellákba bemeno Θ(N) nagyságrendu   be/kimeneti adatsebesség elore kizár bizonyos döntéseket. 7.52 Rendezés

Rendezéskor a feladat az, hogy egy teljesen rendezett G alaphalmazból vett { x1 , . , xN } ele álló halmazt {mi }i=1,,N növekvo  sorrendbe állítsunk, vagyis hogy mi mekbol legyen minden (i < ≤ mk érvényes  k)-ra. A feladatot a következoképpen fogalmazhatjuk meg értékadás- mentes jelölést használva, ahol MAX G maximumát jelöli: Bemeneti muveletek  x(i, j) m(i, j) = xi = MAX 1 1 ≤ i ≤ N, j = 0 , ≤ j ≤ N, i = j − 1 . Számítások m(i, j) = min{ x(i, j − 1), m(i − 1, j)} x(i, j) = max{ x(i, j − 1), m(i − 1, j)} ≤ i ≤ N, 1 ≤ j ≤ i , 1 ≤ i ≤ N, 1 ≤ j ≤ i . (7.47) 1 Kimeneti muveletek  m(i, j) Egy u = mj 1 ≤ j ≤ N, i = N .  = (1, 1) irány menti projekció segítségével a tér-ido-leképezésre x t ! = 1 −1 1 1 ! · i j ! (7.48) a 7.14 ábrán látható egydimenziós szisztolikus rácsot kapjuk, mely a buborékrendezést valósítja meg.  Hasonlóképpen, az alábbi tér-ido-mátrix T =

0 1 1 1 ! (7.49) 312 7. Szisztolikus rendszerek (Eberhard Zehendner) x5 x4 x3 x2 S x1 1 1 1 1 0 MAX MAX MAX MAX MAX X max m5 M m4 min m3 m2 m1 (a) (b) Buborékos rendezés” lineáris szisztolikus rács segítségével: (a) a rács felépítése be/kiviteli sémával; ” (b) Cellaszerkezet. 7.14 ábra a beszúró rendezést megvalósító lineáris szisztolikus rácshoz vezetne, míg végül a T = 1 0 1 1 ! (7.50)  mátrix a kiválasztó rendezést valósítaná meg. tér-ido  A rendezési feladatnál Θ(N) bemeneti adatunk, Θ(N) kimeneti adatunk, és Θ(N) idoszeletünk van. Ez Θ(1) be/kimeneti adatsebességet eredményez. Ellentétben a 751 pontban bemutatott mátrix-vektor szorzással, a be/kimeneti adatsebesség a kommunikációt elvileg itt  cellákon keresztül engedi még kizárólag csak a lineáris szisztolikus rács végpontjain levo meg. Mindazonáltal a rendezés mindhárom leírt változatában a bemenetek az összes cellán

keresztül történnek: a buborékos rendezésnél csak a rendezni való elemek, a kiválasztásos rendezésnél ehhez hozzájönnek még a konstans MAX értékek, a beszúrásos rendezésnél  bemeneti adatként megadni, csak a konstans értékek. Az utóbbiakat ugyan nem kötelezo hanem létrehozhatók közvetlenül a cellákban, vagy kiolvashatók egy csak olvasható (ROM) memóriából is. Mindhárom változat cellavezérlést igényel: a beszúró-, illetve kiválasztásos rendezés azért, mert stacionárius változói vannak, a buborékos rendezés azért, mert a bemeneti adatok és a kiszámított értékek feldolgozása között átkapcsolásra van szükség. 7.53 Lineáris egyenletrendszer alsó háromszögmátrixszal · x = b lineáris egyenletrend× N)-es A mátrix egy alsó háromszögmátrix. A (7.51)-beli képletek egy lokalizált algoritmust írnak le az A szer megoldására, ahol az (N 313 7.5 Lineáris szisztolikus rácsok Bemeneti muveletek  a(i, j) u(i, j)

= ai, j+1 = bi 1 1 ≤ i ≤ N, 0 ≤ j ≤ i − 1 , ≤ i ≤ N, j = 0 . Számítások u(i, j) = u(i, j − 1) − a(i, j − 1) · x(i − 1, x(i, j) = u(i, j − 1)/a(i, j − 1) x(i, j) = x(i − 1, j) j) ≤ i ≤ N, 1 ≤ j ≤ i − 1 , 1 ≤ i ≤ N, j = i , 2 ≤ i ≤ N − 1, 1 ≤ j ≤ i − 1 . 2 (7.51) Kimeneti muveletek  xi = x(i, j) 1 ≤ i ≤ N, j = i .  eltekintve, az érAz összes eddig tanulmányozott példában, a másolási muveletekt  ol téktartomány egy hordozópontjára ugyanazok a számítási muveletek  vonatkoztak: szorzás és összeadás egymás utáni végrehajtása a szorzás-algoritmusok esetében, valamint minimum és maximum párhuzamos végrehajtása a rendezési algoritmusok esetében. A (751) rendszerben ezzel ellentétben egyes hordozópontokra szorzás és kivonás, míg más hordozópontok esetében csak osztás történik. A (7.51) lineáris szisztolikus rácsra való levetítése során, a választott

projekció-iránytól   cellamuködést függoen ugyanolyan, illetve különbözo  kapunk. Az u = (1, 1) projekció-  cellát kapunk, az összes többi iránnyal (és csakis ezzel) egyetlenegy osztóval rendelkezo szorzó- és kivonó egységgel rendelkezik. Az u = (1, 0) vagy u =  (0, 1) mentén történo projekció esetén csupa egyforma cellát kapunk, melyek osztóval, szorzóval és kivonóval is rendelkeznek. Az u =  cellatípussal rendel(1, −1) projekció-irány egy, három különbözo  lineáris szisztolikus rácsot eredményez: mindkét végen levo  cellában csak osztóra van kezo, szükség. Az összes többi cella kap egy szorzó- és kivonó egységet, mindamellett egy osz és egy osztó nélküli cella váltja egymást A projekció egy bizonyos módja tóval rendelkezo egy szisztolikus rácsban inhomogenitáshoz vezethet (ami lehet hasznos – vagy sem). Gyakorlatok 7.5-1 Adjunk meg a mátrix és vektor szorzásának a 751 pontban leírt

változataira (az eredmények megadása egy végcellán keresztül, illetve az összes cellán keresztül) egy alkalmas rácsfelépítést be/kiviteli sémával, cellaszerkezettel, valamint vezérlési mechanizmussal együtt. 7.5-2 Tanulmányozzuk további projekciós irányok hatását a (751) rendszerre  eljárásokhoz 7.5-3 Adjuk meg a 752 pontban leírt beszúró, illetve kiválasztásos rendezo a hozzájuk tartozó szisztolikus rácsokat – beleértve a cellaszerkezetet is.  a 7.14 ábrán látható, buborékrendezésre használt szisztoli75-4? Hogyan muködtethet  o kus rács akár vezérlés nélkül is, a bemeneti adatfolyam ésszeru  megformálásával? 7.5-5? Mi a szerepe a MAX érték használatának a (747) rendszerben? Hogyan lehetne (7.47)-et kifejezni a e konstans érték használata nélkül? Milyen következményei lennének ennek a leírt szisztolikus rácsokra nézve? 314 7. Szisztolikus rendszerek (Eberhard Zehendner) Feladatok 7-1. Szalagmátrix

algoritmusok A 7.1 és 72 alfejezetekben, valamint a 751 és 753 pontokban mindig sur  u  mátrixok érték (az alsó háromszögból indultunk ki, azaz minden ai j mátrixelem nullától különbözo  mátrix esetében a foátló feletti elemek értéke ugyan mind nulla, de ezek nem képeznek bemenetet az említett algoritmus számára).  Ezzel szemben a gyakorlatban gyakran találkozunk szalagmátrixokkal. Ezeknél a foátló körüli keskeny sávot kivéve, a legtöbb átló nulla értékekkel van feltöltve Formálisan fennáll tehát, hogy ai j = 0 minden i, j-re, melyre i − j ≥ K vagy j −i ≥ L, ahol K és L pozitív egész számok. Tehát a sávszélesség, vagyis azon átlók száma, amelyekben a nullától  elemek megengedettek, K különbözo + L − 1.  Feltevodik tehát a kérdés, hogy egy vagy több bemeneti mátrix sávszerkezetét ki lehet-e  használni a szisztolikus számítások optimalizálására. Egyrészt fennáll annak a lehetosége,

hogy elhagyjuk azokat a cellákat, melyek soha nem végeznek hasznos munkát. Egy másik   optimalizálási lehetoség lehetne a be/kimeneti adatfolyam lerövidítése, a teljes futási ido lerövidítése vagy a teljesítmény növelése. Tanulmányozzuk, hogyan optimalizálhatók a fejezetben bemutatott szisztolikus rácsok  a szempontból. ebbol Megjegyzések a fejezethez  A szisztolikus rács fogalmát Kung és Leiserson vezette be, e területen úttöronek számító cikkükben [3].  Karp, Miller és Winograd az egyenletes rekurzív egyenletek területén végeztek úttöro munkát [2]. Rao doktori értekezése [6] és Quinton munkái [5] is lényeges ötletekkel járultak hozzá a szisztolikus rácsok módszeres tervezéséhez. Teich és Thiele [8] cikkükben rámutatnak, hogy a cellavezérlés hasonló módszerekkel  le formálisan, mint az általános rácsfelépítés és a normális cellafunkcionalitás. vezetheto Darte, Robert és Vivien modern könyve [1] a

fordítóprogramok kinomult módszereit  kapcsolja össze a szisztolikus rácsokkal, és alaposan foglalkozik az adatfüggoségek vizsgálatával.  [3] származik. A szalagmátrixokra vonatkozó feladat Kung és Leiserson cikkébol A szisztolikus rendszerek területén a legátfogóbb áttekintést mind a mai napig a [9] monográa nyújtja.  sejtautomataként. Egy cella regiszterei képeMinden szisztolikus rács modellezheto zik a cella állapotát. Szükség van tehát egy faktorizált állapottér használatára Amennyi típusú cellákkal rendelkezik (például változó cellaben a szisztolikus rács különbözo  cellavezérlés révén), ez az állapottér egy újabb kompofunkcionalitás vagy pozíciófüggo nensével írható le. Minden szisztolikus algoritmus felfogható olyan PRAM-algoritmusként, melynek vi selkedése idoben állandó. Ekkor egy szisztolikus cella minden regiszterét egy PRAM memóriacella valósítja meg, mely kizárólag ezt a célt szolgálja.

Mivel minden idoszelet- 7. Megjegyzések a fejezethez 315  a regiszterbol,  és ugyanakkor pontosan egy ben pontosan egy szisztolikus cella olvas ebbol  az EREW-PRAM-modell. szisztolikus cella ír ebbe a regiszterbe, megfelelo A szisztolikus rendszerek a Lynch [4] által leírt szinkronizált hálózatok speciális esetei.  azonos a két rendszerben. A szisztolikus rendszerekben az üzenetek számát A futási ido nem szokás vizsgálni. A szisztolikus rendszerekben gyakran megkívánt – peremen át tör be/kivitel szinkronizált hálózatokkal jól modellezheto  A hibák fogalma a szisztolikus téno rendszerek vizsgálatához nem szükséges. Részletesen foglalkozik a szisztolikus rendszerekkel Sima, Fountain és Kacsuk könyve, amely magyarul is megjelent [7]. Irodalomjegyzék [1] A. Darte, Y Robert, F Vivien Scheduling and Automatic Parallelization Birkhäuser Boston, 2000 314 [2] R. M Karp, R E Miller, S Winograd The organization of computations for uniform

recurrence equations Journal of the ACM, 14:563–590, 1967. 314  [3] H. T Kung, C E Leiserson Systolic arrays (for VLSI) In I S Duff, G W (szerkesztok), Sparse Matrix Proceedings, 256–282. o SIAM, 1978 314 [4] N. A Lynch Distributed Algorithms Morgan Kaufman Publisher, 2001 (Ötödik kiadás Magyarul: Osztott algoritmusok. Kiskapu Kiadó, 2002) 315 [5] P. Quinton Automatic synthesis of systolic arrays from uniform recurrent equations In Proceedings of the 11th Annual International Symposium on Computer Architecture, 208–214. o, 1984 314 [6] S. K Rao Regular iterative algorithms and their implementations on processor arrays Doktori értekezés, Stanford University, 1985. 314 [7] D. Sima, T Fountain, P Kacsuk Advanced Computer Architectures: a Design Space Approach AddisonWesley Publishing Company, 1998 (2 kiadás Magyarul: Korszeru  számítógéparchitektúrák tervezésitérmegközelítésben. Szak Kiadó, 1998) 315 [8] J. Teich, L Thiele Control generation in the design of

processor arrays International Journal of VLSI and Signal Processing, 3(2):77–92, 1991. 314 [9] E. Zehendner Entwurf systolischer Systeme: Abbildung regulärer Algorithmen auf synchrone Prozessorarrays B G Teubner Verlagsgesellschaft, 1996 314 Tárgymutató A, Á adatfolyam, 286 adatfolyam iránya, 289  adatfüggoség, 286 adatsebesség, 293 adatszerkezet indexe, 289 adatszerkezet vektor, 289 ipop állapotkapcsoló, 301  folyamfüggoség, 286 Fourier-Motzkin elimináció, 308 futószalag-elvu  feldolgozás, 278 futószalag-regiszter, 278  függoségi vektor, 286 architektúra szisztolikus, 276 G gazdagép, 269, 276 generikus operátor, 273, 288, 294 B be/kimeneti adatsebesség, 311, 312 be/kiviteli séma, 289, 290áb  bovített, 293, 294áb  be/kiviteli séma, bovített, 294 be/kivitel kiterjesztése, 293, 294 bemeneti adatfolyam, 277 bemeneti csatorna, 271 beszúró rendezés, 312 beviteli séma, 269áb buborékrendezés, 311, 312áb C cella, 269 vezérlésmentes,

298 cellaprogram, 307, 308, 309 cellaszerkezet, 269áb, 280áb, 287 H hardver-algoritmus, 268 háromszögmátrix alsó, 312 hatékonyság, 278 helyzetkép, 291 I, Í  idoszelet diszkrét, 275  idovektor, 281 indexhalmazok transzformációja, 307 indexkifejezés, 307 inhomogenitás, 313 irányított kapcsolat, 276 iterációs vektor, 274 CS csatorna, 271 K kapcsolat, 271, 276 D  diszkrét idoszelet, 275 E, É egyenlet megoldása, 274 egyidejuség,  275 értékadásmentes jelölés, 274 értéktartomány, 274 sur  konvex, 283  u kapcsolatszerkezet, 286 hexagonális, 287 késleltetés, 276 ki/beviteli séma, 277 kihasználtság, 296, 298 kimeneti csatorna, 271 kimeneti normál forma, 308 kiválasztó rendezés, 312 külvilág, 271, 276 kvantikálás, 274 értéktartomány transzformációja, 307 M mátrix F feladat paraméterei, 272 sur  u,  314 mátrix és vektor szorzása, 311 318 Tárgymutató mátrixszorzás, 269, 271, 273, 280 SZ memória, 276

szalagmátrix, 314 szétdarabolás, 277 O, Ó osztó, 313 szimbolikus meghatározás, 283 szinkron munkamód, 275 szisztolika, 268 szisztolikus, 268 szisztolikus algoritmus, 269  Ö, O összeadó, 271 egyenletes, 279 szisztolikus rács, 268, 269, 314 elfajult, 311 összekapcsolás, 296 hexagonális, 280, 284 lineáris, 312áb összetett muvelet,  275 téglalap alakú, 269áb P peremcella, 271 periódus, 304 politóp, 283 projekció, 281 többdimenziós, 278 szisztolikus rács pereme, 310 szisztolikus rendszer, 268–315, 269 szorzás-összeadás, 275 szorzó, 271 projekció iránya, 281, 293 projekciós mátrix, 281 projekciós vektor, 281 T teljesítmény, 304  276, 285 teljes végrehajtási ido, R rács paraméterei, 272 térbeli koordináták, 272, 283  tér-ido-leképezés, 279, 281, 282, 307 regiszter, 271, 287 rekurzív egyenlet, 274 rendezés, 311 S sávszélesség, 314 skalárszorzat, 273 sorba fejtés, 273 stacionárius, 288 stacionárius számítás, 278

stacionárius változók, 278, 296, 299 U, Ú unimoduláris mátrix, 283, 284 V vezérlés globális, 299 helyi, 299 vezérlés, osztott, 303 visszaállítás, 299áb Névmutató Tartalomjegyzék 7. Szisztolikus rendszerek (Eberhard Zehendner) . 268 7.1 . 268 7.11  példa: mátrixok szorzása . Bevezeto 269 7.12 A feladat és a rács paraméterei . 272 7.13 Térbeli koordináták . 272 7.14 Generikus operátorok sorba fejtése . 273 7.15 Értékadásmentes jelölés . 274 7.16 Elemi számítások . 275 7.17  Diszkrét idoszeletek 275 7.18  és belso  kommunikáció Külso 7.19 Futószalag-elvu  feldolgozás 7.2 7.3 7.4 7.5 A szisztolika alapfogalmai . . 276 . 278 . 279 7.21 Példa:

mátrixszorzás stacionárius változók nélkül . 280 7.22  leképezés, mint globális szemléletmód A tér-ido 281 7.23 A térkoordináták szimbolikus meghatározása . 283 7.24  szimbolikus kiszámítása . A teljes végrehajtási ido 285 7.25 A kapcsolatszerkezet levezetése . 286 7.26 A cellaszerkezet meghatározása  Tér-ido-leképezés és szisztolikus rács . . 287 A be/kiviteli séma levezetése . 289 7.31  az iterációs vektorokig . Az adatszerkezetek indexeitol 289 7.32  készült helyzetképek Adatszerkezetekrol . 291 7.33 A be/kiviteli séma megszerkesztése . 292 7.34   Tér-ido-leképezés által eloidézett adatsebesség 7.35  Be/kivitel kiterjesztése és a bovített be/kiviteli séma . 293 7.36 A stacionárius változók kezelése . 296 7.37

Számítások összekapcsolása . 296 Vezérlési szempontok . 298 7.41 Vezérlésmentes cellák . 298 7.42 Globális vezérlésu  cellák . 299 7.43 Helyi vezérlés . 299 7.44 Osztott vezérlés . 303 7.45 A cellaprogram, mint lokális szemléletmód . 293 . 307 Lineáris szisztolikus rácsok . 310 7.51 311 Mátrix és vektor szorzása . 321 Tartalomjegyzék 7.52 Rendezés 7.53 Lineáris egyenletrendszer alsó háromszögmátrixszal . 311 . 312 Irodalomjegyzék . 316 Tárgymutató . 317 Névmutató 319