基于GPU的KMP串匹配并行算法研究

作者：肖汉; 杜莹^*; 肖诗洋; 周清雷

来源：武汉大学学报(工学版), 2023, 56(07): 867-878.

DOI：10.14188/j.1671-8844.2023-07-012

• KMP串匹配
• 正文串
• 模式串
• 图形处理器
• 统一计算设备架构
• 并行算法

KMP(Knuth-Morris-Pratt)串匹配算法在面对大规模数据集时，运算时间将随着数据集的增大而迅速增长。为了提升算法的计算性能，设计了一种基于图像处理器（graphic processing unit,GPU）的KMP串匹配并行算法。针对KMP串匹配算法进行并行特征分析，提出了一种粗粒度和细粒度相结合的并行优化方法，从任务划分、GPU访存和内核配置3方面加以优化。通过数据不重叠划分的方法，在字符串匹配阶段，采用在2个邻接子正文串中搜索匹配位置的策略；在统计匹配数量阶段，采用统一计算设备架构（compute unified device architecture,CUDA）原生的原子加法操作，克服了全局存储器未合并访问的问题，提高了整体性能。结果表明，基于GPU加速的KMP串匹配并行算法提高了计算速度，相比中央处理器（central processing unit,CPU）串行算法和开放多处理（open multiprocessing,OpenMP）并行算法分别获得了39.29倍和29.47倍的加速比，满足了KMP串匹配算法处理大数据集的实时性需求。

• 单位
  东南大学; 郑州师范学院; 土木工程学院