【摘要】：最早為圖形渲染而專門設(shè)計的圖形處理器(GPU),因其越來越強大的浮點運算能力和大規(guī)模并行處理能力,時至今日在通用計算領(lǐng)域也得到了廣泛的應(yīng)用,并且在科學計算領(lǐng)域獲得了極大成功。GPU通用計算已成為當前工業(yè)界和學術(shù)界的研究熱點。面對急劇增長的網(wǎng)絡(luò)流量和包處理復(fù)雜度,網(wǎng)絡(luò)設(shè)備面臨越來越大的計算壓力,利用GPU提高網(wǎng)絡(luò)設(shè)備的處理能力成為GPU通用計算又一個新的應(yīng)用領(lǐng)域。然而與科學計算領(lǐng)域以計算密集型問題為主、數(shù)據(jù)并行性易于利用不同,網(wǎng)絡(luò)計算領(lǐng)域以訪存密集型和I/O密集型任務(wù)為主,且數(shù)據(jù)并行性難以挖掘和利用。將GPU應(yīng)用于網(wǎng)絡(luò)處理領(lǐng)域需對既有算法進行并行化再設(shè)計,使之適應(yīng)GPU的體系結(jié)構(gòu),以充分利用GPU的大規(guī)模并行計算能力。本論文選擇正則表達式匹配和數(shù)據(jù)無損壓縮兩個尚未有效解決的問題,研究它們在GPU上的高效實現(xiàn)方法。正則表達式匹配無論是用硬件還是軟件、在CPU上還是在GPU上實現(xiàn),都面臨難以調(diào)和的時空兩難問題�；贒FA的正則表達式匹配速度快,但存在空間爆炸的問題；基于NFA的正則表達式匹配空間復(fù)雜度低,但匹配速度也慢。論文在深入研究GPU架構(gòu)特點及NFA特征的基礎(chǔ)上,提出一種高效的NFA實現(xiàn)方法。無損數(shù)據(jù)壓縮無論是采用基于字典的壓縮技術(shù)還是基于統(tǒng)計的壓縮技術(shù),數(shù)據(jù)壓縮操作的數(shù)據(jù)間依賴性都很強,數(shù)據(jù)并行性難以挖掘和利用,GPU特有的單指令流多數(shù)據(jù)流并行執(zhí)行模式又進一步增加了并行化的難度。論文研究以上兩種壓縮技術(shù)的代表性算法-基于字典的LZSS壓縮算法和基于統(tǒng)計的哈夫曼編碼算法在GPU上的高效實現(xiàn),并在此基礎(chǔ)上完成了基于這兩種技術(shù)的Deflate數(shù)據(jù)壓縮算法的并行化。論文的主要貢獻和創(chuàng)新點如下：1針對正則表達式匹配的時空兩難問題,論文以空間復(fù)雜度最低的NFA作為正則表達式匹配的基礎(chǔ)實現(xiàn),通過引入狀態(tài)兼容組、兼容超級組、虛擬NFA狀態(tài)等概念優(yōu)化線程的任務(wù)分配,并通過數(shù)據(jù)包交織存儲、全局存儲器歸并訪問等技術(shù)提高線程的訪存效率,實現(xiàn)了正則表達式匹配在GPU上的高效實現(xiàn)。該工作首次解決了正則表達式匹配的時空兩難問題,在獲得10Gbps匹配速度的同時仍然保持算法的線性空間復(fù)雜度。2針對基于字典的無損數(shù)據(jù)壓縮算法LZSS在GPU上并行化程度低的問題,本文以哈希表作為字典的基礎(chǔ)實現(xiàn),通過精巧的數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計有效解決了并行化LZSS算法中最困難的線程串行化問題,并顯著減少了對GPU計算資源的使用。該項工作在壓縮率和壓縮速率兩個方面都明顯優(yōu)于目前在GPU上加速LZSS算法的最好工作。3本文在Deflate無損數(shù)據(jù)壓縮算法的上下文中研究哈夫曼編碼算法在GPU上的并行化,通過精巧的算法設(shè)計和CUDA原子操作有效解決了直方圖計算、哈夫曼樹構(gòu)建和變長編碼的并行化問題。該工作系首次在GPU上完成了Deflate算法的并行化實現(xiàn),在壓縮率接近Deflate算法的同時,壓縮速率超過四核CPU上的Deflate算法實現(xiàn)。本文工作在高效實現(xiàn)正則表達式匹配和無損數(shù)據(jù)壓縮在GPU上并行化的同時,也為其它算法在GPU上的高效實現(xiàn)提供了方法性指導(dǎo)及技術(shù)參考。
【學位授予單位】：中國科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：TP332

【相似文獻】

相關(guān)期刊論文 前10條

1 ;NVIDIA GeForce FX被評為2002年最佳圖形處理器[J];CAD/CAM與制造業(yè)信息化;2003年Z1期

2 李海燕;張春元;李禮;任巨;;圖形處理器的流執(zhí)行模型[J];計算機工程;2008年22期

3 ;MathWorks為MATLAB提供GPU支持[J];電子與電腦;2010年10期

4 楊毅;郭立;史鴻聲;郭安泰;;面向移動設(shè)備的3D圖形處理器設(shè)計[J];小型微型計算機系統(tǒng);2009年08期

5 ;MathWorks為MATLAB提供GPU支持[J];電信科學;2010年10期

6 ;MathWorks為MATLAB提供GPU支持[J];中國電子商情(基礎(chǔ)電子);2010年10期

7 ;MathWorks為MATLAB提供GPU支持[J];電信科學;2010年S2期

8 韓俊剛;劉有耀;張曉;;圖形處理器的歷史現(xiàn)狀和發(fā)展趨勢[J];西安郵電學院學報;2011年03期

9 ;產(chǎn)品推介[J];電子產(chǎn)品世界;2012年09期

10 ;產(chǎn)業(yè)信息[J];單片機與嵌入式系統(tǒng)應(yīng)用;2013年12期

相關(guān)會議論文 前7條

1 張春燕;;一種基于圖形處理器的數(shù)據(jù)流計算模式[A];全國第19屆計算機技術(shù)與應(yīng)用（CACIS）學術(shù)會議論文集（下冊）[C];2008年

2 徐侃;陳如山;杜磊;朱劍;楊陽;;可編程圖形處理器加速無條件穩(wěn)定的Crank-Nicolson FDTD分析三維微波電路[A];2009年全國微波毫米波會議論文集（下冊）[C];2009年

3 周國亮;馮海軍;何國明;陳紅;李翠平;王珊;;基于圖形處理器的Cuboid算法[A];第26屆中國數(shù)據(jù)庫學術(shù)會議論文集（B輯）[C];2009年

4 畢文元;陳志強;;利用可編程圖形處理器加速CT重建與體數(shù)據(jù)的繪制[A];第十一屆中國體視學與圖像分析學術(shù)會議論文集[C];2006年

5 劉偉峰;楊權(quán)一;曹邦功;孟凡密;周潔;;基于GPU的高度并行Marching Cubes改進算法[A];2008年全國開放式分布與并行計算機學術(shù)會議論文集(上冊)[C];2008年

6 林旭生;田緒紅;馮志煒;陳茂資;;GPU加速的蟻群算法在HP模型中的應(yīng)用[A];第十四屆全國圖象圖形學學術(shù)會議論文集[C];2008年

7 方建文;于金輝;陳海英;;三維卡通水與物體交互作用的動畫建模[A];中國計算機圖形學進展2008--第七屆中國計算機圖形學大會論文集[C];2008年

相關(guān)重要報紙文章 前10條

1 樂山　樂水;圖形處理技術(shù)的全球?qū)＠季中蝿輀N];中國知識產(chǎn)權(quán)報;2010年

2 嚴威川;明明白白顯卡“芯”[N];中國電腦教育報;2007年

3 ;NEC圖形處理器每秒運行50.2G條指令[N];計算機世界;2003年

4 游訊;圖形處理器GPU[N];人民郵電;2011年

5 本報記者 姜姝;AMD嵌入式技術(shù)為波音飛機保駕護航[N];中國信息化周報;2014年

6 均兒;人人都有臺超級計算機[N];電腦報;2008年

7 ;AMD啟動“Fusion”企業(yè)品牌推廣計劃[N];人民郵電;2008年

8 本報記者 田夢;Adobe CS4全面支持GPU加速[N];計算機世界;2009年

9 趙欣;“玩”3D，筆記本也行！[N];中國計算機報;2003年

10 ;HP Compaq Evo D210教育信息化的好幫手[N];中國計算機報;2003年

相關(guān)博士學位論文 前5條

1 祖淵;基于圖形處理器的高速并行算法研究[D];中國科學技術(shù)大學;2014年

2 楊珂;基于圖形處理器的數(shù)據(jù)管理技術(shù)研究[D];浙江大學;2008年

3 穆帥;針對不規(guī)則應(yīng)用的圖形處理器資源調(diào)度關(guān)鍵技術(shù)研究[D];清華大學;2013年

4 夏健明;基于圖形處理器的大規(guī)模結(jié)構(gòu)計算研究[D];華南理工大學;2009年

5 黃濤;基于GPU的多點地質(zhì)統(tǒng)計逐點模擬并行算法的研究[D];中國科學技術(shù)大學;2013年

相關(guān)碩士學位論文 前10條

1 黃偉鈿;面向移動平臺的3D圖形處理器的設(shè)計[D];華南理工大學;2011年

2 王旭;圖形處理器的仿真驗證[D];哈爾濱工業(yè)大學;2007年

3 陳林樺;基于圖形處理器的視頻轉(zhuǎn)換技術(shù)的研究與應(yīng)用[D];上海交通大學;2009年

4 張楊;圖形處理器并行計算應(yīng)用研究[D];西南交通大學;2006年

5 闕恒;嵌入式圖形處理器設(shè)計[D];南京航空航天大學;2007年

6 饒志恒;圖形處理器圖形管線的研究與實現(xiàn)[D];湖南大學;2011年

7 楊國東;嵌入式圖形處理器的研究與實現(xiàn)[D];山東大學;2010年

8 王晉君;圖形處理器在錐束CT成像中的應(yīng)用研究[D];首都師范大學;2009年

9 楊新強;基于GPU加速FDTD計算速度的研究與仿真[D];青島大學;2011年

10 李凱倫;基于計算機圖形處理器的海底三維地形可視化[D];哈爾濱工程大學;2013年

，

本文編號：2587689