1基于GPU的并行高性能AC算法

徐東亮 張宏莉 姚崇崇

摘 要：隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)流量的增長速度與網(wǎng)絡(luò)安全系統(tǒng)的過濾能力之間的矛盾日益突出。作為網(wǎng)絡(luò)安全系統(tǒng)的核心模塊——模式匹配模塊的處理能力受到嚴(yán)峻的挑戰(zhàn)。傳統(tǒng)串行模式匹配算法已經(jīng)很難滿足當(dāng)前網(wǎng)絡(luò)的需求。本文改進(jìn)了傳統(tǒng)的AC算法，利用高性能專用并行處理芯片——GPU來提高AC算法的處理速度，提出了一種G-AC算法。實(shí)驗(yàn)表明，在不同數(shù)據(jù)集上，其性能分別是傳統(tǒng)AC算法的10倍以上。

關(guān)鍵詞：AC算法；GPU；模式匹配；G-AC算法

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識號：A 文章編號：2095-2163（2015-）02-

GPU-based Parallel High Performance AC Algorithm

XU Dongliang， ZHANG Hongli， YAO Chongchong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： With the development of the network， the contradiction between the growth rate of network traffic and the filtering capability of the Network security system have become increasingly prominent. As the core modules of network security systems， pattern matching module processing capacity faces serious challenge. The traditional serial algorithm for pattern matching has been difficult to meet the current needs of the network. This paper improves the traditional AC algorithm， using high performance special parallel processing chip GPU to improve the processing speed of AC algorithm， and proposes a new G-AC algorithm. Experiments show that its performance is 10 times more than the performance of traditional AC algorithm on different data sets.

Keywords： AC Algorithm； GPU； Pattern Matching； G-AC Algorithm

0 引 言

模式匹配[1]，即字符串匹配，其應(yīng)用十分廣泛，如網(wǎng)絡(luò)入侵檢測，信息檢索，生物信息等。模式匹配方法的研究歷史已近半個(gè)世紀(jì)之久。1975年由Ahot Corasick提出的Aho-Corasick （AC）算法[2]是經(jīng)典的多模式匹配算法之一，至今仍然頗具現(xiàn)實(shí)影響及客觀性的實(shí)用性。經(jīng)過半個(gè)世紀(jì)的發(fā)展，已經(jīng)有多個(gè)模式匹配算法的性能接近甚至達(dá)到理論上限。但隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)流量的增加卻日益加快，模式匹配模塊的性能已經(jīng)成為網(wǎng)絡(luò)安全系統(tǒng)的瓶頸。

進(jìn)入21世紀(jì)，許多高性能專用硬件芯片的興起，使模式匹配進(jìn)入了利用硬件加速傳統(tǒng)算法的時(shí)代。許多研究者開始轉(zhuǎn)向和聚焦于那些具有強(qiáng)大并行計(jì)算能力的硬件上，各種硬件和專用芯片在模式匹配領(lǐng)域的應(yīng)用日益深入和多樣化。本文就是將傳統(tǒng)的AC算法進(jìn)行結(jié)構(gòu)改進(jìn)，再移植到GPU上，并對其性能進(jìn)行提高。

GPU，即圖形處理單元。自從1999年NVIDIA公司發(fā)布了第一款GPU以來，GPU的發(fā)展就異常迅猛，但當(dāng)時(shí)的GPU只能用于處理圖形計(jì)算，大量的計(jì)算資源則處于閑置浪費(fèi)中。將GPU用于圖形處理以外的其它領(lǐng)域即稱為基于GPU的通用計(jì)算（General-purpose computing on graphics processing units，GPGPU）。隨著GPU的可編程性越來越高，GPU計(jì)算研究吸引了越來越多研究者的青睞和關(guān)注。CPU的邏輯運(yùn)算部件較多，具有強(qiáng)大的邏輯運(yùn)算能力，而GPU數(shù)理運(yùn)算部件較多，由于過多的計(jì)算部件占用了GPU太多的硬件空間，從而導(dǎo)致其邏輯部件較少，并不適合處理大量邏輯運(yùn)算，為此在模式匹配計(jì)算中大都需要借助CPU進(jìn)行邏輯計(jì)算。GPU與CPU的結(jié)構(gòu)對比如圖1。CPU+GPU的異構(gòu)模式是GPGPU計(jì)算的通用模式，其中，GPU負(fù)責(zé)密集型海量數(shù)據(jù)的并行處理，而CPU則主控不適合并行計(jì)算的事務(wù)管理和復(fù)雜邏輯處理。這種模式利用了GPU的高帶寬和高性能的并行計(jì)算能力，并藉此彌補(bǔ)了CPU的計(jì)算能力不足的劣勢。但是，傳統(tǒng)的CPU+GPU的異構(gòu)處理模型卻并不適用于軟件人員的開發(fā)，其應(yīng)用范圍較為有限。

圖 1 CPU與GPU結(jié)構(gòu)示意圖

Fig.1 Structure of CPU and GPU schematic diagram

2007年，隨著NVIDIA公司以CUDA（the Compute Unified Device Architecture）[3]為代表的GPU通用計(jì)算API的普及，GPU的通用計(jì)算在計(jì)算機(jī)領(lǐng)域的應(yīng)用范圍呈現(xiàn)拓展擴(kuò)張態(tài)勢。CUDA是一種軟硬件結(jié)合的架構(gòu)，可使GPU更易于解決復(fù)雜的計(jì)算問題以及更便于實(shí)現(xiàn)數(shù)據(jù)并行計(jì)算。其中包含了CUDA指令集架構(gòu)（ISA）以及GPU內(nèi)部的并行計(jì)算引擎，開發(fā)人員將不再使用圖形學(xué)API，而是利用C語言來編寫程序。支持CUDA的GPU與以前的GPU相比，在架構(gòu)上完成了兩項(xiàng)改進(jìn)，一是引入了片內(nèi)共享存儲器，支持線程間通信和隨機(jī)寫入；二是采用了統(tǒng)一處理架構(gòu)，可以更加有效地利用計(jì)算資源。CUDA的出現(xiàn)極大地方便了各類研究開發(fā)人員。GPU類單指令多數(shù)據(jù)流（Simple Instruction Multiple Data， SIMD）體系結(jié)構(gòu)（如圖2所示），大量的計(jì)算部件則使其善于處理模式匹配算法中的對比字符這一類計(jì)算密集型操作。

圖 2 GPU塊結(jié)構(gòu)示意圖

Fig. 2 GPU blocks structure diagram

1 相關(guān)工作

Giorgos Vasiliadis等人利用CUDA通用并行計(jì)算架構(gòu)實(shí)現(xiàn)了Snort中模式匹配模塊，將經(jīng)典的AC算法移植到GPU上，設(shè)計(jì)了Gnort[4]系統(tǒng)。該系統(tǒng)利用DMA在CPU與GPU之間進(jìn)行數(shù)據(jù)傳輸和GPU的執(zhí)行計(jì)算的異步性實(shí)現(xiàn)最大吞吐量到2.3Gbit/s，在真實(shí)網(wǎng)絡(luò)環(huán)境中，其性能則是Snort的兩倍以上。該工作也將單模式匹配算法KMP、BM在GPU上進(jìn)行了實(shí)現(xiàn)，與在CPU上相應(yīng)算法相比后得知，性能并未獲得顯著的提高，這與PixeSnort系統(tǒng)使用KMP算法表現(xiàn)的性能相符，由此即可得出結(jié)論，單模式匹配算法不適合移植到GPU上。文獻(xiàn)[5]將經(jīng)典的AC算法在Cray XMT、GPU和分布式內(nèi)存架構(gòu)三種不同的硬件上付諸了實(shí)現(xiàn)，并根據(jù)最小化使用內(nèi)存的原則，對三種硬件下的AC算法性能進(jìn)行了對比可知，GPU的性能表現(xiàn)不俗。

近幾年，GPU在網(wǎng)絡(luò)安全系統(tǒng)及模式匹配方面的研究與應(yīng)用已經(jīng)更趨深入，也日漸廣泛。文獻(xiàn)[6]將K-Mismatch技術(shù)的近似模式匹配算法用GPU進(jìn)行了完整的實(shí)現(xiàn)。其中，文獻(xiàn)[6]還提出了線程并行算法、塊-線程并行算法和OPT-block-thread并行算法以及相應(yīng)的GPU實(shí)現(xiàn)。文獻(xiàn)[7，8] 則在GPU上設(shè)計(jì)實(shí)現(xiàn)了層次化并行正則表達(dá)式模式匹配自動機(jī)，且利用GPU作為協(xié)處理器，處理字符匹配問題。大多數(shù)基于GPU實(shí)現(xiàn)的模式匹配方法都是將GPU作為協(xié)處理器，協(xié)助CPU分擔(dān)主要的計(jì)算工作。

2改進(jìn)AC自動機(jī)

AC算法是一種經(jīng)典的前綴匹配算法。該算法使用了一種被稱做Aho-Corasick （AC）自動機(jī)的特殊自動機(jī)。該自動機(jī)由模式集P生成，也就是對trie樹添加了失敗轉(zhuǎn)移函數(shù)擴(kuò)展而成。圖3所示為集合P={ACGATAT， ATATATA， ATATGC， TAGAT}的AC自動機(jī)。自動機(jī)在模式匹配的應(yīng)用中，性能穩(wěn)定，并因其具有不依賴于模式集合和文本本身的特點(diǎn)，而一直得到應(yīng)用者的首肯和認(rèn)定。但自動機(jī)有一個(gè)缺點(diǎn)，就是將需要很大的內(nèi)存空間，尤其在正則表達(dá)式的匹配中，正則表達(dá)式的通配符等引起的狀態(tài)爆炸，將進(jìn)而導(dǎo)致內(nèi)存爆炸，這即使得自動機(jī)在應(yīng)用中受到了強(qiáng)力限制。

圖 3 AC自動機(jī)示意圖

Fig.3 Schematic diagram of AC automaton

由于傳統(tǒng)AC算法的結(jié)構(gòu)占用內(nèi)存過大（每個(gè)字符均需要占用1KB的內(nèi)存空間），當(dāng)模式集超過1萬條時(shí)，普通機(jī)器的內(nèi)存也就難以滿足要求，為此本文將對標(biāo)準(zhǔn)的AC算法進(jìn)行內(nèi)存壓縮。

經(jīng)過統(tǒng)計(jì)發(fā)現(xiàn)，AC自動機(jī)中深度4以內(nèi)的4個(gè)字符被訪問的頻率總和為83.85%，深度5以內(nèi)的5個(gè)字符被訪問的頻率總和則為91.6%，而深度6以內(nèi)的6個(gè)字符被訪問的頻率總和將可達(dá)到93.93%，從以上三項(xiàng)統(tǒng)計(jì)數(shù)據(jù)可以看出，前5個(gè)字符被訪問的頻率較高，從第6個(gè)字符開始，訪問較少。為此研究中可以只建立前5個(gè)字符的半AC自動機(jī)，而第6個(gè)字符以后的字符，即以字符串的形式存儲在自動機(jī)葉結(jié)點(diǎn)的尾部。匹配時(shí)，用前5個(gè)字符的半自動機(jī)進(jìn)行過濾，前5個(gè)字符全部命中，而后再用尾部的剩余字符串進(jìn)行驗(yàn)證。半自動機(jī)結(jié)構(gòu)可如圖4所示。

圖 4 改進(jìn)AC自動機(jī)示意圖

Fig.3 Schematic diagram of the improved AC automaton

3 G-AC算法

GPU的內(nèi)存分為Globe Memory、Texture Memory和Shared Memory三級，其中Globe Memory是GPU的主存，最大，速度也最慢；Shared Memory屬于片上存儲器，最小，速度最快，本文所用GPU的Shared Memory即為48KB，Texture Memory則位于兩者之間。

實(shí)際應(yīng)用中，半AC自動機(jī)遠(yuǎn)遠(yuǎn)超過50KB，無法存儲于片上的SharedMemory，而只能存儲于Texture Memory。

GPU是以塊（Block）為計(jì)算單位的，每一塊默認(rèn)為64KB，為此可將等匹配文本以64KB為單位劃分成塊，最后一塊可能不滿64KB。為了不致遺漏，塊與塊之間要有一部分重疊，重疊的長度即為最長模式匹配的長度，具體如圖5所示。

圖5 文本分塊示例

Fig.5 diagram of text block

由于GPU中邏輯單元較少，不適合處理邏輯運(yùn)算，就使得半AC自動機(jī)的建立和待匹配的分塊都需要在CPU完成。而GPU與CPU的內(nèi)存卻不能統(tǒng)一尋址，所以半AC自動機(jī)和文本塊即需從CPU的主存中轉(zhuǎn)移到GPU的Texture Memory和Globe Memory中。完整的匹配結(jié)構(gòu)如圖6所示。

圖6 改進(jìn)AC算法在GPU的匹配結(jié)構(gòu)

Fig.6 The structure of G-AC匹配時(shí)，將n個(gè)文本塊分別存儲到GPU的n個(gè)block中，所有的block同時(shí)進(jìn)行匹配，匹配的結(jié)構(gòu)存儲到每個(gè)Block的Shared Memory中，最后將結(jié)果匯總到Globe Memory中，再轉(zhuǎn)送至CPU的主存中輸出。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)平臺為，CPU Intel i5-2300 2.8GHz，內(nèi)存 4GB；GPU GeForce9600GSO/GTX570，Globe Memory 512MB/1GB，CUDA 3.20，OS Fedora13。

數(shù)據(jù)集分為等長模式和不等長模式兩部分，每部分都是不30萬條，不等長模式集中模式長度為6～50個(gè)字符不等，待匹配文本的大小為10MB，如表1所示。

表1 數(shù)據(jù)集

Tab.1 Data Set

數(shù)量

長度

文本大小

等長模式集

300000

32

10MB

不等長模式集

300000

6-50

10MB

圖7分別是兩個(gè)數(shù)據(jù)集在GTX570和GeForce9600并行平臺上的實(shí)驗(yàn)對比結(jié)果。由圖7可以看出，GTX570的吞吐量遠(yuǎn)遠(yuǎn)大于GeForce9600，這就說明GTX570的性能要優(yōu)于GeForce9600。

圖7 兩個(gè)平臺上的吞吐量對比

Fig.7 Comparison of throughput on GTX 570 and GeForce 9600

圖8是CPU、GeForce9600和GTX570三個(gè)平臺的執(zhí)行時(shí)間對比，在CPU上運(yùn)行的是經(jīng)典AC算法。由圖8可以看出，在兩個(gè)GPU上運(yùn)行的改進(jìn)AC算法的效率要遠(yuǎn)遠(yuǎn)高于原始AC算法。

圖8 CPU、GeForce9600和GTX570匹配時(shí)間對比

Fig.8 Comparison of execution time on GPU、GTX 570 and GeForce 9600

5 結(jié)束語

本文提出了一個(gè)改進(jìn)的AC算法，并將其移植到兩個(gè)不同的GPU平臺上。通過實(shí)驗(yàn)發(fā)現(xiàn)，不同的GPU平臺對算法的性能有較大的影響，性能高的GPU執(zhí)行算法的效率更高；同時(shí)，無論在等長模式集還是不等長模式集上，改進(jìn)的G-AC算法的效率都遠(yuǎn)遠(yuǎn)高于經(jīng)典的CPU上執(zhí)行的AC算法。這一結(jié)果即可表明，將模式匹配算法移植到GPU上是可行且具有潛力的。

參考文獻(xiàn)：

[1] Navarro G， Raffinot M. Flexible pattern matching in strings： practical on-line search algorithms for texts and biological sequences[M].New York： Cambridge University Press， 2002.

[2] AHO A V， CORASICKk M J. Efficient string matching： an aid to bibliographic search[J]. Communications of the ACM， 1975， 18（6）： 333-340.

[3] NVIDIA. CUDA Best Practices Guide： NVIDIA CUDA C Programming Best Practices Guide CUDA Toolkit 2.3[M]. Santa Clara ： NVIDIA， July 2009：15-25.

[4] VASILIADIS G， ANTONATOS S， POLYCHRONAKIS M.， et al. Gnort： High performance network intrusion detection using graphics processors[C]// LIPPMANN R.， KIRDA E， TRACHTENBERG A. （eds）. RAID 2008. Springer， Heidelberg：LNCS， 2008，5230：116-134.

[5] TURNEO A， VILLA O， CHAVARRIA-MIRANDA D G. Aho-Corasick string matching on shared and distributed-memory parallel architectures[J]. Parallel and Distributed Systems， IEEE Transactions on， 2012， 23（3）： 436-443.

[6] LIU Y， GUO L， LI J， et al. Parallel algorithms for approximate string matching with k mismatches on cuda[C]//Parallel and Distributed Processing Symposium Workshops & PhD Forum （IPDPSW）， 2012 IEEE 26th International. Shanghai ： IEEE， 2012： 2414-2422.

[7] Ponnemkunnath S， Joshi R C. Efficient Regular Expression Pattern Matching on Graphics Processing

Units[M]//Sanjay Ranka，Srinivas Aluru，Rajkumar Buyya：Contemporary Computing. Berlin

Heidelberg： Springer ， 2011：92-101.

[8] LIN C H， LIU C H， CHANG S C. Accelerating regular expression matching using hierarchical parallel machines on GPU[C]//Global Telecommunications Conference （GLOBECOM 2011）， 2011 IEEE. Houston： IEEE， 2011： 1-5.

1 基金項(xiàng)目：國家973重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（2011CB302605）； 國家863高技術(shù)研究發(fā)展計(jì)劃（2011AA010705， 2012AA012502， 2012AA012506）； “十一五”國家科技支撐計(jì)劃（2012BAH37B01）； 國家自然科學(xué)基金。

（11226239，6110018，61173144），CNNICk201211043。

作者簡介：徐東亮（1984-），男，山東威海人，博士研究生，主要研究方向：模式匹配，入侵檢測、信息安全；

張宏莉（1973-），女，吉林榆樹人，博士，教授，博士生導(dǎo)師，主要研究方向：信息內(nèi)容安全、網(wǎng)絡(luò)測量和建模、并行計(jì)算；

姚崇崇（1991-），男，河南駐馬店人，碩士研究生，主要研究方向：字符串匹配、入侵檢測。