基于众核硬件的模式匹配算法加速技术研究

发布时间：2017-04-10 12:22

  本文关键词：基于众核硬件的模式匹配算法加速技术研究，，由笔耕文化传播整理发布。

【摘要】：近年来随着网络化的发展,各行各业的数据呈现爆炸式增加态势。据IDC预测,到2020年全球的数字信息总量将达到惊人的35ZB,信息内容监管将面临巨大挑战。模式匹配算法是文本处理领域基础且非常重要的算法之一,广泛应用在网络入侵检测、生物信息学、图像处理等领域。 基于软件实现的模式匹配算法,由于需要消耗大量的处理器资源和存储资源,系统的实际性能往往不高,采用高性能的硬件来处理海量数据势在必行。GPU是一种具有超强并行计算能力的众核可编程硬件,目前已被用于加速模式匹配算法性能。本文旨在充分利用GPU、CPU各自的硬件特性,结合模式匹配算法的适用性,最终设计并实现高效的模式匹配算法。本论文主要的成果与贡献如下： (1)模式匹配相关技术研究。本文详细介绍了精确模式串匹配相关技术和正则表达式匹配相关技术,并分析了相关算法的优缺点。 (2)提出了在CPU和GPU上实现的基于状态转换表(STT)分割的大规模精确模式串匹配SPAC算法。本算法主要解决由模式串集合生成的Trie树对应STT在GPU中内存占用过大的问题。实验表明,SPAC算法可以在GPU上减少约50%的STT空间占用,在处理大规模精确模式串匹配时效果尤为明显。 (3)提出了在CPU和GPU上实现的高速正则表达式匹配MDFA算法。本算法主要解决在GPU上进行正则表达式匹配时,文本块之间的“边界”问题处理,GPU进行多个子文本块的并行处理,CPU对子文本块的边界进一步处理。实验表明,当正则表达式集合对应的最大可匹配字符串较长(或限定可匹配长度较长)的情况下,MDFA算法可以有效的减少GPU中相邻work-group之间冗余字符的比较。
【关键词】：GPU 并行计算 精确模式串匹配 正则表达式匹配
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP332;TP301.6
【目录】：

• 摘要4-5
• ABSTRACT5-10
• 第一章 绪论10-14
• 1.1 课题背景10-12
• 1.1.1 模式匹配应用广泛10-11
• 1.1.2 网络安全问题突出11
• 1.1.3 传统入侵检测系统的发展瓶颈11-12
• 1.2 课题研究内容及意义12-13
• 1.3 论文组织结构13-14
• 第二章 通用GPU计算研究14-20
• 2.1 GPGPU体系结构14-15
• 2.2 OpenCL 框架15-18
• 2.2.1 OpenCL平台模型15-16
• 2.2.2 OpenCL存储模型16-17
• 2.2.3 OpenCL执行模型17-18
• 2.3 本章小结18-20
• 第三章 大规模精确模式串匹配技术研究20-42
• 3.1 软件精确模式串匹配技术及其研究现状20-26
• 3.1.1 单模式串匹配算法20-23
• 3.1.1.1 Knuth-Morris-Pratt(KMP)算法20-21
• 3.1.1.2 Horspool 算法21-23
• 3.1.2 多模式串匹配算法23-26
• 3.1.2.1 Trie 树23-24
• 3.1.2.2 Aho-Corasick 算法24-26
• 3.1.3 软件大规模精确模式串匹配的不足26
• 3.2 硬件精确模式串匹配技术及其研究现状26-28
• 3.2.1 DPAC 算法26-27
• 3.2.2 PFAC 算法27
• 3.2.3 硬件大规模精确模式串匹配的不足27-28
• 3.3 基于GPU&CPU的大规模精确模式串匹配算法设计28-32
• 3.3.1 改进 Trie 树28-29
• 3.3.2 状态转换表分割29-30
• 3.3.3 大规模精确模式串匹配SPAC算法30-32
• 3.4 基于GPU&CPU的大规模精确模式串匹配算法实现32-38
• 3.4.1 Trie 树节点编号重排序32-34
• 3.4.2 GPU匹配部分34-36
• 3.4.3 CPU匹配部分36-38
• 3.5 实验评估38-40
• 3.5.1 实验平台38
• 3.5.2 实验数据38
• 3.5.3 实验方法38-39
• 3.5.4 实验结果39-40
• 3.6 本章小结40-42
• 第四章 高速正则表达式匹配技术研究42-64
• 4.1 正则表达式匹配技术42-48
• 4.1.1 正则表达式基本概念42-43
• 4.1.2 正则表达式与有限自动机43-47
• 4.1.2.1 有限自动机基本概念43-44
• 4.1.2.2 正则表达式构造NFA44-45
• 4.1.2.3 NFA到DFA的转换45-47
• 4.1.2.4 DFA 最小化47
• 4.1.3 正则表达式匹配47-48
• 4.2 正则表达式匹配技术研究现状48-52
• 4.2.1 D~2FA：Delayed input DFA48-49
• 4.2.2 A-DFA：A Time- and Space-Efficient DFA49-50
• 4.2.3 iNFAnt：GPU-based NFA Implementation50-52
• 4.3 基于GPU&CPU的高速正则表达式匹配算法设计52-56
• 4.3.1 DFA正则表达式匹配52-53
• 4.3.2 数据并行访问53-54
• 4.3.3 边界问题的处理54-55
• 4.3.4 高速正则表达式匹配算法框架55-56
• 4.4 基于GPU&CPU的高速正则表达式匹配算法实现56-59
• 4.4.1 GPU并行数据读取56-57
• 4.4.2 GPU匹配部分实现57-58
• 4.4.3 CPU匹配部分实现58-59
• 4.5 实验评估59-61
• 4.5.1 实验平台59-60
• 4.5.2 实验数据60
• 4.5.3 实验方法60-61
• 4.5.4 实验结果61
• 4.6 本章小结61-64
• 第五章 总结与展望64-66
• 5.1 本文工作总结64
• 5.2 展望64-66
• 参考文献66-70
• 致谢70-72
• 攻读学位期间发表或已录用的学术论文72

【参考文献】

中国期刊全文数据库 前1条

1 王敏杰;朱连轩;;基于Snort的模式匹配算法比较[J];现代电子技术;2011年13期

  本文关键词：基于众核硬件的模式匹配算法加速技术研究，由笔耕文化传播整理发布。

本文编号：296722