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

摘要：

针对信息处理中常见的字符串匹配问题,通过对经典的Brute Force算法和Knuth-Morris-Pratt算法进行分析,根据GPU异构并行计算任务的分配特性,设计一种针对Knuth-Morris-Pratt算法的数据重叠划分并行方案,并提出一种基于移动平台的异构并行字符串匹配算法KMP_MOP.在PowerVR移动平台环境下使用千万级长度的字符串数据对算法的性能进行测试,同时对算法在其他平台的执行情况进行比较,验证了并行算法的性能可移植性.实验结果表明,KMP_MOP算法能充分利用移动平台中的GPU性能,有效提高具有GPU的移动平台设备的字符串匹配效率.

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

所属期刊栏目：55

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2017-04-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：82-88