一種基于魂芯DSP的單模式位并行串匹配算法

陳 瑞 顧乃杰 葉 鴻

(中國科學技術大學計算機科學與技術學院 安徽 合肥 230027)(中國科學技術大學安徽省計算與通信軟件重點實驗室 安徽 合肥 230027)

0 引 言

串匹配是在已知字符序列(文本串)中按照一定的匹配條件搜索給定字符序列(模式串)集合中元素出現位置的搜索問題，是生物信息學、信號處理和信息檢索等方向的核心問題，在涉及字符處理相關領域中具有廣泛的應用[1]。隨著信息時代數據的高速增長，如何快速高效地處理大規模數據的串匹配問題是當前研究的重點。串匹配問題包括多模式匹配和單模式匹配。其中，多模式匹配的研究大多根據自動機原理，其經典算法包括AM算法[2]、AC算法[3]、FS算法[4]等。單模式匹配是研究串匹配問題的基礎，且其他模式匹配算法均由單模式匹配擴展而來，應用領域也最為廣泛，已經成為涉及文本和符號處理領域應用的基本組件。因此，研究精確單模式串匹配問題有重要意義。

另一方面，隨著多媒體技術的飛速發展，DSP處理器以其低功耗和高性能等特點在信號處理和圖像檢索等領域有著重要的應用。高性能DSP處理器不僅擁有強大的計算能力，還具有多種先進技術，單指令流多數據流(Single Instruction Multiple Data,SIMD)、超長指令字(Very Long Instruction Word,VLIW)等特殊的硬件結構使得字符串匹配算法在DSP上得以并行處理。本文提出一種基于魂芯DSP的精確單模式位并行串匹配算法，并在平臺上進行仿真實驗。

單模式串匹配算法眾多，代表性的有按照前綴匹配規則的KMP算法[5]、Shift-Or/And(SO/SA)算法[6]和按照后綴匹配規則的Horspool算法[7]和SBNDM2算法[8]。KMP算法第一個在線性時間解決了串匹配問題，該算法利用已經匹配的已知信息，實現無回溯的字符比較，具有線性時間復雜度。Shift-Or/And算法是一種最基礎的位并行算法，實現線性的串匹配過程，串匹配速度遠快于KMP，該算法維護一個字符串的字符集合，然后利用位操作的內部并行性，實現非確定性有窮自動機(Non-deterministic Finite Automaton,NFA)的全部狀態轉移。按后綴規則匹配的Horspool算法是簡化了的BM(Boyer-Moore)算法[9]，是一種以空間換時間的“跳躍式”匹配算法，在實際應用中比BM算法具有更好的性能。SBNDM2算法在英文語料或者大字符集下搜索具有較高的性能。1985年Galil[10]研究了一種基于軟件的并行串匹配算法，可以在O(log2m)時間復雜度下完成串匹配過程，m是模式長度。該算法的缺點是只適用于對固定字符集進行串匹配。同年，Vishkin[11]改進了Galil提出的并行算法，使其支持字符集可變的情況。戴正華[12]從計算機體系結構的角度出發，基于Shift-Or算法通過組合NFA狀態，降低自動機狀態轉換的次數，提高匹配效率，在不考慮Cache失效的情況下，算法比較次數可減少一半。對于并行串匹配算法，隨著近些年DSP、GPU和FPGA等硬件的高速發展，把經典算法移植到硬件平臺上以提高匹配效率成為研究的熱點。侯淼[13]基于GPU高性能并行架構，把經典的AC算法移植到GPU平臺進行加速，設計實現了數據并行的PAC算法，并取得了顯著的加速效果。Irwin等[14]實現了基于FPGA的并行串匹配算法，相比軟件實現方式，算法性能得到顯著提升。但該方法由于硬件限制，不易操作，難以廣泛應用。李璋等[15]將串匹配算法在CPU、GPU、FPGA上進行了性能的測試與對比，并在GPU上充分利用SIMD結構對算法并行化，在FPGA上利用大量內部邏輯運算單元，實現了高效的串匹配算法。

本文首先通過實驗對比了KMP、Horspool、SO三種經典串匹配算法在魂芯DSP處理器上的執行效率；其次結合處理器的分支預測和零開銷循環等技術對算法的條件分支語句進行優化，以減少分支語句帶來的額外時鐘開銷；最后結合DSP處理器分簇結構和無漏配的字符串分段方法提出一種基于魂芯DSP的精確單模式位并行串匹配算法EPSO。該算法通過將文本串劃分給處理器若干執行簇，減少分簇執行過程中的漏配次數，充分發揮硬件特性，從而有效提升串匹配算法性能。

1 研究背景

1.1 平臺介紹

魂芯DSP是國內某研究所自主研發的一款高性能數字信號處理器[16]，可廣泛應用于各種高性能計算領域。作為魂芯DSP系列的第二代產品，HXDSP 1042是一款32位浮點DSP，采用哈佛結構、超流水線、超長指令字等并行技術。HXDSP 1042處理器體系結構如圖1所示。

圖1 HXDSP 1042體系結構

(1) 內核結構稱為eC104+，核內包含4個結構和功能完全相同的執行單元(Element Operation Unit)，分別用X、Y、Z、T表示。每個單元包含128個通用寄存器、8個乘法器(Multiplier,MUL)、8個算數邏輯運算單元(Arithmetic Logic Unit,ALU)、4個移位器(Shifter,SHF)、1個超算器(Super Unit,SPU)。

(2) 處理器含有3個相互獨立的地址產生器，分別用U、V和W表示。內部數據總線采用非對稱全雙工總線，內部數據讀總線位寬為512位，內部數據寫總線位寬為256位。對于浮點復數而言，支持“兩讀一寫”或“兩寫一讀”，前者是指一個時鐘周期每個執行宏讀取2個32位浮點復數且寫回1個32位浮點復數。后者是指一個時鐘周期每個執行宏寫回2個32位浮點復數且讀入1個32位浮點復數。

(3) 處理器采用VLIW技術，單周期內可并行執行16條共計長達512位寬的指令。條件跳轉等分支指令必須排布在指令槽的首部，且每個指令槽至多有一條此類指令。

1.2 相關算法

蠻力算法(Brute Force,BF)是一種最基本的串匹配算法[12]。該算法首先比較模式串的第一個字符和文本串的第一個字符，如果相等，繼續比較二者的后續字符；否則，比較模式串的第一個字符和文本串的第二個字符是否相同，以此類推，直到得出匹配結果。該算法本質上是基于模式串前綴規則進行匹配，常見的前綴串匹配算法還有KMP和基于位并行的Shift-Or等，基于后綴進行搜索的算法有BM和Horspool等。下面以KMP、Shift-Or、BM、Horspool算法為例描述各個算法的基本原理。

(1) KMP算法。KMP算法從左至右逐字符地掃描文本串的當前窗口，如果在模式串的位置i處發生失配，則文本串向前移動若干距離，即移動i-fp(i)個字符。其中，fp(i)定義[13]如下式所示，i為0時取-1，否則取最大可偏移的值。

(1)

如果找到一個匹配，則令i=s，窗口向前移動距離為fp(s)，下一個窗口對齊文本串s+i-fp(i)的位置。簡單地說，KMP算法記錄的模式串前綴，同時也是已經掃描的文本串的最長后綴字符串。圖2描述了文本串為“ababcab”，模式串為“abcac”的KMP算法匹配過程。

圖2 KMP算法匹配示意圖

(2) Shift-Or(SO)算法。SO算法和KMP算法類似，也是基于前綴規則進行字符串匹配，但其利用計算機機器字位運算的內在并行性，將多個值裝入同一個機器字內，從而加速了串匹配過程。算法1描述了SO算法的基本執行過程，該算法主要維護一個集合D，該集合中保存了所有既是模式串前綴同時又是文本串前綴的字符串。每次讀入新字符后，算法利用位并行的方式更新集合。算法中變量B是一個輔助表，也可以稱之為字典，其關鍵字是模式串中的每個字符，值是一個n位的無符號數，記錄該字符在模式串p中出現的位置。本文串和模式串分別用t和p表示。假設處理到模式串字符p[i]，則對D進行更新。由于集合D標識了字符p[0…j]是否為文本串t[0…i]的后綴，所以D[j]=0當且僅當更新前的D[j-1]=0且t[i]=p[j]。顯然，當D[m-1]值為0時，字符p[0…m-1]是t[0…i]的后綴，找到一個串p的完全匹配。

算法1移位或(Shift-Or，SO)算法

輸入：p=p1p2…pm,t=t1t2…tn

輸出：[idx1…idxs]

1. //Preprocessing

2. forc∈∑ doB[c]=0m

3. forj∈1…mdoB[pj]=B[pj]&1m

4. //Searching

5.D=1m

6. forpos∈1…ndo

7.D=(D<<1)|B[tpos]

8. ifD|01m-1≠1mthen

9. output ″pos-m+1″

(3) Boyer-Moore(BM)算法。BM算法的基本思想是對模式串從右向左進行逆向匹配，在預處理過程中先構造壞字符表和好后綴表。在匹配時利用壞字符和好后綴規則，跳過盡量多的字符。算法包括兩個規則。一個是壞字符規則，假設文本串為t，則從右向左掃描模式串p，若發現某個字符發生失配，則按照兩種情況分別討論。如果當前文本串的字符t[i]在模式串p中沒有出現，則直接將模式串向右跳過模式串長度的距離，否則以最右出現該字符的位置進行對齊。另一個是好后綴規則，好后綴表示已經成功匹配的后綴串，共有以下三種情況。

情況一：模式串中存在最左子串和好后綴相匹配，將模式串向右移動，使得子串與之對齊即可。

情況二：模式串中不存在最左子串和好后綴匹配，尋址模式串的一個最長前綴，并將該前綴串等于好后綴的后綴串，然后使兩者對齊。

情況三：模式串沒有子串和好后綴匹配，并且模式串中找不到最長前綴，移動模式到好后綴的下一個字符即可。

(4) Horspool算法。BM算法簡化后得到Horspool算法，該算法基于文本串從后向前匹配時，將主串匹配窗口的最后一個字符和模式串的最后一個字符比較，若匹配成功，則從后往前繼續比較；若匹配失敗，則根據主串匹配窗口的最后一個字符β在模式串中下一個出現的位置將窗口向右移動，如圖3所示。該算法對BM的壞字符規則進行了改進，BM算法的對齊字符是當前發生失配時文本串當前失配字符，而Horspool算法對齊的是文本串匹配窗口的最后一個字符，即字符β，該字符與模式串中最近出現的β對齊。

圖3 Horspool算法匹配示意圖

2 基于DSP的位并行串匹配算法

本節首先通過具體實驗對比分析KMP、Horspool和Shift-Or算法在DSP上的執行效率，結合硬件特性討論各串匹配算法的性能差異；其次利用零開銷循環技術對算法的條件分支語句進行優化；最后結合處理器分簇結構和零開銷循環技術，提出一種基于HXDSP的高效位并行串匹配算法。

2.1 算法分析

選取KMP、Horspool和Shift-Or三種串匹配算法在HXDSP處理器上進行實驗，測試數據為經典字符集Holy-bible.txt[17](176 813個字符)，模式串用隨機抽取的方式抽取9個不同長度的串作為測試樣本。圖4顯示了三種算法在HXDSP處理器上的運行結果。

圖4 基于HXDSP的串行串匹配算法

測試結果表明，Shift-Or算法和KMP算法性能基本不受模式串長度的影響，針對特定的測試串，其性能基本可以保持穩定；基于后綴規則匹配的Horspool算法不僅性能相對較好，并且隨著模式串長度的增加，時鐘周期數顯著減少。該算法在字符集較大時性能會更好，主要原因在于當模式串長度越大，匹配窗口向前滑動的距離越遠。KMP算法作為前綴算法，模式串長度的變化會對算法性能產生一定的影響，主要是因為文本串向前移動距離的不同導致時鐘開銷出現一定差異。基于位并行的前綴匹配SO算法，由于匹配過程包含大量位運算，并且每一次通過采用位運算的方式進行比較，完成的任務量和模式串長度不相關，因此該算法的時鐘周期基本保持穩定。

串匹配算法的性能和處理器硬件結構密切相關。從硬件層面出發，為了提高算法性能，需要盡可能多地或者盡可能早地執行指令。SIMD是高性能處理器的一個重要特性，該技術通過增加指令中完成的操作數，減少完成任務或程序所需要的指令來提高處理器性能。這使得在高性能處理器上加速串匹配算法成為可能，對于上述三種串匹配算法，由于KMP和Horspool算法在匹配過程中是根據一定的規則跳過若干字符距離來提高串匹配效率，若采用數據并行策略，將劃分好的文本串交給不同的函數單元進行同時匹配，算法將不能利用SIMD技術的優勢，并且會導致無法同時做同樣的匹配操作。對于位并行的Shift-Or算法，其核心思想是通過更新掩碼集合D來記錄模式串的前綴匹配情況，這種匹配過程能夠很好地應用在SIMD結構中，采用分治的思想通過將劃分好的文本串同時在DSP處理器的四個簇中并行執行，能夠更好地利用HXDSP的硬件資源，充分發揮處理器的計算能力，從而加速串匹配過程。

2.2 算法實現

上述串匹配算法中，基于位并行的Shift-Or算法在高性能DSP處理器中能夠通過分簇結構更好地將算法并行化。下面首先從HXDSP指令級優化層面對串行代碼進行優化，再采用分治思想提出合適的字符串分段方法對算法實施并行化，最后提出高效的基于位并行的EPSO算法。

分析算法1的循環部分，其中針對輔助表B的預處理部分耗時可忽略不計(文本串長度達到一定規模后)，時鐘開銷主要集中在更新集合D過程中，即算法1的第6行至第9行的循環體部分。從指令層面對算法1進行優化，包括計算開銷和條件分支開銷。針對計算，除了盡可能提高指令行的并行處理能力之外，需考慮流水線的數據相關。算法1中的D進行更新過程中的移位操作、或操作串行性強，無法利用循環展開的方法來減少運算過程中的流水線停頓，即循環體內涉及串行運算的時鐘開銷已經沒有更多的優化空間。反觀條件跳轉部分，由于每一次循環都要產生額外的10個時鐘周期，算法1的第8行判斷是否找到一個成功匹配同樣是條件判斷操作，同樣需要產生一定的時鐘開銷，相比運算部分，這兩個條件判斷所占用的時鐘周期是運算部分耗費時間的兩倍，采用分支預測可以有效提高條件判斷和條件分支語句的執行效率。

算法2優化條件分支語句。

HXDSP 1042處理器提供如下兩條指令：

指令1：if {x,y,z,t}Rm[bit]==0/1 b

指令2：if lc0/nlco b

上述指令在串匹配算法的條件分支語句中具有重要作用。指令1表示寄存器Rm的第bit位為0或1時跳轉至pro處，該指令簡化了算法1第8行成功找到匹配點的過程，省去掩碼計算過程和掩碼與集合D的或非操作，由于該過程在算法1的串行版本下耗費4至6個時鐘周期，循環體內計算過程以及條件分支判斷總的耗費時鐘周期為40左右，因此該指令可以減少算法10%～15%的時鐘開銷。指令2是基于LC0和LC1寄存器的分支指令，預測機制較為特殊，該指令在取指時讀取LC0和LC1寄存器的值，并以此作為是否分支的判斷依據。該指令同樣能在每個循環體內減少8個時鐘開銷左右，帶來20%左右的性能提升。

為了發揮HXDSP四個簇的計算能力，針對算法2考慮四路并行化，提出一種字符串分段方法以提高計算資源和帶寬使用率，進一步提升串匹配效率。并行化的基本思想是將長度為n文本串平均分成4組，對于不能整除的用空字符填充，記為Ti(i=1,2,3,4)。將四組長度相等的文本串分別和模式串P匹配，實現文本匹配過程的并行處理。分段方法的關鍵在于子文本串在相鄰處有可能出現遺漏現象，由于在各段子串的連接處有可能存在和模式串相等的串，因此在將各子串分給不同的執行簇時有一定的概率出現漏配問題。為了避免漏配，有以下3種解決方案。

(1) 由于四個簇并行執行，那么分配給四個簇的文本串長度要保證一致。為了解決相鄰子文本串的漏匹配問題，考慮為每個簇分配長度為n/4+m-1的串。

T{x,y,z,t}=Ti+m-1i=1,2,3,4

(2)

式中：T{x,y,z,t}表示分配給每個簇的字符串，m是模式串的長度，字符Tx{n/4…n/4+m-1x,y,z,t}表示簇X文本串的后m個序列，該序列由T1的最后一個字符和T2的前m-1個字符組成。Ty則由T2和T3的前m-1個字符組成。Tz同理，Tt則不同，除了包括T4之外，需要額外補充長度為m-1的字符，如圖5中長為m-1的區域，以保證四個簇的文本串長度一致。

圖5 基于HXDSP的并行串匹配過程

(2) 針對Tt文本串改進，將Tt的起始位置向前回溯m-1個字符，如圖6所示，盡管這樣Tt的匹配和Tz的匹配存在m-1次的重復匹配，但硬件資源充足情況下，省去補充字符的過程，簡化了Tt的匹配過程。

圖6 簇T上串劃分的改進方案

(3) 由于Tt額外重復匹配了m-1次，考慮繼續對方案二進行優化，把該m-1次重復匹配均勻地分配給其余三個執行單元，即每個簇需要匹配的字符減少了(m-1)/4個，如下式所示：

T{x,y,z,t}=Ti+3(m-1)/4i=1,2,3,4

(3)

由于基于位并行的SO算法受字長限制，長度m往往小于處理器字長(32或64)，文本串在一定規模時，這種優化帶來的提升幾乎可以忽略，并且該方案對m的取值敏感，當m-1不能整除4時，依然需要補充額外字符，這種優化策略導致的額外時鐘開銷遠大于其帶來的性能提升。

綜上所述，結合處理器的分簇結構和上述分段方法，可有效提高串匹配算法效率。在算法2的基礎上按照上述方案(2)的劃分方法，提出一種有效的并行移位或串匹配算法，稱之為EPSO，偽代碼如算法3所示。該算法對文本串的拆分存在4無法被n整除的現象，會導致1～3個串出現漏匹配的問題。為了解決該問題，采用方案一，在文本串text末尾補充e個空字符，其中e=4-n%4，然后按照上述算法進行并行化，匹配完成時為了消除補充字符對串匹配結果的影響，記簇T中成功匹配點為p，忽略p>|n/4|-n%4的設置輔助表B和匹配過程中用于更新的集合D，用本節介紹的字符串分段方法結合處理器的分簇結構把經過預處理的串傳輸給不同的執行簇，分別按照位并行的方式對D進行移位或計算，最后采用算法2中的條件判斷指令分別輸出四個簇的成功匹配點。

算法3高效位并行算法(EPSO)

輸入：p=p1p2…pm,t=t1t2…tn

輸出：[idx1…idxs]

1. //Preprocessing

2. forc∈∑ do {x,y,z,t}B[c]=0m

3. forj∈1…mdo {x,y,z,t}B[pj]=B[pj]&1m

4. //Searching

5. {x,y,z,t}D=1m‖i1=1‖i2=n/4+1

6.i3=n/2+1‖i4=3n/4-m+2

7. fork∈1…(n/4+m-1) do

8. {x,y,z,t}D=({x,y,z,t}D<<1)|B[t{i1,i2,i3,i4}]

9. if {x}D[bit]==0 then output ″k-m+1″

10. if {y}D[bit]==0 then output ″n/4+k-m+1″

11. if {z}D[bit]==0 then output ″n/2+k-m+1″

12. if {t}D[bit]==0 then output ″3n/4+k-m+1″

13.i1++‖i2++‖i3++‖i4++

3 實驗分析

本文實驗基于HXDSP 1042仿真平臺[18]，待匹配文本為測試集Holy-bible.txt(703 KB)和E.coli的DNA序列(coli_str_k_12_substr_mg1655,15,2 143 bp)，在文本中隨機抽取100個串作為測試樣本。為了精確統計串匹配算法消耗時間，實驗采用全局寄存器CC0進行計數。為避免磁盤影響實驗結果，所有字符串均已讀入內存，只針對匹配過程進行計時，測試三種位并行算法不同匹配條件下的匹配效率。

實驗選取KMP算法和Horspool算法作為SO、ESO、EPSO算法的對比算法，實驗結果如表1和表2所示。數據表明，703 KB大小的英文文本串下，ESO算法的平均匹配時間達到2.855 ms，EPSO算法的平均匹配時間達到0.716 ms，和經典的SO算法相比，加速比分別達到1.96和7.81。當文本串選取擁有152 143個堿基對的大腸桿菌DNA序列時，ESO算法的平均匹配時間達到3.317 ms，EPSO算法的平均匹配時間達到0.834 ms，相比SO算法，加速比分別可達1.94和7.72左右。HXDSP的實驗結果表明，基于位并行的SO算法通過在該處理器上的并行實施和優化，在英文語料和DNA序列中均有良好的性能提升。

表1 DNA字符集下串匹配時鐘開銷

表2 英文語料下串匹配時鐘開銷

為了更好地對比實驗結果，將本文算法與范洪博等[20]在Intel E2160處理器上的串匹配工作進行比較。一般來說，魂芯DSP處理器相比現階段主流Inter處理器擁有更低的主頻和功耗。Inter E2160處理器主頻達到2.7 GHz，功耗為65 W，遠高于魂芯DSP功耗，兩者具有相同的核心數和相當的制作工藝。

本文工作基于單核四路SIMD的魂芯DSP進行，范洪博等基于位并行原理提出S2BNDM算法，并在Intel E2160處理器上進行測試，該算法相比NEW、Horspool、KMP等的性能有明顯提升。其中NEW算法在小字符集和長模式下具有顯著的優勢，在英文語料情況下，算法S2BNDM和S2BNDM’分別在短模式和長模式下具有較高的匹配效率。結果的對比以KMP算法為基準，選取單模式匹配NEW[19]、S2BNDM[20]、S2BNDM’[20]作為對比算法，分別比較上述幾種高效算法和EPSO算法相比各平臺KMP算法的性能提升情況，對比結果如圖7、圖8所示。

圖7 DNA序列串匹配算法增速對比

圖8 英文語料串匹配算法增速對比

結果表明，在DNA字符集下，當模式串長度小于16時，相比KMP，EPSO算法匹配速度快于其他三種算法。當模式串長度大于16時，EPSO算法可帶來的性能加速比例略小于NEW算法，且和S2BNDM算法和S2BNDM’算法相當，這主要是因為EPSO算法屬于非模式敏感型算法，而其他三種算法在模式長度不同時，匹配過程中跳躍的距離不同，性能也不同。在英文語料下，以KMP算法為基準，EPSO算法帶來的性能提升明顯高于其他三種算法，EPSO算法的匹配速度是KMP算法的6.5倍左右。根據前文對兩種處理器的分析，在各項指標不超過Inter處理器的情況下，基于魂芯DSP的單模式位并行算法EPSO比NEW、S2BNDM等算法表現出更好的性能提升效果。

4 結 語

本文通過分析串匹配算法在DSP上的執行效果，結合HXDSP處理器平臺的分簇體系結構和零開銷循環等技術，提出一種基于位并行的無漏配的高效串匹配算法，能充分發揮硬件資源優勢，有效提升單模式串匹配算法的效率。該算法在電子對抗、入侵檢測等方面有應用價值，對推動國產信息化處理起著重要作用。

接下來的工作將在本文基礎上，繼續挖掘新一代多核魂芯DSP結構下位并行串匹配算法性能優化的潛力，將優化工作擴展到多模式匹配和近似匹配等更多的方面。