基于GPU的近似字符串匹配并行算法的研究
發(fā)布時(shí)間：2018-10-14 14:46
【摘要】：圖形處理器（GPU）具有很強(qiáng)的并行處理能力，并且計(jì)算成本低，利用GPU加速字符串操作已經(jīng)成為了當(dāng)前并行計(jì)算領(lǐng)域的研究熱點(diǎn)。近似字符串匹配技術(shù)在病毒檢測、文件檢索、計(jì)算生物學(xué)等很多領(lǐng)域都有著廣泛的應(yīng)用，傳統(tǒng)的串行算法運(yùn)算速度慢，而現(xiàn)存的并行算法都是基于多處理器模式，計(jì)算成本很高。因此，在GPU上研究有效的近似字符串匹配并行算法具有重大的實(shí)際意義。本文的主要研究內(nèi)容及貢獻(xiàn)如下： 首先，對GPU通用計(jì)算的編程環(huán)境進(jìn)行了總結(jié)，重點(diǎn)研究了NVIDIA CUDA的工作原理，編程模型和存儲器模型，以及如何配置CUDA編程環(huán)境。 其次，對于允許k-mismatch的近似字符串匹配問題，基于CUDA模型，本文提出了三種并行算法，即線程級并行算法，，兩級并行算法，以及兩級并行優(yōu)化算法。兩級并行優(yōu)化算法在利用GPU強(qiáng)大并行處理能力的同時(shí)，使得各線程負(fù)載均衡，并且利用GPU的存儲器模型減少了每個(gè)線程對全局存儲器中數(shù)據(jù)的訪問次數(shù)。本文使用真實(shí)的DNA序列作為實(shí)驗(yàn)數(shù)據(jù)對算法的性能進(jìn)行評估，實(shí)驗(yàn)結(jié)果表明，其中兩級并行優(yōu)化算法在GPU上的執(zhí)行時(shí)間對于傳統(tǒng)的CPU端串行算法加速比可達(dá)到40-80，加速比變化與理論分析一致，其它兩個(gè)算法的加速比也可以達(dá)到10左右。 最后，對于允許k-difference的近似字符串匹配問題，基于動態(tài)規(guī)劃的方法，通過消除編輯距離矩陣中同一行數(shù)據(jù)間的依賴關(guān)系，本文提出了一種有效的并行算法。該算法使用很少的線程同步次數(shù)，并且具有很高的并行度。本文分別在GPU和多核CPU上對算法進(jìn)行了實(shí)現(xiàn)，并對兩種環(huán)境下對算法的加速比進(jìn)行了分析。實(shí)驗(yàn)結(jié)果表明，本文的并行算法在GPU上的執(zhí)行時(shí)間對于傳統(tǒng)的CPU端串行算法加速比可達(dá)到7-12，在雙核CPU上算法的加速比可以達(dá)到1.3，在24核CPU上的加速比可以達(dá)到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.
【學(xué)位授予單位】：黑龍江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP338.6
本文編號：2270790
[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.
【學(xué)位授予單位】：黑龍江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP338.6
【共引文獻(xiàn)】
相關(guān)期刊論文 前2條
1 鐘誠,宋彬;生物序列比對算法分析與比較[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年03期
2 宋彬,陳國良,鄢超,沈一飛;多序列比對問題的并行近似算法[J];中國科學(xué)技術(shù)大學(xué)學(xué)報(bào);2005年05期
相關(guān)博士學(xué)位論文 前2條
1 王文奇;入侵檢測與安全防御協(xié)同控制研究[D];西北工業(yè)大學(xué);2006年
2 尹傳環(huán);結(jié)構(gòu)化數(shù)據(jù)核函數(shù)的研究[D];北京交通大學(xué);2008年
相關(guān)碩士學(xué)位論文 前6條
1 羅程;基于核聚類和序列分析的網(wǎng)絡(luò)入侵檢測方法的研究[D];廣西大學(xué);2005年
2 王少飛;數(shù)字圖像壓縮算法的并行化方法研究[D];山東師范大學(xué);2008年
3 何偉;使用隨機(jī)投影技術(shù)發(fā)現(xiàn)生物序列特征的算法[D];鄭州大學(xué);2002年
4 范立新;用位并行法進(jìn)行過濾的中文近似串匹配算法[D];浙江大學(xué);2006年
5 郭海濤;用加強(qiáng)的后綴數(shù)組查找MUM[D];西安電子科技大學(xué);2007年
6 范大娟;異構(gòu)機(jī)群系統(tǒng)上單模式單正文串近似串匹配并行算法研究[D];廣西大學(xué);2007年
本文編號：2270790
本文鏈接：http://www.sikaile.net/kejilunwen/jisuanjikexuelunwen/2270790.html
最近更新
教材專著
