串匹配是计算机研究领域的一个经典问题,是网络内容分析系统的关键技术之一。随着互联网的普及和发展,海量信息的处理和新的应用需求对串匹配技术提出了新的挑战。在现实生活中,串匹配技术的应用十分广泛,其主要应用领域包括:入侵检测、病毒检测、信息检索、信息过滤、计算生物学等等。串匹配技术的研究与发展是与现实应用息息相关的,近年来,新的应用需求对串匹配技术提出了新的要求和挑战。可编程图像处理器单元(GPU)已经发展成为绝对的计算主力。由于具有由高内存带宽驱动的多个核心,今天的GPU为图像和非图像处理提供了难以置信的资源。GPU的每秒浮点数操作(54GLOPS)几乎是Intel Core2 Du(o5.6GFLOPS)的十倍。由于GPU具有如此巨大的运算潜力,越来越多的应用试图将通用计算任务移植到GPU上来做。利用GPU的SIMD流处理器作为通用计算平台已经得到了广泛的研究和应用,这使得GPU能够成为一个有效的CPU协处理器,获得较高的性价比。本文从GPU的体系结构出发,研究如何在GPU上给予图形管道流水线的编程方法及NVIDIA CUDA统一计算设备架构,如何开发串匹配算法的数据并行性适合在GPU上运行的串匹配算法。本文的主要工作包括:首先,GPU上通用计算编程方法进行了研究:研究了OpenGL、BROOK、CG等GPU上通用计算的编程方法,以及如何开发基于图形管道流水线的通用计算原理。在此基础上进一步研究了NVIDIA CUDA的编程模型与并行线程设计方法,并通过设计实例,总结了CUDA并行算法设计关键技术与一般性方法。其次,设计了适合GPU的并串匹配算法的设计与实现:BF算法是串匹配算法中最基础的算法,但它是串行算法,不适合GPU的体系结构。本文通过对需要处理的数据增加一定比例的冗余信息的方法,设计了适合CUDA计算数据的独立性特点的并行字符串匹配算法。实验结果表明基于CUDA架构的并行串匹配算法获得约10倍的加速比。最后,提出了一种针对待匹配数据字符分布特征的链式状态转移表存储方法,在给定的内存访问代价模型基础上,给出了链式状态转移表内存访问代价函数,并证明了使用Huffman编码对访问序列重编码可以使访问代价最小。