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

吉林大学学报(理学版)

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

刘磊¹, 李广力¹, 徐玥¹, 张桐搏¹, 吕帅^1,2,3

1. 吉林大学计算机科学与技术学院, 长春 130012; 2. 吉林大学数学学院, 长春 130012;3. 吉林大学符号计算与知识工程教育部重点实验室, 长春 130012

收稿日期:2016-05-13 出版日期:2017-01-26 发布日期:2017-02-02
通讯作者: 吕帅 E-mail:lus@jlu.edu.cn

Heterogeneous Parallel String Matching AlgorithmBased on Mobile Platform

LIU Lei¹, LI Guangli¹, XU Yue¹, ZHANG Tongbo¹, LV Shuai^1,2,3

1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;2. College of Mathematics, Jilin University, Changchun 130012, China; 3. Key Laboratory of SymbolicComputation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Received:2016-05-13 Online:2017-01-26 Published:2017-02-02
Contact: LV Shuai E-mail:lus@jlu.edu.cn

摘要/Abstract

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

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

Abstract: 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.

Key words: mobile platform, string matching, heterogeneous parallel computing, overlapping partition

中图分类号:

TP391

刘磊, 李广力, 徐玥, 张桐搏, 吕帅. 基于移动平台的异构并行字符串匹配算法[J]. 吉林大学学报(理学版), 2017, 55(01): 82-88.

LIU Lei, LI Guangli, XU Yue, ZHANG Tongbo, LV Shuai. Heterogeneous Parallel String Matching AlgorithmBased on Mobile Platform[J]. Journal of Jilin University Science Edition, 2017, 55(01): 82-88.

[1]	王玉, 申铉京, 周昱洲, 林鸿斌. 一种求解交通网络中最短路径问题的人工蜂群算法[J]. 吉林大学学报(理学版), 2021, 59(5): 1144-1150.
[2]	朱新丽, 才华, 寇婷婷, 杜冬晖, 孙俊喜. 行人多目标跟踪算法[J]. 吉林大学学报(理学版), 2021, 59(5): 1161-1170.
[3]	张震, 张照崎, 朱留存, 刘济尘, 魏金占, 蔡旭航, 赵成龙. 一种基于Shi-Tomasi和改进LBP的特征匹配及目标定位快速算法[J]. 吉林大学学报(理学版), 2021, 59(5): 1171-1178.
[4]	孙启隆, 于萍, 司振惠, 郭鑫, 王岩. 基于暗通道的沙尘图像增强算法[J]. 吉林大学学报(理学版), 2021, 59(5): 1179-1187.
[5]	刘高天, 段锦, 范祺, 吴杰, 赵言. 基于改进RFBNet算法的遥感图像目标检测[J]. 吉林大学学报(理学版), 2021, 59(5): 1188-1198.
[6]	胡雅婷, 陈营华, 宝音巴特, 曲福恒, 李卓识. 一种增量式MinMax k-Means聚类算法[J]. 吉林大学学报(理学版), 2021, 59(5): 1205-1211.
[7]	聂逯松, 常方圆, 常学智, 刘畅, 金有为, 刘国晟, 付加胜, 韩霄松. 一种新型的自适应多核学习算法[J]. 吉林大学学报(理学版), 2021, 59(5): 1212-1218.
[8]	蒲晓川, 黄俊丽, 祁宁, 宋长松. 基于密度信息熵的K-means算法在客户细分中的应用[J]. 吉林大学学报(理学版), 2021, 59(5): 1245-1251.
[9]	焦冲, 苏科华, 吴博文, 任术波, 辛宁. 一种基于局部平均法向变形的网格参数化方法[J]. 吉林大学学报(理学版), 2021, 59(4): 867-876.
[10]	丁通, 刘元宁, 朱晓冬, 刘帅, 张齐贤, 张阔. 面向残差网络多元特征的轻量级虹膜分类[J]. 吉林大学学报(理学版), 2021, 59(4): 877-882.
[11]	孙俊, 才华, 朱新丽, 胡浩, 李英超. 基于双重注意力机制的深度人脸表示算法[J]. 吉林大学学报(理学版), 2021, 59(4): 883-890.
[12]	傅博, 王瑞子, 王丽妍, 张湘怡. 基于深度卷积神经网络的水下偏色图像增强方法[J]. 吉林大学学报(理学版), 2021, 59(4): 891-899.
[13]	李晓峰, 李东, 王妍玮. 基于深度残差网络的医学超声图像多尺度边缘检测算法[J]. 吉林大学学报(理学版), 2021, 59(4): 900-908.
[14]	张震, 张照崎, 朱留存, 苗志滨, 王骥月, 李修明, 赵成龙, 张坤伦. 基于Harris-改进LBP的特征匹配及目标定位算法[J]. 吉林大学学报(理学版), 2021, 59(3): 568-576.
[15]	李二强, 陈凯健, 周漾. 可控多重纹理扩展合成与迁移[J]. 吉林大学学报(理学版), 2021, 59(3): 577-586.