Informatikai Tudományok Doktori Iskola

 

Témavezető: Dr. Juhász Sándor

BME Villamosmérnöki és Informatikai Kar, Automatizálási és Alkalmazott Informatikai Tanszék

Hash táblák teljesítmény modellezése és optimalizálása

A kutatási téma néhány soros bemutatása

Nagymennyiségű adat kezeléséhez, például adatbányászati alkalmazásokban, adattömörítési feldolgozáshoz gyakran alkalmaznak szótár alapú adat leképzést. Ezen szótárak hash táblákkal valósíthatóak meg, azonban általános hash tábla implementációk nem képesek nagymennyiségű adat kezelésére.

A célom a kutatásom során olyan hash táblák kialakítása volt, amelyek elfoglalt memória szempontjából és teljesítmény szempontjából is ideális viselkedést biztosítanak. Ehhez megvizsgáltam a hash táblák belső felépítését, és olyan módszereket kerestem, amelyekkel a belső struktúra robusztusabbá, a feladathoz jobban alkalmazkodóvá tehető. Megvizsgáltam, milyen faktorok befolyásolják a teljesítményt, és ezek hogyan modellezhetőek, valamint ezen modellekre építve hogyan lehet jobb tárolási struktúrát tervezni.

Kihasználva az asztali és szerver számítógépekben elterjedt többmagos processzorokat, olyan módszereket kerestem, amelyek képessé teszik a hash táblát több feldolgozó szál kiszolgálására. Adatstruktúrák több szálból való használatára két féle megoldást szoktak alkalmazni; az egyik esetében az adatstruktúra zárakat és kölcsönös kizárást alkalmaz, a másik esetében zárak használata nélkül atomi utasításokkal működik az adatstruktúra. Mindkét módszer rendelkezik előnyökkel és hátrányokkal, ezeket megvizsgálva mindkét módszer szerint készítettem párhuzamos hash tábla implementációkat. Zármentes megoldások esetében eltérő un. progress condition feltételeknek megfelelő algoritmusokat adtam, míg a zárakat alkalmazó megoldásnál a hash tábla által alkalmazandó zárak optimális számára és elhelyezésére készítettem modellt.