，

(中原工學(xué)院，鄭州 450007)

隨著計(jì)算機(jī)硬件技術(shù)的迅速發(fā)展，計(jì)算機(jī)硬盤(pán)更新?lián)Q代的頻率越來(lái)越快，硬盤(pán)存儲(chǔ)能力也越來(lái)越大，T數(shù)量級(jí)的硬盤(pán)正逐漸成為基本的配置,這為人們存儲(chǔ)更多的數(shù)據(jù)和文件提供了有利條件。伴隨著大數(shù)據(jù)時(shí)代產(chǎn)生的海量信息，電腦硬盤(pán)里的文件也越來(lái)越多，這給數(shù)據(jù)挖掘、敏感信息發(fā)現(xiàn)帶來(lái)新的挑戰(zhàn)。此外，在進(jìn)行數(shù)據(jù)挖掘和敏感信息檢查時(shí),不僅僅是文件名檢查，還包括文件內(nèi)容的提取分析。在大的硬盤(pán)下遍歷搜索所有文件的內(nèi)容，如果設(shè)計(jì)的搜索算法不合理，將極大增加分析時(shí)間成本，影響數(shù)據(jù)分析的檢查效果,尤其是當(dāng)數(shù)據(jù)檢查工作量較大時(shí)，可能成為不可承受之重。

當(dāng)前多核處理器得到了廣泛的應(yīng)用。在單機(jī)多核的架構(gòu)下, 由于單個(gè)線程在某一時(shí)刻僅能被一個(gè)處理器執(zhí)行，傳統(tǒng)的單線程串行算法不能充分有效地利用多核處理器的計(jì)算資源[1-2]，只有采用并行計(jì)算的方式，才能有效利用系統(tǒng)資源。

本文提出了一種基于多核處理器的并行搜索技術(shù)。根據(jù)系統(tǒng)的CPU數(shù)量以及GPU等硬件信息，基于多核處理器技術(shù)設(shè)計(jì)并行搜索算法，結(jié)合C++AMP等最新并行編程技術(shù)，通過(guò)任務(wù)均衡調(diào)度算法，實(shí)現(xiàn)各線程的任務(wù)均衡，從而實(shí)現(xiàn)低延遲、高吞吐量和高響應(yīng)度的并行計(jì)算，提高對(duì)CPU、GPU等資源的利用率，對(duì)數(shù)據(jù)信息進(jìn)行高效挖掘，為數(shù)據(jù)挖掘、敏感信息發(fā)現(xiàn)等技術(shù)研究奠定較好的基礎(chǔ)。

1 相關(guān)技術(shù)的應(yīng)用

1.1 并行搜索

并行計(jì)算設(shè)計(jì)主要有兩種方式：其一，向量化設(shè)計(jì)，主要適用于流水作業(yè)超標(biāo)量處理機(jī)調(diào)度；其二，采用多線程技術(shù)進(jìn)行任務(wù)分治，主要適用于多處理機(jī)及集群方式[3]。本文設(shè)計(jì)的并行搜索技術(shù)采用的就是這種多線程技術(shù)任務(wù)分治方法。

在傳統(tǒng)意義上，GPU一直是作為圖形圖像專(zhuān)用處理器。但是，在操作系統(tǒng)支持下GPU也可以完成一些通用的計(jì)算任務(wù)。因此，可以將并行計(jì)算從多核CPU擴(kuò)展到多核CPU與GPU共同組成的異構(gòu)硬件平臺(tái)上。其主要技術(shù)有兩種：一種是并行異構(gòu)編程O(píng)penCL，這是眾多軟硬件廠商共同支持的面向異構(gòu)系統(tǒng)的通用并行編程開(kāi)放框架，技術(shù)相對(duì)成熟；另一種則是微軟推出的C++ AMP(Accelerated Massive Parallelism，加速大規(guī)模并行計(jì)算)編程模型[4]。這兩種框架都是底層支持的并行循環(huán)模式技術(shù)，前者更局限于對(duì)圖形的處理，后者具有更好的通用性和易用性。

1.2 文本的編碼方式及內(nèi)容分割技術(shù)

并行搜索需要調(diào)用多個(gè)內(nèi)核完成一個(gè)文本的快速匹配搜索，將待搜索的文本內(nèi)容分割成若干段，以實(shí)現(xiàn)多個(gè)搜索步驟同時(shí)執(zhí)行。在分割過(guò)程中會(huì)出現(xiàn)兩個(gè)問(wèn)題：一是如何避免將一個(gè)檢索詞(或稱(chēng)為匹配串)分到不同段落里;二是如何避免將一個(gè)字符的字節(jié)分到不同段落里。

針對(duì)問(wèn)題一，本文采用冗余法。除第一段之外，其余每段的開(kāi)頭需要向前一個(gè)段落的末尾至少冗余讀取一定長(zhǎng)度的字節(jié)，字節(jié)的長(zhǎng)度等于檢索詞(或稱(chēng)為匹配串)的長(zhǎng)度。即如果一個(gè)文本里有檢索詞，就可以確保在某個(gè)段落里至少會(huì)有一個(gè)完整的檢索詞，保證能夠搜索到該檢索詞。

問(wèn)題二關(guān)系到文本的編碼方式問(wèn)題，因?yàn)橐粋€(gè)字符可用不同的編碼方式表示，保存在文本中的“0、1”代碼不同，用的字節(jié)個(gè)數(shù)不同。文本的編碼方式主要有4種，分別是ANSI、Unicode、Unicode big edian和UTF-8。字符“A”、“程”、“B”、“序”文本編碼如表1所示，表中用4種編碼分別表示“A”、“程”、“B”、“序”這4個(gè)字符的“0、1代碼”。

ANSI編碼是默認(rèn)的編碼方式，ANSI編碼中英文字符表示使用標(biāo)準(zhǔn)ASCII編碼，標(biāo)準(zhǔn)ASCII是單字節(jié)編碼系統(tǒng)。其中第一位作為奇偶校驗(yàn)碼，后7位總共可以表示128個(gè)字符。其他符號(hào)和漢字用GB2312編碼(只針對(duì)Windows簡(jiǎn)體中文版，如果是繁體中文版會(huì)采用Big5碼)表示，即每一個(gè)漢字及符號(hào)用兩個(gè)字節(jié)來(lái)表示。GB2312編碼規(guī)定：一個(gè)字節(jié)的碼值小于127，即表示此字符與標(biāo)準(zhǔn)ASCII編碼表示的字符相同。針對(duì)ANSI編碼，解決方法是判斷一個(gè)字節(jié)的碼值。如果碼值小于127，則該字符是一個(gè)英文字符；否則，該字符是一個(gè)漢字或是符號(hào)的一部分。然后，再根據(jù)GB2312 編碼表判斷該字符是否是一個(gè)有效漢字。用此方法可避免將一個(gè)漢字(或是符號(hào))分到不同的段落中。

表1 字符“A”“程”“B”“序”文本編碼表

Unicode編碼主要指的是UCS-2編碼方式，即直接用兩個(gè)字節(jié)表示一個(gè)字符。Unicode編碼對(duì)任何字符都是采用兩個(gè)字節(jié)編碼。對(duì)Unicode編碼分割時(shí)，采用每段分的字節(jié)個(gè)數(shù)都是2的倍數(shù)，這樣就可以避免將一個(gè)字符分到不同的段落里。

從表1 可以看出，Unicode編碼選用的little endian編碼格式，它與Unicode big endian編碼選用的big endian編碼格式的高低字節(jié)剛好相反。采用與Unicode編碼相同的方法分段，即可解決分段時(shí)遇到的問(wèn)題二。

UTF-8編碼是一種針對(duì)Unicode的可變長(zhǎng)度字符編碼，用1～4個(gè)字節(jié)編碼Unicode字符。表2是UTF-8編碼與Unicode編碼轉(zhuǎn)換規(guī)則表。

表2 UTF-8編碼與Unicode編碼轉(zhuǎn)換規(guī)則表

從表2可以看出，如果一個(gè)字節(jié)的第一位是0，那么此UTF-8格式字符就占一個(gè)字節(jié)，并且是一個(gè)英文字符；如果一個(gè)字節(jié)的第一位是1，那么此UTF-8格式字符肯定是漢字(只有英文和中文的文檔)；從第二位、第三位、第四位這3個(gè)位是0還是1，可以確定此UTF-8格式字符占幾個(gè)字節(jié)。如果一個(gè)字節(jié)的第一位是1，而第二位是0，則此字節(jié)是一個(gè)字符的中間字節(jié)。針對(duì)UTF-8編碼，通過(guò)此方法可以避免在分割文本內(nèi)容時(shí)將一個(gè)UTF-8字符分到兩個(gè)段里。

2 并行搜索模型

2.1 并行循環(huán)搜索模型

異步代理庫(kù)和PPL模式庫(kù)將編程者引入了一種全新的并行編程模型[5]，在很大程度上簡(jiǎn)化了C++開(kāi)發(fā)者在CPU上編寫(xiě)并行程序的工作。為使C++開(kāi)發(fā)者利用GPU并行編程，微軟于2011年6月推出了C++AMP 異構(gòu)并行編程框架，并在2012年2月的Going Native大會(huì)上發(fā)布了C++AMP的開(kāi)放規(guī)范，在開(kāi)發(fā)工具中正式提供了對(duì)它的支持。C++開(kāi)發(fā)者可以將并行計(jì)算從單純的多核CPU擴(kuò)展到多核CPU與GPU共同組成的異構(gòu)硬件平臺(tái)上[4]。本文采用C++AMP中的并行循環(huán)方法——Parallel_for_each實(shí)現(xiàn)并行搜索。

并行循環(huán)的執(zhí)行順序是不確定的，在并行條件下各步驟的操作通常會(huì)同步進(jìn)行，甚至有時(shí)候兩個(gè)步驟的操作順序會(huì)與它們?cè)诖醒h(huán)中的情況完全相反。但是可以保證的是，當(dāng)循環(huán)完成時(shí)，所有的步驟都會(huì)被執(zhí)行到[5]。本文的并行搜索只需要返回檢索到的結(jié)果，然后對(duì)各個(gè)線程得到的結(jié)果進(jìn)行整理，得出最后的結(jié)論。并行搜索對(duì)單個(gè)結(jié)果的順序沒(méi)有嚴(yán)格的要求，符合并行循環(huán)的特點(diǎn)。

并行循環(huán)一般適用于執(zhí)行一些具有獨(dú)立性的迭代操作，這意味著并行循環(huán)處理的多組數(shù)據(jù)之間必須具有獨(dú)立性操作，它們之間不存在對(duì)本地內(nèi)存或磁盤(pán)文件的共同寫(xiě)操作[5]。本文采取的方法是將搜索文本分割成若干段，段與段之間的操作具有獨(dú)立性，且它們之間不存在對(duì)本地內(nèi)存或磁盤(pán)文件的共同寫(xiě)操作。所以，本文的文本搜索符合并行循環(huán)模式。

本文的目的是測(cè)試并行循環(huán)搜索模型與多線程并行搜索模型的性能，所以，分割段數(shù)分別是處理器個(gè)數(shù)的1倍、2倍和3倍(針對(duì)2核計(jì)算機(jī)，為了作比較，4核計(jì)算機(jī)是1/2倍、1倍和2倍)。用分割段初始化數(shù)組vc，數(shù)組vc中有多少個(gè)元素，就有多少個(gè)線程來(lái)并行執(zhí)行該搜索任務(wù)，這些線程會(huì)同時(shí)調(diào)用多個(gè)處理器來(lái)完成搜索任務(wù)，達(dá)到快速搜索的目的。

并行循環(huán)搜索算法描述如下：

①根據(jù)分割情況建立數(shù)組vc，即將每段作為vc的一個(gè)元素；

②并行循環(huán)搜索

parallel_for_each(

vc.extent；

[&](index<1> idx) restrict(amp)

{

Thread_Strindex_BF(idx，vc，ntemp，flag)；

}

)；

參數(shù)說(shuō)明：

第一個(gè)參數(shù)是vc.extent，用于描述并行搜索拓?fù)浣Y(jié)構(gòu)的對(duì)象，vc中有多少個(gè)元素，就可以指定多少個(gè)線程并行執(zhí)行這個(gè)搜索任務(wù);

第二個(gè)參數(shù)是一個(gè)lambda表達(dá)式。Thread_Strindex_BF是匹配搜索函數(shù)，每一個(gè)并行的搜索線程都會(huì)執(zhí)行這個(gè)函數(shù)。參數(shù)idx是線程編號(hào)，參數(shù)vc是被匹配段，ntemp是每個(gè)段落中的字節(jié)個(gè)數(shù)，flag是檢索詞(或稱(chēng)匹配串)。從被匹配串的第1個(gè)字節(jié)開(kāi)始找第一個(gè)與flag相等的子串，直至每個(gè)段的最后一個(gè)字節(jié)為止，成功,返回“1”，否則,返回“0”。

2.2 多線程并行模式

多線程并行模式是指運(yùn)行程序創(chuàng)建多個(gè)并行執(zhí)行的線程來(lái)完成各自的任務(wù)。在多線程程序中，當(dāng)一個(gè)線程必須等待時(shí)，CPU 可以運(yùn)行其他線程而不用等待，大大提高了程序效率。但是，并不是開(kāi)的線程數(shù)越多，搜索的速度就會(huì)越快，因?yàn)榫€程之間的切換也需要花費(fèi)時(shí)間，所以開(kāi)線程需要考慮到它的綜合性能，可以開(kāi)與處理器個(gè)數(shù)相等的線程數(shù)，這樣每個(gè)CPU上運(yùn)行一個(gè)線程，不用來(lái)回切換，充分利用每個(gè)處理器資源。如果計(jì)算機(jī)采用的是超線程，即一個(gè)CPU上運(yùn)行兩個(gè)線程，開(kāi)的線程數(shù)可以是處理器個(gè)數(shù)的兩倍。為了測(cè)試兩種并行搜索的性能，開(kāi)的線程數(shù)與并行循環(huán)搜索模型的線程數(shù)相同。多線程并行搜索模型如圖1所示。

圖1 多線程并行搜索模型

多線程并行搜索模型先通過(guò)任務(wù)分割技術(shù)將文本內(nèi)容分割成n個(gè)段，根據(jù)分割后的段和搜索函數(shù)創(chuàng)建n個(gè)線程，開(kāi)啟并執(zhí)行這些線程，得到各個(gè)線程運(yùn)行結(jié)果，然后整理得出最后的結(jié)論。

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

本文主要研究異構(gòu)并行計(jì)算循環(huán)搜索模型與多線程搜索模型的不同性能，為基于多核處理器的并行搜索技術(shù)找到更好的搜索模型，因此有必要對(duì)這兩種并行搜索模型的實(shí)驗(yàn)結(jié)果進(jìn)行分析比較。

3.1 實(shí)驗(yàn)環(huán)境

采用兩核電腦1臺(tái)，電腦配置型號(hào)：Intel(R) Core(TM)2 Duo；CPU：E4600 @2.40GHz；內(nèi)存：4GB；操作系統(tǒng)：windows7 32位。

采用四核8線程電腦1臺(tái)，電腦配置型號(hào)：Intel(R) Core(TM)i7；CPU：870 @2.93GHz；內(nèi)存：8GB；操作系統(tǒng)：windows7 64位。

3.2 結(jié)果分析

通過(guò)在兩核處理器和四核處理器的計(jì)算機(jī)上對(duì)同一個(gè)文件不同線程進(jìn)行測(cè)試，得到不同的測(cè)試結(jié)果，如圖2和圖3所示。

圖2 兩核處理器計(jì)算機(jī)對(duì)同一文件不同線程測(cè)試結(jié)果

從圖2可以看出，在兩核處理器計(jì)算機(jī)上并行循環(huán)搜索的速度優(yōu)于多線程搜索速度，多線程搜索模型中4個(gè)線程比2個(gè)線程的速度要快，而8個(gè)線程的速度介于2個(gè)線程和4個(gè)線程之間。這說(shuō)明并不是并行的線程數(shù)越多，速度就會(huì)越快。要根據(jù)處理器的數(shù)量，合理創(chuàng)建并行線程數(shù)。并行循環(huán)搜索模型與多線程搜索模型比較，有稍許變化，8個(gè)元素的并行循環(huán)不比4個(gè)元素的并行循環(huán)速度慢，但是搜索速度提高非常小。按此規(guī)律推斷，隨著并行元素?cái)?shù)量的增加，搜索速度同樣不會(huì)提高反而會(huì)降低。在這一點(diǎn)上，兩者的特點(diǎn)是相同的。在500 MB的搜索范圍內(nèi)，并行循環(huán)搜索的3個(gè)模型之間的差別沒(méi)有多線程搜索模型明顯，這說(shuō)明并行循環(huán)搜索模型在這個(gè)范圍內(nèi)的速度都很快，也說(shuō)明并行循環(huán)搜索模型優(yōu)于多線程搜索模型。

由圖3可知，四核計(jì)算機(jī)與兩核計(jì)算機(jī)相比，情況基本類(lèi)似?？傮w而言，并行循環(huán)的搜索速度優(yōu)越，而且在四核計(jì)算機(jī)上運(yùn)行時(shí)，多線程搜索模型中的2個(gè)線程的搜索速度幾乎沒(méi)有什么變化，4個(gè)線程和8個(gè)線程的搜索速度則得到了提高。與圖2相比，變化最明顯的是8個(gè)線程的搜索速度比4個(gè)線程的搜索速度快。這說(shuō)明需要合理創(chuàng)建并行線程數(shù)，才能得到較好的性能。

總體來(lái)說(shuō)，不管是在兩核處理器電腦上還是在四核處理器電腦上，并行循環(huán)搜索模式都比多線程搜索模式搜索的速度優(yōu)越，也說(shuō)明將C++AMP異構(gòu)并行編程運(yùn)用于文本內(nèi)容的搜索，可提高搜索性能，并且在某種程度上是優(yōu)于多線程搜索的。

圖3 四核處理器計(jì)算機(jī)對(duì)同一文件不同線程測(cè)試結(jié)果

4 結(jié) 語(yǔ)

本文利用多核處理器平臺(tái)的處理性能，通過(guò)并行循環(huán)搜索模式和多線程并行搜索模式，使得文本內(nèi)容搜索速度得到提升。對(duì)解決大容量硬盤(pán)、大數(shù)據(jù)的海量信息搜索奠定了很好的基礎(chǔ)，有利于數(shù)據(jù)挖掘和敏感信息等技術(shù)的研究。隨著多核處理器的快速發(fā)展，基于多核處理器的文本內(nèi)容搜索技術(shù)研究會(huì)有重要的意義，本文的研究順應(yīng)多核技術(shù)發(fā)展的趨勢(shì)。有些廠商正嘗試將GPU和CPU融合在一起，如果將來(lái)的處理器上集成了GPU和CPU，并且可以通過(guò)一條總線將二者與內(nèi)存直接連在一起，本文的研究會(huì)有更大的價(jià)值。

參考文獻(xiàn):

[1] Knuth D E, Morris J H, Pratt V R.Fast Patternmatching in Strings[J].SIAM Journal of Computing，1997, 6(2):323-350.

[2] 伊君翰.基于多核處理器的并行編程模型[J].計(jì)算機(jī)工程,2009, 35(8):62-64.

[3] 陳國(guó)良.并行算法的設(shè)計(jì)和分析[M].北京：高等教育出版社,2009:16-26.

[4] 陳冠誠(chéng).C++ AMP異構(gòu)并行編程解析[J].程序員,2012(4):30-34.

[5] Colin C, Ade M.Visual C++并行編程實(shí)戰(zhàn)[M].凌杰，譯.北京：機(jī)械工業(yè)出版社,2012:22-26.