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

2 BÁLINT E. ÉS DEÁK I. számítási feladatot jelenti, amelyet egy feladatmodul úgy végezhet el, hogy közben nem kommunikál más feladatmodulokkal: ez a jellemző tehát elsősorban azt tükrözi, hogy mekkora a kommunikáció szerepe az algoritmusban). Egy adott algoritmus gyakran természetes módon osztható fel függetlenül végrehajtható részfeladatokra, s a felosztás meghatározza, milyen lesz a feladatmodulok közötti kommunikáció. Ez persze nem azt jelenti, hogy az algoritmus minden párhuzamos változata szük­ségszerűen azonos modulszemcsézettségű: néhány algoritmusnak olyan párhuzamos implementációját is kidolgozták már, melyben a feladatmodulok szemcsézettsége eltér az általánostól. Azt, hogy ezek közül melyik jobb, elméleti és gyakorlati vizs­gálatoknak kell eldöntenie. Persze az elvi és gyakorlati összehasonlítás gyakran más-más eredményhez ve­zet. Egyes párhuzamos algoritmusok például hiába gyorsak, hatékonyak, csak ide­ális számítógépen implementálhatók — melyekben nincs sem memória-elérési, sem kommunikációs korlátozás —, vagy az implementációhoz speciális többprocesszoros rendszer felépítésére van szükség (általában a szisztolés rendszereket felhasználó al­goritmusok ilyenek), esetleg a felhasznált processzorok száma függ a megoldandó feladat méretétől, így a már létező gépek csak kis feladatok megoldására alkalmaz­hatók. Egy létező gépre tervezett párhuzamos algoritmus pedig éppen azért lesz az elméletileg elvártnál kevésbé gyors vagy hatékony, mert alkalmazkodik az adott gép korlátaihoz. A párhuzamos algoritmusok vizsgálata persze minden irányba kiterjed, a létrehozott algoritmusok között minden változatra találunk példákat. A párhuzamos számítógépek felépítéséről és működéséről Hockney 1981, Ma­nuel 1988, Deák 1991 könyve illetőleg összeállítása nyújt áttekintést, az általános számítógépes algoritmusokat pedig Bertsebas 1989 és Quinn könyve foglalja össze. A cikkben az utóbbi években megjelent eredményekről nyújtunk áttekintést: a párhuzamos számítógépeken alkalmazható operációkutatási, optimalizálási algorit­musokról, az ezekkel elérhető számítógépes eredményekről adunk összefoglalást. A következő szakaszban a lineáris programozás szimplex módszerére vonatkozó ered­ményeket foglaljuk össze. A harmadik szakaszban a kombinatorikus optimalizálás branch and bound módszerének párhuzamos változatait tekintjük át. A negyedik részben a dekompozíciós, az ötödik részben pedig a relaxációs módszerekkel fog­lalkozunk, míg az utolsó szakaszban egyéb algoritmusokra vonatkozó eredményeket írunk le. 2. A szimplex algoritmus A lineáris programozási feladatok megoldására széles körben alkalmazott szimp­lex algoritmussal, gyakorlati és elvi jelentősége alatt, már többen foglalkoztak, többen próbáltak különböző szempontok szerint és különböző párhuzamos környe­zetben implementálni. A kidolgozott párhuzamos szimplex algoritmusok közül a legtöbb kis modulszemcsézettségű: a szimplex iterációk három lépésén (pivot osz­lop kiválasztása, pivot sor meghatározása, pivotálás) belül osztják fel az algoritmust párhuzamosan végrehajtható feladatokra. Az így kapott részfeladatok között gya- Alkalmazott Matematikai Lapok 17 (1993)

Next