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

在審

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

本發明一種基于CUDA的快速非重疊模板匹配計算方法，屬于基于CUDA的快速非重疊模板匹配計算技術領域；所要解決的技術問題為：提供一種基于CUDA的快速非重疊模板匹配計算方法，使隨機性測試做到高速或實時測試；解決該技術問題采用的技術方案為：預先搭建用于非重疊模板匹配計算的CUDA環境，包括CPU端和GPU端；采集待檢測樣本數據，并將數據存儲于CPU端；在GPU端分配存儲空間，將檢測數據與模板從CPU傳至GPU端；將每條待檢測數據序列分為N個長度為M的子塊，控制GPU端并行計算長度為m的模板在第i個子塊序列中發生的次數W_i；將所述W_i值傳回CPU端進行P?value計算；本發明應用于非重疊模板匹配計算。

技術領域

本發明一種基于CUDA的快速非重疊模板匹配計算方法，屬于基于CUDA的快速非重疊模板匹配計算技術領域。

背景技術

隨機數廣泛應用于擴頻通信，科學計算，數值分析，雷達測距和身份認證等科學研究和工程技術領域；尤其在密碼學領域，隨機數被廣泛應用于密鑰產生，初始化向量，安全協議，數字水印，碼分多址和大素數產生等方面，由于密碼體制的安全性在一定程度上由隨機數決定，一段有缺陷的隨機序列可能導致整個密碼系統的信息泄露，因此生成隨機數必須經過嚴格的統計學特征來論證其特性；隨機性測試就是通過概率統計的方法計算被測序列包含的某些參數來評估其隨機性，其中NIST SP 800-22標準經過嚴格的理論推導和實驗分析，從各個方面對隨機數及隨機數發生器進行評估，其專業性和權威性已經被國際信息安全界廣泛認可，成為最具代表性的測試標準。

雖然目前的隨機數發生器已經可以達到很高的速率，但是隨機性測試的速度卻遠遠不能與之匹配，因此無法對隨機數做到高速甚至實時測試；NIST發布的測試標準中包含單比特頻數測試、塊內頻數測試、游程測試、塊內最大游程測試、二元矩陣秩測試、離散傅立葉變換測試、非重疊模板匹配測試、重疊模板匹配測試、Maurer的通用統計測試、線性復雜度測試、序列測試、近似熵測試、累加和測試、隨機游動測試以及隨機游動狀態頻數測試等15個測試項。經過測驗，利用NIST官方發布的的測試套件sts-2.1.2測試1GB隨機數文本(ASCII格式)耗時高達一小時左右(所用CPU為Intel core i7-3770，物理核心數為4個，主頻3.4GHz，帶寬25.6GB/s，主機的內存為8GB)，而其中涉及非重疊模板匹配測試用時最多，如圖二所示，占總測試耗時的36％左右；非重疊模板匹配測試將待檢序列分為若干個長度為M比特的不重疊子塊，然后統計每個子塊中預先定義的模式串的發生次數，通過實測模式串的出現次數與預期數之間的匹配程度來評估被測序列的隨機性。假設模式串長度為m位，如果匹配窗口中m位的模式串與序列逐一配對成功，那么窗口向后移動m位繼續搜索，否則，窗口只向后移動一位。在NIST官方發布的的測試套件sts-2.1.2中非重疊模板匹配測試通過CPU進行計算，計算速度慢，無法實現對隨機數進行高速甚至實時測試。由此可見，在利用NIST測試對隨機數的質量進行評估時，如何提高非重疊模板匹配測試的速度是本領域技術人員亟待解決的問題。

發明內容

本發明為了克服現有技術中存在的不足，所要解決的技術問題為：提供一種基于CUDA的快速非重疊模板匹配計算方法，使隨機性測試做到高速或實時測試。

為了解決上述技術問題，本發明采用的技術方案為：一種基于CUDA的快速非重疊模板匹配計算方法，包括以下步驟：

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

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

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

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