论文部分内容阅读
随着网络的迅猛发展，网络安全的重要性也日益凸显，对网络内容的检测成为网络安全体系中不可或缺的一部分。海量数据的处理和层出不穷的应用需求使网络内容检测技术面临着严峻的挑战，而字符串匹配算法正是网络内容检测的核心技术，因此，提高串匹配算法的性能至关重要。而传统的以串行方式执行的串匹配算法的性能难以满足日益增长的网络需求，用并行代替串行成为解决问题的关键。随着GPU (Graphic Processing Unit?图形处理单兀）、TCAM (TernaryContent Addressable Memory，三元内容可寻址存储器）、FPGA (FieldProgrammable Gate Array*现场可编程门阵列）和Bloom filter等硬件的兴起和发展，基于硬件的并行算法成为了研究的热点。同时，由于NVIDIAGPU具有成本低和高吞吐量的特点，成为了高性能并行计算的新生力量。本文分别介绍了基于软件和硬件实现的并行串匹配算法，深入分析了基于GPU、TCAM、FPGA和Bloomfilter等硬件的并行串匹配算法的基本理论。基于GPU的高性能并行架构，把经典的AC (Aho-Corasick)算法移植到GPU平台上进行加速，设计并实现了数据并行的PAC (Parallel Algorithm based on AC)算法。PAC算法的预处理部分在CPU上串行执行，模式匹配部分交由GPU并行处理，将数据集分块，GPU的每个线程处理一个数据块，进行模式匹配。但是，PAC算法需要进行“边界检测”，降低了算法的性能。为了消除PAC算法在内的数据并行算法存在的“边界检测”问题，本文提出了一种新颖的并行串匹配算法PAT (Parallel Algorithm based on Trie),该算法的设计也是本文的创新点。移除AC自动机的所有失效转移和初始状态的自循环转移，得到一棵Trie树，称之为PAT自动机，为输入数据的每个字符分配一个线程，搜索PAT自动机完成模式匹配。重点研究了PAT算法的实现以及GPU实现上的优势，并提出了算法的优化策略，包括减少GPU全局存储器的内存处理、消除输出表的访问和减小状态转移表查找的延迟。通过实验得出，在NVIDIA GPU G94上实现的PAC和PAT算法与AC算法相比，分别达到了4.75和8.43的加速比。通过GPU的加速技术，大大提高了字符串匹配算法的性能，并且PAT算法在GPU实现上获得了更优的性能。