Új ütemező algoritmusok a magas szintű szintézisben
(Összefoglalás)

Orbán András, Műszaki informatika szak, V. évfolyam
Mann Zoltán Ádám, Műszaki informatika szak, V. évfolyam

Konzulens: Dr. Arató Péter


A magas szintű szintézis (HLS) alapfeladata egy magas szinten (pl. programozási 
nyelven, pszeudokódban stb.) specifikált algoritmushoz az azt megvalósító optimális hardver 
illetve szoftver struktúra automatikus megtervezése. Az optimalizálás különböző szempontok 
alapján történhet, például hardver esetén a megvalósításban szereplő processzorok száma, a chip 
mérete stb. A HLS számos nehéz matematikai (gráfelméleti, algoritmuselméleti stb.) problémát 
vet fel, amelyek közül néhány bizonyíthatóan NP-teljes. Ezek hatékony megoldására a mérnöki 
tapasztalatot felhasználó heurisztikus közelítéseket lehet használni.
A szintézis folyamata jól elkülöníthető lépésekre bontható, ezek közül mind futási idő, 
mind az eredmény minősége szempontjából az ütemezés problémája a kritikus. Ez egy 
kombinatorikus optimalizálási feladat, melynek során az eredeti algoritmusban szereplő elemi 
műveleteket megvalósító logikai egységek indítási idejét kell meghatározni oly módon, hogy a 
kapott ütemezés valamilyen előre megfogalmazott optimalitási kritériumnak minél jobban 
megfeleljen. A probléma NP-teljes, így nagy méretű bemenetek esetén különböző heurisztikákkal 
kell a kombinatorikus robbanást megakadályozni. 
Erre a feladatra készítettünk két különböző megoldást. Az első egy genetikus algoritmus, 
melyet C nyelven implementáltunk. Ennek során különböző ütemezésekből egy egész populációt 
állítunk össze, melyet az evolúciót szimuláló lépésekkel alakítgatunk, törekedve arra, hogy egyre 
jobb tulajdonságú egyedek jöjjenek létre. 
A másik megoldás logikai programozáson alapul, és Prolog nyelven íródott. Ebben az 
esetben a feladatot korlát-kielégítési problémaként fogalmazzuk meg, és a Prolog CLP 
(Constraint Logic Programming) könyvtárát használjuk a korlátok kezelésére. Többszörös lokális 
kereséssel és egy korábbi tapasztalatokból származó heurisztika felhasználásával igyekszünk 
minél jobb megoldást találni.
A dolgozat a két megoldás ismertetése mellett részletesen összehasonlítja azokat 
egymással, valamint más, eddig is alkalmazott algoritmusokkal.