中文摘要：

针对信息处理中常见的字符串匹配问题,通过对经典的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.