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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 方建文;于金輝;陳海英;;三維卡通水與物體交互作用的動(dòng)畫(huà)建模[A];中國(guó)計(jì)算機(jī)圖形學(xué)進(jìn)展2008--第七屆中國(guó)計(jì)算機(jī)圖形學(xué)大會(huì)論文集[C];2008年

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

1 樂(lè)山　樂(lè)水;圖形處理技術(shù)的全球?qū)＠季中蝿?shì)[N];中國(guó)知識(shí)產(chǎn)權(quán)報(bào);2010年

2 嚴(yán)威川;明明白白顯卡“芯”[N];中國(guó)電腦教育報(bào);2007年

3 ;NEC圖形處理器每秒運(yùn)行50.2G條指令[N];計(jì)算機(jī)世界;2003年

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

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

6 均兒;人人都有臺(tái)超級(jí)計(jì)算機(jī)[N];電腦報(bào);2008年

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

8 本報(bào)記者 田夢(mèng);Adobe CS4全面支持GPU加速[N];計(jì)算機(jī)世界;2009年

9 趙欣;“玩”3D，筆記本也行！[N];中國(guó)計(jì)算機(jī)報(bào);2003年

10 ;HP Compaq Evo D210教育信息化的好幫手[N];中國(guó)計(jì)算機(jī)報(bào);2003年

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

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

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

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

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

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

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

1 黃偉鈿;面向移動(dòng)平臺(tái)的3D圖形處理器的設(shè)計(jì)[D];華南理工大學(xué);2011年

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

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

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

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

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

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

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

9 楊新強(qiáng);基于GPU加速FDTD計(jì)算速度的研究與仿真[D];青島大學(xué);2011年

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

，

本文編號(hào)：2587689