基于移动平台的异构并行字符串匹配算法  

Heterogeneous Parallel String Matching Algorithm Based on Mobile Platform

作　　者：刘磊[1] 李广力 徐玥[1] 张桐搏 吕帅[1,2,3] LIU Lei LI Guangli XU Yue ZHANG Tongbo LU Shuai(College of Computer Science and Technology, Jilin University, Changchun 130012, China College of Mathematics, J ilin University, Changchun 130012, China Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, J ilin University, Changchun 130012, China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学数学学院,长春130012 [3]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《吉林大学学报（理学版）》2017年第1期82-88,共7页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:61300049);高等学校博士学科点专项科研基金(批准号:20120061120059;20120061110045);吉林省青年科研基金(批准号:20140520069JH);吉林省自然科学基金(批准号:20150101054JC);吉林大学研究生创新基金(批准号:2016181)

摘　　要：针对信息处理中常见的字符串匹配问题,通过对经典的Brute Force算法和KnuthMorris-Pratt算法进行分析,根据GPU异构并行计算任务的分配特性,设计一种针对Knuth-Morris-Pratt算法的数据重叠划分并行方案,并提出一种基于移动平台的异构并行字符串匹配算法KMP_MOP.在PowerVR移动平台环境下使用千万级长度的字符串数据对算法的性能进行测试,同时对算法在其他平台的执行情况进行比较,验证了并行算法的性能可移植性.实验结果表明,KMP_MOP算法能充分利用移动平台中的GPU性能,有效提高具有GPU的移动平台设备的字符串匹配效率.For common string matching problem in information processing, we analyzed the classical algorithms as Brute Force and Knuth-Morris-Pratt. According to the distribution characteristics of GPU heterogeneous parallel computing task, we designed a parallel scheme for data overlapping partition based on Knuth-Morris-Pratt algorithm, and proposed a heterogeneous parallel string matching algorithm KMP_MOP based on mobile platform. We tested the algorithm performance in PowerVR mobile platform by using strings with lengths of tens of millions. Also we compared execution of algorithm running on other platforms, verifying the portability of the parallel algorithm. The experimental result indicates that the KMP_MOP algorithm can make full use of the GPU performance in mobile platform, and effectively improve the string matching efficiency of mobile platform devices with GPU.

关 键 词：字符串匹配 重叠划分 移动平台 异构并行计算 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]