Futtatható gráf párhuzamos futtatása

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

Manapság a számítási kapacitás iránti igény, a számítógépek minden alkalmazási területén jelentősen növekszik. A megnövekedett igény kielégítéséhez nagyban hozzájárul az elérhető hardverek teljesítményének növekedése, valamint ezzel párhuzamosan az új szoftveres megoldások kialakítása is. A futtatható gráf egy olyan absztrakciós réteget képez, amelynek segítségével általános és gyors megoldás nyújtható a matematikai képletek kiszámításához. A képletek kiszámítására nagy igény van többek között a pénzügyi területen, ahol számos termék árát kell a lehető legrövidebb idő alatt meghatározni.

Egy futtatható gráf egy olyan gráf, amelynek a csúcsai egy-egy függvényt reprezentálnak. Egy gráf futtatásán, a gráfban lévő összes függvény kiértékelést értjük. A gráf élei irányítottak és azt határozzák meg, hogy az egyes függvények eredményei mely más függvényeknek a bemenete. Mivel a csúcsok bármilyen matematikai függvényt jelenthetnek, a gráf segítségével minden olyan képlet meghatározható, amely leírható matematikai függvények egymás utána alkalmazásával.

Az én feladatom a futtatható gráfok ütemezési tervének az elkészítése volt. Mivel a gráfokat egy többprocesszoros környezetben lesznek végrehajtva, az ütemezésnek a végrehajtás sorrendjén túl meg kell mondania, hogy az egyes függvényeket melyik processzor, milyen sorrendben hajtsa végre.

A munkám során megterveztem az ütemezési tervnek formátumát, valamint megterveztem és elkészítettem több listás ütemezésen alapuló algoritmus implementációját. Ezt követően a genetikus algoritmust alkalmaztam az ütemezési problémára és úgy alakítottam, hogy az minél jobb ütemezési tervet tudjon készíteni.

A végrehajtás tovább gyorsítható a legutolsó végrehajtás részeredményeinek felhasználásával. Ehhez egy olyan algoritmust dolgoztam ki és implementáltam, amelynek segítségével meghatározható, hogy mely csúcsokat kell újból végrehajtani, ha rendelkezésünkre áll a megelőző futás részeredményei.

Letölthető fájlok

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