基于多核處理器的文本并行搜索技術研究

，

(中原工學院，鄭州 450007)

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

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

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

1 相關技術的應用

1.1 并行搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

2 并行搜索模型

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

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

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

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

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

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

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

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

parallel_for_each(

vc.extent；

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

{

Thread_Strindex_BF(idx，vc，ntemp，flag)；

}

)；

參數(shù)說明：

第一個參數(shù)是vc.extent，用于描述并行搜索拓撲結構的對象，vc中有多少個元素，就可以指定多少個線程并行執(zhí)行這個搜索任務;

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

2.2 多線程并行模式

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

圖1 多線程并行搜索模型

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

3 實驗結果與分析

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

3.1 實驗環(huán)境

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

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

3.2 結果分析

通過在兩核處理器和四核處理器的計算機上對同一個文件不同線程進行測試，得到不同的測試結果，如圖2和圖3所示。

圖2 兩核處理器計算機對同一文件不同線程測試結果

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

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

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

圖3 四核處理器計算機對同一文件不同線程測試結果

4 結 語

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

參考文獻:

[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].計算機工程,2009, 35(8):62-64.

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

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

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