續(xù)士強　祝永志

摘要：如何提高字符串實際匹配效率一直是信息匹配領(lǐng)域中非常重要的研究課題。在分析字符串匹配并行規(guī)律的基礎(chǔ)上，結(jié)合GPU并行體系結(jié)構(gòu)，對Sunday算法實現(xiàn)并行化。在CPU和GPU不同計算平臺上分別做了對比實驗，實驗結(jié)果顯示基于GPU并行實現(xiàn)的Sunday算法比傳統(tǒng)Sunday算法具有更高的匹配速度。

關(guān)鍵詞關(guān)鍵詞：CUDA；Sunday算法；并行計算

DOIDOI：10.11907/rjdk.143766

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2015）002005103

基金項目基金項目：山東省自然科學基金項目（ZR2013FL015）；山東省研究生教育創(chuàng)新資助計劃項目（SDYY12060）

作者簡介作者簡介：續(xù)士強（1990-），男，山東滕州人，曲阜師范大學信息科學與工程學院碩士研究生，研究方向為網(wǎng)絡(luò)與并行計算；祝永志（1964-），男，吉林榆樹人，曲阜師范大學信息科學與工程學院教授、碩士生導(dǎo)師，研究方向為網(wǎng)絡(luò)與并行計算。

0引言

字符串匹配被廣泛應(yīng)用于解決搜索引擎、網(wǎng)絡(luò)入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等諸多問題中。目前關(guān)于字符串匹配算法的研究已經(jīng)相對成熟，傳統(tǒng)的串匹配算法實現(xiàn)思想主要分為前綴搜索、后綴搜索和子串搜索，經(jīng)典的算法[1]有KMP算法、Shift-And算法、BM算法、BDM算法等等。然而傳統(tǒng)算法在實際應(yīng)用中并沒有表現(xiàn)理論上的優(yōu)勢，比如，在一個普通文本文件中查找字符串，BF算法用的時間通常比KMP算法要少，即使后者在時間復(fù)雜度上要優(yōu)于前者。因此，選擇一種在實際應(yīng)用中性能較好的算法，對于提高效率至關(guān)重要。

隨著圖形處理器性能的不斷提高，特別是通用并行計算架構(gòu)（CUDA）的推出，圖形處理器已不再局限于圖形圖像處理，其在通用計算方面已經(jīng)遠遠超越了CPU。由于GPU的特點就是處理密集型數(shù)據(jù)和并行數(shù)據(jù)計算，因此，CUDA編程模型非常適合解決大規(guī)模并行計算問題。

1CUDA編程模型

CUDA（Compute Unified Device Architecture），是由NVIDIA推出的通用并行計算架構(gòu)，它在C語言基礎(chǔ)上添加了適用于GPU并行計算的API和開發(fā)庫，是在GPU強大計算能力基礎(chǔ)上建立的效率更高的密集數(shù)據(jù)計算解決方案。

在NVIDIA的GPU中，最基本的處理單元是SP（流處理器），多個SP組成一個SM（流多處理器），它們之間可以共享控制邏輯和指令緩存。在CUDA編程下，程序執(zhí)行的最小單位是thread（線程），每個thread都有各自的一份register和local memory。一組thread組成一個block（線程塊），在同一個block中的thread可以存取同一塊共享內(nèi)存，最后執(zhí)行同一kernel函數(shù)的block構(gòu)成一個grid（塊網(wǎng)格）。CUDA架構(gòu)下的程序包括運行在CPU上負責串行執(zhí)行的Host端，以及運行在GPU上作并行計算的Device端。Kernel函數(shù)由host端調(diào)用，能生成大量的線程，每個線程處理對應(yīng)的數(shù)據(jù)塊，從而實現(xiàn)了數(shù)據(jù)的并行處理。grid的所有線程都執(zhí)行同一個kernel函數(shù)。CUDA的device在實際執(zhí)行時，以block為單位，并將每個block分給SM執(zhí)行，同一block中的thread，又以32個組成一個warp一起執(zhí)行。每個SM只執(zhí)行一個block中的warp，由于在實際執(zhí)行過程中，某個warp需要訪問全局存儲器，這時SM就會切換到別的warp來繼續(xù)執(zhí)行。因此，一個SM可以同時處理多個block。

2基于GPU的Sunday算法并行化

2.1Sunday字符串匹配算法

Sunday算法源于BM算法充分利用壞字符的思想。Sunday算法將計算好后綴的時間節(jié)約下來，將所有情況歸為壞字符規(guī)則來匹配，這對短模式串匹配十分有利。因此，Sunday算法的匹配過程基本應(yīng)用的就是BM算法的壞字符規(guī)則，即當字符串不匹配時，判斷目標串進行匹配的下一字符是否在模式串中出現(xiàn)，如果出現(xiàn)，則模式串移動到目標串中最右端的該字符串的下一位置；如果沒有出現(xiàn)，則模式串直接跳過模式串字符長度。

Sunday算法實現(xiàn)如下：

while（main_i

{

int tem=main_i；

while（sub_j

{

if（mainStr[main_i] == subStr[sub_j]）

{

main_i++；

sub_j++；

continue；

}

else{

if（tem+subStrLen > mainStrLen）

return -1；

char firstRightChar=

mainStr[tem+subStrLen]；

main_i+=

char step[（unsigned char）firstRightChar]；

sub_j=0；

break；

}

}

if（sub_j == subStrLen）

return main_i-subStrLen；

}

2.2字符串并行劃分設(shè)計

CUDA編程模型是基于并行執(zhí)行多個線程來實現(xiàn)大規(guī)?？焖儆嬎愕?，因此字符串要實現(xiàn)并行匹配，就必須將原有的字符串劃分成多個小字符串，再將小字符串分散到各個線程中，線程對分配的小字符串進行匹配。但是，僅僅做到簡單劃分是不夠的，通常串行的字符串匹配算法，無論算法如何設(shè)計向前跳躍，匹配始終帶有一定的順序性，在劃分后的局部字符串匹配位置必須到下一小字符串才能找到。為了解決劃分字符串過程中存在的漏解問題，采用冗余數(shù)據(jù)是簡單可行的方法。

假設(shè)將長度為T的文本串均勻分成互不重疊的m段，分布在0～（m-1）線程中，則顯然每個線程中字符串長度為[n/m]，再將長度為s的模式串分配到各個線程，使得每個線程都對分到的小字符串進行匹配[3]。為了解決漏解問題，在每個線程分得的小字符串末尾位置存儲與其相鄰的長度為s-1的字符串。

2.3Sunday算法并行實現(xiàn)

串行實現(xiàn)的Sunday算法，通過極少的比較次數(shù)來獲得較大的跳躍距離，與BF算法相比，避免了大量回溯匹配的產(chǎn)生。而基于GPU這種并行體系結(jié)構(gòu)的并行算法，利用多個線程并行執(zhí)行解決問題，原有較長的字符串劃分到各個線程，使得每個線程字符串長度明顯縮短，比串行集中式的匹配算法速度提高很多。

2.3.1數(shù)據(jù)預(yù)處理

為了最大限度地利用CPU資源，目標串的存取與分片工作放在CPU進行。首先在內(nèi)存中分配一塊大致與目標串物理存儲大小相等的存取空間。比如目標串存儲的文本大小為10M，那么就在內(nèi)存中申請大約10M的地址空間，目的是為了使目標串讀入主存，便于程序存取。當然，實際申請地址空間時，空間大小是根據(jù)讀取到的目標串大小而設(shè)定的。通過I/O操作將目標串從外部文件讀入到內(nèi)存后，對目標串進行如下分片操作：

（1）根據(jù)目標串的總長度與CUDA的線程數(shù)來確定每個線程要處理字符串的長度。雖然GPU可以創(chuàng)建上百萬甚至上千萬線程，但是同時并行的線程總數(shù)卻十分有限。因此，創(chuàng)建合理數(shù)量的線程不僅可以避免一些額外開銷，而且可以提升算法總體效率。以GT750M為例，每個block最多可以同時運行的線程數(shù)是2 048，但根據(jù)實驗結(jié)果，取1 024比較好。這是因為每個CUDA線程處理性能有限，分片后小字符串如果太長，線程匹配耗時增加，算法的整體匹配效率會變差。如果太短，那么分配的線程總數(shù)就多，用于線程分配和回收的額外時間大大增加，算法的效率就得不到提高。因此，合理的分片對于最終匹配效果十分重要。經(jīng)過實驗，分片后的小字符串長度驗證取64為宜。

（2）字符串的漏解處理[4]。由于對字符串進行了分片操作，小字符串末尾和開始位置的字符就喪失了原來的順序，同一串的字符分到不同線程，而這一字符串可能恰好是匹配串，這樣就造成匹配過程的漏解情況。為了解決這個問題，必須在每個小字符串后面添加下一段字符串的前m-1個的字符（m為模式串長度）。這里需要說明的是，添加冗余數(shù)據(jù)的處理在CPU端進行。由于模式串的長度相對較短，即使在分片較多的情況下，所添加的冗余字符對算法的匹配效率也不會造成大的影響。需要注意的是，添加冗余字符后，模式串的實際匹配位置需要作移位處理，保持結(jié)果正確。

2.3.2并行匹配

改進算法對字符串實際匹配操作都是在GPU中完成的，因此目標串要再從內(nèi)存讀取到顯存，與內(nèi)存申請地址空間類似。通過cudaMalloc函數(shù)在顯存中申請地址空間，然后再調(diào)用cudaMemcpy函數(shù)將內(nèi)存中的目標串復(fù)制到顯存中。這樣，GPU就能直接對顯存中的目標串進行匹配操作。調(diào)用kernel函數(shù)完成字符的匹配后，再把顯存存儲的匹配結(jié)果復(fù)制到內(nèi)存的變量中進行顯示。

Kernel函數(shù)對字符串匹配操作過程：①根據(jù)blockIdx與threadIdx變量確定當前線程的實際線程號；②根據(jù)線程號找到要處理的字符串位置；③對每個小字符串實現(xiàn)Sunday算法。每個線程處理字符串長度與分片后的小字符串長度一致。

Kernel函數(shù)的部分代碼如下：

__global__ void sunday_kernel（char *g_subStr，int subStr_len，int aim_len，char *aim_text，int *gpu_pos）

{

int i=threadIdx.x+threadIdx.y*16+blockIdx.x*256；

int j=0；

int c = 0； //計數(shù)

int m = i*64；

int n = 0；

while（m+n

if（aim_text[m+n]== g_subStr [j]）

{

n++；

j++；

count++；

}

else {

n++；

j = 0；

count = 0；

}

if（c== subStr_len）

{

*gpu_pos = m+n-count；

}

}

3實驗結(jié)果與分析

實驗環(huán)境硬件配置：CPU：Intel Core i5-3230M，主頻：2.60GHz，內(nèi)存：4GB。GPU采用GT750M 核心頻率950MHz，顯存2G。操作系統(tǒng)是Windows XP professional 2002 Service Package 3，軟件平臺為CUDA 5.5，實驗集成環(huán)境Visual Studio 2010。

使用人類基因DNA部分序列集合字符串作為文本串匹配數(shù)據(jù)集。本文第一組實驗，測試在相同文本大小的目標串情況下，不同匹配算法消耗的匹配時間對比，實驗文本大小為30M，模式串為“test”，實驗結(jié)果見表1，匹配時間結(jié)果以ms為單位；第二組實驗，測試CPU與GPU固定模式串長度在不同文本大小字符串的匹配時間對比，實驗過程中對字符串文本隨機插入模式串“test”，再對模式串進行匹配，實驗結(jié)果見表2，匹配時間以ms為單位，匹配位置單位為字符個數(shù)。

表1不同算法消耗的匹配時間對比

[]BF算法[]KMP算法[]Sunday算法

匹配時間（ms）[]85.784 66[]215.690 48[]73.988 68

匹配位置[]32 157 335[]32 157 335[]32 157 335

表2Sunday算法與GPU并行Sunday算法字符串匹配消耗時間對比

文本大小[]1M[]8M[]16M[]30M[]53M[]77M

CPU匹配時間（ms）[]2.942 78[]20.341 69[]40.153 63[]75.152 00[]133.682 68[]191.519 03

GPU匹配時間（ms）[]2.008 25[]7.455 17[]14.277 82[]25.333 25[]43.330 85[]61.758 17

匹配匹配位置[]1 024 997[]8 353 018[]17 037 000[]32 157 327[]55 622 541[]80 752 081

從第一組實驗結(jié)果可以看出，在相同文本大小的目標串和相同的模式串情況下，Sunday算法的匹配時間最短，BF算法次之，而KMP算法匹配時間最長。傳統(tǒng)的字符串匹配算法實現(xiàn)的基本思路是，根據(jù)模式串按照從左到右或從右到左的順序依次與模式串匹配，若不匹配，則根據(jù)相應(yīng)規(guī)則進行移位跳躍。大部分的字符串匹配算法只是對如何進行移位跳躍進行改進，而這個改進還必須根據(jù)模式串的自身結(jié)構(gòu)是否具有前后綴匹配來實現(xiàn)。實際應(yīng)用中，特別是文本字符串匹配時，輸入的模式串很難經(jīng)常有前后綴自相匹配的情況。因此，針對于這方面的改進算法，匹配時間比BF算法沒有明顯的降低，甚至比BF算法耗費的時間更長，這是因為改進算法在移動跳躍之前，還要對模式串遍歷和比較。而Sunday算法通過模式串尾部字符與目標串相應(yīng)字符比較，獲得盡可能大的跳躍距離，避免了重復(fù)字符匹配。因此，Sunday算法大大提高了匹配效率。

由表2實驗結(jié)果可以看出，在不同大小的文本字符串匹配中，GPU并行的Sunday算法與傳統(tǒng)Sunday算法維持約3倍的加速比。GPU先天強大的并行處理能力為字符串并行匹配提供了良好的工具。在實際程序運行中，GPU線程的分配和結(jié)果數(shù)據(jù)的回傳占用了較多的時間，盡管如此，字符串的匹配速度還是獲得了較大的提升。與此同時，將模式串存儲到共享內(nèi)存的方式也避免了頻繁訪問顯存帶來的額外時間開銷，因為顯存的讀寫速度比共享內(nèi)存的速度慢得多。

4結(jié)語

本文在分析字符串匹配并行執(zhí)行特點的基礎(chǔ)上，利用GPU數(shù)據(jù)并行化的架構(gòu)特點，設(shè)計出適合于GPU運行的快速字符串匹配算法。雖然算法使得字符串匹配速度有所提升，但是還有較大的改進空間，將字符串匹配放在顯卡上進行還可以進一步提高字符讀取速度，提高字符匹配效率。

參考文獻參考文獻：

＼[1＼]谷岳，谷建華.基于GPU加速的并行字符串匹配算法[J].微電子學與計算機，2013（9）：3033.

[2]潘冠華，張興忠.Sunday算法效率分析[J].計算機應(yīng)用，2012（11）：30823084，3088.

[3]陳國良，林潔，顧乃杰. 分布式存儲的并行串匹配算法的設(shè)計與分析[J].軟件學報，2000（6）： 771778.

[4]唐定車，劉任任，譚建龍.基于統(tǒng)一計算設(shè)備架構(gòu)的并行串匹配算法[J].計算機應(yīng)用，2009（1）： 399401.

[5][美]科克，胡文美.大規(guī)模并行處理器編程實戰(zhàn)[M].北京：清華大學出版社，2010：3177.

責任編輯（責任編輯：杜能鋼）