Megosztott állapotterű tervezésitér bejáró algoritmusok
Napjainkban az informatika számos területén használunk gráffeldolgozó algoritmusokat a modellezési és fejlesztési folyamatok során. Többek között ábrázolhatók gráfokkal a tervezett rendszer modelljei, tudás- és adatbázisok, vagy összetett adatszerkezetek. A gráffeldolgozó algoritmusok ezeken a gráfokon képesek műveleteket végezni, például a rendszertervezésben architektúra javaslatokat állíthatunk elő automatikusan, a tudásbázison pedig következtetéseket végezhetünk a segítségükkel. Ezeknek a problémáknak az egyik lehetséges automatizált megoldási módszere a tervezési tér bejárás (angolul Desing Space Exploration, DSE), mely képes előállítani egy gráfnak több verzióját majd adott célfüggvény szerint kiválasztani a legmegfelelőbbet ezek közül.
Az ilyen algoritmusok futása során gyakran nagy méretű gráfok óriási mennyiségű különböző verzióját kell egyszerre tárolnunk és kezelnünk olyan módon, hogy nem csak egy korábbi verzióra való visszaállást tegyük lehetővé, hanem az összes verzió elérhető legyen egy időben. Ezáltal lehetővé válik a modellek különböző verzióinak összehasonlítása és a verziók közötti szabad váltogatás. Ez azonban rendkívül erőforrásigényes feladat: az algoritmus futása sokáig tarthat egy számítógépen, illetve a rendelkezésre álló memória is kevésnek bizonyulhat. További problémát jelentenek a bonyolult gráf generálási folyamat során esetlegesen előforduló hibák, amik érvénytelen eredmény gráfhoz vezethetnek.
A dolgozatom célja egy olyan módszer kidolgozása és bemutatása, ami lehetővé teszi a gráf feldolgozó algoritmusok térben vagy időben elosztott futtatását, ezzel javítja a tervezésitér bejárás teljesítményét, illetve robusztusságát.
A dolgozatomban bemutatok egy olyan algoritmust, ami képes a gráf verziók perzisztens tárolására és hálózaton való átküldésére, illetve a hálózaton keresztül megkapott gráf verziókat képes a saját felfedezett állapotteréhez hozzáadni. A perzisztens tárolással időbeli elosztottságot biztosít, így az algoritmus futása bármikor megszakítható és később folythatható az elmentett adatok alapján. A hálózaton való megosztással pedig a futásidő javítható, azáltal, hogy több számítógép képes egy adott problémán együtt dolgozni és a tervezési teret közösen bejárni. Az általam kidolgozott algoritmust esettanulmányok segítségével szemléltetem, módszer hatékonyságát teljesítménymérések segítségével vizsgálom.
A tervezésitér bejáró algoritmus futásideje az állapottér megosztásának köszönhetően javul, így olyan feladatok megoldásában is hatékonyabban lehet használni, ahol az állapottér nagy mérete miatt eddig nem lehetett. Ezenkívül az állapottér megosztás használható a robusztusság növelésére is az tervezésitér párhuzamos bejárásával. Legvégül a bejárás bármikor leállíthatóvá és újraindíthatóvá válik.
