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üksé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 vizsgálatoknak kell eldöntenie. Persze az elvi és gyakorlati összehasonlítás gyakran más-más eredményhez vezet. 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ó algoritmusok 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 alkalmazható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, Manuel 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 algoritmusokró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ó eredmé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 foglalkozunk, 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 szimplex 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örnyezetben 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 oszlop 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)