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

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

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

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

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