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

Research on parallel algorithm of KMP string matching based on GPU

作　　者：肖汉 杜莹 肖诗洋 周清雷[4] XIAO Han;DU Ying;XIAO Shiyang;ZHOU Qinglei(School of Information Science and Technology,Zhengzhou Normal University,Zhengzhou 450044,China;School of Geography and Tourism,Zhengzhou Normal University,Zhengzhou 450044,China;School of Civil Engineering,Southeast University,Nanjing 211189,China;School of Computer and Artificial Intelligence,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]郑州师范学院信息科学与技术学院,河南郑州450044 [2]郑州师范学院地理与旅游学院,河南郑州450044 [3]东南大学土木工程学院,江苏南京211189 [4]郑州大学计算机与人工智能学院,河南郑州450001

出　　处：《武汉大学学报（工学版）》2023年第7期867-878,共12页Engineering Journal of Wuhan University

基　　金：国家自然科学基金项目(编号:61250007,61572444);河南省高等学校重点科研项目(编号:22A520049)。

摘　　要：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串匹配算法处理大数据集的实时性需求。In face of large scale datasets,the operation time of KMP(Knuth-Morris-Pratt)string matching algorithm will increase rapidly with the increase of dataset size.In order to improve the computational performance of the algorithm,a parallel KMP string matching algorithm based on graphics processing unit(GPU)is designed.In this paper,the parallel characteristics of KMP string matching algorithm are analyzed,and a parallel optimization method based on the combination of coarse granularity and fine granularity is proposed,which is optimized from three aspects:task partition,GPU memory access and kernel configuration.Through the method of data non-overlapping partition,the strategy of searching the matching position in the two adjacent subtext strings is adopted in the string matching stage.In the matching quantity statistics phase,the atomic addition operation native to compute unified device architecture(CUDA)is adopted,and the unmerged access to the global memory is overcome,thus the overall performance is improved.The resultsshow that the KMP string matching algorithm accelerated by GPU improves the computing speed,and the acceleration ratio is 39.29 times and 29.47 times higher than that of CPU serial algorithm and open multiprocessing(OpenMP)parallel algorithm,respectively.It meets the real-time requirement of KMP string matching algorithm to deal with large data sets.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]