论文部分内容阅读
图形处理器（GPU）具有很强的并行处理能力，并且计算成本低，利用GPU加速字符串操作已经成为了当前并行计算领域的研究热点。近似字符串匹配技术在病毒检测、文件检索、计算生物学等很多领域都有着广泛的应用，传统的串行算法运算速度慢，而现存的并行算法都是基于多处理器模式，计算成本很高。因此，在GPU上研究有效的近似字符串匹配并行算法具有重大的实际意义。本文的主要研究内容及贡献如下：首先，对GPU通用计算的编程环境进行了总结，重点研究了NVIDIA CUDA的工作原理，编程模型和存储器模型，以及如何配置CUDA编程环境。其次，对于允许k-mismatch的近似字符串匹配问题，基于CUDA模型，本文提出了三种并行算法，即线程级并行算法，两级并行算法，以及两级并行优化算法。两级并行优化算法在利用GPU强大并行处理能力的同时，使得各线程负载均衡，并且利用GPU的存储器模型减少了每个线程对全局存储器中数据的访问次数。本文使用真实的DNA序列作为实验数据对算法的性能进行评估，实验结果表明，其中两级并行优化算法在GPU上的执行时间对于传统的CPU端串行算法加速比可达到40-80，加速比变化与理论分析一致，其它两个算法的加速比也可以达到10左右。最后，对于允许k-difference的近似字符串匹配问题，基于动态规划的方法，通过消除编辑距离矩阵中同一行数据间的依赖关系，本文提出了一种有效的并行算法。该算法使用很少的线程同步次数，并且具有很高的并行度。本文分别在GPU和多核CPU上对算法进行了实现，并对两种环境下对算法的加速比进行了分析。实验结果表明，本文的并行算法在GPU上的执行时间对于传统的CPU端串行算法加速比可达到7-12，在双核CPU上算法的加速比可以达到1.3，在24核CPU上的加速比可以达到8-13，并且加速比的变化与理论分析一致。