基于GPU并行串匹配算法的研究.pdf

1、串匹配是計算機研究領域的一個經典問題,是網絡內容分析系統(tǒng)的關鍵技術之一。隨著互聯網的普及和發(fā)展,海量信息的處理和新的應用需求對串匹配技術提出了新的挑戰(zhàn)。在現實生活中,串匹配技術的應用十分廣泛,其主要應用領域包括:入侵檢測、病毒檢測、信息檢索、信息過濾、計算生物學等等。串匹配技術的研究與發(fā)展是與現實應用息息相關的,近年來,新的應用需求對串匹配技術提出了新的要求和挑戰(zhàn)。
　　可編程圖像處理器單元(GPU)已經發(fā)展成為絕對的計算主力。由

2、于具有由高內存帶寬驅動的多個核心,今天的GPU為圖像和非圖像處理提供了難以置信的資源。GPU的每秒浮點數操作(54GLOPS)幾乎是Intel Core2Duo(5.6GFLOPS)的十倍。由于GPU具有如此巨大的運算潛力,越來越多的應用試圖將通用計算任務移植到GPU上來做。利用GPU的SIMD流處理器作為通用計算平臺已經得到了廣泛的研究和應用,這使得GPU能夠成為一個有效的CPU協處理器,獲得較高的性價比。
　　本文從GPU的體

3、系結構出發(fā),研究如何在GPU上給予圖形管道流水線的編程方法及NVIDIACUDA統(tǒng)一計算設備架構,如何開發(fā)串匹配算法的數據并行性適合在GPU上運行的串匹配算法。本文的主要工作包括:
　　首先,GPU上通用計算編程方法進行了研究:研究了OpenGL、BROOK、CG等GPU上通用計算的編程方法,以及如何開發(fā)基于圖形管道流水線的通用計算原理。在此基礎上進一步研究了NVIDIACUDA的編程模型與并行線程設計方法,并通過設計實例,總結了

4、CUDA并行算法設計關鍵技術與一般性方法。
　　其次,設計了適合GPU的并串匹配算法的設計與實現:BF算法是串匹配算法中最基礎的算法,但它是串行算法,不適合GPU的體系結構。本文通過對需要處理的數據增加一定比例的冗余信息的方法,設計了適合CUDA計算數據的獨立性特點的并行字符串匹配算法。實驗結果表明基于CUDA架構的并行串匹配算法獲得約10倍的加速比。
　　最后,提出了一種針對待匹配數據字符分布特征的鏈式狀態(tài)轉移表存儲方法,