作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (14): 265-267. doi: 10.3969/j.issn.1000-3428.2011.14.090

• 开发研究与设计技术 • 上一篇    下一篇

基于GPU的位并行多模式串匹配研究

赵光南,吴承荣   

  1. (复旦大学计算机科学技术学院,上海 200433)
  • 收稿日期:2011-03-16 出版日期:2011-07-20 发布日期:2011-07-20
  • 作者简介:赵光南(1986-),男,硕士研究生,主研方向:网络安全;吴承荣,副教授

Research on Multiple Pattern String Matching with Bit-parallelism Based on GPU

ZHAO Guang-nan, WU Cheng-rong   

  1. (School of Computer Science, Fudan University, Shanghai 200433, China)
  • Received:2011-03-16 Online:2011-07-20 Published:2011-07-20

摘要:

图形处理器(GPU)具有较强的单一运算能力及高度并行的体系结构。根据上述特点,选择基于位并行技术的多模式串匹配算法M-BNDM,将其移植到GPU上加以实现和优化。通过对需要处理的数据进行预处理,将串匹配的过程简化为更适合CUDA计算数据的位操作。对基于CUDA架构的并行串匹配算法的性能影响因子进行分析。实验结果表明,与同等CPU算法相比,该算法能够获得约十几倍的加速比。

关键词: 图形处理器, 多模式字符串匹配, 位并行, M-BNDM算法, 加速

Abstract:

Considering the strong computing ability and a high degree of parallel architecture of Graphic Processing Unit(GPU), the paper chooses one of multiple string match algorithms based on bit-parallelism, called M-BNDM algorithm, which is to be implemented on GPU and optimized. The process for string matching is simplified to bit operation that is more suitable for data computing of Compute Unified Device Architecture (CUDA) through data preprocessing. Experimental result shows the solution is about 10 times faster than equivalent CPU algorithm. Furthermore, some factors that will infect string matching performance are analyzed.

Key words: Graphic Processing Unit(GPU), multiple pattern string matching, bit-parallelism, M-BNDM algorithm, speed up

中图分类号: