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

doi:10.3778/j.issn.1002-8331.2010.21.036

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (21): 129-131.DOI: 10.3778/j.issn.1002-8331.2010.21.036

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

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

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

收稿日期:2009-01-06 修回日期:2009-03-23 出版日期:2010-07-21 发布日期:2010-07-21
通讯作者: 薛淞文

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

摘要/Abstract

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

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

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

中图分类号:

TP311.1

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

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.

[1]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[2]	孙云浩，李逢雨，李冠宇，韩冰，邢维康. 面向RDF图的多模式匹配方法[J]. 计算机工程与应用, 2020, 56(13): 84-92.
[3]	王红，祝寒，林海舟. 航空安全事故因果关系抽取方法的研究[J]. 计算机工程与应用, 2020, 56(11): 265-270.
[4]	朱超，吴素萍. 特征点检测DoG并行算法[J]. 计算机工程与应用, 2020, 56(10): 36-43.
[5]	谭章禄，王兆刚，胡翰. 时间序列趋势相似性度量方法研究[J]. 计算机工程与应用, 2020, 56(10): 94-99.
[6]	黄思猛1，程良伦2，王涛2. 基于双数组trie树的多模式复杂事件检测方法[J]. 计算机工程与应用, 2019, 55(4): 91-95.
[7]	陈亚中1，李振军1，李荣华1，毛睿1，乔少杰2. TSCAN：利用并行策略改进的图结构聚类算法[J]. 计算机工程与应用, 2019, 55(1): 76-83.
[8]	王德政1，张益农1，杨帆2. 基于MapReduce的并行PLS过程监控算法实现[J]. 计算机工程与应用, 2018, 54(24): 61-65.
[9]	夏念，嵩天. 短规则有效的快速多模式匹配算法[J]. 计算机工程与应用, 2017, 53(7): 1-8.
[10]	王歧1，2，3，卢毓海1，3，刘洋1，3，刘燕兵1，3，谭建龙1，3，孙波4. 支持模式串动态更新的多模式匹配Karp-Rabin算法[J]. 计算机工程与应用, 2017, 53(4): 39-44.
[11]	范洪博，史舒鹏，张晶. 改进的AAC多模式实时匹配算法[J]. 计算机工程与应用, 2017, 53(3): 68-73.
[12]	李莉1，江育娥1，林劼1，江秉华2. 基于KMP算法的改进算法KMPP[J]. 计算机工程与应用, 2016, 52(8): 33-37.
[13]	张玉叶1，王颖颖1，王春歆2，彭海军1. 分析参数相关和时序特征的飞行动作识别方法[J]. 计算机工程与应用, 2016, 52(5): 246-249.
[14]	孙劲光1，吴素红2. 基于空间分割与椭球包围盒的碰撞检测算法[J]. 计算机工程与应用, 2016, 52(4): 217-222.
[15]	喻津1，周浩杰2，柴志雷1. 一种基于众核架构的稠密光流并行计算方法[J]. 计算机工程与应用, 2016, 52(16): 186-191.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics