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

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

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

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

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