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

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

• 摘要4-5
• ABSTRACT5-10
• 第一章 緒論10-14
• 1.1 課題背景10-12
• 1.1.1 模式匹配應(yīng)用廣泛10-11
• 1.1.2 網(wǎng)絡(luò)安全問題突出11
• 1.1.3 傳統(tǒng)入侵檢測系統(tǒng)的發(fā)展瓶頸11-12
• 1.2 課題研究內(nèi)容及意義12-13
• 1.3 論文組織結(jié)構(gòu)13-14
• 第二章 通用GPU計(jì)算研究14-20
• 2.1 GPGPU體系結(jié)構(gòu)14-15
• 2.2 OpenCL 框架15-18
• 2.2.1 OpenCL平臺(tái)模型15-16
• 2.2.2 OpenCL存儲(chǔ)模型16-17
• 2.2.3 OpenCL執(zhí)行模型17-18
• 2.3 本章小結(jié)18-20
• 第三章 大規(guī)模精確模式串匹配技術(shù)研究20-42
• 3.1 軟件精確模式串匹配技術(shù)及其研究現(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 硬件精確模式串匹配技術(shù)及其研究現(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ī)模精確模式串匹配算法設(shè)計(jì)28-32
• 3.3.1 改進(jìn) Trie 樹28-29
• 3.3.2 狀態(tài)轉(zhuǎn)換表分割29-30
• 3.3.3 大規(guī)模精確模式串匹配SPAC算法30-32
• 3.4 基于GPU&CPU的大規(guī)模精確模式串匹配算法實(shí)現(xiàn)32-38
• 3.4.1 Trie 樹節(jié)點(diǎn)編號(hào)重排序32-34
• 3.4.2 GPU匹配部分34-36
• 3.4.3 CPU匹配部分36-38
• 3.5 實(shí)驗(yàn)評估38-40
• 3.5.1 實(shí)驗(yàn)平臺(tái)38
• 3.5.2 實(shí)驗(yàn)數(shù)據(jù)38
• 3.5.3 實(shí)驗(yàn)方法38-39
• 3.5.4 實(shí)驗(yàn)結(jié)果39-40
• 3.6 本章小結(jié)40-42
• 第四章 高速正則表達(dá)式匹配技術(shù)研究42-64
• 4.1 正則表達(dá)式匹配技術(shù)42-48
• 4.1.1 正則表達(dá)式基本概念42-43
• 4.1.2 正則表達(dá)式與有限自動(dòng)機(jī)43-47
• 4.1.2.1 有限自動(dòng)機(jī)基本概念43-44
• 4.1.2.2 正則表達(dá)式構(gòu)造NFA44-45
• 4.1.2.3 NFA到DFA的轉(zhuǎn)換45-47
• 4.1.2.4 DFA 最小化47
• 4.1.3 正則表達(dá)式匹配47-48
• 4.2 正則表達(dá)式匹配技術(shù)研究現(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的高速正則表達(dá)式匹配算法設(shè)計(jì)52-56
• 4.3.1 DFA正則表達(dá)式匹配52-53
• 4.3.2 數(shù)據(jù)并行訪問53-54
• 4.3.3 邊界問題的處理54-55
• 4.3.4 高速正則表達(dá)式匹配算法框架55-56
• 4.4 基于GPU&CPU的高速正則表達(dá)式匹配算法實(shí)現(xiàn)56-59
• 4.4.1 GPU并行數(shù)據(jù)讀取56-57
• 4.4.2 GPU匹配部分實(shí)現(xiàn)57-58
• 4.4.3 CPU匹配部分實(shí)現(xiàn)58-59
• 4.5 實(shí)驗(yàn)評估59-61
• 4.5.1 實(shí)驗(yàn)平臺(tái)59-60
• 4.5.2 實(shí)驗(yàn)數(shù)據(jù)60
• 4.5.3 實(shí)驗(yàn)方法60-61
• 4.5.4 實(shí)驗(yàn)結(jié)果61
• 4.6 本章小結(jié)61-64
• 第五章 總結(jié)與展望64-66
• 5.1 本文工作總結(jié)64
• 5.2 展望64-66
• 參考文獻(xiàn)66-70
• 致謝70-72
• 攻讀學(xué)位期間發(fā)表或已錄用的學(xué)術(shù)論文72

【參考文獻(xiàn)】

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

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

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

本文編號(hào)：296722