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 (be­leé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 ele­jén, még a párhuzamos számítógépek, a többprocesszorra rendszerek tényleges meg­jelené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 ku­tatá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árhuza­mra 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ét­rehozni. A operációkutatás területe az egyik első olyan terület, ahol már érezhető en­nek 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él­dá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 ki­dolgoztá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 feladat­modulok 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)

Next