ALKALMAZOTT MATEMATIKAI LAPOK 17. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1993)
1993 / 1-2. sz. - BÁLINT ERZSÉBET - DEÁK ISTVÁN: Párhuzamos számítógépek: optimalizálási programok
PÁRHUZAMOS SZÁMÍTÓGÉPEK: OPTIMALIZÁLÁSI PROGRAMOK 3 kolt a kommunikáció: ezek az algoritmusok az adatokat osztják el a processzorok között, és a számításokat a processzorok együtt végzik el. Vannak már durván szemcsézett gépekre kidolgozott változatok is, de ezek is csak a három lépésen belül párhuzamosítanak, és az implementációs eredmények szerint kevésbé jók, mint a kis modulszemcsézettségű algoritmusok. A szimplex algoritmus első párhuzamos változatai esetén szisztolés rendszereket terveztek az algoritmus végrehajtására. Az első rendszer (K. Onaga és H. Nagayasu (1984)) egy VLSI wavefront array processor implementáció volt, melyben az algoritmus végrehajtásához szükséges processzorok száma a megoldandó feladat méretétől függött. Egy másik szisztolés rendszerben (A.A. Bertossi, M.A. Bonicelli, 1987) a processzorok egy m X n-es fa-hálózatot alkotnak (ahol m — 1 a feltételek, n — 1 a változók száma), azaz a feldolgozóegységek közül mn egy m x n-es négyzetrácson helyezkedik el, és a többi csúccsal úgy van összekötve, hogy az i-edik sorban lévők is illetve a j-edik oszlopban lévők is egy teljes bináris fa leveleit alkotják (i = 0,..., m — 1, j = 0,..., n — 1). A négyzetrácson elhelyezkedő processzorok között vannak elosztva a feladat adatai, a többi processzor a levelek és a fák gyökereit összekötő, általános célú host processzor közötti kommunikációt biztosítja. Az egyes feldolgozóegységek működése egy közös órajelhez van szinkronizálva. A processzorok felépítése egyszerű: néhány regiszterből, egy aritmetikai és logikai egységből és egy vezérlőegységből állnak. A processzorok közötti kommunikáció kétirányú síneken keresztül zajlik. Bertossi és Bonicelli, alsó becslést adva arra az időre, amely alatt egy p x q-as (p X q = 0(mn)) tömbben illetve egy bináris fa-hálózatban összekapcsolt többprocesszoros rendszer végre tud hajtani egy pivot lépést, azt is megmutatta, hogy ezen a rendszeren jobb eredmények érhetők el, mint bármely tömbprocesszoron. A chip felépítésével viszont az a gond, hogy bár a VLSI technológiával az ilyen — sok, viszonylag egyszerű processzorból álló — szisztolés rendszert egyetlen, vagy legfeljebb néhány áramköri tokban meg lehet valósítani, előfordulhat (minél nagyobb integráltságú egy áramkör, annál gyakrabban), hogy néhány feldolgozóegység vagy sín meghibásodik, ilyen esetben a rendszeren implementált algoritmusok eredményei sem megbízhatók. Széles körben foglalkoznak már azzal a kérdéssel, hogyan lehet olyan hibatűrő redszereket tervezni, amelyek a hibákat felismerik és, önmagukat például újrakonfigurálva, más, működőképes struktúrát alakítanak ki. Ilyen rendszer az A.A. Bertossi és M.A. Bonicelli által a szimplex algoritmus végrehajtására tervezett másmilyen felépítésű VLSI chip (A.A. Bertossi, M.A. Bonicelli, 1989). Ebben a PE-k egy ún. cousin-connected tree-t (CCT) alkotnak, azaz egy olyan teljes bináris fát, amelyben egy tetszőleges csúcs bal (jobb) utóda a csúcs bátyjának bal (jobb) utódával is össze van kapcsolva. A rendszerben ki kell jelölni a hibás csúcsokat; azok a csúcsok, amelyek a fa gyökeréből nem érhetők el nem hibás csúcsokon keresztül haladó egyszerű úton, az algoritmus szempontjából szintén használhatatlanok: ezek lesznek a „halott" csúcsok. A többi csúcs „élő". Az újrakonfigurált topológia egy hármas fa lesz (reconfigured ternary tree, RTT), csúcsai az élő csúcsok, élei pedig a CCT azon élei, melyeknek nincs hibás vagy halott Alkalmazott Matematikai Lapok 17 (1993) MAGYAR TUDOMÁNYOS AKADÉMIA KÖNYVTÁR-'