Általános lokális keresésen alapuló gráfmintaillesztési keretrendszer

OData támogatás
Konzulens:
Dr. Horváth Ákos
Méréstechnika és Információs Rendszerek Tanszék

Szoftvermodellezési feladatok során a modellek, amiket jellemzően gráfként reprezentálnak, tartalmazzák a tervezési információkat. Ezek feldolgozásával használjuk ki ennek a megjelenítési formának az előnyeit, és hasznosítjuk az ismereteket. A modelleken végzett műveletek egyik célja hagyományosan a végrehajtható programkód előállítása.

Modelleken végzett tipikus műveletek egyike a keresés, mely során a cél bizonyos feltételnek megfelelő elemek, azaz egy almodell felderítése. Ez részfeladata a transzformációnak, ami vagy egy köztes modellt, vagy forráskódot állít elő a bemeneti modell alapján. Szintén a keresésen alapul a jólformáltság ellenőrzése, ami vizsgálja, hogy a modell felépítése követi-e a modellezési nyelv szabályait.

Dolgozatomban az almodellek keresését gráfmintaillesztést segítségével végeztem. A gráfmintaillesztés általánosan egy komplex problémakör, azonban különböző megközelítések már ismertek a megoldására. Egyik gyakori módszer a lokális keresésen alapuló mintaillesztési technika, mely egy kezdeti pontból kiindulva keresi meg az illeszkedéseket. A módszer hatékonyan működik optimális keresési terv mellett, azonban az optimális keresési tervet csakis az éppen vizsgált modell struktúrája határozza meg.

Munkám során adaptáltam és implementáltam egy lokális keresésen alapuló gráfmintaillesztési algoritmuscsaládot. A megvalósított módszer lényege, hogy a modell számossági jellemzői alapján számítja ki a keresési tervet. Emellett elkészítettem a keresés egy egyszálú, valamint egy párhuzamos verzióját is. A dolgozatban bemutatom az algoritmus főbb gondolatait és lépéseit, illetve a megvalósítás sajátosságait. A megoldást a nyílt forráskódú \eiq keretrendszerbe is integráltam, törekedve a komponensek újrafelhasználására.

Mindkét típusú megvalósítás teljesítményét és skálázhatóságát mérésekkel is alátámasztom, és egymással, illetve a korábban már meglévő inkrementális algoritmus végrehajtási idejével is összehasonlítom. Emellett elemzem, hogy mely gráfmintaillesztési forgatókönyvek mellett melyik módszer bizonyul kedvezőbbnek. Az erdemények szerint az alkalmankénti futtatást igénylő, illetve a memóriaszegény környezetben végzett feladatok során is a lokális keresésen alapuló algoritmus részesítendő előnyben.

Letölthető fájlok

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