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

有效

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

1.一種基于GPU計算的字符串匹配方法，包括CPU預處理階段和GPU匹配階段；其中，?

在所述CPU預處理階段的過程中：?

對所述特征字符串進行預處理；其中，首先構建位向量掩碼表，并根據所述位向量掩碼表生成快速過濾子表；然后將所述位向量掩碼表和所述快速過濾子表拷貝到GPU全局存儲器；?

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

對待匹配數據進行預處理，并將預處理后的待匹配數據從所述CPU主存中的所述待匹配數據緩存中復制到所述GPU全局存儲器中的所述待匹配數據緩存中保存；?

在所述GPU匹配階段的過程中，?

根據對所述特征字符串進行預處理所構建的位相量掩碼表以及生成的快速過濾子表，采用GPU多線程任務并行執行方式對每個GPU線程中的預處理后的待匹配數據分別與預處理后的所述特征字符串前綴和所述特征字符串后綴進行匹配；?

將匹配成功的待匹配數據與相應的所述特征字符串逐字進行確認，并保存在所述結果緩存中，最后將結果緩存的數據拷貝到所述CPU主存中的所述結果緩存中。?

2.如權利要求1所述的基于GPU計算的字符串匹配方法，其中，?

在所述CPU預處理階段的過程中，?

將拷貝有所述位向量掩碼表和所述快速過濾子表的所述GPU全局存儲器與紋理存儲器綁定；?

將保存有所述待匹配數據的GPU全局存儲器與所述紋理存儲器綁定。?

3.如權利要求2所述的基于GPU計算的字符串匹配方法，其中，?

在通過GPU多線程任務并行執行方式對預處理后的待匹配數據與所述特?征字符串前綴和所述特征字符串后綴分別進行匹配的過程中，?

根據所述每個GPU線程的標識確定預處理后的待匹配數據的起始偏移，根據第一特征字符串前綴的長度和第二特征字符串前綴的長度確定所述GPU線程的匹配窗口；?

從距離所述預處理后的待匹配數據的起始偏移的第一特征字符串前綴長度的位置上，獲取一個算法字符，根據所述算法字符在所述紋理存儲器中查到所述快速過濾子表的相應比特位，根據所述相應比特位判斷所述GPU線程是否繼續執行；如果所述相應比特位為0，結束所述GPU線程執行，如果所述相應比特位為1，則所述GPU線程繼續執行；?

如果所述相應比特位為1時，根據所述算法字符在所述紋理存儲器中查到所述位向量掩碼表獲取一個位向量掩碼值，將所述位向量掩碼值設為初始狀態向量，以所述算法字符的位置作為起點，在所述GPU線程的匹配窗口內正向依次獲取所述算法字符，以位并行方式進行向量更新，在所述向量更新過程中，所述預處理后的待匹配數據與所述特征字符串后綴進行匹配；?

根據所述特征字符串后綴的匹配結果，將在以位并行方式進行向量更新中獲取的最后的狀態向量作為初始向量，以距離所述預處理后的待匹配數據的起始偏移的第二特征字符串前綴長度的位置作為起點，在所述GPU線程的匹配窗口內反向依次獲取算法字符，以位并行方式進行反向向量更新；在所述反向向量更新中，所述預處理后的待匹配數據與所述特征字符串前綴進行匹配。?

4.如權利要求3所述的基于GPU計算的字符串匹配方法，其中，?

在所述每個GPU線程在一個匹配窗口內進行字符串匹配的過程中，?

所述匹配窗口的長度等于一個第一特征字符串長度跟一個第二特征字符串長度的和；相鄰兩個所述GPU線程處理預處理后的待匹配數據的起始位置的距離為一個所述第一特征字符串長度。?