2012年8月湖北第二师范学院学报
Aug．2012第29卷第8期
Journal of Hubei University of Education
Vol．29
No.8
基于GPU 的串匹配算法研究综述
孙延维1，2
，张
慧
2
（1．重庆邮电大学计算机科学与技术学院，重庆400065；2．湖北第二师范学院计算机学院，武汉430205）
摘
要：串匹配是一个非常经典的问题，本文通过回顾和分析GPU 的串匹配算法的国内外研究近况，提出了GPU 的串匹
配算法的一些新的研究方向，
特别是将一些编译解释性的工作放在GPU 上实现的思想。关键词：GPU ；GPGPU ；串匹配；正则表达式；编译收稿日期：2012－06－15
中图分类号：TP301．6
文献标识码：A
文章编号：1674-344X （2012）08-0025-03基金项目：2010湖北省教育厅科学技术研究重点项目（D2903002）
作者简介：孙延维（1979－），男，湖北潜江人，讲师，研究方向为嵌入式、
GPGPU 。张
慧（1971－），女，湖北武汉人，副教授，研究方向为网络应用、嵌入式。
1引言
字符串长度17模式串长度近年来GPU （Graphic Process Unit 图形处理单元）已经具备了实现大规模快速计算的编程能力，NVIDA 公司提出的计算统一设备架构（Computer Unified
Device Architecture ，简称CUDA ）技术就是这方面的杰出代表。CUDA 编程给人们一种新的理念，人们可以将GPU 高速并行处理能力广泛应用于数字图像处理算法、石油勘探、天气预测、分子动力学模拟等领域，大幅度提高程序运算速度。GPGPU （General －Purpose computing on Graphics Processing Units ）就是基于GPU 的通用计算。目前国内外关于CUDA 的研究主要集
中于算法的设计和CUDA 优势的阐明［1］
。
字符串匹配在计算机病毒码匹配、信息检索、数据
挖掘和生物基因技术领域中都有广泛的应用。字符串
的匹配算法有很多，比如RK 算法、KMP 算法和BF 算法等。虽然串匹配是一个非常经典的问题，但当前却
面临着较大的挑战：处理数据的规模越来越大，匹配效率要求越来越高，而GPU 的高速并行处理能力正好可以解决这个问题。2
基于GPU 的串匹配算法研究进展
自NVIDIA 公司在1999年提出GPU 概念以来，伴
随着半导体工艺技术的不断发展，芯片上集成的晶体
管数目不断增加，
GPU 峰值性能一直以超过摩尔定律的速度增加，平均每过6个月都要翻一番。GPU 具有
浮点计算能力强、带宽高、性价比高、能耗低等优点，目前已被广泛用于图形处理以外的应用中。特别是统一渲染架构发布以来，越来越多的科研人员（包括无任何图形API 编程经验的科研人员）开始GPU 非图形应
用的研究，逐渐形成了新的GPGPU 研究领域［2］
。对于GPGPU 领域的研究工作，董荦等已从GPU 的发展
历史、体系结构、编程模型、软件环境和成功案例等方
面进行了系统阐述［1］
。本文仅从GPU 的串匹配算法的角度对国内外的研究工作进行回顾和分析。2．1基于GPU 的BF 算法
字符串匹配函数中，
BF 算法是一个最基础的算法，但在具体的应用中，它的性能与KMP 等算法相比还是较优的。C ++库函数中的串匹配算法就选的是它。它的优点在于不需要进行模式串的预处理操作，需要的额外空间也是固定的，但它是串行算法，不适合图形处理器。
基于GPU 实现BF 精确串匹配算法［3］
，主要选取图形处理器中的像素处理单元进行处理。GPU
是实现类似于单指令多数据流（SIMD ）的体系结
构，由于其拥有大量的计算部件单元使得它非常适合处理串匹配算法中的重复性匹配操作。但是，由于
逻辑控制部件在GPU 中相对较少，所以GPU 的逻辑处理能力较弱，然而要想提高BF 算法性能，对匹配算法中的分支跳转等逻辑指令的处理是需要重点考虑的。另外，由于字符串文件数据需要输入输出，所以GPU 和CPU 之间相对较低的传输带宽也是基于GPU 的串匹配算法需要解决的问题。在匹配算法的具体实现中，以模式串长度大小的窗口为介质进行滚动扫描时，根据GPU 的每个像素有四个通道，因此每处理一位像素就等同于同时处理了四个通道的结构特点，同时从目标串中取四个与此窗口大小相同的子串进行匹配，这样一次就能得到目标串中
四个字符位的匹配结果［3］
。这样如果GPU 有32个像素处理器，
这样如果在很好很完全地流水线并行的情·
52·
况下，一次能得到目标串中128位字符位置的匹配结果，其效率之高是相当惊人的。
上面的算法如果单就字符串匹配而言，计算效率肯定大大地高于CPU，但是需要将数据上传至显存以及计算完毕后同样需要将结果下载至内存，这样的过程占用了大量的时间，其通信时间与计算时间极度不成比例。关于这一点和GPU的特点有关系，首先，GPU是为了加速图形图像处理而出现的，它适用于计
算密集型及数据密集型的运算，适用于流媒体的计算，在所做计算相同的情况下，数据量越大，它的处理效率越高。其次，平台上AGP总线也大大地降低了它的传输频率，因此它表现出来的带宽会大大地小于其理论的带宽。最后，可以通过多遍渲染的方式大大降低CG 初始化及数据上传下载时间所占的总时间的比率，从而提高计算效率。
2．2基于GPU的位并行多模式串匹配
串匹配算法一般又可以分为单模式匹配和多模式匹配。单模式匹配每次匹配一个模式串，多模式匹配一次匹配多模式串。显然后者匹配算法效率更高，许多学者对多模式匹配在不同环境下的快速算法进行过深入的研究［4－5］。
串匹配中处理的数据主要是由一个具有多个关键词的集合和输入待匹配的文本组成。把输入的文本划分成很多页，用不同的流处理器（Stream Processor，SP）处理不同的页面来实现并行；而关键词集合可以划分成多个更小的子集，然后由不同的流多处理器来负责一个或几个这些子集对输入文本的匹配，实现并行化。对于流多处理器（Stream MultiProcessor，SM），不同的流多处理器利用不同的每个关键词子集去处理相同的页面；对于流处理器，在同一个流多处理器上的不同的流处理器，它们处理同一个关键词子集，但是处理不同的文本页面。整个算法分为两个部分：预处理和模式匹配。预处理是在CPU上进行的，主要任务是构造B表和文本划分。其中B表是算法中定义的位串数组。它需维护一个集合，记
录关键词中每个字符在关键词中出现的位置。GPU主要实现算法中的匹配过程，执行分为多个线程块（Block），若干个线程块组成一个线程网格（Grid），Grid内的不同Block处理不同的关键词子集，每个Block里的每个线程处理一个关键词，每一个Grid处理所有的关键词，不同Grid 处理相同的关键词去匹配不同的页面［6］。每个线程都相互独立地利用本算法去匹配页面。
在同等的条件下，基于GPU的位并行多模式串匹配算法相对于基于CPU的模式匹配算法可以获得约13倍的加速比［6］。这样的一个加速比还是有相当大的优势的，但由于GPU本身硬件资源的限制，在某些情况下的GPU的位并行多模式串匹配算法并不是很适用，比如当实时性和吞吐量都有很高要求的时候，今后可以针对这些方面进行研究和改进。
2．3基于GPU的正则表达式匹配
正则表达式，指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串，许多程序设计编程语言都支持利用正则表达式的字符串操作。正则表达式的匹配一般根据有限自动机理论，先将正则表达式转换成等价的非确定性有限自动机（Nondeterministic Finite Automaton，NFA），直接基于NFA进行匹配或将NFA转换为等价的确定性有限自动机（Deterministic Finite Automaton，DFA），然后基于DFA进行匹配。基于NFA的匹配中，由于状态转移的不确定性，算法效率较低，但NFA的状态表比较小；基于DFA的匹配中，一次处理一个字节，匹配速度相对较快，但状态表很大。在深度报文检测中，一般采用速度更快的确定性有限自动机DFA方法进行模式匹配［6］。
对于基于GPU的正则表达式匹配，为了更大限度地提高匹配的速度，必须尽可能地并行化匹配任务。在匹配时，多个GPU线程是并行执行的，每个线程都可以独立地完成相应的任务，当匹配完成后会将匹配的结果上传至GPU的全局存储器中。待所有线程匹配结束后，CPU就可以从GPU的全局存储器下载匹配的结果。匹配引擎首先将正则表达式集编译成一个确定性有限自动机，然后将有限自动机的状态表绑定到GPU的纹理存储器，最后将报文加载至全局存储器［7］。在匹配时虽然访存密集但相对集中，而纹理存储器配有高速缓存（Cache），所以访问速度很快。在匹配过程中需要对报文逐字节进行处理，所以全局存储器的访问开销很大，如果对全局存储器的访问不能满足合并访问的条件，匹配算法的性能会很低。可行的方法是利用线程共享存储器对报文进行缓冲进而使线程对全局存储器的访问满足合并访问约束。
在基于GPU的引擎中，GPU作为CPU的协处理器只负责匹配工作，而CPU则负责正则表达式的编译，被匹配文本的收集，DFA状态表和报文从内存向GPU存储器的加载，以及从GPU全局存储器下载匹配结果等。匹配结果由报文标识符命中的正则表达式标识符以及报文中命中位置索引组成。这里存在两个层次的并行：Block与Block之间的并行和Block内线程之间的并行。为了使应用能获得更高的效率，Block 的数目应是GPU中流多处理器（SM）数目的2倍以上，使GPU各SM单元满负荷运行。同时，为了隐藏存储器延迟，提高并行性，Block内线程的数目在满足硬件资源约束的前提下也应该尽可能地加大。
与基于CPU的传统方法相比，GPU的实现方法使正则表达式匹配速度提高了约16倍［7］。在基于GPU
的应用中，关键的步骤是对程序的优化。在CUDA环境下，对应用的优化除了对算法的优化外，主要体现在
·
62
·
对存储器访问的优化，设备与主机通信优化，运行配置优化，指令优化以及线程的负载均衡优化等［8］。
3进一步研究的方向
随着GPU硬件技术的发展，当GPU的存储器容量增大以及访问速度提高时，针对正则表达式的匹配引擎将会出现新的设计思路，如可以将每一个表达式独立编译成确定性有限自动机并使用单一独立的线程并行匹配所有报文等等有限自动机状态表的爆炸问题直接制约着匹配引擎支持的正则表达式的数目，同时状态表的增大会导致访存分散，这样缓存的命中率也会降低。下一步可以研究基于GPU的简化状态表的匹配引擎，使其支持的正则表达式数目更多，同时提高性能。
针对目前有些直译式程序设计语言编写的程序执行速度慢的问题，比如Python语言编写的程序。在研究GPU的串匹配算法的基础上，可以尝试研究将编译解释过程中的词法分析和语法分析阶段放在GPU上进行，利用GPU的高速并行性快速得出编译解释结果。通过对利用GPU实现编译的研究可以加深对GPU编译处理潜力的认识，随着这种认识的深化，也可以考虑在GPU实现一种编译转换机制，可以将传统的适合数值程序设计语言编写的程序转换成GPU可以支持运行的程序，例如我们可以转换Fortran语言编写的一些高性能计算的程序，更好地发挥GPU的运算性能，大大缩减这些高性能计算的计算时间。
4结束语
从本文上面的分析可以看出，目前关于GPU的串匹配算法的研究虽然有了一些成果，但大多数还是停留在理论上，而且利用GPU进行并行处理后，整个系统的软硬件协同设计代价太高，并且可升级性较差。针对这些问题，本文提出了一些新的研究方向，特别是动态将一些编译解释性的工作放在GPU上实现的思想具有一定的创新点，这种有实际价值的研究方向具有一定的宣传和推广价值。
参考文献：
［1］董荦，葛万成，陈康力．CUDA并行计算的应用研究［J］．信息技术，2010，（4）．
［2］卢凤顺，宋君强，银福康，等．CPU/GPU协同并行计算研究综述［J］．计算机科学，2011，（3）．
［3］张庆丹，戴正华，冯圣中，孙凝晖．基于GPU的串匹配算法研究［J］．计算机应用，2006，（7）．
［4］武永超，华蓓．基于网络处理器的多模式串匹配研究［J］．计算机工程，2009，（8）
［5］Huang Nen－Fu，Hung Hsien－Wei．A GPU－based Multiple Pattern Matching Algorithm for Network Intrusion Detection Systems ［C］．Proc．of the22nd International Conference on Advanced Information Networking and Applications．Okinawa，Japan：IEEE Computer Society，2008．
［6］赵光南，吴承荣．基于GPU的位并行多模式串匹配研究［J］．计算机工程，2011，（7）．
［7］王磊，陈曙晖，苏金树，许孟晋．深度报文检测中基于GPU 的正则表达式匹配引擎［J］．计算机应用研究，2010，（11）．［8］张舒，褚艳丽，赵开勇，张钰勃．GPU高性能运算之CUDA ［M］．北京：中国水利出版社，2009．
Research Survey of String Matching Algorithm Based
on Graphic Processing Unit
SUN Yan-wei1，2，ZHANG Hui2
（1．College of Computer Science and Technology，Chongqing University of Posts and
Telecommunications，Chongqing400065，China；
2．School of Computer Science，Hubei University of Education，Wuhan430205，China）
Abstract：String matching is an exquisite classic matter．After analysing and looking back to the study condition of GPU string matching at home and abroad，we bring out some new researching point concerning algorithm of GPU string matching in this paper，especially the idea of dynamically realizing the compiler explanation on GPU．
Key words：GPU；GPGPU；stringing matching；regular expression；compiling
·
72
·

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。