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

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

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

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