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

Abstract

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

CLC Number:

TP391

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]	WANG Yu, SHEN Xuanjing, ZHOU Yuzhou, LIN Hongbin. An Artificial Bee Colony Algorithm for Solving the Shortest Path Problem in Traffic Network [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1144-1150.
[2]	ZHU Xinli, CAI Hua, KOU Tingting, DU Donghui, SUN Junxi. Pedestrian Multi-target Tracking Algorithm [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1161-1170.
[3]	ZHANG Zhen, ZHANG Zhaoqi, ZHU Liucun, LIU Jichen, WEI Jinzhan, CAI Xuhang, ZHAO Chenglong. A Fast Algorithm for Feature Matching and Target Location Based on Shi-Tomasi and Improved LBP [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1171-1178.
[4]	SUN Qilong, YU Ping, SI Zhenhui, GUO Xin, WANG Yan. Dust Image Enhancement Algorithm Based on Dark Channel [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1179-1187.
[5]	LIU Gaotian, DUAN Jin, FAN Qi, WU Jie, ZHAO Yan. Target Detection for Remote Sensing Image Based on Improved RFBNet Algorithm [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1188-1198.
[6]	HU Yating, CHEN Yinghua, BAOYIN Bate, QU Fuheng, LI Zhuoshi. An Incremental MinMax k-Means Clustering Algorithm [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1205-1211.
[7]	NIE Lusong, CHANG Fangyuan, CHANG Xuezhi, LIU Chang, JIN Youwei, LIU Guosheng, FU Jiasheng, HAN Xiaosong. A Novel Self-adaptive Multiple Kernel Learning Algorithm [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1212-1218.
[8]	PU Xiaochuan, HUANG Junli, QI Ning, SONG Changsong. Application of K-Means Algorithm Based on Density Information Entropy in Customer Segmentation [J]. Journal of Jilin University Science Edition, 2021, 59(5): 1245-1251.
[9]	JIAO Chong, SU Kehua, WU Bowen, REN Shubo, XIN Ning. Mesh Parameterization Method Based on Local Average Normal Deformation [J]. Journal of Jilin University Science Edition, 2021, 59(4): 867-876.
[10]	DING Tong, LIU Yuanning, ZHU Xiaodong, LIU Shuai, ZHANG Qixian, ZHANG Kuo. Lightweight Iris Classification Based on Multiple Features in Residual Network [J]. Journal of Jilin University Science Edition, 2021, 59(4): 877-882.
[11]	SUN Jun, CAI Hua, ZHU Xinli, HU Hao, LI Yingchao. Deep Face Representation Algorithm Based on Dual Attention Mechanism [J]. Journal of Jilin University Science Edition, 2021, 59(4): 883-890.
[12]	FU Bo, WANG Ruizi, WANG Liyan, ZHANG Xiangyi. Enhancement Method of Underwater Color Cast Image Based on Deep Convolutional Neural Network [J]. Journal of Jilin University Science Edition, 2021, 59(4): 891-899.
[13]	LI Xiaofeng, LI Dong, WANG Yanwei. Multi-scale Edge Detection Algorithm for Medical Ultrasonic Image Based on Deep Residual Network [J]. Journal of Jilin University Science Edition, 2021, 59(4): 900-908.
[14]	ZHANG Zhen, ZHANG Zhaoqi, ZHU Liucun, MIAO Zhibin, WANG Jiyue, LI Xiuming, ZHAO Chenglong, ZHANG Kunlun. Feature Matching and Target Location Algorithm Based on Harris Improved LBP [J]. Journal of Jilin University Science Edition, 2021, 59(3): 568-576.
[15]	LI Erqiang, CHEN Kaijian, ZHOU Yang. Controllable Multi-texture Extended Synthesis and Transfer [J]. Journal of Jilin University Science Edition, 2021, 59(3): 577-586.

Heterogeneous Parallel String Matching AlgorithmBased on Mobile Platform

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10