【摘要】：圖形處理器（GPU）具有很強的并行處理能力，并且計算成本低，利用GPU加速字符串操作已經成為了當前并行計算領域的研究熱點。近似字符串匹配技術在病毒檢測、文件檢索、計算生物學等很多領域都有著廣泛的應用，傳統(tǒng)的串行算法運算速度慢，而現存的并行算法都是基于多處理器模式，計算成本很高。因此，在GPU上研究有效的近似字符串匹配并行算法具有重大的實際意義。本文的主要研究內容及貢獻如下： 首先，對GPU通用計算的編程環(huán)境進行了總結，重點研究了NVIDIA CUDA的工作原理，編程模型和存儲器模型，以及如何配置CUDA編程環(huán)境。 其次，對于允許k-mismatch的近似字符串匹配問題，基于CUDA模型，本文提出了三種并行算法，即線程級并行算法，，兩級并行算法，以及兩級并行優(yōu)化算法。兩級并行優(yōu)化算法在利用GPU強大并行處理能力的同時，使得各線程負載均衡，并且利用GPU的存儲器模型減少了每個線程對全局存儲器中數據的訪問次數。本文使用真實的DNA序列作為實驗數據對算法的性能進行評估，實驗結果表明，其中兩級并行優(yōu)化算法在GPU上的執(zhí)行時間對于傳統(tǒng)的CPU端串行算法加速比可達到40-80，加速比變化與理論分析一致，其它兩個算法的加速比也可以達到10左右。 最后，對于允許k-difference的近似字符串匹配問題，基于動態(tài)規(guī)劃的方法，通過消除編輯距離矩陣中同一行數據間的依賴關系，本文提出了一種有效的并行算法。該算法使用很少的線程同步次數，并且具有很高的并行度。本文分別在GPU和多核CPU上對算法進行了實現，并對兩種環(huán)境下對算法的加速比進行了分析。實驗結果表明，本文的并行算法在GPU上的執(zhí)行時間對于傳統(tǒng)的CPU端串行算法加速比可達到7-12，在雙核CPU上算法的加速比可以達到1.3，在24核CPU上的加速比可以達到8-13，并且加速比的變化與理論分析一致。
[Abstract]:Graphics processor (GPU) has strong parallel processing ability and low computing cost. Using GPU to speed up string operation has become a hot research topic in the field of parallel computing. Approximate string matching technology has been widely used in virus detection, file retrieval, computational biology and many other fields. The traditional serial algorithm is slow, while the existing parallel algorithms are based on multiprocessor mode. The calculation cost is very high. Therefore, it is of great practical significance to study the efficient parallel algorithm of approximate string matching on GPU. The main contents and contributions of this paper are as follows: firstly, the programming environment of GPU general computing is summarized, and the working principle, programming model and memory model of NVIDIA CUDA are emphatically studied, as well as how to configure CUDA programming environment. Secondly, for the approximate string matching problem that allows k-mismatch, this paper proposes three parallel algorithms based on CUDA model, namely, thread-level parallel algorithm, two-level parallel algorithm, and two-level parallel optimization algorithm. The two-level parallel optimization algorithm makes use of the powerful parallel processing ability of GPU to balance the load of each thread and reduces the number of times each thread accesses the data in the global memory by using the memory model of GPU. In this paper, real DNA sequences are used as experimental data to evaluate the performance of the algorithm. The experimental results show that, The execution time of the two-stage parallel optimization algorithm on GPU can reach 40-80 for the traditional CPU serial algorithm. The speedup variation is consistent with the theoretical analysis, and the speedup ratio of the other two algorithms can reach about 10. Finally, for the approximate string matching problem with k-difference, an efficient parallel algorithm is proposed by eliminating the dependency between the same row of data in the edit distance matrix based on dynamic programming. The algorithm uses a few thread synchronization times and has a high degree of parallelism. In this paper, the algorithm is implemented on GPU and multi-core CPU, and the speedup ratio of the algorithm is analyzed in the two environments. The experimental results show that, The execution time of the parallel algorithm on GPU can reach 7-12 for the traditional CPU serial algorithm, 1.3 for dual-core CPU and 8-13 for 24-core CPU. It is consistent with theoretical analysis.
【學位授予單位】：黑龍江大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：TP338.6

【共引文獻】

相關期刊論文 前2條

1 鐘誠,宋彬;生物序列比對算法分析與比較[J];廣西大學學報(自然科學版);2004年03期

2 宋彬,陳國良,鄢超,沈一飛;多序列比對問題的并行近似算法[J];中國科學技術大學學報;2005年05期

相關博士學位論文 前2條

1 王文奇;入侵檢測與安全防御協(xié)同控制研究[D];西北工業(yè)大學;2006年

2 尹傳環(huán);結構化數據核函數的研究[D];北京交通大學;2008年

相關碩士學位論文 前6條

1 羅程;基于核聚類和序列分析的網絡入侵檢測方法的研究[D];廣西大學;2005年

2 王少飛;數字圖像壓縮算法的并行化方法研究[D];山東師范大學;2008年

3 何偉;使用隨機投影技術發(fā)現生物序列特征的算法[D];鄭州大學;2002年

4 范立新;用位并行法進行過濾的中文近似串匹配算法[D];浙江大學;2006年

5 郭海濤;用加強的后綴數組查找MUM[D];西安電子科技大學;2007年

6 范大娟;異構機群系統(tǒng)上單模式單正文串近似串匹配并行算法研究[D];廣西大學;2007年

本文編號：2270790