基于GPU的AC模式匹配改进算法

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (18): 7-12.

基于GPU的AC模式匹配改进算法

汪宏1，2，王鹏1，2

1.中国科学院上海高等研究院，上海 201210
2.上海市信息技术研究中心，上海 201210

出版日期:2015-09-15 发布日期:2015-10-13

Improved AC pattern matching algorithm based on GPU

WANG Hong1，2, WANG Peng1，2

1.Shanghai Advanced Research Institute, Chinese Academy of Sciences, Shanghai 201210, China
2.Shanghai Information Technology Research Center, Shanghai 201210, China

Online:2015-09-15 Published:2015-10-13

摘要/Abstract

摘要： 字符串匹配算法的应用非常广泛，在信息检索、信息安全等领域都起着关键的作用。近年来，由于GPU通用计算的高速发展，且GPU具有很强的并行计算能力和很高的存储器访问带宽，利用GPU来加速字符串匹配算法吸引了越来越多的关注。提出的改进的AC模式匹配算法，在对前人工作的基础上，进一步消除了output表的存储，将纹理存储器中的查表操作转换为数值比较操作，与改进前算法相比，速度提高了80%以上；进一步的，引入了多个可变参数，提高AC算法的有效数据匹配率，并优化线程块的大小，优化后的算法与采用一种特殊匹配方式的高效的PFAC算法相比，速度提高了9%以上。

关键词: 图形处理器（GPU）计算, 模式匹配, Aho-Corasick算法, 统一计算架构（CUDA）编程模型

Abstract: String matching is a widely used algorithm which plays a pivotal role in areas such as information retrieval, information security, etc.. In recent years, due to the rapid development of general-purpose GPU computing, fast parallel computing ability and high bandwidth memory access of GPU, using GPU to accelerate string matching algorithm has attracted more and more attention. On the basis of the previous work, the improved AC pattern matching algorithm which is proposed in this paper, further eliminates the storage requirement of the output table, converts the look-up operations in texture memory to numerical comparison operations. Compared to the previous algorithm which doesn’t adopt this improvement, the speed is accelerated by over 80%. Moreover, several variables are introduced to enhance effective data matching rate and optimize thread block size. Compared to an efficient algorithm-PFAC, which uses a special matching mode, the optimized algorithm is more than 9% faster.

Key words: Graphic Process Unit（GPU） computing, pattern matching, Aho-Corasick algorithm, Compute Unified Device Architecture（CUDA） programming model

汪宏1，2，王鹏1，2. 基于GPU的AC模式匹配改进算法[J]. 计算机工程与应用, 2015, 51(18): 7-12.

WANG Hong1，2, WANG Peng1，2. Improved AC pattern matching algorithm based on GPU[J]. Computer Engineering and Applications, 2015, 51(18): 7-12.

[1]	孙云浩，李逢雨，李冠宇，韩冰，邢维康. 面向RDF图的多模式匹配方法[J]. 计算机工程与应用, 2020, 56(13): 84-92.
[2]	王红，祝寒，林海舟. 航空安全事故因果关系抽取方法的研究[J]. 计算机工程与应用, 2020, 56(11): 265-270.
[3]	谭章禄，王兆刚，胡翰. 时间序列趋势相似性度量方法研究[J]. 计算机工程与应用, 2020, 56(10): 94-99.
[4]	黄思猛1，程良伦2，王涛2. 基于双数组trie树的多模式复杂事件检测方法[J]. 计算机工程与应用, 2019, 55(4): 91-95.
[5]	夏念，嵩天. 短规则有效的快速多模式匹配算法[J]. 计算机工程与应用, 2017, 53(7): 1-8.
[6]	王歧1，2，3，卢毓海1，3，刘洋1，3，刘燕兵1，3，谭建龙1，3，孙波4. 支持模式串动态更新的多模式匹配Karp-Rabin算法[J]. 计算机工程与应用, 2017, 53(4): 39-44.
[7]	范洪博，史舒鹏，张晶. 改进的AAC多模式实时匹配算法[J]. 计算机工程与应用, 2017, 53(3): 68-73.
[8]	李莉1，江育娥1，林劼1，江秉华2. 基于KMP算法的改进算法KMPP[J]. 计算机工程与应用, 2016, 52(8): 33-37.
[9]	张玉叶1，王颖颖1，王春歆2，彭海军1. 分析参数相关和时序特征的飞行动作识别方法[J]. 计算机工程与应用, 2016, 52(5): 246-249.
[10]	袁淼，王鑫. 基于抽样的Deep Web模式匹配框架[J]. 计算机工程与应用, 2015, 51(3): 117-123.
[11]	胥永康1，杨光露2，路松峰3. 基于压缩后缀数组的近似字符串匹配算法[J]. 计算机工程与应用, 2015, 51(23): 139-142.
[12]	沈璐1，2，纪允1，纪冬宝3，李萍4. 带可变长度通配符的模式匹配算法[J]. 计算机工程与应用, 2015, 51(15): 43-47.
[13]	文举荣，王永利，刘伟. 支持多类型瑕疵度量的RETE改进算法[J]. 计算机工程与应用, 2015, 51(15): 48-55.
[14]	巫喜红. 改进的QS模式匹配算法的性能分析[J]. 计算机工程与应用, 2014, 50(2): 44-48.
[15]	魏东平，朱新向，吴玉雁. 改进的XML小枝模式匹配方法[J]. 计算机工程与应用, 2013, 49(8): 125-128.