Gráf tulajdonságok számítási idejének optimalizálása párhuzamos programozási módszerekkel

OData támogatás
Konzulens:
Csernai Márton László
Távközlési és Médiainformatikai Tanszék

Napjainkban fontos kérdés a gráf problémák kutatása, algoritmusok tervezése és optimalizálása, hiszen a modern hálózatok, például az internet topológia és közösségi hálózat, könnyedén reprezentálhatóak gráfokkal. A párhuzamos programozási paradigma azért terjedt el, mert egy feladat független részeinek párhuzamos szálakban futtatása eredményeképpen gyorsabban tudja a processzor elvégezni az adott feladatot. A vizsgált hálózatok mérete meghaladhatja a több millió csomópontot, emiatt a hagyományos gráf vizsgáló módszerek túl időigényessé válhatnak, ezért aktív érdeklődés övezi a gráf vizsgáló algoritmusok párhuzamosítását. A szakdolgozatom során bemutatom a párhuzamosítási lehetőségeket processzorra egy szabadon felhasználható multi platform szálkezelő könyvtárral, illetve grafikus kártyára a CUDA programnyelvvel, melynek alapjait részletesen ismertetem. Bemutatom a választott processzor szálkezelő könyvtár és a CUDA használatát Visual Studio 2010 fejlesztőkörnyezetben. Megtervezem és megvalósítom a következő algoritmusokat processzorra szekvenciális, illetve több szálú változatban és grafikus kártyára több szálú változatban: fokszámeloszlás számítás, klaszterezettség számítás, szélességi bejárás, maximális folyam-minimális vágás. Letesztelem az algoritmusok helyességét. Részletesen megvizsgálom a megvalósított párhuzamos algoritmusok futási idejét, és megmutatom, hogy a klaszterezettség és maximális folyam számítás esetén párhuzamosítással akár 40%-os futási idő csökkenést is el lehet érni.

Letölthető fájlok

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