Implementation of parallel algorithms for randomized pattern matching on cluster of workstations

doi:10.3778/j.issn.1002-8331.2010.21.036

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (21): 129-131.DOI: 10.3778/j.issn.1002-8331.2010.21.036

• 网络、通信、安全 • Previous Articles Next Articles

Implementation of parallel algorithms for randomized pattern matching on cluster of workstations

XUE Song-wen，SHEN Wei-chang，YAN Gong-xiao，QIAO Long

School of Information Science and Technology，Northwest University，Xi’an 710127，China

Received:2009-01-06 Revised:2009-03-23 Online:2010-07-21 Published:2010-07-21
Contact: XUE Song-wen

随机模式匹配并行算法在工作站机群上的实现

薛淞文，申卫昌，剡公孝，乔龙

西北大学信息科学与技术学院，西安 710127

通讯作者: 薛淞文

Abstract

Abstract: A newly improved pattern matching algorithm is designed by analyzing randomized algorithm for pattern matching and an effective parallel algorithm for pattern matching based on MPICH is designed according to the features of task communication on MPICH parallel programming environment.Text string is divided into overlapped sub-string according to the quantity of process in COW（Cluster of Workstations），and each process executes pattern matching parallelly.The experimental results show that the pattern matching speed is accelerated and the utilization of resources in COW is also improved.

Key words: pattern matching, an implementation of the Message Passing Interface（MPICH）, parallel algorithm, cluster of workstations

摘要： 对随机模式匹配算法进行了改进，并根据MPICH并行编程环境中任务间通信的特点，设计了一种基于MPICH的改进的随机模式匹配并行算法。根据运行在COW（工作站机群）上的进程数目将文本串进行重叠划分，每个进程完成一个文本子串的模式匹配。实验结果表明，该改进的随机模式匹配并行算法有效地加快了模式匹配的速度，提高了工作站机群的资源利用率。

关键词: 模式匹配, 消息传递编程标准的一种实现（MPICH）, 并行算法, 作站机群

CLC Number:

TP311.1

XUE Song-wen，SHEN Wei-chang，YAN Gong-xiao，QIAO Long. Implementation of parallel algorithms for randomized pattern matching on cluster of workstations[J]. Computer Engineering and Applications, 2010, 46(21): 129-131.

薛淞文，申卫昌，剡公孝，乔龙. 随机模式匹配并行算法在工作站机群上的实现[J]. 计算机工程与应用, 2010, 46(21): 129-131.

[1]	YANG Jie, WU Suping. Parallel Algorithm for Point Cloud Reconstruction [J]. Computer Engineering and Applications, 2020, 56(6): 213-219.
[2]	SUN Yunhao, LI Fengyu, LI Guanyu, HAN Bing, XING Weikang. Multi-pattern Matching Method for RDF Graph [J]. Computer Engineering and Applications, 2020, 56(13): 84-92.
[3]	WANG Hong, ZHU Han, LIN Haizhou. Research on Causality Extraction of Civil Aviation Accident [J]. Computer Engineering and Applications, 2020, 56(11): 265-270.
[4]	ZHU Chao, WU Suping. Feature Point Detection DoG Parallel Algorithm [J]. Computer Engineering and Applications, 2020, 56(10): 36-43.
[5]	TAN Zhanglu, WANG Zhaogang, HU Han. Research on Trend Similarity Measurement Method of Time Series [J]. Computer Engineering and Applications, 2020, 56(10): 94-99.
[6]	HUANG Simeng1, CHENG Lianglun2, WANG Tao2. Multi-Pattern Complex Event Detection Method Based on Double-Array Trie-Tree [J]. Computer Engineering and Applications, 2019, 55(4): 91-95.
[7]	CEHN Yazhong1, LI Zhenjun1, LI Ronghua1, MAO Rui1, QIAO Shaojie2. Improved Graph Structure Clustering Algorithm by Using Parallel Strategy [J]. Computer Engineering and Applications, 2019, 55(1): 76-83.
[8]	REN Shengbing, WANG Zhijian, WANG Yu. Layout mining and pattern matching algorithm on automatic Web page design [J]. Computer Engineering and Applications, 2018, 54(3): 227-232.
[9]	WANG Dezheng1, ZHANG Yinong1, YANG Fan2. Implementation of parallel PLS algorithm of process monitoring using MapReduce [J]. Computer Engineering and Applications, 2018, 54(24): 61-65.
[10]	XIA Nian, SONG Tian. Short-rule-efficient rapid multi-pattern matching algorithm [J]. Computer Engineering and Applications, 2017, 53(7): 1-8.
[11]	WANG Qi1，2，3, LU Yuhai1，3, LIU Yang1，3, LIU Yanbing1，3, TAN Jianlong1，3, SUN Bo4. Dynamical adaptive Karp-Rabin multi-pattern matching algorithm [J]. Computer Engineering and Applications, 2017, 53(4): 39-44.
[12]	FAN Hongbo, SHI Shupeng, ZHANG Jing. Improvement of multi-patterns string matching algorithms of Advanced AC [J]. Computer Engineering and Applications, 2017, 53(3): 68-73.
[13]	LI Li1, JIANG Yu’e1, LIN Jie1, JIANG Binghua2. Improved algorithm KMPP based on KMP [J]. Computer Engineering and Applications, 2016, 52(8): 33-37.
[14]	ZHANG Yuye1, WANG Yingying1, WANG Chunxin2, PENG Haijun1. Acrobatic maneuver reorganization method compared with parameters relevance and feature of sequence change [J]. Computer Engineering and Applications, 2016, 52(5): 246-249.
[15]	SUN Jinguang1, WU Suhong2. Collision detection algorithm based on ellipsoid bounding box and spatial decomposition [J]. Computer Engineering and Applications, 2016, 52(4): 217-222.

Implementation of parallel algorithms for randomized pattern matching on cluster of workstations

随机模式匹配并行算法在工作站机群上的实现

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics