Mintaillesztés GPU gyorsítási lehetőségeinek vizsgálata

OData támogatás
Konzulens:
Szántó Péter
Méréstechnika és Információs Rendszerek Tanszék

A mintaillesztés fontos szerepet játszik a számítástudományban. A hálózati sávszélesség vagy pusztán a feldolgozandó adatmennyiség nagy léptékű növekedése kikényszeríti a hálózatbiztonság (Network Intrusion Detection and Prevention Systems, NIDS/NIPS) területén, az antivírus rendszerekben, a nukleotid és aminosav szekvenciák illesztésére használt biológiai adatbázisokban valamint az általános célra használt keresőrendszerekben az áteresztőképesség fejlesztését.

Az egy és több kulcsszavas keresés gyorsításának lehetőségét nyújtja a GPGPU, vagyis a grafikus feldolgozó egység általános célú alkalmazása. Ez a megoldás elősegíti az idő nagy részében a PC-kben kihasználatlanul hagyott nagy számítási teljesítmény kiaknázásán túlmenően a CPU tehermentesítését is, miközben az újrakonfigurálhatóság tekintetében kevéssé rugalmas célhardverekkel (ASIC, FPGA) ellentétben a GPU alacsony költségű társprocesszorként gazdaságosan fejleszthető és üzemeltethető.

Az elmúlt évtizedben számos, főként NVIDIA termékre optimalizált CUDA-C nyelvű implementáció látott napvilágot. Ezek mindegyike embarrassingly parallel GPGPU megoldásnak tekinthető, ahol a GPU skalár processzorai valamely már létező szekvenciális algoritmust vagy annak kissé módosított változatát hajtják végre egymástól független karaktersorozatokon, így eliminálva a szálak közötti kommunikáció szükségességét.

Hillis és Steele már 1986-ban felvetették a scan algoritmus primitíven alapuló lexikai analízis ötletét [1], ahol az operátorként használt bináris asszociatív függvény-kompozíció szolgál a művelet operátoraként, és az állapotgépen alapuló mintaillesztő algoritmus állapottáblájának állapotszámmal arányos oszlopai alkotják annak bemeneti rendezett operandushalmazát. Az általuk prezentált szöveghosszal és állapotszámmal arányos algoritmus komplexitása messze túlszárnyalja a jelenlegi szekvenciális algoritmusokét, ezért alkalmazása nem célravezető.

A diplomatervemben megadom az eredeti Hillis-Steele algoritmus egy mintaillesztésre alkalmazható módosítását, amely komplexitásának állapotszám függése szublineáris. Az implementáció során az NVIDIA cég Fermi architektúrájú processzorait tekintem az optimalizálás alapjának. A kiválasztott scan primitív gyakorlatban történő alkalmazása során külön kihívást jelent, hogy a Horn [2] és Sengupta et al. [3] által publikált shared memórián alapuló CUDA-C scan implementációk nem alkalmazhatók. A nem coalescent olvasási műveletek csökkentése adatátrendezést és egészen új címzési struktúra kialakítását követeli meg. Az elkészült kernel teljesítményének bemeneti adatoktól való függését mérések segítségével tekintem át és ennek alapján elemzem annak valós körülmények közötti használhatóságát, továbbá kitekintést adok az elkészült munka továbbfejlesztésének lehetséges irányaira is.

[1] W. D. Hillis and G. L. Steele, “Data parallel algorithms,” Communications of the ACM, vol. 29, no. 12, pp. 1170–1183, Dec. 1986.

[2] D. Horn, “Stream reduction operations for GPGPU applications,” In GPU Gems 2, chap. ch. 36, 573–589, 2005.

[3] S. Sengupta, J. D. Owens, and A. E. Lefohn, “A Work-Efficient Step-Efficient Prefix-Sum Algorithm,” pp. 1–2, 1986.

Letölthető fájlok

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