Gráfalapú modellek kezelése OpenCL környezetben

OData támogatás
Konzulens:
Dr. Mezei Gergely
Automatizálási és Alkalmazott Informatikai Tanszék

Napjainkban egyre több és több helyen használnak gráfokat az informatikai területen az egyes problémák vagy entitások közötti kapcsolatok reprezentálására. A gráfelmélet egy nagyon fontos kutatási ága a matematikának, és nagyon sok gráfelméleti kérdésre létezik algoritmus, ami véges lépésszám alatt válaszol az adott kérdésre. Vannak azonban olyan kérdések is, amik bizonyítottan NP-teljes problémák. Egy ilyen probléma például a kiegyensúlyozott gráf particionálás is, amely esetében még a relaxált probléma is NP-nehéz.

A diplomamunkám során a gráfparticionálási problémát ismertetem, és annak egy olyan lehetséges megoldását, amely képes a mai nagyteljesítményű videókártyák számítási kapacitását kihasználva megoldást adni a relaxált gráfparticionálási problémára.

A diplomamunka első részében ismertetésre kerül a gráfparticionálási probléma és a mai videókártyákban rejlő számítási potenciál, illetve a videókártya programozás lehetőségei. Ezt követően bemutatom a gráfparticionálással kapcsolatos irodalomkutatásom eredményeit. Itt bemutatásra kerülnek azok a publikációk, amelyekből ihletet merítettem a saját implementációm elkészítéséhez.

A diplomamunka további részében az a tervezési folyamat és implementáció kerül bemutatásra, amelynek segítségével létrehoztam a saját particionáló megoldásomat. A fejezetek során részletesen bemutatásra kerül minden megoldás és algoritmus, illetve azok a módosítások, amelyeket elvégeztem a forrásokban talált eljárásokon.

Az implementáció után bemutatom a mérési eredményeket, amelyben az implementált particionáló algoritmusomat hasonlítom össze egy széles körben elterjedt, CPU-n futó eljárással. Végezetül értékelem a kapott eredményeket, és megosztom a diplomamunka során szerzett tapasztalataimat és azokkal kapcsolatos gondolataimat.

Letölthető fájlok

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