基于GPU的近似字符串匹配并行算法的研究.pdf

1、圖形處理器(GPU)具有很強(qiáng)的并行處理能力，并且設(shè)備成本低，利用GPU加速字符串操作已經(jīng)成為了當(dāng)前并行計(jì)算領(lǐng)域的研究熱點(diǎn)。近似字符串匹配技術(shù)在病毒檢測、文件檢索、計(jì)算生物學(xué)等很多領(lǐng)域都有著廣泛的應(yīng)用，傳統(tǒng)的串行算法運(yùn)算速度慢，而現(xiàn)存的并行算法都是基于多處理器模式，計(jì)算設(shè)備成本很高，耗電量大。因此，在GPU上研究有效的近似字符串匹配并行算法具有重大的實(shí)際意義。本文的主要研究內(nèi)容及貢獻(xiàn)如下：
　　 首先，對GPU通用計(jì)算的編程環(huán)境進(jìn)

2、行了總結(jié)，重點(diǎn)研究了NVIDIACUDA的工作原理，編程模型和存儲器模型，以及如何配置CUDA編程環(huán)境。
　　 其次，對于允許k-mismatch的近似字符串匹配問題，基于CUDA模型，本文提出了三種并行算法，即線程級并行算法，兩級并行算法，以及兩級并行優(yōu)化算法。兩級并行優(yōu)化算法在利用GPU強(qiáng)大并行處理能力的同時(shí)，使得各線程負(fù)載均衡，并且利用GPU的存儲器模型減少了每個(gè)線程對全局存儲器中數(shù)據(jù)的訪問次數(shù)。本文使用真實(shí)的DNA序列作

3、為實(shí)驗(yàn)數(shù)據(jù)對算法的性能進(jìn)行評估，實(shí)驗(yàn)結(jié)果表明，兩級并行優(yōu)化算法在GPU上的執(zhí)行時(shí)間對于傳統(tǒng)的CPU端串行算法的加速比可達(dá)到40-80，加速比變化趨勢與理論分析一致，其它兩個(gè)算法的加速比也可以達(dá)到7-10。
　　 最后，對于允許k-difference的近似字符串匹配問題，基于動(dòng)態(tài)規(guī)劃的方法，通過消除編輯距離矩陣中同一行數(shù)據(jù)間的依賴關(guān)系，本文提出了一個(gè)空間復(fù)雜度為O(|Σ|n)，時(shí)間復(fù)雜度為O（(|Σ|+m)n／M）的并行算法DA