Algoritmus- és adatstruktúra-optimalizálás többmagos környezetben

OData támogatás
Konzulens:
Dr. Juhász Sándor
Automatizálási és Alkalmazott Informatikai Tanszék

Az algoritmusok párhuzamosítása manapság egyre inkább előtérbe kerül, a többmagos processzorok általános térhódítása miatt. A programok teljesítőképessége ezeken az architektúrákon már inkább párhuzamos végrehajtással növelhető, ezen a területen viszont általában komoly kihasználatlan erőforrások vannak.

Dolgozatomban a rendezési algoritmusok témakörével foglalkozom, a párhuzamosíthatóság kérdését előtérbe helyezve. Bevezetésként összefoglalom a leggyakrabban használt rendező algoritmusokat. Majd két, eredetileg egy szálon futó, ám jól párhuzamosítható algoritmuson bemutatom, hogy milyen megközelítéssel lehet, és milyennel nem lehet jó eredményeket elérni. Ez a két algoritmus a Mergesort és a Quicksort. Az elsőhöz olyan módszert keresek, mely a feladatot igyekszik minél szimmetrikusabban felosztani, így érve el jó párhuzamosítást. A másodiknál ettől eltérő megközelítéssel, inkább a feldolgozó folyamatok (ún. szálak), akár aránytalanul elosztott feladatokhoz való jó alkalmazkodását célzom meg. Utóbbihoz egy párhuzamos könyvtárat használok, a Task Parallel Library-t amely a szálkezelést a fejlesztő számára jelentősen leegyszerűsíti.

Ezek mellett bemutatok egy saját ötlet alapján készített algoritmust is, mely különböző – nem csak rendező – algoritmusok eredményeit, illetve már létező rendező algoritmusokat használ fel. Az elkészített párhuzamos algoritmusokat mások által implementált, ismert egyszálú algoritmusokkal és a Parallel Patterns Library beépített párhuzamos rendezéseivel hasonlítom össze. Az összehasonlítás alapja a futásidő, a gyorsulás és a skálázódás különböző (egész szám és karakteres) bemeneteken.

A karakteres bemenetek rendezése kapcsán kitérek a Unicode kódolások sajátosságaira, és az általa kínált nagyszerű lehetőségekre.

Az implementációt és a méréseket C++/CLI és natív C++ környezetben végeztem, amiknek sajátosságairól is ejtek pár szót a párhuzamos programozás kapcsán.

Összességében azt tapasztaltam, hogy bár a párhuzamos könyvtárak megkönnyítik párhuzamos végrehajtású programok készítését, a jó eredményhez elengedhetetlen az is, hogy a fejlesztők ismerjék a rendelkezésre álló fejlesztőeszközöket és tisztában legyenek az algoritmusok elméletével.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.