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

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

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

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 hit-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.