一種新型動(dòng)態(tài)可重構(gòu)的正則表達(dá)式匹配引擎設(shè)計(jì)

高陽陽，徐烈偉，俞 劍，許 薇

(1.復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海 201203； 2.上海復(fù)旦微電子集團(tuán)股份有限公司，上海 200433)

正則表達(dá)式匹配是根據(jù)預(yù)定義的特定字符及其組合所構(gòu)成的正則表達(dá)式對(duì)文本字符串進(jìn)行邏輯過濾的一種邏輯操作，在網(wǎng)絡(luò)安全、文本處理、信息檢索以及醫(yī)學(xué)等領(lǐng)域都有著廣泛的應(yīng)用[1].正則表達(dá)式匹配技術(shù)在早期的計(jì)算機(jī)和信息技術(shù)出現(xiàn)時(shí)就已經(jīng)產(chǎn)生[2]，但隨著近年來大數(shù)據(jù)、云計(jì)算以及互聯(lián)網(wǎng)技術(shù)和應(yīng)用的快速發(fā)展，海量的數(shù)據(jù)處理對(duì)文本檢測(cè)和匹配的要求急劇提高，對(duì)正則表達(dá)式匹配的匹配特性、匹配速度以及匹配規(guī)則的動(dòng)態(tài)更新能力等各個(gè)方面都提出了更高的要求和挑戰(zhàn).

正則表達(dá)式匹配算法通常采用有限自動(dòng)機(jī)(Finite Automata machine, FA)來實(shí)現(xiàn)[3]，分為確定性有限自動(dòng)機(jī)(Deterministic Finite Automation, DFA)和非確定性有限自動(dòng)機(jī)(Non-deterministic Finite Automation, NFA).在DFA中[4]，自動(dòng)機(jī)的狀態(tài)跳轉(zhuǎn)是唯一確定的，因此只需要對(duì)字符串進(jìn)行1次遍歷，匹配速度快，但帶來的問題是無法匹配具有回溯特征的正則表達(dá)式，導(dǎo)致其匹配特性較少.同時(shí)，基于DFA的匹配算法在每個(gè)狀態(tài)跳轉(zhuǎn)時(shí)消耗1個(gè)待匹配的輸入字符，其計(jì)算處理的空間復(fù)雜度隨著輸入字符的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)，因此基于DFA的匹配算法普遍存在預(yù)處理時(shí)間過長(zhǎng)的問題，無法滿足大規(guī)模數(shù)據(jù)處理和需要?jiǎng)討B(tài)更新匹配規(guī)則的計(jì)算場(chǎng)景和計(jì)算需求.

基于NFA的匹配算法中，每輸入1個(gè)字符會(huì)同時(shí)產(chǎn)生多個(gè)后繼狀態(tài)，允許對(duì)正則表達(dá)式進(jìn)行回溯操作，具有更為豐富的匹配特性.并且，NFA的空間復(fù)雜度隨輸入字符的個(gè)數(shù)呈線性增長(zhǎng)，可以有效解決基于DFA的匹配算法所存在的預(yù)處理時(shí)間過長(zhǎng)的問題，因此目前主流的正則表達(dá)式匹配引擎(如Perl、Python的re模塊以及Java的regex庫等)均基于NFA進(jìn)行設(shè)計(jì).然而，NFA狀態(tài)跳轉(zhuǎn)的不確定性也使得計(jì)算的時(shí)間復(fù)雜度較高，導(dǎo)致其匹配速度較慢[5-6].因此，更多圍繞NFA的最新研究都著眼于利用硬件的并行化工作特點(diǎn)來提高正則表達(dá)式的匹配速度，主要有ASIC和FPGA 2種實(shí)現(xiàn)方式.ASIC[7-8]實(shí)現(xiàn)方式的計(jì)算速度高但靈活性差，其匹配規(guī)則無法自動(dòng)更新，同時(shí)，多種不同類型的復(fù)雜的正則表達(dá)式也無法通過預(yù)設(shè)計(jì)電路的方式來實(shí)現(xiàn)快速匹配，導(dǎo)致有限的硬件資源無法覆蓋更多的匹配特性和提供更高的匹配能力.相比于ASIC實(shí)現(xiàn)方式，F(xiàn)PGA實(shí)現(xiàn)方式具有電路可編程的特性，其硬件電路的計(jì)算功能可以像軟件一樣通過編程來修改，可以靈活地分配硬件資源，增大匹配特性，同時(shí)可以減少更新匹配規(guī)則時(shí)的重配置時(shí)間，使得基于FPGA實(shí)現(xiàn)的正則表達(dá)式快速匹配成為目前主流的技術(shù)解決方案.

圍繞基于FPGA的正則表達(dá)式快速匹配和計(jì)算加速，賀偉[9]提出了一種基于FPGA的動(dòng)態(tài)元件級(jí)可重構(gòu)的正則表達(dá)式匹配算法，通過對(duì)FPGA中可編程SRAM的配置來實(shí)現(xiàn)匹配電路的動(dòng)態(tài)更新，提高正則表達(dá)式匹配的預(yù)處理速度.算法將不同元字符所對(duì)應(yīng)的NFA映射成硬件電路，采用多路選擇器將這些電路組合成正則表達(dá)式匹配中的單元電路，如圖1所示.

圖1 正則表達(dá)式匹配的單元電路Fig.1 Unit circuit of regular expression matching

圖1中，虛線框內(nèi)是單字符匹配的基本電路，通過對(duì)多路選擇器的選擇信號(hào)進(jìn)行配置，可以實(shí)現(xiàn)正則表達(dá)式中的幾類基本元字符(“*”、“+”、“?”、“{}”和“|”)對(duì)單字符子表達(dá)式的匹配功能.例如，當(dāng)選擇信號(hào)1和2均置為“01”時(shí)，電路實(shí)現(xiàn)的功能為“r*”；當(dāng)選擇信號(hào)1和2分別置為“01”和“10”時(shí)，電路實(shí)現(xiàn)的功能為“r{n}”，其中，r是字符比較器中預(yù)存的字符，n是計(jì)數(shù)器中預(yù)存的數(shù)值.算法將這種可重構(gòu)的單元電路級(jí)聯(lián)起來，通過改變配置信息，可以實(shí)現(xiàn)多種形式的正則表達(dá)式匹配.但在實(shí)際工作場(chǎng)景中，正則表達(dá)式所包含的元字符種類及組合方式非常多，無法一一枚舉，因此這種可重構(gòu)設(shè)計(jì)所能覆蓋的匹配特性較少，具有很大的局限性.

為此，Zsolt等[10]提出了基于CPU-FPGA架構(gòu)的正則表達(dá)式匹配算法，首先將連續(xù)的普通字符以及范圍匹配(例如“[a—z]”)的表達(dá)式視作1個(gè)字符串，采用單個(gè)標(biāo)記(token)來表征字符串(例如，將正則表達(dá)式“(abc)|(def)”表征成“x|y”)的方法將正則表達(dá)式化簡(jiǎn)并分割成若干個(gè)較短的單個(gè)標(biāo)記，再將化簡(jiǎn)后的正則表達(dá)式構(gòu)造成NFA，利用FPGA硬件電路對(duì)這些單個(gè)標(biāo)記所代表的子表達(dá)式進(jìn)行快速的并行匹配.采用這種方式，可以在擴(kuò)展匹配特性的同時(shí)提高匹配速度.Vaibhav[11]則提出了另一種軟硬件協(xié)同計(jì)算的硬件加速算法，以元字符(例如“*”、“+”、“?”、“{}”、“|”等)為標(biāo)記將正則表達(dá)式分割成多個(gè)匹配組件(component)，并用“前導(dǎo)信號(hào)(precedence vector，指激活當(dāng)前狀態(tài)的狀態(tài)信號(hào))”和“重復(fù)量詞(repetition bound，指組件重復(fù)的次數(shù))”2個(gè)參數(shù)表征每個(gè)匹配組件.以正則表達(dá)式“ab{2,4}c”為例，“a”、“b{2,4}”、“c”為分割得到的匹配組件，匹配組件“b{2,4}”的前導(dǎo)信號(hào)為“a”，重復(fù)量詞為[2,4]；匹配組件“c”的前導(dǎo)信號(hào)為“b”，重復(fù)量詞為[1,1]).算法繼而對(duì)匹配組件進(jìn)行參數(shù)提取，通過改變這些參數(shù)，實(shí)現(xiàn)對(duì)不同形式正則表達(dá)式的匹配.采用這種元字符分割、參數(shù)提取以及動(dòng)態(tài)重構(gòu)匹配規(guī)則的方法，可以進(jìn)一步擴(kuò)展匹配特性，但仍然無法匹配對(duì)多字符子表達(dá)式進(jìn)行“*”、“+”操作的正則表達(dá)式，也無法匹配出現(xiàn)無界重復(fù)量詞(如{n,})的正則表達(dá)式.

上述采用FPGA來實(shí)現(xiàn)的正則表達(dá)式匹配算法[9-11]，通過對(duì)FPGA的動(dòng)態(tài)可重構(gòu)特性的有效利用，提高了正則表達(dá)式的匹配特性和匹配速度，同時(shí)縮短了構(gòu)造正則表達(dá)式匹配規(guī)則的預(yù)處理時(shí)間，但是其匹配速度受限于FPGA的最高工作頻率，仍然無法更好地滿足大規(guī)模數(shù)據(jù)處理的加速計(jì)算要求.為了進(jìn)一步提高匹配速度，同時(shí)進(jìn)一步增加可覆蓋到的匹配特性，本文提出了一種動(dòng)態(tài)可重構(gòu)的正則表達(dá)式匹配算法，采用參數(shù)化一致性表達(dá)方法來以豐富算法的匹配特性和提高正則表達(dá)式的動(dòng)態(tài)匹配能力.同時(shí)，采用專用并行計(jì)算電路與FPGA電路的混合計(jì)算框架和軟硬件協(xié)同的工作模式，提出和設(shè)計(jì)了一種新型動(dòng)態(tài)可重構(gòu)計(jì)算硬件，不僅可以最大化地利用FPGA電路的可重構(gòu)特性完成正則表達(dá)式的動(dòng)態(tài)更新來提高正則表達(dá)式匹配的預(yù)處理速度，專用并行計(jì)算電路的使用更大大提高了并行匹配計(jì)算的匹配速度.

1 參數(shù)化一致性表達(dá)的匹配算法

1.1 正則表達(dá)式的NFA構(gòu)造和一致性表達(dá)

基于NFA的正則表達(dá)式匹配，首先需要完成的是NFA的構(gòu)造.經(jīng)典的NFA構(gòu)造算法[12]，以遞歸方式將正則表達(dá)式劃分為若干子表達(dá)式，得到每個(gè)子表達(dá)式所對(duì)應(yīng)的子NFA，再根據(jù)子表達(dá)式之間的運(yùn)算關(guān)系構(gòu)造完整的NFA.圖2為4種基本子表達(dá)式的NFA構(gòu)造示例，其中： m1和m2分別表示2個(gè)狀態(tài)機(jī);ε表示空串匹配;s為初始狀態(tài);f為接受狀態(tài).

圖2 正則表達(dá)式的NFA構(gòu)造示例Fig.2 NFA construction example of regular expression

對(duì)于長(zhǎng)度為n的正則表達(dá)式，NFA的空間復(fù)雜度為O(n)，正則表達(dá)式可以較為快速地轉(zhuǎn)化為NFA，其預(yù)處理時(shí)間較短.但另一方面，NFA中可能同時(shí)存在多個(gè)激活狀態(tài)(例如，圖2(c)中，NFA處于初始狀態(tài)時(shí)，狀態(tài)s1和狀態(tài)s2均處于激活狀態(tài))，每輸入1個(gè)字符會(huì)產(chǎn)生多個(gè)可能的后繼狀態(tài).當(dāng)NFA中所有狀態(tài)均處于激活狀態(tài)時(shí)，任意一個(gè)狀態(tài)都有跳轉(zhuǎn)到其他所有狀態(tài)的可能，在這種最壞情況下，串行匹配的時(shí)間復(fù)雜度為O(n2)，匹配速度較慢.

有鑒于此，最新研究均采用硬件來并行地加速處理NFA中的多個(gè)激活狀態(tài)，提高正則表達(dá)式的匹配速度.圖3所示為對(duì)應(yīng)上述4種基本子表達(dá)式的邏輯電路[13]，其中： N1和N2分別表示2個(gè)單字符匹配模塊；i表示模塊輸入(該模塊處于激活狀態(tài)時(shí)，輸入高電平)；o表示匹配結(jié)果.

圖3 4種正則表達(dá)式匹配的硬件實(shí)現(xiàn)Fig.3 Four types of hardware implementation for regular expression matching

在圖3(a)中，當(dāng)輸入字符和預(yù)先存儲(chǔ)在比較器中的單字符子表達(dá)式相同時(shí)，比較結(jié)果為1，表示匹配成功.對(duì)比圖2(c)和圖3(c)可以看到，當(dāng)同時(shí)存在多個(gè)激活狀態(tài)時(shí)，可以通過將單字符匹配電路并聯(lián)的方式，并行處理正則表達(dá)式中的所有激活狀態(tài)，提高匹配速度.但是不同類型的元字符及其組合所構(gòu)成的正則表達(dá)式對(duì)應(yīng)的是不同的匹配計(jì)算模型，受到硬件計(jì)算資源的限制，無法將各種類型的匹配計(jì)算模型都一一映射成硬件電路，從而限制了算法所能覆蓋到的匹配特性.對(duì)此，本文提出一種參數(shù)化一致性表達(dá)方法，通過將各種類型的正則表達(dá)式統(tǒng)一成包含有限匹配類型的同一種匹配規(guī)則，通過固化匹配計(jì)算的架構(gòu)及可并行化的底層計(jì)算模型，來實(shí)現(xiàn)對(duì)各種不同類型正則表達(dá)式的通用的匹配計(jì)算.

首先，是將正則表達(dá)式的匹配類型合并成盡可能少的種類，并對(duì)其實(shí)現(xiàn)一致性的表達(dá)，以便算法后續(xù)工作可以從中提取出能有效表征所有匹配計(jì)算類型的表達(dá)式參數(shù).在進(jìn)行匹配計(jì)算時(shí)，可以將一些較為復(fù)雜的元字符，展開成最基本的元字符(例如“*”、“+”、“?”、“|”)，以減少元字符的種類(例如①和②).此外，對(duì)于不會(huì)對(duì)匹配計(jì)算結(jié)果產(chǎn)生影響的元字符，則進(jìn)行合并(例如③和④).

① 范圍匹配

范圍匹配是指對(duì)指定范圍內(nèi)的任意字符進(jìn)行匹配，例如“[a—z]”表示匹配“a”到“z”范圍內(nèi)的任意字符.由于正則表達(dá)式中對(duì)范圍的匹配種類繁多，且對(duì)應(yīng)不同的計(jì)算方法，為了使各種類型的范圍匹配都可以用統(tǒng)一的計(jì)算模型加以實(shí)現(xiàn)，本文在算法設(shè)計(jì)中引入了1種新的元字符“&”和4種比較符號(hào)“=”、“≥”、“≤”、“≠”，以使類似于“[a—z]”這樣的范圍匹配表達(dá)式可以被展開成“(≥a)&(≤z)”的形式(其中“&”表示“同時(shí)滿足左右兩邊的條件”)，由此將范圍匹配轉(zhuǎn)化成由“&”、“|”、比較符號(hào)以及普通字符所構(gòu)成的最小化的正則表達(dá)式，在等價(jià)的前提下簡(jiǎn)化了范圍匹配中可能存在的元字符種類.表1所示為3種典型的范圍匹配的轉(zhuǎn)換方式，其中對(duì)于“W”，其轉(zhuǎn)換后的表達(dá)式中還存在比較符號(hào)“>”和“<”，為了減少比較符號(hào)的種類，可以進(jìn)一步結(jié)合被其比較的普通字符，將“>”和“<”分別轉(zhuǎn)換為“≥”和“≤”，例如“>z”可以轉(zhuǎn)換為“≥{”(在ASCII碼表中，字符“{”在字符“z”的后1位).

② 重復(fù)匹配

重復(fù)匹配是指對(duì)某個(gè)普通字符或子表達(dá)式進(jìn)行多次連續(xù)的匹配，例如，表達(dá)式“a{3,5}”表示連續(xù)匹配“a”3次、4次或者5次，因?yàn)樵址?”表示匹配字符0次或1次，因此可以將上述表達(dá)式展開成“aaaa?a?”，這樣正則表達(dá)式中的每一個(gè)普通字符對(duì)應(yīng)1次匹配操作，僅用基本元字符“?”、“+”就可以完全表征任意形式的重復(fù)匹配.表2所示為3種典型的重復(fù)匹配的轉(zhuǎn)換方式.

表1 范圍匹配的轉(zhuǎn)換方式

表2 重復(fù)匹配的轉(zhuǎn)換方式

③ 非貪婪匹配

非貪婪匹配(例如“*?”、“+?”、“??”等)指匹配盡可能少的字符，與之相對(duì)應(yīng)的是貪婪匹配(“*”、“+”、“?”等)，指匹配盡可能多的字符.例如分別用表達(dá)式“ab+?”和“ab+”匹配字符串“abbb”，均會(huì)匹配成功，但“ab+?”匹配到的字符串是“ab”，而“ab+”匹配到的字符串是“abbb”.在并行匹配時(shí)，當(dāng)“a”匹配成功后，每匹配上1個(gè)“b”，都會(huì)顯示匹配成功，即無論使用哪種表達(dá)式對(duì)該字符串進(jìn)行匹配，均會(huì)連續(xù)顯示3次匹配成功.因此非貪婪匹配和貪婪匹配在匹配的過程和結(jié)果上都是等價(jià)的，而貪婪匹配中的元字符是最原始也是最基本的元字符，因此，在不影響匹配結(jié)果的前提下，本文在匹配規(guī)則中將非貪婪匹配均轉(zhuǎn)化成貪婪匹配，表3(見第710頁)所示為2種典型的非貪婪匹配的轉(zhuǎn)換方式.

④ 零寬斷言

零寬斷言用于匹配在這個(gè)位置之前或之后的字符表達(dá)式.例如正則表達(dá)式“a(?=b)”匹配在字符“b”這個(gè)位置之前的字符“a”，用該表達(dá)式匹配字符串“abac”時(shí)，只有當(dāng)“a”字符后緊接著“b”字符，才表示匹配成功，即該表達(dá)式僅可以匹配成功1次(字符串中的第1個(gè)“a”).因此，正則表達(dá)式“a(?=b)”和“ab”在匹配的過程和結(jié)果上都是等價(jià)的，可以將位置匹配簡(jiǎn)化成普通的字符匹配.表4(見第710頁)所示為2種典型的零寬斷言的轉(zhuǎn)換方式.

通過上述的范圍匹配、重復(fù)匹配、非貪婪匹配以及零寬斷言4種方式的轉(zhuǎn)換，本文將眾多類型的正則表達(dá)式元字符最終合并成5類：“*”、“+”、“?”、“|”和“&”.由此，轉(zhuǎn)換后的正則表達(dá)式可以表征成由普通字符(用ASCII碼表示的字符)、元字符(“*”、“+”、“?”、“|”和“&”)以及比較符號(hào)(“=”、“≥”、“≤”、“≠”)所構(gòu)成的更為統(tǒng)一且簡(jiǎn)單的表達(dá)形式，減少了正則表達(dá)式的匹配類型，同時(shí)可以方便地采用盡可能少的參數(shù)來進(jìn)一步加以抽象表征.

表3 非貪婪匹配的轉(zhuǎn)換方式

表4 零寬斷言的轉(zhuǎn)換方式

1.2 參數(shù)的提取和轉(zhuǎn)換

完成了一致性表達(dá)之后，需要進(jìn)一步提取出可以完全表征各類正則表達(dá)式的參數(shù)，并將其轉(zhuǎn)換成匹配計(jì)算時(shí)可以識(shí)別及更改的配置信息.其中，最主要的工作是構(gòu)造正則表達(dá)式所對(duì)應(yīng)的NFA，并確定NFA中每個(gè)狀態(tài)所對(duì)應(yīng)的轉(zhuǎn)移函數(shù).由圖2可知，轉(zhuǎn)移函數(shù)分為字符匹配和空串匹配.字符匹配由輸入字符和正則表達(dá)式中普通字符的比較結(jié)果決定，用來匹配正則表達(dá)式中的單個(gè)普通字符，在此，本文引入?yún)?shù)“比較信號(hào)”來表征4種情況的比較關(guān)系，分別是“=”、“≥”、“≤”、“≠”；空串匹配由正則表達(dá)式中的元字符類型決定，用來將匹配單字符子表達(dá)式的子NFA組合成完整的NFA，在此，本文引入?yún)?shù)“使能信號(hào)”來表征字符匹配后的狀態(tài)跳轉(zhuǎn)關(guān)系，正則表達(dá)式中的每個(gè)普通字符都有其對(duì)應(yīng)的使能信號(hào)(包含一個(gè)或多個(gè)字符)，當(dāng)NFA匹配上某字符所對(duì)應(yīng)的使能信號(hào)時(shí)，狀態(tài)就會(huì)發(fā)生跳轉(zhuǎn)來進(jìn)行該字符的匹配.例如圖2(b)中，當(dāng)字符“r1”匹配成功后，NFA處于f1狀態(tài)，并通過空串匹配跳轉(zhuǎn)到f2狀態(tài)，開始對(duì)字符“r2”進(jìn)行匹配，因此字符“r2”的使能信號(hào)是“r1”.

在硬件實(shí)現(xiàn)NFA時(shí)，由圖3可知，每個(gè)單字符匹配對(duì)應(yīng)一個(gè)比較器，可以將這些比較器的輸入和輸出根據(jù)使能信號(hào)連接起來(一個(gè)單字符匹配對(duì)應(yīng)的比較器的輸入是其使能信號(hào)對(duì)應(yīng)的比較器的輸出)，來實(shí)現(xiàn)完整的正則表達(dá)式匹配.同時(shí)，針對(duì)本文提出的元字符“&”，則通過參數(shù)“級(jí)聯(lián)信號(hào)”的引入來表征用“&”連接字符時(shí)的字符間轉(zhuǎn)移函數(shù).例如正則表達(dá)式“(≥x)&(≤z)”(原表達(dá)式為“[x—z]”)包含2個(gè)普通字符“x”、“z”，作為一個(gè)整體，需要將“≥x”的子表達(dá)式NFA的匹配結(jié)果級(jí)聯(lián)到“≤z”的子表達(dá)式NFA，只有待匹配的字符同時(shí)匹配上“≥x”和“≤z”時(shí)，匹配才被認(rèn)為是成功的.其中，正則表達(dá)式的匹配結(jié)果并不是硬件實(shí)現(xiàn)時(shí)最后一個(gè)字符所對(duì)應(yīng)的比較器輸出結(jié)果，而是NFA中結(jié)束狀態(tài)所對(duì)應(yīng)的使能信號(hào)的匹配結(jié)果，例如正則表達(dá)式“a(b|c)”，只要“b”或者“c”中任意一個(gè)字符匹配上，即表示該正則表達(dá)式匹配成功(“b”和“c”所對(duì)應(yīng)的NFA狀態(tài)均可以通過空串匹配跳轉(zhuǎn)到結(jié)束狀態(tài)，即結(jié)束狀態(tài)的使能信號(hào)為“b”和“c”).因此，正則表達(dá)式可以由： ① 表達(dá)式中的普通字符和每個(gè)普通字符對(duì)應(yīng)的特性參數(shù)(比較信號(hào)、使能信號(hào)和級(jí)聯(lián)信號(hào))；② 最終狀態(tài)所對(duì)應(yīng)的使能信號(hào)所表征，匹配結(jié)果為最終狀態(tài)對(duì)應(yīng)的使能信號(hào)的匹配輸出結(jié)果.

由于提取特性參數(shù)的目的是將正則表達(dá)式的特性參數(shù)映射成可實(shí)現(xiàn)的硬件電路中的配置信息，因此需要結(jié)合硬件電路的可實(shí)現(xiàn)性來進(jìn)一步處理這些特性參數(shù).本文提出2個(gè)定義，定義①： 對(duì)于預(yù)處理后的正則表達(dá)式，按從左到右的順序?qū)φ齽t表達(dá)式中的普通字符進(jìn)行排序，稱在某字符左邊的字符，是該字符的前序字符；定義②： 將來自前序字符的使能信號(hào)稱為前驅(qū)使能信號(hào)，來自本身及后序字符的使能信

表5 “a(bc)*[x—z]”中的特性參數(shù)

號(hào)稱為后驅(qū)使能信號(hào).由于算法在配置計(jì)算電路時(shí)，會(huì)按照普通字符的前后順序依次分配單字符匹配電路，前驅(qū)使能和后驅(qū)使能所分別對(duì)應(yīng)的硬件結(jié)構(gòu)是不同的，因此，本文在算法設(shè)計(jì)中將字符的匹配使能特性再細(xì)分為3類，分別是前驅(qū)使能特性、后驅(qū)使能特性、使能選擇信號(hào)，分別進(jìn)行參數(shù)提取.

以正則表達(dá)式“a(bc)*[x—z]”為例，表5為從該正則表達(dá)式中提取出的特性參數(shù).

表6 前驅(qū)使能信號(hào)對(duì)應(yīng)的配置信息

表7 “a(bc)*[x—z]”對(duì)應(yīng)的配置信息

提取出這些特性參數(shù)后，還需要將其轉(zhuǎn)化為匹配計(jì)算時(shí)可以識(shí)別及更改的配置信息.本文采用二進(jìn)制的方法來表征這些特性參數(shù)，例如用二進(jìn)制數(shù)“00”來表征比較信號(hào)中的“=”、“01”表征“≥”、“10”表征“≤”、“11”表征“≠”.由于前驅(qū)和后驅(qū)使能信號(hào)需要在多個(gè)單字符匹配模塊間通過傳遞信號(hào)來實(shí)現(xiàn)，因此提出一種表6所示的參數(shù)轉(zhuǎn)換方式.

使能信號(hào)可能出現(xiàn)多級(jí)傳遞的情況(例如正則表達(dá)式“a(bc)*[x—z]”中的“a”需要通過“b”和“c”傳遞給“x”)，在傳遞時(shí)配置信息會(huì)發(fā)生沖突，此時(shí)需要配置多條傳遞線來保證信號(hào)的正常傳遞.以正則表達(dá)式“a(bc)*[x—z]”為例，表7給出了表5中的參數(shù)對(duì)應(yīng)的配置信息.其中，“c”的前驅(qū)使能是“b”，需要將“b”的前驅(qū)使能傳遞線配置成“10”；“x”的前驅(qū)使能是“a|c”，需要將“a”的傳遞線配置成“10”、“b”的傳遞線配置成“01”、“c”的傳遞線配置成“11”才能完成信號(hào)傳遞.此時(shí)，“b”的傳遞線配置發(fā)生了沖突，需要用2條傳遞線分別傳遞“c”和“x”使能信息(對(duì)應(yīng)于表7中的“線1”和“線2”選項(xiàng))，并判斷“c”和“x”的使能信號(hào)所分別對(duì)應(yīng)的傳遞線(對(duì)應(yīng)于表7中的“選擇”選項(xiàng))，由此實(shí)現(xiàn)對(duì)使能傳遞線的配置.

由表7的配置信息可以看到，字符“b”的前驅(qū)使能在“a”中進(jìn)行的配置(“a”的前驅(qū)使能傳遞線1被配置成“10”，表示將本級(jí)的匹配信號(hào)“a”傳遞給下一級(jí)“b”)，即當(dāng)前字符的前驅(qū)使能在上一個(gè)字符中完成配置.由于正則表達(dá)式的最終匹配結(jié)果是最終狀態(tài)所對(duì)應(yīng)的使能信號(hào)的輸出值，因此，將最后一個(gè)字符“z”的前驅(qū)使能傳遞線配置為“10”，“z”中前驅(qū)使能信號(hào)的輸出值即代表最終的匹配結(jié)果.上述配置方法，通過若干條使能傳遞線將單字符匹配模塊級(jí)聯(lián)起來，實(shí)現(xiàn)了對(duì)完整正則表達(dá)式的匹配.

由此，通過這種參數(shù)化的提取和轉(zhuǎn)換，任意經(jīng)過一致性表達(dá)處理后的正則表達(dá)式，均可以用以上二進(jìn)制信息完全表征，在進(jìn)行匹配計(jì)算時(shí)，可以由若干相同結(jié)構(gòu)的單字符匹配模塊級(jí)聯(lián)而成.并且，通過將這些完全表征正則表達(dá)式的參數(shù)集合轉(zhuǎn)化為可以進(jìn)行動(dòng)態(tài)重構(gòu)的配置信息，只需要改變這些配置信息，無需修改硬件電路結(jié)構(gòu)，即可實(shí)現(xiàn)不同正則表達(dá)式的匹配.上述本文所設(shè)計(jì)和實(shí)現(xiàn)的這種參數(shù)化一致性的表達(dá)算法，在擴(kuò)展了匹配特性的同時(shí)降低了硬件電路的復(fù)雜度，提高了電路的工作效率.表8為文獻(xiàn)[9]和[11]中正則表達(dá)式匹配特性和本文的比較，可以看到，本文這種參數(shù)化一致性表達(dá)算法相比文獻(xiàn)[9]和[11]具有更寬泛的匹配特性.

表8 正則表達(dá)式匹配算法的匹配特性比較

1.3 電路映射

由1.2節(jié)可知，任意單字符子表達(dá)式的匹配功能均可由比較信號(hào)、使能信號(hào)和級(jí)聯(lián)信號(hào)這3種參數(shù)完全表征，其匹配計(jì)算模型由相對(duì)應(yīng)的3個(gè)部分構(gòu)成： ① 輸入待匹配的字符和表征普通字符的ASCII碼，根據(jù)比較信號(hào)，輸出比較結(jié)果；② 根據(jù)使能信號(hào)，輸入來自其他單字符子表達(dá)式的匹配結(jié)果，輸出使能結(jié)果；③ 輸入比較結(jié)果和使能結(jié)果，根據(jù)級(jí)聯(lián)信號(hào)，確定本級(jí)單字符子表達(dá)式的最終匹配結(jié)果.通過前驅(qū)和后驅(qū)使能傳遞線將單字符子表達(dá)式級(jí)聯(lián)起來，在進(jìn)行正則表達(dá)式匹配時(shí)，待匹配的輸入字符并行地進(jìn)行上述單字符匹配的計(jì)算，最終的匹配結(jié)果是最后一級(jí)單字符匹配模塊的前驅(qū)使能傳遞線的輸出結(jié)果.以正則表達(dá)式“a(bc)*[x—z]”為例，若將NFA直接映射成硬件電路，每一個(gè)單字符子表達(dá)式對(duì)應(yīng)的電路都是不同的，而通過1.1節(jié)和1.2節(jié)中對(duì)正則表達(dá)式的參數(shù)化一致性表達(dá)，固化了匹配計(jì)算的架構(gòu)及單字符匹配的底層計(jì)算模型，并且正則表達(dá)式可以由計(jì)算模型中的“表征普通字符的ASCII碼”、“比較信號(hào)”、“使能信號(hào)”、“級(jí)聯(lián)信號(hào)”等參數(shù)完全表征，將這些參數(shù)集合轉(zhuǎn)換為配置信息，只需要更改上述配置，即可實(shí)現(xiàn)各類正則表達(dá)式的匹配.

由此，本文所提出的參數(shù)化一致性表達(dá)的正則表達(dá)式匹配算法的設(shè)計(jì)框架如圖4所示.

圖4 正則表達(dá)式匹配算法的框架示意圖Fig.4 Schematic diagram of the regular expression matching algorithm

圖4中，算法通過對(duì)正則表達(dá)式的一致性表達(dá)，把各種類型的正則表達(dá)式轉(zhuǎn)換成由普通字符和特定元字符(“*”、“+”、“?”、“|”和“&”)等構(gòu)成的統(tǒng)一形式的正則表達(dá)式，再從這種一致性表達(dá)的正則表達(dá)式規(guī)則中抽象和提取出可以完全表征各類正則表達(dá)式的參數(shù)集合，并轉(zhuǎn)化為配置信息，然后將這種可以用參數(shù)完全表征的正則表達(dá)式匹配規(guī)則映射成固定計(jì)算模型的硬件電路，并行地進(jìn)行正則表達(dá)式匹配.對(duì)于不同類型的正則表達(dá)式，可以通過改變硬件電路的配置信息來實(shí)現(xiàn)正則表達(dá)式的快速匹配.

2 動(dòng)態(tài)可重構(gòu)匹配加速引擎的實(shí)現(xiàn)

2.1 軟硬件協(xié)同工作架構(gòu)

根據(jù)1.3節(jié)敘述，本文將正則表達(dá)式的匹配任務(wù)劃分成如下2個(gè)部分： ① 軟件實(shí)現(xiàn)的編譯模塊；② 硬件實(shí)現(xiàn)的配置和計(jì)算模塊.圖5所示為實(shí)現(xiàn)該正則表達(dá)式匹配算法的架構(gòu).

圖5 算法實(shí)現(xiàn)的架構(gòu)Fig.5 Algorithm implementation architecture

首先，軟件編譯模塊利用軟件靈活易修改的特點(diǎn)來實(shí)現(xiàn)對(duì)正則表達(dá)式的參數(shù)化一致性表達(dá)，通過軟件實(shí)現(xiàn)的預(yù)處理模塊對(duì)各種類型的正則表達(dá)式進(jìn)行一致性表達(dá)處理，將其轉(zhuǎn)化為統(tǒng)一的形式，再從中提取出可以完全表征這類正則表達(dá)式的參數(shù)集合，將統(tǒng)一形式的正則表達(dá)式匹配規(guī)則映射成可并行執(zhí)行匹配任務(wù)的子表達(dá)式，并將參數(shù)集合轉(zhuǎn)化為配置信息.隨后，硬件加速模塊完成對(duì)正則表達(dá)式匹配的快速更新和并行計(jì)算.

為進(jìn)一步達(dá)到硬件計(jì)算加速的效果，本文提出了一種在FPGA中內(nèi)嵌ASIC電路的混合計(jì)算框架，分別實(shí)現(xiàn)匹配規(guī)則的可重構(gòu)配置和匹配計(jì)算的并行計(jì)算加速.其中： FPGA電路根據(jù)軟件編譯獲得的配置信息，負(fù)責(zé)完成對(duì)正則表達(dá)式匹配計(jì)算模型的動(dòng)態(tài)更新；ASIC電路是以單字符匹配(core)電路為基本單元構(gòu)成的并行計(jì)算陣列，通過配置信息將若干個(gè)core電路級(jí)聯(lián)起來構(gòu)成完整的正則表達(dá)式匹配電路，完成正則表達(dá)式的高速并行匹配計(jì)算.這種硬件架構(gòu)在最大化利用FPGA電路的可重構(gòu)特性進(jìn)行正則表達(dá)式更新的同時(shí)，采用專用ASIC電路實(shí)現(xiàn)的并行匹配計(jì)算可以極大地提高匹配計(jì)算的速度.

2.2 動(dòng)態(tài)可重構(gòu)配置電路

圖6 動(dòng)態(tài)重配置模塊的電路結(jié)構(gòu)Fig.6 Dynamic reconfiguration module circuit

本文采用基于FPGA設(shè)計(jì)的動(dòng)態(tài)可重構(gòu)(dynamical reconfigurable programming, drp)電路對(duì)正則表達(dá)式匹配電路進(jìn)行配置，這種動(dòng)態(tài)可重構(gòu)配置電路在更新匹配規(guī)則的同時(shí)仍然能保證電路的動(dòng)態(tài)接續(xù)，當(dāng)完成重配置操作后即可立刻進(jìn)行新的匹配計(jì)算，可以最大程度地減少更新匹配規(guī)則時(shí)所需要的重配置時(shí)間.drp電路由控制模塊和SRAM陣列組成，通過讀寫端口對(duì)SRAM陣列進(jìn)行配置，如圖6所示，讀寫端口的位寬均為16，可以同時(shí)對(duì)16個(gè)SRAM進(jìn)行并行配置.

drp電路的設(shè)計(jì)需要確定其所配置的SRAM數(shù)量.首先，需要確定1個(gè)單字符匹配(core)電路所需要的SRAM數(shù)量.由1.2節(jié)可知，正則表達(dá)式可能需要多條傳遞線來進(jìn)行使能信號(hào)的傳遞，不同的正則表達(dá)式所需要的SRAM數(shù)量是不同的.本文分別從regexlib庫(http：∥regexlib.com/)和snort規(guī)則集(http：∥ snort.org/)中，根據(jù)正則表達(dá)式的幾類常用場(chǎng)景(字符串匹配、郵箱/日期/時(shí)間等合法性檢查、網(wǎng)絡(luò)入侵檢測(cè)等)，隨機(jī)選取了100條正則表達(dá)式來完成對(duì)drp電路和并行計(jì)算電路的設(shè)計(jì)參數(shù)的選擇，選取的目標(biāo)是使其能夠盡量覆蓋所有類型的元字符種類.根據(jù)1.2節(jié)中所述的配置方法，分別提取正則表達(dá)式中每個(gè)普通字符對(duì)應(yīng)的使能信號(hào)，并將其轉(zhuǎn)化為二進(jìn)制的配置信息，選取的實(shí)驗(yàn)結(jié)果表明： 這100條正則表達(dá)式均可以通過最多4條前驅(qū)使能傳遞線和3條后驅(qū)使能傳遞線來完成匹配計(jì)算.因此，權(quán)衡硬件的資源消耗和表達(dá)式的常用匹配場(chǎng)景，本文采用了4條前驅(qū)使能傳遞線和4條后驅(qū)使能傳遞線來進(jìn)行core電路間的使能信號(hào)傳遞(即本文無法匹配需要超過4條前驅(qū)或者后驅(qū)使能傳遞線的正則表達(dá)式).綜上，1個(gè)core電路需要33個(gè)SRAM進(jìn)行配置(包括8位ASCII碼、10位前驅(qū)使能信號(hào)、10位后驅(qū)使能信號(hào)、2位使能選擇信號(hào)、2位比較信號(hào)和1位級(jí)聯(lián)信號(hào)).由此，對(duì)于1個(gè)長(zhǎng)度為n的正則表達(dá)式(n為所包含的普通字符的個(gè)數(shù))，共需要33×n位二進(jìn)制數(shù)來對(duì)其進(jìn)行完全的表征.

其次，還需要確定1個(gè)drp電路對(duì)多少個(gè)core電路進(jìn)行配置.統(tǒng)計(jì)計(jì)算上述隨機(jī)選取的正則表達(dá)式匹配所需要的core電路的個(gè)數(shù)，統(tǒng)計(jì)結(jié)果顯示，87%的表達(dá)式所需個(gè)數(shù)低于64.因此，綜合考慮匹配速度(硬件中包含越多的core電路，匹配速度越快)、預(yù)處理速度(每個(gè)drp電路控制越少的core電路，預(yù)處理速度越快)以及版圖的面積限制，本文采用了1個(gè)drp電路對(duì)64個(gè)core電路進(jìn)行參數(shù)配置的設(shè)計(jì).根據(jù)這種設(shè)計(jì)，當(dāng)正則表達(dá)式長(zhǎng)度小于(或等于)64時(shí)，只需要1個(gè)drp電路工作即可完成配置更新；當(dāng)正則表達(dá)式長(zhǎng)度大于64時(shí)，需要將更多的core電路級(jí)聯(lián)，并通過多個(gè)drp電路進(jìn)行配置以實(shí)現(xiàn)匹配計(jì)算.

綜上所述，對(duì)于64位長(zhǎng)度的正則表達(dá)式，需要64×33=2112個(gè)SRAM對(duì)其進(jìn)行動(dòng)態(tài)可重構(gòu)配置，考慮到drp的端口位寬和SRAM陣列在FPGA中的布局布線，最終所設(shè)計(jì)的drp電路中共包含64×40=2560個(gè)SRAM.采用這種設(shè)計(jì)，在端口位寬為16、且若干個(gè)drp電路可以并行工作的情況下，任意長(zhǎng)度的正則表達(dá)式的配置均可以在2560/16=160個(gè)時(shí)鐘周期內(nèi)完成，平均每個(gè)core電路可以在160/64=2.5個(gè)時(shí)鐘周期內(nèi)完成計(jì)算.

2.3 并行計(jì)算電路

相比ASIC電路，F(xiàn)PGA的LUT電路結(jié)構(gòu)在實(shí)現(xiàn)相同的正則表達(dá)式匹配電路時(shí)，會(huì)需要消耗更多的邏輯電路資源以及更多的布線資源，時(shí)鐘頻率也會(huì)嚴(yán)重受限于其本身的最高工作頻率.因此，對(duì)于正則表達(dá)式的并行匹配計(jì)算，本文采用了專用ASIC電路來加以實(shí)現(xiàn).根據(jù)1.3節(jié)中的計(jì)算模型，首先搭建單字符匹配電路，如圖7所示.

圖7 單字符匹配模塊的結(jié)構(gòu)框圖Fig.7 Block diagram of the single character matching module

core電路主要由4個(gè)部分構(gòu)成：

1) 比較模塊.比較器的2個(gè)輸入分別是待匹配的字符和表征普通字符的ASCII碼，根據(jù)比較信號(hào)選擇需要的比較結(jié)果；

2) 使能模塊.該模塊的功能是根據(jù)使能選擇信號(hào)決定該電路所需的信號(hào)類型(前驅(qū)使能信號(hào)或后驅(qū)使能信號(hào))，模塊還包含2個(gè)子模塊： 前驅(qū)使能模塊和后驅(qū)使能模塊，分別進(jìn)行其所對(duì)應(yīng)的前驅(qū)和后驅(qū)使能信號(hào)的傳遞；

3) 級(jí)聯(lián)模塊.該模塊的功能是根據(jù)級(jí)聯(lián)信號(hào)決定當(dāng)前電路的匹配結(jié)果是否和前一級(jí)電路的匹配結(jié)果有關(guān)，當(dāng)前電路最終的匹配結(jié)果由該模塊輸出；

4) 時(shí)序模塊.通過D觸發(fā)器進(jìn)行電路流水線的設(shè)計(jì)，每個(gè)時(shí)鐘周期完成對(duì)1個(gè)輸入字符的處理.

針對(duì)使能模塊中的前驅(qū)和后驅(qū)使能信號(hào)的傳遞，本文提出和設(shè)計(jì)了一種由多路選擇器(MUX)和或門構(gòu)成的菊花鏈(daisy-chaining)結(jié)構(gòu)，采用這種設(shè)計(jì)，前驅(qū)和后驅(qū)信號(hào)可以在任意數(shù)量的core電路之間進(jìn)行傳遞.其中，前驅(qū)使能菊花鏈將core電路從前向后進(jìn)行級(jí)聯(lián)，后驅(qū)使能菊花鏈將core電路從后向前進(jìn)行級(jí)聯(lián).以前驅(qū)使能菊花鏈為例，2條菊花鏈的電路結(jié)構(gòu)如圖8所示.

圖8 前驅(qū)使能菊花鏈結(jié)構(gòu)圖Fig.8 Structure diagram of precursor enable daisy-chaining

圖8中，菊花鏈的輸入是級(jí)聯(lián)模塊的輸出信號(hào)(match_next)和使能模塊的輸入信號(hào)(pre)，MUX的選擇端由對(duì)應(yīng)的配置位流決定，輸出信號(hào)(pre_next)同時(shí)也是下一級(jí)core電路中使能模塊的輸入信號(hào)(pre).其中，最后一級(jí)core電路中“pre_next”的信號(hào)值是整個(gè)正則表達(dá)式的匹配結(jié)果.通過這樣的菊花鏈設(shè)計(jì)，計(jì)算電路可以分割為若干相同的匹配單字符子表達(dá)式的core電路，core電路可以級(jí)聯(lián)以匹配任意長(zhǎng)度的正則表達(dá)式，也可以獨(dú)立并行地匹配不同的正則表達(dá)式.相比文獻(xiàn)[10]和文獻(xiàn)[11]中需要若干不同功能的底層模塊(兩者均需要分別對(duì)分割產(chǎn)生的字符串和化簡(jiǎn)后的正則表達(dá)式進(jìn)行匹配計(jì)算)，本文設(shè)計(jì)的并行計(jì)算電路僅通過單一的基本單元即可實(shí)現(xiàn)正則表達(dá)式匹配功能，降低了硬件復(fù)雜度.

圖9 正則表達(dá)式匹配的硬件加速引擎的設(shè)計(jì)示意圖Fig.9 Schematic diagram of hardware acceleration engine for regular expression matching

由2.2節(jié)可知，1個(gè)drp電路可以完成對(duì)64個(gè)core電路的SRAM配置，圖9為由64個(gè)core電路級(jí)聯(lián)而成的正則表達(dá)式匹配加速引擎的設(shè)計(jì)示意圖.其中，每個(gè)方框代表1個(gè)core電路，core電路間的箭頭方向是前驅(qū)使能級(jí)聯(lián)線的方向，后驅(qū)使能級(jí)聯(lián)線的方向與此相反.這種core電路的布局方式，縮短了版圖實(shí)現(xiàn)時(shí)的布線長(zhǎng)度，可以進(jìn)一步提高匹配速度.

對(duì)圖9所示的匹配引擎進(jìn)行仿真驗(yàn)證，采用TSMC 28nm CMOS工藝進(jìn)行專用ASIC電路設(shè)計(jì)，當(dāng)其工作頻率在1GHz時(shí)，可以在1ns 內(nèi)完成對(duì)單個(gè)字符子表達(dá)式的匹配.同樣的匹配計(jì)算模塊設(shè)計(jì)，當(dāng)其實(shí)現(xiàn)在Kintex-7 FPGA上時(shí)，實(shí)驗(yàn)得到的一個(gè)單字符子表達(dá)式匹配完成的時(shí)間為5ns.因此，采用ASIC設(shè)計(jì)實(shí)現(xiàn)的并行計(jì)算模塊，可以為單字符子表達(dá)式的匹配提供5倍以上的計(jì)算加速.

3 測(cè)試結(jié)果

3.1 正則表達(dá)式匹配引擎的物理設(shè)計(jì)

圖10 reb電路的物理版圖Fig.10 Physical layout of the reb circuit

本文設(shè)計(jì)和實(shí)現(xiàn)的動(dòng)態(tài)可重構(gòu)硬件電路采用TSMC 28nm CMOS工藝進(jìn)行流片，完整的動(dòng)態(tài)可重構(gòu)的正則表達(dá)式匹配引擎(Dynamic Reconfigurable Regular expression matching engine, DRR-engine)電路由70個(gè)的圖10所示的正則表達(dá)式匹配單元(regex expression matching block, reb)電路構(gòu)成，每個(gè)reb電路包含1個(gè)基于FPGA實(shí)現(xiàn)的drp電路和4個(gè)采用ASIC方式設(shè)計(jì)實(shí)現(xiàn)的并行匹配計(jì)算(regex)電路，其中，每個(gè)regex電路包含16個(gè)core電路.reb電路的物理版圖的面積是0.07mm×0.25mm=0.0175mm2(regex和drp電路的面積相等).DRR-engine中所有的core電路(共計(jì)64×70=4480個(gè))均通過菊花鏈級(jí)聯(lián)，單獨(dú)的core電路可以根據(jù)SRAM配置級(jí)聯(lián)起來以匹配較長(zhǎng)的正則表達(dá)式，也可以獨(dú)立工作.綜上，本文設(shè)計(jì)實(shí)現(xiàn)的DRR-engine中包含70個(gè)drp模塊和280個(gè)regex模塊，最多可以同時(shí)進(jìn)行280個(gè)正則表達(dá)式(假設(shè)每個(gè)表達(dá)式所需要的core電路數(shù)量≤16個(gè))的并行匹配.

3.2 實(shí)驗(yàn)條件和硬件測(cè)試

本文所設(shè)計(jì)實(shí)現(xiàn)的DRR-engine模塊是整個(gè)AI-FPGA芯片的一個(gè)組成部分，圖11(見第716頁)是DRR-engine模塊在AI-FPGA芯片中所在的物理位置示意，測(cè)試用到的3個(gè)模塊分別是： 數(shù)據(jù)傳輸(PCIE)模塊、數(shù)據(jù)存儲(chǔ)(BRAM)模塊、DRR-engine模塊.測(cè)試平臺(tái)以及測(cè)試流程如圖12(見第716頁)所示，軟件編譯模塊接收和處理正則表達(dá)式，生成對(duì)應(yīng)的硬件配置信息，通過PCIE模塊(圖11中黑色框②所示)將配置信息傳遞給DRR-engine模塊(圖11中紅色框①所示)中的配置模塊進(jìn)行動(dòng)態(tài)可重構(gòu)配置；BRAM模塊(圖11中黃色框③所示)中存儲(chǔ)待匹配的字符串，DRR-engine模塊從BRAM模塊接收字符串?dāng)?shù)據(jù)，完成正則表達(dá)式的并行匹配計(jì)算，輸出匹配結(jié)果.

本文實(shí)驗(yàn)所采用的regexlib庫是互聯(lián)網(wǎng)中第一個(gè)正則表達(dá)式庫，包含各種類型的正則表達(dá)式，也是最為常用的正則表達(dá)式庫.本文基于regexlib庫完成正則表達(dá)式匹配的測(cè)試和驗(yàn)證.

3.2.1 匹配特性

從regexlib庫中隨機(jī)選取1000個(gè)正則表達(dá)式進(jìn)行匹配計(jì)算.匹配實(shí)驗(yàn)的測(cè)試結(jié)果顯示，本文算法可以很好地支持包括貪婪匹配、零寬斷言、范圍匹配、重復(fù)匹配以及由元字符“*”、“+”、“?”、“|”和普通字符組成的各種類型的正則表達(dá)式的匹配，覆蓋87%的匹配類型.未覆蓋到的正則表達(dá)式類型主要是反向引用和一部分轉(zhuǎn)義字符等.

圖11 AI-FPGA芯片的物理版圖Fig.11 Physical layout of the AI-FPGA chip

圖12 測(cè)試平臺(tái)及測(cè)試流程Fig.12 Test platform and test process

3.2.2 預(yù)處理速度

從regexlib庫中隨機(jī)選取300個(gè)算法可實(shí)現(xiàn)匹配的正則表達(dá)式，對(duì)drp模塊的重構(gòu)時(shí)間進(jìn)行測(cè)試，drp模塊的最高工作頻率設(shè)置為500MHz.測(cè)試結(jié)果顯示： 通過并行地對(duì)SRAM進(jìn)行配置，可以在0.32μs內(nèi)完成對(duì)所有正則表達(dá)式匹配電路的配置，平均每個(gè)正則表達(dá)式的配置時(shí)間為32ns.

3.2.3 匹配計(jì)算速度

從regexlib庫中隨機(jī)選取300個(gè)包含所有硬件可實(shí)現(xiàn)的元字符種類的正則表達(dá)式，分別對(duì)一段50MB 的文本進(jìn)行匹配.測(cè)試結(jié)果顯示，當(dāng)執(zhí)行快速匹配任務(wù)的regex并行計(jì)算電路的工作主頻設(shè)置為1GHz 時(shí)，在對(duì)單個(gè)正則表達(dá)式進(jìn)行匹配的情況下，每一個(gè)正則表達(dá)式均可以在20ms內(nèi)完成對(duì)全部文本的匹配，吞吐率為1Gb/s；在對(duì)多個(gè)正則表達(dá)式進(jìn)行匹配的情況下，280個(gè)regex電路可以相互獨(dú)立地同時(shí)工作，可以支持最多280個(gè)正則表達(dá)式的并行匹配，此時(shí)，吞吐率達(dá)到280Gb/s.

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

表9給出了本文算法與其他同類算法的比較.文獻(xiàn)[9-11]均采用基于FPGA的正則表達(dá)式匹配算法，其中文獻(xiàn)[11]同時(shí)完成了基于FPGA和基于ASIC的匹配電路設(shè)計(jì).從表9的實(shí)驗(yàn)結(jié)果可見，對(duì)比文獻(xiàn)[11]基于ASIC實(shí)現(xiàn)的快速匹配電路，本文所設(shè)計(jì)實(shí)現(xiàn)的動(dòng)態(tài)可重構(gòu)的正則表達(dá)式匹配引擎在吞吐率上大致相當(dāng)，但具有更為豐富的匹配特性和動(dòng)態(tài)可重構(gòu)的匹配能力.

對(duì)比文獻(xiàn)[9-11]基于FPGA實(shí)現(xiàn)的可重構(gòu)加速匹配算法，本文算法通過對(duì)正則表達(dá)式進(jìn)行參數(shù)化一致性表達(dá)、并將參數(shù)信息映射到硬件電路上的方法，無須更改并行計(jì)算的單元匹配硬件電路即可實(shí)現(xiàn)匹配特性的動(dòng)態(tài)更新，具有更完備的動(dòng)態(tài)可重構(gòu)的匹配能力.在匹配特性上，本文算法相較于文獻(xiàn)[9]和文獻(xiàn)[11]具有更豐富的匹配特性，與文獻(xiàn)[10]大致相當(dāng).而在匹配速度上，依據(jù)本文算法所實(shí)現(xiàn)的加速匹配引擎(DRR-engine)，相較于其他同類型的匹配引擎均具有超過5倍以上的提升.

表9 正則表達(dá)式匹配引擎算法比較

4 結(jié) 論

本文提出了一種更為寬泛和一致性的參數(shù)化設(shè)計(jì)，通過對(duì)正則表達(dá)式的一致性表達(dá)，簡(jiǎn)化了表達(dá)式匹配的計(jì)算復(fù)雜度，并進(jìn)一步抽象和提取出可以完全表征各類正則表達(dá)式的參數(shù)集合，將其轉(zhuǎn)化為可重構(gòu)計(jì)算硬件的配置信息，在擴(kuò)展了正則表達(dá)式匹配特性的同時(shí)降低了配置復(fù)雜度，減少了預(yù)處理時(shí)間.在此基礎(chǔ)上，本文采用FPGA+ASIC的混合計(jì)算框架，設(shè)計(jì)了基于FPGA的動(dòng)態(tài)可重構(gòu)配置(drp)電路，和以單字符匹配(core)電路為基本單元的可擴(kuò)展的regex并行計(jì)算陣列，完成了動(dòng)態(tài)可重構(gòu)的正則表達(dá)式匹配計(jì)算加速引擎的設(shè)計(jì)和實(shí)現(xiàn)，并在TSMC 28nm CMOS工藝下完成了芯片的流片.實(shí)驗(yàn)結(jié)果表明，本文提出的動(dòng)態(tài)可重構(gòu)的正則表達(dá)式匹配算法和基于FPGA+ASIC混合計(jì)算框架所實(shí)現(xiàn)的并行化計(jì)算加速引擎，與目前同類型的正則表達(dá)式計(jì)算引擎相比，不僅在正則表達(dá)式的匹配特性上提供了更為完整的覆蓋能力，具有更快速的動(dòng)態(tài)可配置能力，同時(shí)在匹配速度上獲得了超過5倍以上的提升，最大吞吐率達(dá)到280Gb/s.