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

《基于GPU的近似字符串匹配并行算法的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中文摘要中又摘要图形处理器(GPU)具有很强的并行处理能力，并且设备成本低，利用GPU加速字符串操作已经成为了当前并行计算领域的研究热点。近似字符串匹配技术在病毒检测、文件检索、计算生物学等很多领域都有着广泛的应用，传统的串行算法运算速度慢，而现存的并行算法都是基于多处理器模式，计算设备成本很高，耗电量大。因此，在GPU上研究有效的近似字符串匹配并行算法具有重大的实际意义。本文的主要研究内容及贡献如下：首先，对GPU通用计算的编程环境进行了总结，重点研究了NVIDIACUDA的工作原理，编程模型和存储器模型，以及如何配置CUDA编程环境。其次，对于允许k-mismatch的近似字符串匹配

2、问题，基于CUDA模型，本文提出了三种并行算法，即线程级并行算法，两级并行算法，以及两级并行优化算法。两级并行优化算法在利用GPU强大并行处理能力的同时，使得各线程负载均衡，并且利用GPU的存储器模型减少了每个线程对全局存储器中数据的访问次数。本文使用真实的DNA序列作为实验数据对算法的性能进行评估，实验结果表明，两级并行优化算法在GPU上的执行时间对于传统的CPU端串行算法的加速比可达到40．80，加速比变化趋势与理论分析一致，其它两个算法的加速比也可以达到7．10。最后，对于允许k-difference的近似字符串匹配问题，基于动态规划的方法，通过消除编辑距离矩阵中同一行数据间的依赖

3、关系，本文提出了一个空间复杂度为o(1∑l，z)，时间复杂度为D(盟学)的并行算法DAsMP，，z为文本长度，m为模式长度，l∑I为字典表集合的大小，M为处理器个数。本文分别在GPU．币IJ多核CPU上对算法进行了实现，并对两种环境下算法的加速比进行了分析。实验结果表明，DASMP算法在GPU上的执行时间对于传统的CPU端串行算法的加速比可以达到7．13，在双核CPU上算法的加速比可以达到1．3，在24核CPU上的加速比可以达N8．12，并且加速比的变化趋势与理论分析一致。关键字：近似串匹配，GPU，并行算法，汉明距离，编辑距离黑龙江大学硕士学位论文AbstractGPUhashighp

4、arallelprocessingcapabilityandlowcostofequipments．AcceleratingstringoperationsonGPUhasbeenaresearchfocusonparallelcomputingarea．Approximatestringmatchingtechniquehasbeenwidelyappliedtomanyfieldssuchasvirusdetection，textminingandcomputationalbiology．Thetraditionalsequentialalgorithmsareslow,andthe

5、parallelalgorithmsareallbasedonmultipleprocessors，whichhavehighcostofequipmentsandenergy．Therefore，theeffectiveparallelalgorithmforapproximatestringmatchinghassignificantpracticalsignificance．砀emainresearchsandcontributionsofthisthesisareasfollows。Firstly,thispapersummarizestheprogrammingenvironm

6、entforGPGPU，andstudiestheworkingprinciple，programmingmodel，storagemodelandprogrammingenvironmentconfigurationmethodofCUDAindetail．Secondly,fortheproblemofk-mismatchapproximatestingmatching．BasedonCUDA，thispaperpresentsthreeparallelalgorithms，namely,thethreadparallelalgorithm，theblock-threadparall

7、elalgorithm，andtheOPT-block-threadparallelalgorithm．TheOPT-block-threadparallelalgorithmCantakefulladvantageofthepowerfulparallelcapabilityofGPU．Furthermore，itbalancestheloadamongthethreesandoptimizestheexecutiontimewi