Elosztott algoritmusok optimális alkalmazása klaszterekben

Juhász Sándor

Budapesti Műszaki és Gazdaságtudományi Egyetem

Villamosmérnöki és Informatikai Kar

Automatizálási és Alkalmazott Informatikai Tanszék

1111 Budapest, Goldmann György tér 3. IV. em.

E-mail: juhasz.sandor@aut.bme.hu

Kivonat

A szabványos kommunikációs hálózattal összekötött, szabványos személyi számítógépekből felépített klaszterek olcsó alternatívát kínálnak a hagyományos szuperszámítógépekkel szemben a nagy számítási igényű feladatok elvégzésére, mivel a modulárisan felépülő klaszterekben a hibatűrés és a skálázás megoldása lényegesen egyszerűbb. Az általános célú kommunikációs elemek azonban kisebb átbocsátó képességet biztosítanak drágább speciálisan egy adott feladathoz kifejlesztett társaiknál, ezért a klaszterekben az elosztott algoritmusok tervezésekor a kommunikáció tervezése kritikus szerephez jut. Minden elosztott megoldásnál felvetődik, és a klasztereknél a szűkebb kommunikációs keresztmetszet miatt különös hangsúlyt is kap az a kérdés, hogy a feladat elosztásával járó munka költsége nem haladja-e meg az elosztásból származó hasznot, azaz megéri-e egyáltalán és milyen mértékben és feltételek mellett érdemes az adott problémát elosztva megoldani.

Az algoritmusok futási sebességét alapvetően befolyásolja feladatok csomópontok között történő szétosztására, valamint az eredmény összeállításához alkalmazott kommunikációs minta is. Cikkünkben a tartomány dekompozícióval felbontható, eredményüket több iterációs lépéssel előállítható feladatosztályt vizsgáltuk. Bemutatásra kerül egy matematikai modell, mely ennek a viszonylag általános feladatosztálynak az elosztott megoldásmenetét írja le. Ebből a modellből egyértelműen meghatározható, hogy érdemes-e egyáltalán, és ha igen, milyen paraméterek alkalmazása mellett lehet az adott feladatot egy adott hardver környezetben optimálisan elosztottan megoldani. Választ kapunk arra a kérdésre is, hogy a megoldásban résztvevő csomópontok száma hogyan befolyásolja az eredmény előállításának sebességét, az előállításához szükséges munkaráfordítást és a számítás hatásfokát.

A számítások gyakorlati alkalmazhatóságát a cikk végén két gyakorlati példával illusztráljuk, melyek a lineáris algebra illetve a számítógépes képszintézis terültéről származnak.