邢光升

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

關鍵詞：字符串匹配;CPU;GPU;測試優(yōu)化;多線程;多進程

中圖分類號：TP3? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）16-0278-02

開放科學（資源服務）標識碼（OSID）：

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

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

1 實驗條件及環(huán)境

（1）帶GTX系列顯卡筆記本兩臺：主要用于程序代碼編寫，程序編譯、調試;

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

（3）帶GTX1070卡的GPU工作站：CPU+GPU處理模式調式測試;

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

2 實驗原理及思路

2.1 多線程/進程字符串匹配算法

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

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

CUDA流在加速應用程序方面起著重要的作用。CUDA流表示一個GPU操作隊列，并且該隊列中的操作將以指定的順序執(zhí)行。我們可以在流中添加一些操作，如核函數(shù)啟動，內存復制等。將這些操作添加到流的順序也就是他們的執(zhí)行順序。可以將流視為有序的操作序列，其中即包含內存復制操作，又包含核函數(shù)調用。然而，在硬件中沒有流的概念，而是包含一個或多個引擎來執(zhí)行內存復制操作，以及一個引擎來執(zhí)行核函數(shù)。

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

2.3 GPU+CPU異構算法實現(xiàn)思路

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

2.4 GPU熱啟動問題及解決思路

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

3 實驗結果

我們把實驗整體分為三個部分，分別是：

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

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

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

1）多進程部分

2）多線程部分

3）GPU+CPU異構部分

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

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

由上述實驗結果可以發(fā)現(xiàn)，對于gtx1070ti顯卡來說，其每個block最大thread數(shù)量為1024，超過這個數(shù)量運行會報錯，同時1024也是最佳運行效率點。

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

由實驗結果可以發(fā)現(xiàn)，對于gtx1070ti顯卡來說，在block數(shù)量為36-38時運行效率較高，超過38運行效率會下降，這與查閱資料得到的結論block數(shù)量為Multiprocessor數(shù)量兩倍時能夠充分利用SM資源達到運行效率最佳的結論相吻合，gtx1070ti的Multiprocessor數(shù)量為19，由實驗結果可知可以適用于一般實驗結論。

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

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

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

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

4 結語

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

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