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

吉林大学学报(理学版)

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

刘磊¹, 李广力¹, 徐玥¹, 张桐搏¹, 吕帅^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]	贺怀清, 翟羽佳, 刘浩翰, 惠康华. 基于特征增强的3D目标检测模型ICasA[J]. 吉林大学学报(理学版), 2026, 64(4): 823-0834.
[2]	胡亨伍, 李松涛. 基于小波相位滤波的X光图像多层次模糊增强方法[J]. 吉林大学学报(理学版), 2026, 64(4): 835-0841.
[3]	熊哲源, 汪灿华, 郑炳城, 沈志伟. 基于改进注意力W-Net的超声图像分割算法[J]. 吉林大学学报(理学版), 2026, 64(4): 842-0848.
[4]	唐菁敏, 罗浩天, 虞贵财. 人工噪声辅助的无人机通感一体化安全波束成形[J]. 吉林大学学报(理学版), 2026, 64(4): 879-0886.
[5]	王红斌, 张煊赫, 侯明辉. 基于层级知识增强和义原知识的中文隐式情感分析[J]. 吉林大学学报(理学版), 2026, 64(3): 568-0580.
[6]	陈海鹏, 孔鸣, 张洪语, 孙宝胜. 基于边界感知与特征融合的病理图像分割网络[J]. 吉林大学学报(理学版), 2026, 64(3): 581-0590.
[7]	高凯, 王晟宇, 付强, 才华, 张晨洁, 王伟刚. 基于多层级交互式特征融合的三维目标检测算法[J]. 吉林大学学报(理学版), 2026, 64(3): 591-0602.
[8]	张弄, 徐哲文, 刘长征. 基于领域先验知识的时空神经网络模型在MJO预报中的应用[J]. 吉林大学学报(理学版), 2026, 64(3): 617-0626.
[9]	张书达, 李慧盈. 融合欧氏与双曲几何的深度度量学习方法[J]. 吉林大学学报(理学版), 2026, 64(2): 284-0290.
[10]	吴建, 王兴旺, 孙亚峰, 于美铭. 基于多压缩机制协同的轻量化模型在课堂行为检测中的应用[J]. 吉林大学学报(理学版), 2026, 64(2): 301-0310.
[11]	姜昀奇, 韩晓同, 田原. 基于大语言模型与适配器驱动的知识图谱补全算法[J]. 吉林大学学报(理学版), 2026, 64(2): 291-0300.
[12]	路扬, 张学沛, 马小蕾, 王一博, 白金峰. 基于多模态自适应融合的呼吸频率预测方法[J]. 吉林大学学报(理学版), 2026, 64(2): 319-0328.
[13]	金先进, 张晋恒, 杨建平, 孙晓海, 周兵. 基于改进YOLOv9的玉米幼苗轻量级杂草检测模型Weed-YOLO[J]. 吉林大学学报(理学版), 2026, 64(2): 329-0343.
[14]	刘爽, 吕俊良, 秦宇航, 秦丹丹, 孙佳慧. 基于YOLOv8的PCB缺陷检测改进算法[J]. 吉林大学学报(理学版), 2026, 64(2): 344-0350.
[15]	廉雄杰, 董振. 基于XLM-RoBERTa-Large-Finetuned-Conll03-English模型结合CRF的中文命名实体识别微调优化方法[J]. 吉林大学学报(理学版), 2026, 64(2): 370-0376.