基于GPU加速的快速字符串匹配算法

續(xù)士強(qiáng)　祝永志

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

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

DOIDOI：10.11907/rjdk.143766

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）002005103

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

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

0引言

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

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

1CUDA編程模型

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

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

2基于GPU的Sunday算法并行化

2.1Sunday字符串匹配算法

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

Sunday算法實(shí)現(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è)計(jì)

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

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

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

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

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

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

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

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

2.3.2并行匹配

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

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

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； //計(jì)數(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實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(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，軟件平臺(tái)為CUDA 5.5，實(shí)驗(yàn)集成環(huán)境Visual Studio 2010。

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

表1不同算法消耗的匹配時(shí)間對(duì)比

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

匹配時(shí)間（ms）[]85.784 66[]215.690 48[]73.988 68

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

表2Sunday算法與GPU并行Sunday算法字符串匹配消耗時(shí)間對(duì)比

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

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

GPU匹配時(shí)間（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

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

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

4結(jié)語

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

參考文獻(xiàn)參考文獻(xiàn)：

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

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

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

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

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

責(zé)任編輯（責(zé)任編輯：杜能鋼）