本文關鍵詞：基于眾核硬件的模式匹配算法加速技術研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：近年來隨著網(wǎng)絡化的發(fā)展,各行各業(yè)的數(shù)據(jù)呈現(xiàn)爆炸式增加態(tài)勢。據(jù)IDC預測,到2020年全球的數(shù)字信息總量將達到驚人的35ZB,信息內(nèi)容監(jiān)管將面臨巨大挑戰(zhàn)。模式匹配算法是文本處理領域基礎且非常重要的算法之一,廣泛應用在網(wǎng)絡入侵檢測、生物信息學、圖像處理等領域。 基于軟件實現(xiàn)的模式匹配算法,由于需要消耗大量的處理器資源和存儲資源,系統(tǒng)的實際性能往往不高,采用高性能的硬件來處理海量數(shù)據(jù)勢在必行。GPU是一種具有超強并行計算能力的眾核可編程硬件,目前已被用于加速模式匹配算法性能。本文旨在充分利用GPU、CPU各自的硬件特性,結合模式匹配算法的適用性,最終設計并實現(xiàn)高效的模式匹配算法。本論文主要的成果與貢獻如下： (1)模式匹配相關技術研究。本文詳細介紹了精確模式串匹配相關技術和正則表達式匹配相關技術,并分析了相關算法的優(yōu)缺點。 (2)提出了在CPU和GPU上實現(xiàn)的基于狀態(tài)轉換表(STT)分割的大規(guī)模精確模式串匹配SPAC算法。本算法主要解決由模式串集合生成的Trie樹對應STT在GPU中內(nèi)存占用過大的問題。實驗表明,SPAC算法可以在GPU上減少約50%的STT空間占用,在處理大規(guī)模精確模式串匹配時效果尤為明顯。 (3)提出了在CPU和GPU上實現(xiàn)的高速正則表達式匹配MDFA算法。本算法主要解決在GPU上進行正則表達式匹配時,文本塊之間的“邊界”問題處理,GPU進行多個子文本塊的并行處理,CPU對子文本塊的邊界進一步處理。實驗表明,當正則表達式集合對應的最大可匹配字符串較長(或限定可匹配長度較長)的情況下,MDFA算法可以有效的減少GPU中相鄰work-group之間冗余字符的比較。
【關鍵詞】：GPU 并行計算 精確模式串匹配 正則表達式匹配
【學位授予單位】：北京郵電大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP332;TP301.6
【目錄】：

• 摘要4-5
• ABSTRACT5-10
• 第一章 緒論10-14
• 1.1 課題背景10-12
• 1.1.1 模式匹配應用廣泛10-11
• 1.1.2 網(wǎng)絡安全問題突出11
• 1.1.3 傳統(tǒng)入侵檢測系統(tǒng)的發(fā)展瓶頸11-12
• 1.2 課題研究內(nèi)容及意義12-13
• 1.3 論文組織結構13-14
• 第二章 通用GPU計算研究14-20
• 2.1 GPGPU體系結構14-15
• 2.2 OpenCL 框架15-18
• 2.2.1 OpenCL平臺模型15-16
• 2.2.2 OpenCL存儲模型16-17
• 2.2.3 OpenCL執(zhí)行模型17-18
• 2.3 本章小結18-20
• 第三章 大規(guī)模精確模式串匹配技術研究20-42
• 3.1 軟件精確模式串匹配技術及其研究現(xiàn)狀20-26
• 3.1.1 單模式串匹配算法20-23
• 3.1.1.1 Knuth-Morris-Pratt(KMP)算法20-21
• 3.1.1.2 Horspool 算法21-23
• 3.1.2 多模式串匹配算法23-26
• 3.1.2.1 Trie 樹23-24
• 3.1.2.2 Aho-Corasick 算法24-26
• 3.1.3 軟件大規(guī)模精確模式串匹配的不足26
• 3.2 硬件精確模式串匹配技術及其研究現(xiàn)狀26-28
• 3.2.1 DPAC 算法26-27
• 3.2.2 PFAC 算法27
• 3.2.3 硬件大規(guī)模精確模式串匹配的不足27-28
• 3.3 基于GPU&CPU的大規(guī)模精確模式串匹配算法設計28-32
• 3.3.1 改進 Trie 樹28-29
• 3.3.2 狀態(tài)轉換表分割29-30
• 3.3.3 大規(guī)模精確模式串匹配SPAC算法30-32
• 3.4 基于GPU&CPU的大規(guī)模精確模式串匹配算法實現(xiàn)32-38
• 3.4.1 Trie 樹節(jié)點編號重排序32-34
• 3.4.2 GPU匹配部分34-36
• 3.4.3 CPU匹配部分36-38
• 3.5 實驗評估38-40
• 3.5.1 實驗平臺38
• 3.5.2 實驗數(shù)據(jù)38
• 3.5.3 實驗方法38-39
• 3.5.4 實驗結果39-40
• 3.6 本章小結40-42
• 第四章 高速正則表達式匹配技術研究42-64
• 4.1 正則表達式匹配技術42-48
• 4.1.1 正則表達式基本概念42-43
• 4.1.2 正則表達式與有限自動機43-47
• 4.1.2.1 有限自動機基本概念43-44
• 4.1.2.2 正則表達式構造NFA44-45
• 4.1.2.3 NFA到DFA的轉換45-47
• 4.1.2.4 DFA 最小化47
• 4.1.3 正則表達式匹配47-48
• 4.2 正則表達式匹配技術研究現(xiàn)狀48-52
• 4.2.1 D~2FA：Delayed input DFA48-49
• 4.2.2 A-DFA：A Time- and Space-Efficient DFA49-50
• 4.2.3 iNFAnt：GPU-based NFA Implementation50-52
• 4.3 基于GPU&CPU的高速正則表達式匹配算法設計52-56
• 4.3.1 DFA正則表達式匹配52-53
• 4.3.2 數(shù)據(jù)并行訪問53-54
• 4.3.3 邊界問題的處理54-55
• 4.3.4 高速正則表達式匹配算法框架55-56
• 4.4 基于GPU&CPU的高速正則表達式匹配算法實現(xiàn)56-59
• 4.4.1 GPU并行數(shù)據(jù)讀取56-57
• 4.4.2 GPU匹配部分實現(xiàn)57-58
• 4.4.3 CPU匹配部分實現(xiàn)58-59
• 4.5 實驗評估59-61
• 4.5.1 實驗平臺59-60
• 4.5.2 實驗數(shù)據(jù)60
• 4.5.3 實驗方法60-61
• 4.5.4 實驗結果61
• 4.6 本章小結61-64
• 第五章 總結與展望64-66
• 5.1 本文工作總結64
• 5.2 展望64-66
• 參考文獻66-70
• 致謝70-72
• 攻讀學位期間發(fā)表或已錄用的學術論文72

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 王敏杰;朱連軒;;基于Snort的模式匹配算法比較[J];現(xiàn)代電子技術;2011年13期

  本文關鍵詞：基于眾核硬件的模式匹配算法加速技術研究，由筆耕文化傳播整理發(fā)布。

本文編號：296722