[發明專利]基于GPU計算的字符串匹配方法和系統

有效

• 申請號: 201310509249.0
• 申請日: 2013-10-23
• 公開（公告）號: CN103559018A
• 公開（公告）日: 2014-02-05
• 發明（設計）人: 侯智瀚;楊梟
• 申請（專利權）人: 東軟集團股份有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京鴻元知識產權代理有限公司 11327
• 代理人: 陳英俊

技術領域

本發明涉及信息識別技術領域，更為具體地，涉及一種基于GPU計算的字符串匹配方法和系統。

背景技術

隨著網絡技術的不斷發展和日益豐富的網絡應用，對網絡的攻擊方式層出不窮，因此網絡安全產品也集成了越來越多的安全功能，如入侵防御系統、病毒檢測、垃圾郵件檢測、應用識別等，網絡安全產品的應用需要以對通過的網絡流量進行深度數據報文檢測為基礎，但是深度報文檢測的模式匹配是制約整個安全產品系統性能的瓶頸。

隨著GPU(Graphic?Processing?Unit，圖形處理器)技術的發展，GPU已經成為適合高并行性和計算量大的應用處理核心。由CPU和GPU組成的異構計算機為計算領域帶來了一場革命。通過將工作負載的不同部分匹配到最適合的處理器，可以極大地提升計算機的性能，并且GPU在低成本的并行計算和良好的擴展性等方面的優點使其成為安全產品系統中一種字符串匹配的新的執行模型。

圖1示出了現有的基于GPU的字符串匹配方法流程。

如圖1所示，現有的基于GPU的字符串匹配方法流程包括：首先對特征串集合進行預處理，形成通常是二維數組的自動機狀態轉換表，并將該表拷貝到GPU全局存儲器中且與紋理存儲器綁定，使用帶有Cache（高速緩沖存儲器）的紋理存儲器可以提高訪存的效率，并在主機內存中采用雙緩沖區機制分別用于存儲積攢的網絡數據報文和復制到GPU存儲器中；然后啟動大量線程對數據報文進行字符串匹配處理，數據報文存儲在GPU全局存儲器或紋理存儲器中（或再從GPU全局存儲器拷貝到共享存儲器中以降低訪存延時）接著在GPU中執行匹配函數；最終將匹配結果從GPU存儲器復制到CPU主存中。

在國內外已有的基于GPU的字符串匹配方法中，在GPU上進行字符串匹配主要有兩種方法，第一種是數據并行，比如專利申請號為201010539214.8的中國專利申請所公開的基于GPU的高速網絡報文內容檢測方法，該專利申請披露了該方法執行的方式，將數據報文分成多個片段，然后每個片段啟動一個線程執行字符串匹配工作；第二種是任務并行，比如臺灣清華大學的Cheng-Hung?Lin，Chen-Hsiung?Liu，Lung-Sheng?Chien和Shih-Chieh?Chang四人在ieee上發表的論文《Accelerating?Pattern?Matching?Using?a?Novel?Parallel?Algorithm?on?GPUs》（2012年12月），其中論述了以下執行方式：在GPU上啟動與數據報文字符長度相等數量的線程，每個字符都作為匹配工作的開始位置，對應著一個線程。

上述兩種進行字符串匹配的方法各自存在著不足。

在數據并行方式中，采用每個線程匹配等長的數據報文片段，因此每個線程處理的字符位置間隔較大，不利于集中訪存，對于有Cache機制就會造成大量Cache的換進換出操作，增加了匹配過程中的訪存開銷。并且需要較大的數據報文才能啟動足夠數量的線程發揮GPU并行處理的優勢。字符串匹配算法分支較多，多模字符串匹配算法在匹配失敗時需要回退處理，由于GPU較差的邏輯處理能力，多模字符串匹配算法的執行流程包含過多的分支將造成GPU處理單元執行效率降低。同時，還需要考慮“邊緣檢測”的情況，即匹配命中的數據位于兩個片段分片的位置。

在任務并行方式中，每個字符都作為起始偏移，啟動一個線程進行匹配。每字節的任務并行方式會啟動大量的線程，即使有的線程執行時間較短，但是大量線程的啟動也會有很大的時間開銷。并且，每個啟動的線程至少都會有兩次訪存操作，包括：從待匹配數據讀值以及查找狀態轉換表。所以線程增加的同時也增加了內存訪問的次數，進而影響性能。最后，每個線程都會返回一個結果，那么將匹配結果復制到CPU主存也會占用很多的時間。

因此，以上兩種現有的進行字符串匹配的方法都各自存在著效率不高的問題。

發明內容

鑒于上述問題，本發明的目的是提供一種基于GPU計算的字符串匹配方法和系統，以解決cache利用率低、啟動線程數量多和訪存開銷大等問題，從而提升特征字符串匹配過程的性能。

本發明提供的基于GPU計算的字符串匹配方法，包括CPU預處理階段和GPU匹配階段；其中，

在CPU預處理階段的過程中：對特征字符串進行預處理；其中，首先構建位向量掩碼表，并根據位向量掩碼表生成快速過濾子表；將位向量掩碼表和快速過濾子表拷貝到GPU全局存儲器；

分別在CPU主存和GPU全局存儲器上分配待匹配數據緩存和結果緩存；