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
Alkalmazott Matematikai Lapok 17 (1993) 1-18 PÁRHUZAMOS SZÁMÍTÓGÉPEK, OPTIMALIZÁLÁSI PROGRAMOK BÁLINT ERZSÉBET ÉS DEÁK ISTVÁN Budapest A jelenleg létező párhuzamos számítógépes architektúrák rövid leírása után az optimalizálási programcsomagok és algoritmusok párhuzamos változatait tekintjük át. A cikk lényegi részében három fő témával foglalkozunk: a szimplex algoritmus változatai, a nemlineáris programozás (beleértve a hálózati folyamatokat) és a diszkrét programozás szoftverjei. A cikket egy 40-nél több tételt tartalmazó irodalomjegyzék egészíti ki. 1. Bevezetés A párhuzamos algoritmusok elméletének tanulmányozása a hatvanas évek elején, még a párhuzamos számítógépek, a többprocesszorra rendszerek tényleges megjelenése előtt megkezdődött. A különböző típusú párhuzamos rendszerek gyakorlati megvalósulása tovább fokozta a kutatók érdeklődését. Az utóbbi években egyre többen foglalkoznak az ilyen algoritmusok implementációjának kérdésével. A kutatások nagy része arra irányul, hogyan lehet az egyes algoritmusoknak minél jobb (gyorsabb, hatékonyabb) párhuzamos változatát létrehozni már meglévő párhuzamra számítógépeken. Sokan foglalkoznak azzal a kérdéssel is, hogyan lehetne egy adott algoritmus végrehajtása szempontjából minél jobb párhuzamra rendszert létrehozni. A operációkutatás területe az egyik első olyan terület, ahol már érezhető ennek a kutatásnak a hatása: számos olyan probléma, algoritmus van itt, amely nagy hasznát veszi a párhuzamos végrehajtási technika alkalmazásának — ilyenek például a nagy méretű operációkutatási feladatok, a fan kereső algoritmusok, szinte minden dinamikus programozási probléma, stb. A párhuzamra feldolgozás lehetővé teszi egyrészt azt, hogy nagyméretű feladatokat az eddiginél gyorsabban oldjunk meg, másrészt azt, hogy olyan komplex feladatokra, amelyek megoldása eddig túl költséges, esetleg lehetetlen volt, most gazdaságos megoldásokat adjunk, kiszélesítve így az operációkutatás számára megközelíthető problémák körét. Néhány operációkutatási algoritmusnak már több párhuzamra változatát is kidolgozták. Ezek persze számos jellemzőjükben különböznek egymástól: másképp történik bennük az algoritmus egymástól független feladatokra osztása, a feladatmodulok együttműködését, az algoritmus helyes végrehajtását biztosító vezérlés, eltérnek a kommunikáció geometriájában. Jellemző azonban, hogy egy algoritmus különböző párhuzamra implementációiban a modulok szemcsézettsége nagyjából azonos.A párhuzamos algoritmus moduljainak szemcsézettsége azt a maximális Alkalmazott Matematikai Lapok 17 (1993)