[發明專利]一種基于圖形處理單元的非確定有限自動機的匹配方法及裝置

有效

• 申請號: 201210290345.6
• 申請日: 2012-08-15
• 公開（公告）號: CN102902713A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 董群峰
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京凱特來知識產權代理有限公司 11260
• 代理人: 鄭立明;趙鎮勇

1.一種基于圖形處理單元的非確定有限自動機的匹配方法，其特征在于，包括：

計算非確定有限自動機NFA中所有狀態兩兩之間的相容性，并根據所述相容性對所述各個狀態進行編碼形成虛擬NFA，以獲得虛擬NFA對應的虛擬NFA狀態轉換表；其中，所述相容性是指，若NFA中的兩個狀態在NFA匹配過程中不同時處于活躍狀態，則該兩個狀態相容，否則，為不相容；

將所述虛擬NFA狀態轉換表存儲在圖形處理單元GPU的全局存儲器中，并基于該虛擬NFA狀態轉換表匹配經過交織處理的待處理數據包中數據。

2.根據權利要求1所述的方法，其特征在于，所述計算NFA中所有狀態兩兩之間的相容性的步驟包括：

針對NFA狀態建立N×N的二維表，N為NFA的狀態數目，NFA狀態依次為0，1，2，…，N-1；在該二維表中，第i+1行和第j+1列的表項由[i，j]表示；如果狀態i和j是相容的，則表項[i，j]內容設置為true，如果狀態i和j是不相容的，則表項[i，j]內容設置為false；其中，分別將表項[0，0]，[1，1]，[2，2]，…，[N-1，N-1]的內容置為false；

建立初始為空的第一隊列queue并進行初始化，依次將狀態對(0，0)，(1，1)，(2,2)，…，(N-1，N-1)壓入第一隊列queue中；

彈出第一隊列queue首部的狀態對(i，j)，使用狀態i，j遍歷全部可能的輸入字符0-255查詢NFA狀態，其中，以當前輸入字符作為轉換字符，以狀態i為源狀態，查詢該NFA狀態獲得目的狀態集合Di，以狀態j為源狀態，查詢該NFA狀態獲得目的狀態集合Dj；檢查狀態集合Di和狀態集合Dj的并集Di∪Dj，并將該并集當中的任意兩個狀態所組成的狀態對（s，t）對應的所述二維表表項內容置為false，若狀態對（s，t）所對應的二維表表項中的內容之前記錄為true，則還需要將狀態對（s，t）壓入第一隊列queue的尾部；

判斷第一隊列queue是否非空，如果是，過程結束，否則，繼續再執行所述彈出第一隊列queue首部的狀態對(i，j)的步驟。

3.根據權利要求1或2所述的方法，其特征在于，所述根據所述相容性對所述各個狀態進行編碼形成虛擬NFA的步驟包括：

根據所述相容性將NFA中的所有狀態分組，獲得至少一個相容組，所述相容組中的任意兩個狀態之間相容；

將得到的所述相容組合并獲得超級相容組，再對所述超級相容組進行編碼形成虛擬狀態，并獲得虛擬NFA。

4.根據權利要求3所述的方法，其特征在于，所述根據所述相容性將NFA中的所有狀態分組，獲得至少一個相容組的步驟包括：

獲得空的第二隊列queue，在建立的無向圖中一次或多次選取邊度數最大的一條邊，將該邊對應的兩個頂點對應的狀態壓入所述第二隊列queue，并從該無向圖當中去除這條邊，更新剩余無向圖當中各項頂點度數和邊度數；其中，所述無向圖的頂點為NFA的一個狀態，邊為NFA中兩個不相容的狀態對應的頂點之間的連線，頂點度數為與該頂點相連的邊的總數目，邊度數為該邊所關聯的兩個頂點的頂點度數之和；

在建立的無向圖中一次或多次選取邊度數最大的一條邊的過程中，若當前被選中邊從無向圖當中移除，剩余圖變為空，則這條邊不壓入第二隊列queue，拆分這條邊的兩個關聯頂點，各自構成一個單元素的獨立集，再使用第二隊列queue中收集的邊對應的狀態對構成新的無向圖，并執行所述獲得空的第二隊列queue的步驟，所述的獨立集對應一個相容組；若剩余無向圖中不存在邊并且非空，則將無向圖中剩余頂點構成一個頂點獨立集，將第二隊列queue中與該獨立集中的狀態相容的NFA狀態加入該獨立集中，再使用第二隊列queue中剩余的頂點構成新的無向圖，并執行所述獲得空的第二隊列queue的步驟；若第二隊列queue空，則過程結束。

5.根據權利要求3所述的方法，其特征在于，所述將得到的所述相容組合并獲得超級相容組的步驟包括：

按照相容組狀態數的大小進行降序排序，得到降序排列的相容組集合；

從所述降序排列的相容組集合中依次順序取出相容組并加入到當前占用比特數最少的超級相容組當中，同時更新該超級相容組占用的比特數，其中，每個超級相容組初始占用的比特數為0。