Bloom Filter hatékony implementálása CPU-n és GPU-n

OData támogatás
Konzulens:
Dr. Dudás Ákos
Automatizálási és Alkalmazott Informatikai Tanszék

Munkám célja egy hatékony Bloom Filter implementáció megadása volt. A Bloom Filterek olyan struktúrák, amelyek egy nagyobb adathalmazt képesek alapvetően kis helyen reprezentálni, és csak két műveletet támogatnak. Elemek hozzáadását ehhez a halmazhoz, illetve ezeknek az elemeknek a tartalmazásának vizsgálatát. Az utóbbi néhány évtizedben a Bloom Filterek felhasználási köre egyre szélesebbé vált, és egyre újabb és újabb variációit sikerült létrehozni. Saját megoldásomat először processzoron, majd videokártyán is megvalósítottam.

A processzoros implementáció során C++11-es eszközöket használtam fel, amely különféle eszközöket nyújt szálak kezeléshez, mint például a szálak indítása, illetve szinkronizációja. Előnyük ezeknek az eszközöknek, hogy szabványosított megoldásokat nyújtanak, így nagyobb eséllyel több platformon is fordítható lesz a kész alkalmazás.

A videokártyás megvalósításhoz az NVIDIA CUDA architektúrát használtam. Előnye, hogy viszonylag könnyen tanulható, már ismert nyelvek segítségével lehet megoldásokat készíteni. A nagyobb kihívást a videokártya sajátosságainak elsajátítása jelenti, mint például a különböző memóriaterületek, valamint problémák hatékony párhuzamosítása. A videokártyák általános célú programozásában hatalmas lehetőségek rejlenek, ha sikerül egy adott problémát elegendő mértékben párhuzamosítani, akkor jelentős teljesítmény-növekedésre tehetünk szert.

Dolgozatomban egy rövid bevezető után ismertetem a Bloom Filter struktúrát és a CUDA architektúrát. Ezek után egy egyszerű Bloom Filter működését mutatom be, majd különböző párhuzamosított verziók kerülnek ismertetésre, amelyek a processzoron futnak. Ezen párhuzamosított Bloom Filterek mögött található ötleteket megpróbálom átültetni a videokártyára is. Végül összehasonlítom a legjobban sikerült megoldásokat és értékelem működésüket.

Letölthető fájlok

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