數據流字符串匹配算法并行化運行與性能測試

邢光升

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

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

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

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

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

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

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

1 實驗條件及環境

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

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

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

（4）模擬字符串數據文件，大小500MB。

2 實驗原理及思路

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

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

2.2 CUDA流編程實現思路

CUDA流在加速應用程序方面起著重要的作用。CUDA流表示一個GPU操作隊列，并且該隊列中的操作將以指定的順序執行。我們可以在流中添加一些操作，如核函數啟動，內存復制等。將這些操作添加到流的順序也就是他們的執行順序?？梢詫⒘饕暈橛行虻牟僮餍蛄校渲屑窗瑑却鎻椭撇僮?，又包含核函數調用。然而，在硬件中沒有流的概念，而是包含一個或多個引擎來執行內存復制操作，以及一個引擎來執行核函數。

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

2.3 GPU+CPU異構算法實現思路

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

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

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

3 實驗結果

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

（1）MPI編程實現數據流字符串匹配算法在天河平臺的多進程運算效率優化測試;

（2）OpenMP編程實現數據流字符串匹配算法在天河平臺的多線程運算效率優化測試;

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

1）多進程部分

2）多線程部分

3）GPU+CPU異構部分

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

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

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

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

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

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

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

在實際測試過程中取CPU線程數2-16，CPU數據占比0.05-0.95（粒度為0.05）進行測試，在實際測試過程中發現在工作站環境下測試優化比較煩瑣，存在多個最佳優化組合區域。

可以發現存在以下優化組合區間，在CPU分配數據占比為0.05時，CPU優化線程數為1、2;在CPU分配數據占比為0.1時，CPU優化線程數為3、4、5;在CPU分配數據占比為0.15時，CPU優化線程數為3、4、5;在CPU分配數據占比為0.2時，CPU優化線程數為7、8;在線程數為3，數據占比為0.1和在線程數為7，數據占比為0.2時能夠達到比較好的優化效果，有較大概率能夠達到優化時間在210ms以下。

4 結語

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

【通聯編輯：代影】