最早为图形渲染而专门设计的图形处理器(GPU),因其越来越强大的浮点运算能力和大规模并行处理能力,时至今日在通用计算领域也得到了广泛的应用,并且在科学计算领域获得了极大成功。GPU通用计算已成为当前工业界和学术界的研究热点。面对急剧增长的网络流量和包处理复杂度,网络设备面临越来越大的计算压力,利用GPU提高网络设备的处理能力成为GPU通用计算又一个新的应用领域。然而与科学计算领域以计算密集型问题为主、数据并行性易于利用不同,网络计算领域以访存密集型和I/O密集型任务为主,且数据并行性难以挖掘和利用。将GPU应用于网络处理领域需对既有算法进行并行化再设计,使之适应GPU的体系结构,以充分利用GPU的大规模并行计算能力。本论文选择正则表达式匹配和数据无损压缩两个尚未有效解决的问题,研究它们在GPU上的高效实现方法。正则表达式匹配无论是用硬件还是软件、在CPU上还是在GPU上实现,都面临难以调和的时空两难问题。基于DFA的正则表达式匹配速度快,但存在空间爆炸的问题；基于NFA的正则表达式匹配空间复杂度低,但匹配速度也慢。论文在深入研究GPU架构特点及NFA特征的基础上,提出一种高效的NFA实现方法。无损数据压缩无论是采用基于字典的压缩技术还是基于统计的压缩技术,数据压缩操作的数据间依赖性都很强,数据并行性难以挖掘和利用,GPU特有的单指令流多数据流并行执行模式又进一步增加了并行化的难度。论文研究以上两种压缩技术的代表性算法-基于字典的LZSS压缩算法和基于统计的哈夫曼编码算法在GPU上的高效实现,并在此基础上完成了基于这两种技术的Deflate数据压缩算法的并行化。论文的主要贡献和创新点如下：1针对正则表达式匹配的时空两难问题,论文以空间复杂度最低的NFA作为正则表达式匹配的基础实现,通过引入状态兼容组、兼容超级组、虚拟NFA状态等概念优化线程的任务分配,并通过数据包交织存储、全局存储器归并访问等技术提高线程的访存效率,实现了正则表达式匹配在GPU上的高效实现。该工作首次解决了正则表达式匹配的时空两难问题,在获得10Gbps匹配速度的同时仍然保持算法的线性空间复杂度。2针对基于字典的无损数据压缩算法LZSS在GPU上并行化程度低的问题,本文以哈希表作为字典的基础实现,通过精巧的数据结构及算法设计有效解决了并行化LZSS算法中最困难的线程串行化问题,并显著减少了对GPU计算资源的使用。该项工作在压缩率和压缩速率两个方面都明显优于目前在GPU上加速LZSS算法的最好工作。3本文在Deflate无损数据压缩算法的上下文中研究哈夫曼编码算法在GPU上的并行化,通过精巧的算法设计和CUDA原子操作有效解决了直方图计算、哈夫曼树构建和变长编码的并行化问题。该工作系首次在GPU上完成了Deflate算法的并行化实现,在压缩率接近Deflate算法的同时,压缩速率超过四核CPU上的Deflate算法实现。本文工作在高效实现正则表达式匹配和无损数据压缩在GPU上并行化的同时,也为其它算法在GPU上的高效实现提供了方法性指导及技术参考。