[發明專利]一種基于CUDA的快速非重疊模板匹配計算方法

在審

• 申請號: 202010658627.1
• 申請日: 2020-07-09
• 公開（公告）號: CN111913798A
• 公開（公告）日: 2020-11-10
• 發明（設計）人: 張建國;侯銳;李凱凱;韓紅
• 申請（專利權）人: 太原理工大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 太原高欣科創專利代理事務所(普通合伙) 14109
• 代理人: 冷錦超;鄧東東

1.一種基于CUDA的快速非重疊模板匹配計算方法，其特征在于：包括以下步驟：

步驟一：預先搭建用于非重疊模板匹配計算的CUDA環境，包括CPU端和GPU端；

步驟二：采集待檢測樣本數據，并將數據存儲于CPU端；

步驟三：在GPU端分配存儲空間，將檢測數據與模板從CPU傳至GPU端；

步驟四：將每條待檢測數據序列分為N個長度為M的子塊，控制GPU端并行計算長度為m的模板在第i個子塊序列中發生的次數W_i；

步驟五：將所述W_i值傳回CPU端進行P-value計算，所述P-value為在假設序列隨機成立的情況下，錯誤被接受的概率。

2.根據權利要求1所述的一種基于CUDA的快速非重疊模板匹配計算方法，其特征在于：所述步驟四中控制GPU端并行計算所述待檢測樣本數據中匹配模板發生次數的具體包括：

定義運行在所述GPU端的Kernel核函數，以對所述待檢測樣本的多個子塊中模板的發生次數進行并行計算：

將所述待檢測樣本序列從CPU端傳輸至GPU的全局內存，根據所述模板數量確定并行計算時的所需線程塊以及線程的數量，依據預先設定的線程塊的參數和所述線程數量計算得到所述kernel核函數在并行計算時所對應的網格參數，在所述CPU端調用API函數以控制所述Kernel核函數在所述GPU端上運行，以得到所述的發生次數，并將計算得到的所述發生次數從GPU端傳輸至CPU端。

3.根據權利要求2所述的一種基于CUDA的快速非重疊模板匹配計算方法，其特征在于：所述步驟四中模板在子塊序列中發生次數的計算步驟為：

步驟4.1：將每條序列分為N個長度為M的子塊；

步驟4.2：使用二進制格式讀取隨機數數據后，用移位算法將m位隨機數倒序寫入整型數中，即將隨機數打包；

步驟4.3：使用移位算法將m位模板序列倒序寫入整型數中，即將模板序列打包；

步驟4.4：用一個m位模板序列打包后的模板串與連續的m位隨機數打包后的序列串進行匹配；

如果模板串=序列串，那么表示模板匹配成功一次，表示第i個子塊中模板B發生的次數W_i加一，并執行步驟4.5；

如果模板串≠序列串，則執行步驟4.6；

步驟4.5：將隨后的m位隨機數繼續打包生成一個新的序列串數據，重復步驟4.4；

步驟4.6：讀取一個新的隨機數，再將這個新的隨機數寫入序列串中的第8位，打包后生成一個新的序列串數據，然后重復步驟4.4。

4.根據權利要求3所述的一種基于CUDA的快速非重疊模板匹配計算方法，其特征在于：所述步驟四中控制GPU端進行數據并行計算處理具體為：將數據分塊產生的子塊序列均同時和模板序列進行匹配，實現子塊序列之間的并行計算；每條線程只負責一個模板的計算，實現模板之間的并行計算。