Modellparticionálási algoritmusok optimalizálása

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

Napjainkban a modellfeldolgozás során a gyakorlatban sokszor felmerülnek olyan nagy méretű modellek, melyek kezelése nem hatékony egyetlen számítógépen. Mind a számítási, mind a tárolási kapacitás szűkös keresztmetszet lehet, ezért ezeket a modelleket célszerű elosztott környezetben feldolgozni. Ehhez azonban a modelleket szét kell osztanunk az egymással kommunikáló számítógépek között úgy, hogy a modellfeldolgozás közben minél kevesebb üzenetet kelljen küldeniük a számítógépeknek. Ezt úgy érhetjük el, ha minimalizálni próbáljuk a particionált modellrészek közötti kapcsolatok számát.

A modellek általában könnyen leírhatóak gráfként, amiben a csúcsok az entitásoknak, az élek a köztük levő kapcsolatoknak felelnek meg. Így a modellek felosztásának problémája visszavezethető gráfok particionálására, ahol a partíciók közötti élek minimalizálása a cél.

A feladat részeként először tanulmányoztam a kapcsolódó szakirodalmat és részletesen megvizsgáltam a megoldandó feladatot. Megterveztem az algoritmus lépéseit és áttekintettem az előzetes információ felhasználásának lehetőségeit. Létrehoztam egy keretprogramot az algoritmus futtatásához, majd megvalósítottam az algoritmus lépéseinek különböző változatait és a modell szemantikájának ismeretét felhasználó továbbfejlesztett verziót. Ezt követően a teszteléshez gráfokat generáltam, majd több teszteset felhasználásával elemeztem az algoritmus paramétereit.

A diplomamunkámban bemutatom a már létező algoritmusokat a gráfparticionálási probléma megoldására, majd pontosítom a megoldandó feladatot. Ezután ismertetem az általam tervezett algoritmus lépéseit és a különböző megvalósításokat, közben kitérek a modell szemantikájának felhasználására. Utána bemutatom a gráfok generálásának módszerét és a tesztesetek eredményének elemzését. Végül áttekintem az elvégzett munkát és felvázolom az algoritmus továbbfejlesztési lehetőségeit.

Letölthető fájlok

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