數(shù)據(jù)流字符串匹配算法并行化運(yùn)行與性能測(cè)試

邢光升

摘要：該文實(shí)驗(yàn)?zāi)M數(shù)據(jù)流在本地或集群分布式處理的條件下，多線程多進(jìn)程、CPU+GPU異構(gòu)等處理模式的字符串匹配測(cè)試，研究了在多進(jìn)程，多線程下最佳并行運(yùn)行節(jié)點(diǎn)數(shù)，GPU最佳優(yōu)化參數(shù)設(shè)置，CPU+GPU異構(gòu)環(huán)境下最佳搭配優(yōu)化方案。

關(guān)鍵詞：字符串匹配;CPU;GPU;測(cè)試優(yōu)化;多線程;多進(jìn)程

中圖分類(lèi)號(hào)：TP3? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）16-0278-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

網(wǎng)絡(luò)數(shù)據(jù)處理過(guò)程中對(duì)于高速帶寬環(huán)境下關(guān)鍵包快速識(shí)別提取要求較高，現(xiàn)行常用的做法是基于硬件的深度包檢測(cè)設(shè)備（DPI），盡管該設(shè)備針對(duì)五元組和關(guān)鍵字匹配識(shí)別的性能強(qiáng)悍，現(xiàn)行可以達(dá)到40Gbps線速，幾百萬(wàn)條五元組匹配和幾十萬(wàn)條關(guān)鍵字匹配的性能，但由于其可擴(kuò)展性差，不能與后面其他的軟件程序松耦合度的靈活結(jié)合，且價(jià)格昂貴，通常一臺(tái)DPI設(shè)備一塊10Gbps處理板卡需要幾十萬(wàn)的價(jià)格，因此更多的用在海量高速網(wǎng)絡(luò)數(shù)據(jù)處理當(dāng)中，對(duì)于對(duì)線速處理要求一般，關(guān)鍵字匹配條數(shù)不多的情況就可以直接在通用的X86平臺(tái)或者集群下實(shí)現(xiàn)，甚至在帶有GPU卡的平臺(tái)環(huán)境下高效運(yùn)行，如何有效地利用有限的資源最大程度地提高匹配速度成了需要研究的重點(diǎn)。

實(shí)驗(yàn)?zāi)M數(shù)據(jù)流在本地或集群分布式處理的條件下，字符串匹配挖掘，主要包括多線程多進(jìn)程、CPU+GPU異構(gòu)等處理模式，給定關(guān)鍵字對(duì)整個(gè)數(shù)據(jù)流進(jìn)行搜索匹配，并對(duì)處理過(guò)程進(jìn)行記時(shí)，觀察對(duì)比并行化處理下的效果，并且查找優(yōu)化在并行運(yùn)行過(guò)程中最佳優(yōu)化時(shí)間，并記錄此時(shí)綁定的核數(shù)。研究在多進(jìn)程，多線程下最佳并行運(yùn)行節(jié)點(diǎn)數(shù)，GPU最佳優(yōu)化參數(shù)設(shè)置，CPU+GPU異構(gòu)環(huán)境下最佳搭配優(yōu)化方案。

1 實(shí)驗(yàn)條件及環(huán)境

（1）帶GTX系列顯卡筆記本兩臺(tái)：主要用于程序代碼編寫(xiě)，程序編譯、調(diào)試;

（2）天河二超算平臺(tái)：程序在CPU環(huán)境下并行運(yùn)行測(cè)試（多進(jìn)程 多線程）;

（3）帶GTX1070卡的GPU工作站：CPU+GPU處理模式調(diào)式測(cè)試;

（4）模擬字符串?dāng)?shù)據(jù)文件，大小500MB。

2 實(shí)驗(yàn)原理及思路

2.1 多線程/進(jìn)程字符串匹配算法

該算法是基于樸素字符串匹配改進(jìn)成的可以進(jìn)行多進(jìn)程實(shí)現(xiàn)的。字符串匹配算法主要是兩個(gè)循環(huán)嵌套，但是兩個(gè)循環(huán)都是相互獨(dú)立的，所以我們每次滑動(dòng)的窗口從原來(lái)的1，變?yōu)檫M(jìn)程數(shù)n，也就是每個(gè)進(jìn)程每次只識(shí)別匹配字段的長(zhǎng)度，然后跳到n個(gè)字符后繼續(xù)識(shí)別。最后再把每個(gè)進(jìn)程所計(jì)算部分匹配的字符串總數(shù)規(guī)約到0號(hào)進(jìn)程，統(tǒng)一輸出。

2.2 CUDA流編程實(shí)現(xiàn)思路

CUDA流在加速應(yīng)用程序方面起著重要的作用。CUDA流表示一個(gè)GPU操作隊(duì)列，并且該隊(duì)列中的操作將以指定的順序執(zhí)行。我們可以在流中添加一些操作，如核函數(shù)啟動(dòng)，內(nèi)存復(fù)制等。將這些操作添加到流的順序也就是他們的執(zhí)行順序?？梢詫⒘饕暈橛行虻牟僮餍蛄校渲屑窗瑑?nèi)存復(fù)制操作，又包含核函數(shù)調(diào)用。然而，在硬件中沒(méi)有流的概念，而是包含一個(gè)或多個(gè)引擎來(lái)執(zhí)行內(nèi)存復(fù)制操作，以及一個(gè)引擎來(lái)執(zhí)行核函數(shù)。

因此，在某種程度上，用戶(hù)與硬件關(guān)于GPU工作的排隊(duì)方式有著完全不同的理解，而CUDA驅(qū)動(dòng)程序則負(fù)責(zé)對(duì)用戶(hù)和硬件進(jìn)行協(xié)調(diào)。首先，在操作被添加到流的順序中包含了重要的依賴(lài)性。CUDA驅(qū)動(dòng)程序需要確保硬件的執(zhí)行單元不破壞流內(nèi)部的依賴(lài)性。也就是說(shuō)，CUDA驅(qū)動(dòng)程序負(fù)責(zé)安裝這些操作的順序把它們調(diào)度到硬件上執(zhí)行，這就維持了流內(nèi)部的依賴(lài)性。

2.3 GPU+CPU異構(gòu)算法實(shí)現(xiàn)思路

主要按比例將實(shí)驗(yàn)數(shù)據(jù)分配到GPU眾核模式和CPU多線程模式中進(jìn)行檢測(cè)，GPU控制獨(dú)占一個(gè)線程，其他線程優(yōu)化分配處理分配到CPU中的數(shù)據(jù)，延伸出的問(wèn)題是，由于GPU獨(dú)占一個(gè)線程，可能會(huì)破壞了原有單獨(dú)測(cè)試CPU多線程模式的最佳工作狀態(tài)，因此在具體測(cè)試過(guò)程中將CPU線程數(shù)加入考慮。

2.4 GPU熱啟動(dòng)問(wèn)題及解決思路

任何一個(gè)CUDA程序，在第一次調(diào)用CUDAAPI時(shí)后都要花費(fèi)毫秒級(jí)的時(shí)間去初始化運(yùn)行環(huán)境，后續(xù)還要分配顯存，傳輸數(shù)據(jù)，啟動(dòng)內(nèi)核，每一樣都有延遲。為了解決這一問(wèn)題，保證測(cè)試時(shí)間的正確性，因此在測(cè)試過(guò)程中測(cè)試過(guò)程循環(huán)運(yùn)行多次，保證GPU在第一次調(diào)用后完全實(shí)現(xiàn)熱啟動(dòng)。

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

我們把實(shí)驗(yàn)整體分為三個(gè)部分，分別是：

（1）MPI編程實(shí)現(xiàn)數(shù)據(jù)流字符串匹配算法在天河平臺(tái)的多進(jìn)程運(yùn)算效率優(yōu)化測(cè)試;

（2）OpenMP編程實(shí)現(xiàn)數(shù)據(jù)流字符串匹配算法在天河平臺(tái)的多線程運(yùn)算效率優(yōu)化測(cè)試;

（3）CUDA編程CPU+GPU模式下的關(guān)鍵字符串匹配程序，在GPU工作站上進(jìn)行CPU+GPU異構(gòu)運(yùn)算效率優(yōu)化測(cè)試。

1）多進(jìn)程部分

2）多線程部分

3）GPU+CPU異構(gòu)部分

（1）首先完成在工作站（gtx1070ti）環(huán)境下最優(yōu)block和thread點(diǎn)測(cè)試，截圖并記錄不同點(diǎn)下的結(jié)果。先找到每個(gè)block的最大線程數(shù)量，是否時(shí)最佳運(yùn)行效率。然后再找到每種GPU下最佳效率點(diǎn)的block數(shù)，判斷是否時(shí)最大block承載數(shù)。

（a）測(cè)試每個(gè)block內(nèi)thread數(shù)量極限及對(duì)于運(yùn)行效率的影響，此時(shí)固定block數(shù)量為38，分別測(cè)試thread數(shù)量在32、64、128、256、512、1024、1025、2048時(shí)候的運(yùn)行情況。

由上述實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，對(duì)于gtx1070ti顯卡來(lái)說(shuō)，其每個(gè)block最大thread數(shù)量為1024，超過(guò)這個(gè)數(shù)量運(yùn)行會(huì)報(bào)錯(cuò)，同時(shí)1024也是最佳運(yùn)行效率點(diǎn)。

（b）測(cè)試block數(shù)量對(duì)于運(yùn)行效率的影響。接（1）中測(cè)試結(jié)果固定每個(gè)block中thread數(shù)量為1024，分別測(cè)試block數(shù)量為1、4、8、16、32、34、36、37、38、39、40，觀察運(yùn)行結(jié)果

由實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，對(duì)于gtx1070ti顯卡來(lái)說(shuō)，在block數(shù)量為36-38時(shí)運(yùn)行效率較高，超過(guò)38運(yùn)行效率會(huì)下降，這與查閱資料得到的結(jié)論block數(shù)量為Multiprocessor數(shù)量?jī)杀稌r(shí)能夠充分利用SM資源達(dá)到運(yùn)行效率最佳的結(jié)論相吻合，gtx1070ti的Multiprocessor數(shù)量為19，由實(shí)驗(yàn)結(jié)果可知可以適用于一般實(shí)驗(yàn)結(jié)論。

結(jié)合上述兩個(gè)顯卡的實(shí)驗(yàn)結(jié)果結(jié)合查詢(xún)資料，目前流行的GTX顯卡系列單個(gè)block數(shù)量支持最佳（最大）thread數(shù)量為1024，最佳block數(shù)量為Multiprocessor數(shù)兩倍。

（2）以之前測(cè)試的最優(yōu)CUDA流數(shù)量和每個(gè)CUDA流分配數(shù)據(jù)量的最佳優(yōu)化點(diǎn)作為GPU多CUDA流的基礎(chǔ)運(yùn)行參數(shù)，分別進(jìn)行CPU+GPU異構(gòu)環(huán)境下的初始優(yōu)化測(cè)試。

在實(shí)際測(cè)試過(guò)程中取CPU線程數(shù)2-16，CPU數(shù)據(jù)占比0.05-0.95（粒度為0.05）進(jìn)行測(cè)試，在實(shí)際測(cè)試過(guò)程中發(fā)現(xiàn)在工作站環(huán)境下測(cè)試優(yōu)化比較煩瑣，存在多個(gè)最佳優(yōu)化組合區(qū)域。

可以發(fā)現(xiàn)存在以下優(yōu)化組合區(qū)間，在CPU分配數(shù)據(jù)占比為0.05時(shí)，CPU優(yōu)化線程數(shù)為1、2;在CPU分配數(shù)據(jù)占比為0.1時(shí)，CPU優(yōu)化線程數(shù)為3、4、5;在CPU分配數(shù)據(jù)占比為0.15時(shí)，CPU優(yōu)化線程數(shù)為3、4、5;在CPU分配數(shù)據(jù)占比為0.2時(shí)，CPU優(yōu)化線程數(shù)為7、8;在線程數(shù)為3，數(shù)據(jù)占比為0.1和在線程數(shù)為7，數(shù)據(jù)占比為0.2時(shí)能夠達(dá)到比較好的優(yōu)化效果，有較大概率能夠達(dá)到優(yōu)化時(shí)間在210ms以下。

4 結(jié)語(yǔ)

通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn)，對(duì)比三種并行化手段，在相同算法并行方式的條件下，MPI的多進(jìn)程并行對(duì)500MB數(shù)據(jù)的字符串匹配，最快可以做到206ms;OpenMP的多線程并行，最快可以做到271ms;以CPU+GPU的異構(gòu)形式的多線程并行，在線程數(shù)為3，數(shù)據(jù)占比為0.1和在線程數(shù)為7，數(shù)據(jù)占比為0.2時(shí)能夠達(dá)到比較好的優(yōu)化效果，最快可以達(dá)到206ms。在CPU+GPU異構(gòu)的條件下我們?cè)诠ぷ髡局信艹龅慕Y(jié)果可以和天河平臺(tái)中跑出的結(jié)果基本相當(dāng)，而單塊gtx1070ti的價(jià)格遠(yuǎn)比天河集群的單節(jié)點(diǎn)都是12核至強(qiáng)E5的CPU的價(jià)格低得多，整個(gè)工作站的配置費(fèi)用也比服務(wù)器集群低得多，這說(shuō)明在字符串匹配方面眾核GPU+CPU異構(gòu)模式在特定場(chǎng)景下比CPU集群有更高的性?xún)r(jià)比，證明CPU+GPU異構(gòu)在字符串匹配算法的并行優(yōu)化是有意義的。下一步在日常的工作學(xué)習(xí)中還要進(jìn)一步研究各種情況下的并行優(yōu)化設(shè)計(jì)，以及GPU的高效運(yùn)用。

【通聯(lián)編輯：代影】