Informatika | Számítógép-architektúrák » 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 c21 c22 c23 c24 c25 a34 a33 a32 a31 0 c31 c32 c33 c34 c35 0 (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 × N méretu  A mátrixnak egy N × 5 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  konkrét feladat A beviteli séma az N = 4 értéknek felel meg. A 71 ábra a következo megoldását mutatja: A·B =C , ahol   a11  A =   a21 a31   b11  b21  B =   b31 b41   c11  C =   c21 c31    a24   , a12 a13 a14 a22 a23 a32 a33 b12 b13 b14 b22 b23 b24 b32 b33 b34 b42

b43 b44 c12 c13 c14 c22 c23 c24 c32 c33 c34 a34    b25   , b35   b15 b45    c25   , c15 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 ← 1 to N1 do for j ← 1 to N2 2 do c(i, j) ← 0 3 for k ← 1 to N3 4 do c(i, j) ← c(i, j) + a(i, k) · b(k, j) 5 6 return C Ha N1 = N2 = N3 , akkor ennek az algoritmusnak a végrehajtása során Θ(N ) összea3 dást, Θ(N ) szorzást és Θ(N ) értékadást kell végrehajtani, ezért egy soros processzoron a 3 3 futási ideje Θ(N ). A P 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 . Számítások c(i, j, k) = c(i, j, k − 1) + a(i, k) · b(k, j) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 . (7.1) Kimeneti muveletek  ci j = c(i, j, N3 ) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 . 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 = 0-val jelöljük, a kimeneti adatokat  pedig k = N3 -mal. A következoket kapjuk: Bemeneti muveletek  c(i, j, k) = 0 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 .

Számítások c(i, j, k) = c(i, j, k − 1) + a(i, k) · b(k, j) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 . (7.2) Kimeneti muveletek  ci j = c(i, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 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. A fentieket alkalmazva a (7.1) rendszerre, a c(i, j, k) = c(i, j, k − 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) = 0 bemeneti muvelethez  is ugyanazt az (i, j, k) koordinátahármast rendelhetjük

hozzá; persze  értéktartományokat itt minden esetre érvényes, hogy k = 0. Egyébként a példában szereplo ú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 = 0 az ido 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  történik. Másrészt ugyanúgy megfelelne az is, ha az (i, j, k) koordinátákat az i + j + k idoponthoz 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   számításra

ekkor a t = 3 idopontban  idopontban megy végbe. A legelso 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 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 1 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , b(i, j, k) = bk j i = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , c(i, j, k) = 0 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 . Számítások a(i, j, k) = a(i, j − 1, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , b(i, j, k) = b(i − 1, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , c(i, j, k) = c(i, j, k − 1) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3

(7.3) + a(i, j − 1, k) · b(i − 1, j, k) . Kimeneti muveletek  ci j = c(i, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 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ács ban is a t = i + j + k idopontban történik az (i, j, k) elemhez kapcsolódó számítások elvégzése. Ugyanezt egy  π=  1 1 1 (7.4) 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 (7.5)     i  1 ·  j  = i + j + k .   (7.6) k A 7.1 ábrán látható példában végrehajtott muveletek  z = (x, y) térkoordinátáit, a 7.13 pontban leírt egyezményünk alapján a v = (i, j, k) iterációs vektorokból következtethet- jük ki. Az itt megválasztott leképezés

az R 3 tér k tengely menti projekcióját végzi el. 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 = (0, 0, 1) egy lehetséges proA (7.7)-ben szereplo 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 π idovektor.  T elso  példa esetén a tér-ido-leképezés   A 7.1 ábrán szereplo T mátrixa a következo:   1  T =   0 1    0   , 0 0 1 1 (7.12) 1  példa esetén pedig a 7.3 ábrán szereplo   0  T =   −1 1 −1 1 1    0   . 1 (7.13) 1  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 R 2 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 R -ból) Általában olyan értéktartományok fordulnak elo, 3  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 Z 3 rács projekciója egy egész számú P projekciós mátrix által a Z 2 rácshoz vezet,  amennyiben a P-t egy π egész számú idovektor megválasztásával egy unimoduláris T mátrixra 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 invertá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 (N3 − 1, 0), (N3 − 1, 1 − N1 ), (0, 1 − N1 ) , (1 − N2 , N2 − N1 ), (1 − N2 , N2 − 1), (N3 − N2 , N2 − N1 ) . (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. 7.2 Tér-ido-leképezés  és szisztolikus rács 285 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 − 1, 1 − 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 ezzel a teljes tartományt. Minden alkalommal azonban, amikor a téglalapot egy cellával feljebb és jobbra toljuk, csupán N1 + N3 − 1 új cella jön hozzá az eddigiekhez. Ez összesen N1 N3 + (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 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  mely szerint N1 , N2 , N3 ≥ 1 N2 , 1 + N1 + N3 , 1 + N2 + N3 , N1 +

N2 + N3 }. Az alapfeltevésbol,  következik, hogy a minimum 3, a maximum pedig N1 + 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  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 A feladat paramétereinek az N1  12 − 3 + 1 = 10 idoszeletet  kiszámolt teljes végrehajtási ido tesz ki. Ha N1 = N2 = N3 , akkor a szisztolikus algoritmus egy Θ(N ) cellát tartalmazó rend2  alatt határozza meg két, N × N méretu szerrel Θ(N) ido  mátrix szorzatát. 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  c(i, j, k) irányában, egy adatfolyam történik. Van tehát egy adatfolyamunk c(i, j, k − 1)-tol a(i, j − 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  kapott A c(i, j, k) iterációs vektora (i, j, k), a c(i, j, k − 1)-é pedig (i, j, k − 1). Az ebbol különbségvektor pedig     i      dC =   j  −  k i j k−1      0      =  0  . (7.18) 1  módon kapjuk: Ugyanúgy, megfelelo        i   i   0        dA =  j  −  j − 1   =  1     k és k   

    i   i − 1   1        dB =  j  −     j  =  0  . k k (7.19) 0 0 (7.20) 287 7.2 Tér-ido-leképezés  és szisztolikus rács  hogy A (7.3) rendszer a(i, j, k) = a(i, j − 1, k) 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) kifejezésben. Ugyanez érvényes a b(i, j, k) = 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 0  váltoszámítjuk ki. Ha ennek kiszámításához egy másik, v iterációs vektorral rendelkezo 0

0  zópéldányra is szükség van, akkor ez a P · v cellában számítódott ki és d = v − v függoségi 0 0  vektor jellemzi a köztük fennálló adatfüggoséget. Ez a z = P · v cellától a z = P · v cella  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) 0 = P · v − P · v0 = P · (v − v0 ) = P · d. ~  cellán belül történik, ami Amennyiben P · d = 0, a kommunikáció a számítást végzo leképzés lineáris voltából következik, hogy z − z   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  cella közötti kommunikációra lesz szükség. Ha viszont P · d , ~ 0, akkor két különbözo 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 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 = (−1, 1), P · d B = (0, −1) és P · dC = (1, 0) A három P · d vektornak zok  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 π · v ido 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 iterációs

vektorral 0  változópéldány szükséges, akkor ez utóbbi értéke a π · v idoszeletben  rendelkezo került 0   kommunikáció tehát pontosan kiszámításra. A d = v − v függoségi vektornak megfelelo  π · v − π · v0 idoszeletet vesz igénybe. 0 Mivel a (7.6) leképezés lineáris, fennáll π · v − π · v = π · (v − v0 ) = π · 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 egyes tárolt érték esetén, a cellának pontosan π · d regiszterre van szüksége, melyeken az  é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 · d , ~ 0, illetve (7.6)  és (7.4) összefüggések következtében π · d = 1 Tehát minden egyes d függoségi vektorhoz 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 = (0, 1, 0) függoségi vektor tartozik. Ennek projekciója, P · dA = (−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 az A regiszteren keresztül). Ugyanígy b(i − 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 tül), c(i, j, k − 1) pedig fentrol 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   1  T =   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 R 3 nek elemei, és mind egy egyenesen helyezkednek el a q = (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   1  j  =  0    k 0    0   · 0 1 i k !      0   0      + j ·  1  +  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á.  megjelenítés az alábbi: Mivel b(i, j, k) = bk j , a B mátrixnak megfelelo     i   0  j  =  0    k 1    1   · 0 0 k j !      1   0      + i ·  0  +  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   1  j

 =  0    k 0    1   · 0 i      0   0      + k ·  0  +  0  .     ! j 0 1 (7.25) 0 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,  sorban levo  elemhez vezeto  átmenetet írja le: (1, 0) = (x + 1, y) − (x, y). és a következo  helyzetképeket mutatnak A 7.1(a) és 76 ábrákon látható be/kiviteli sémák különbözo  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ó, 0  az itt most nem lényeges. Tehát a π · v = π · v egyenloséget összevetjük azzal, hogy v = H ·w+λ·q+ p és 0 v = H · w 0 + λ0 · q + p . (7.26) Ez azt eredményezi, hogy π · H · (w − w0 ) + (λ − λ0 ) · π · q = 0 ,

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

∆z = (2, −1) térbeli A sorok esetében a ∆w = (0, 1) különbségvektorunk van, melybol különbségvektor következik. Ugyanígy az oszlopok esetében ∆w = (1, 0)-ból következik a ∆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    ·  1  = 0   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 = (0, 0) cellában legyenek. lelo 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 7.3 A be/kiviteli séma levezetése 293   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) = a n ik 1 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 , b(i, j, k, n) = b i = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 , c(i, j, k, n) = 0 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0, 1 ≤ n ≤ 3 . n kj 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) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 , b(i, j, k, n) = b(i − 1, j, k, n) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 , c(i, j, k, n) = c(i, j, k − 1, n) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , 1 ≤ n ≤ 3 . + a(i, j − 1, k, n) · b(i − 1, j, k, n) Kimeneti muveletek  ci j = c(i, j, k, n) n 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 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   0  T =   −1 1 −1 1 1 0 1 1    0   . 0 (7.32) 1 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.   megválasztásával a három megT utolsó sora újraépíti a π idovektort. A π megfelelo  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) Kiszámítjuk most az átlagos kihasználtságot összekapcsolással, illetve e nélkül az N1 = 3, N2 = 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 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) c11 c21 c31 c12 c22 c32 c13 c23 c33 c14 c24 c34 c15 c25 c35 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 szom kapcsolatait az A és B mátrix elemeinek szédos (i, j + 1) és (i + 1, 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 + 1, j) cellának továbbítanánk, ez

értékütkö zéshez vezetne: mivel az (i + 1, 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 1 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , b(i, j, k) = bk j i =

0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , c(i, j, k) = 0 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 . Számítások a(i, j, k) = a(i, j − 1, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , b(i, j, k) = b(i − 1, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , c(i, j, k) = c(i, j, k − 1) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 (7.33) + a(i, j − 1, k) · b(i − 1, j, k) . Átvezetés b(i, j, k) = c(i, j, k − 1) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ i + N3 , c(i, j, k) = b(i − 1, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 + 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) = aik 1 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , b(i, j, k) = bk j i = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , c(i, j, k) = di j 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , k = 0 . Számítások a(i, j, k) = a(i, j − 1, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , b(i, j, k) = b(i − 1, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , c(i, j, k) = c(i, j, k − 1) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 (7.35) + a(i, j − 1, k) · b(i − 1, j, k). Átvezetés b(i, j, k) = c(i, j, k − 1) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ i + N3 , c(i, j, k) = b(i − 1, j, k) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 + 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 + N3   idoszeletben kapcsol át adattovábbító üzemmódba, és a t + N1 + 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  N1 + N3 idoszeletben egy új (7.34) feladat

megoldásába kezdhet, ugyanez a 711 ábrán lát ható szisztolikus rács esetében csak minden 2N1 + 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 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 i = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 . s(i, j, k, n) = 1 i = 0, 1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ N1 + N3 . s(i, j, k, n) = s(i − 1, j, k, n) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 . Adatbevitel a(i, j, k, n) = aik n 1 ≤ i ≤ N1 , j = 0, 1 ≤ k ≤ N3 , b(i, j, k, n) = bk j i = 0, 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 , n n+1 b(i, j, k, n) = dN +N

+1−k, j 1 i = 0, 1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ N1 + N3 . 3 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 . Adatokkal végzett muveletek  a(i, j, k, n) = a(i, j − 1, k, n) ( b(i, j, k, n) = 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 , b(i − 1, j, k, n) : s(i − 1, j, k, n) = 0 c(i, j, k − 1, n) : s(i − 1, j, k, n) = 1   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 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 . : s(i − 1, j, k, n) = 0 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 , : s(i − 1, j, k, n) = 1 Adatkivitel c1+N +N −k, j = b(i, j, k, n) i = N1 , 1 ≤ j ≤ N2 , 1 + N3 ≤ k ≤ N1 + N3 . n 1 3 (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   1  T =   0 1 0 0 0 1 0 0 1 1 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 b43 b33 b23 b13 d13 d23 d33 b44 b34 b24 b14 d14 d24 d34 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 i = 1, j = 0, 1 ≤ k ≤ N3 , s(i, j, k, n) = 1 i = 1, j = 0, 1 + N3 ≤ k ≤ N1 + N3 , s(i, j, k, n) = s(i − 1, j, k, n) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N1 + N3 , (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) 1 ≤ i ≤ N1 , 1 ≤ j ≤ N2 , 1 ≤ k ≤ N3 . A c programváltozók c(i, j, k − 1) példánya az i, j és k − 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:       i   0 −1  x   y  = T ·  j  =  −1 1      t k 1 1      i     0   ·  j  . 1 (7.39) k 1 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.       −1 −2  x   i   j  = T −1 ·  y  = 1 ·  −1 1   3    k t 2 1      x     1   ·  y  . 1 1 (7.40) t  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   a következo  is biztosítja. A π idovektorra és u projekciós irányra vonatkozóan elegendo tulajdonság: π · u , 0.  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)) = F (. , s(ψ s (v)), ), v ∈ S . (7.41) ψr , valamint ψ s indexfüggvények a programváltozók példányait indexkifejezés- A  párokként állítják elo.  transzformációja Az értéktartomány egy S -en injektív ϕ függvény segítségével történo  által a (7.41) a következoképpen alakul át: r(ψr (ϕ −1 ahol ϕ −1 (e))) = F (. , s(ψ s (ϕ −1 (e))), . ), e ∈ ϕ(S ) , (7.42) egy függvény, amely ϕ(S )-en a ϕ inverz függvényét képezi. Az új indexfüggvények −1 ψr ◦ ϕ , valamint ψ s ◦ ϕ−1 . 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 (742) a következoképpen alakul: r(ϑr (ψr (ϕ −1 (e)))) = F (. , s(ϑ s (ψ s (ϕ −1 (e)))),

. ), e ∈ ϕ(S ) . Amennyiben a kimeneti normál formát szeretnénk megkapni, a ϑr ◦ ψr ◦ ϕ −1 (7.43) -nek az identi- tásfüggvénynek kell lennie. A (példában látható) legegyszerubb  esetben ψr mindig az identitásfüggvény és ψ s egy  ψ s (v) = v − d alakú affin leképezés, konstans d-vel, a már ismert függoségi vektorral. ψr  ki d = ~ ugyanúgy fejezheto 0-ral. Az értéktartományok transzformációja a ϕ(v) = T · 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 opc,  src, dst) minden egyes idoszeletben pontosan adottnak kell lennie.  adódik. A veAz éppen

végrehajtandó muvelet  (opc) közvetlenül az F függvénybol  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. Fourier”  adódik az új T · d függoségi   áll, A (7.44) rendszerbol vektor, amely két komponensbol   A ∆z térbeli rész, mint különbegy 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 ∆t − 1 másolási muveletet  hajt végre, melynek során az operandusok értékei ∆t − 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, y, t) = b(x − 1, y, t − 1) : s(x − 1, y, t − 1) = 0 c(x, y, t − 1) :

s(x − 1, y, t − 1) = 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) (7.45) : s(x − 1, y, t − 1) = 0 : s(x − 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á-  kapják. C(0, −1) a cella bal szélén henak a cella középpontjához viszonyított helyzetébol lyezkedik el, C(0, 1) a jobb szélen, C(−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 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) 1 + x + y ≤ t ≤ x + y + N3 , b(x, y, t) = b(x − 1, y, t − 1) 1 + x + y ≤ t ≤ x + y + N3 , c(x, y, t) = c(x, y, t − 1) 1 + x + y ≤ t ≤ x + y + N3 + 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 + 1 + N3 ≤ t ≤ 2 ∗ x + y + N3 , (7.46) x + y + 1 + N3 ≤ t ≤ 2 ∗ x + y −1 + N3 .  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 Θ(N)-nek kell lennie. A beviteli mátrixnak Θ(N ) 2   eleme van, tehát Θ(N) elemet kell idoszeletenként bevinni. Egy idoszeleten belül a vég adatok száma azonban korlátozott. Az esetünkben Θ(N) nagyságrendu cellákba bemeno   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 ≤ mk érvényes mekbol  legyen minden (i < k)-ra. A feladatot a következoképpen fogalmazhatjuk meg értékadásmentes jelölést használva, ahol MAX G maximumát jelöli: Bemeneti muveletek 

x(i, j) = xi 1 ≤ i ≤ N, j = 0 , m(i, j) = MAX 1 ≤ j ≤ N, i = j − 1 . Számítások m(i, j) = min{ x(i, j − 1), m(i − 1, j)} 1 ≤ i ≤ N, 1 ≤ j ≤ i , x(i, j) = max{ x(i, j − 1), m(i − 1, j)} 1 ≤ i ≤ N, 1 ≤ j ≤ i . (7.47) Kimeneti muveletek  m(i, j) = m j 1 ≤ j ≤ N, i = N .  Egy u = (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 A (7.51)-beli képletek egy lokalizált algoritmust írnak le az A · x = b lineáris egyenletrendszer megoldására, ahol az (N × N)-es A mátrix egy alsó háromszögmátrix 313 7.5 Lineáris szisztolikus rácsok Bemeneti muveletek  a(i, j) = ai, j+1 1 ≤ i ≤ N, 0 ≤ j ≤ i − 1 , u(i, j) = bi 1 ≤ i ≤ N, j = 0 . Számítások u(i, j) = u(i, j − 1) − a(i, j − 1) · x(i − 1, j) 2 ≤ i ≤ N, 1 ≤ j ≤ i − 1 , x(i, j) = u(i, j − 1)/a(i, j − 1) 1 ≤ i ≤ N, j = i , x(i, j) = x(i − 1, j) 2 ≤ i ≤ N − 1, 1 ≤ j ≤ i − 1 . (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

 cellatípussal rendelrendelkeznek. Az u = (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 + L − 1. különbözo  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 H hardver-algoritmus, 268 háromszögmátrix alsó, 312 bemeneti adatfolyam, 277 hatékonyság, 278 bemeneti csatorna, 271 helyzetkép, 291 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 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

kapcsolatszerkezet, 286 hexagonális, 287 késleltetés, 276 ki/beviteli séma, 277 kihasználtság, 296, 298 E, É kimeneti csatorna, 271 egyenlet megoldása, 274 egyidejuség,  275 kimeneti normál forma, 308 értékadásmentes jelölés, 274 értéktartomány, 274 sur  konvex, 283  u 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