基于CPU+GPU异构平台的字符串匹配算法研究与实现

论文摘要

字符串匹配是计算机科学领域中最基础的技术之一,广泛应用于信息检索、网络安全等领域。然而,随着匹配内容（如网页、网络数据包等）的不断增加以及搜索形式日益复杂（从精确匹配到正则表达式匹配）。字符串匹配迫切需要采用新的高性能技术去设计更有效以及质量更高的算法来满足海量数据的应用需求。与此同时,由CPU+GPU（中央处理器+图像处理器）组成的异构处理平台已经成为主流的并行解决方案。CPU在执行指令和复杂逻辑方面发挥其高效性的优势,而GPU在浮点计算、并行计算以及内存带宽上大大超越了CPU。本论文旨在利用CPU+GPU异构多核的高并行能力,研究经典的字符串匹配算法,分析算法复杂度和适用性,设计和优化高性能并行匹配算法,提升字符串匹配的性能。本论文首先概述字符串匹配的广泛应用及面临的挑战,同时对GPU的架构特点及其特有的开发框架CUDA（the Compute Unified Device Architecture,计算统一设备框架）进行了论述,阐述了CUDA编程中如何调度线程、如何分配内存以达到充分利用GPU计算能力的技巧,并介绍了国内外基于GPU的字符串匹配研究。其次本文对经典的多模式字符串匹配算法——AC算法（Aho-Corasick算法）进行了移植优化,通过结合CPU+GPU异构平台的特点将AC算法向GPU移植并设计成并行匹配算法——GAC （GPU-based Aho-Corasick）。接着将GAC实现于网页匹配系统中,获得了比原系统28倍的速度提升。最后论文研究了高级字符串匹配——正则表达式的实现原理,通过设计表扩展、数据并行以及流水线等方案,完成了异构平台上的高性能正则表达式匹配系统——GFlex（GPU-based Flex）,相比原串行系统甚至于多核并行系统在性能上有了显著地提高。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 字符串匹配的广泛应用
• 1.1.2 GPU 简介
• 1.2 国内外研究现状
• 1.3 论文研究内容及意义
• 1.4 论文的主要工作
• 1.5 论文的组织结构
• 第二章 GPU 体系结构及已有算法分析
• 2.1 GPU 体系结构
• 2.2 GPU 存储结构
• 2.3 CUDA 编程
• 2.4 基于GPU 的字符串匹配算法
• 2.4.1 基于GPU 的KMP 算法
• 2.4.2 基于GPU 的AC 算法
• 2.4.3 基于GPU 的NFA 算法
• 2.4.4 算法评述
• 2.5 本章小结
• 第三章 基于CPU+GPU 上的AC 算法优化
• 3.1 AC 算法介绍
• 3.2 数据结构设计
• 3.2.1 AC 自动机数据结构
• 3.2.2 文本数据结构
• 3.2.3 匹配结果数据结构
• 3.3 GAC 算法设计
• 3.3.1 算法框架
• 3.3.2 算法执行流程
• 3.3.3 GPU 内存分配优化
• 3.4 CPU 上的实现
• 3.4.1 CPU 上的预处理过程
• 3.4.2 CPU 上的后处理过程
• 3.5 GPU 上算法优化方案
• 3.5.1 Version1 版本设计
• 3.5.2 Version2 版本设计
• 3.5.3 Version3 版本设计
• 3.6 本章小结
• 第四章 GAC 实验测试及结果分析
• 4.1 测试平台
• 4.2 测试用例
• 4.3 CPU 串行系统测试
• 4.4 GAC 系统测试
• 4.4.1 Version1 版本测试
• 4.4.2 Version2 版本测试
• 4.4.3 Version3 版本测试
• 4.5 测试结果分析
• 4.5.1 实验数据
• 4.5.2 规律分析
• 4.6 本章小结
• 第五章 CPU+GPU 上的并行正则表达式匹配
• 5.1 正则表达式匹配的问题描述
• 5.2 正则表达式匹配的一般方法
• 5.2.1 NFA 方法
• 5.2.2 DFA 方法
• 5.3 多核并行PCRE 匹配系统
• 5.4 多核并行Flex 匹配系统
• 5.4.1 Flex 和PCRE 的规则差异与解决方法
• 5.4.2 预处理过程
• 5.4.3 基于Flex 的并行匹配过程
• 5.4.4 利用PCRE 进行后处理
• 5.5 异构平台上的GFlex 匹配系统
• 5.5.1 GFlex 的设计与实现
• 5.6 本章小结
• 第六章 并行正则表达式匹配系统测试与分析
• 6.1 测试平台
• 6.2 测试用例
• 6.3 CPU 串行系统测试
• 6.4 多核并行PCRE 系统测试
• 6.5 多核并行Flex 匹配系统测试
• 6.6 异构并行GFlex 匹配系统测试
• 6.7 本章小结
• 第七章总结与展望
• 7.1 本文总结
• 7.2 展望
• 参考文献
• 攻读硕士学位期间取得的研究成果
• 致谢
• 附件