GPU平臺(tái)的論文
1 引言
數(shù)據(jù)壓縮被廣泛應(yīng)用于不同領(lǐng)域，這些領(lǐng)域通常涉及到大規(guī)模數(shù)據(jù)的處理與存儲(chǔ)，或者涉及到遠(yuǎn)距離的網(wǎng)絡(luò)數(shù)據(jù)傳輸。數(shù)據(jù)壓縮能夠有效地降低數(shù)據(jù)的存儲(chǔ)空間，并且可以減少網(wǎng)絡(luò)的傳輸時(shí)間。如圖1所示，由于采用了串行的方法，傳統(tǒng)的數(shù)據(jù)壓縮與解壓縮過程非常耗時(shí)，成為系統(tǒng)運(yùn)行的瓶頸。如果能夠有效利用目前硬件平臺(tái)的并行能力，降低壓縮與解壓縮所需的時(shí)間，系統(tǒng)性能(例如視頻解碼速度、實(shí)時(shí)網(wǎng)絡(luò)響應(yīng)時(shí)間等)將大大提高為了獲得比串行壓縮與解壓縮算法更好的性能，許多常用的壓縮與解壓縮工具都已經(jīng)采用了并行的實(shí)現(xiàn)方法。例如，WinZip和Winrar已經(jīng)使用塊級并行對多核系統(tǒng)進(jìn)行優(yōu)化，以實(shí)現(xiàn)數(shù)據(jù)級并行(datalevel parallelism，DLP)和線程級并行(thread levelparallelism，TLP)。這些工具背后的基本思想是將輸入數(shù)據(jù)分成多個(gè)小塊，再使用不同CPU核對每個(gè)數(shù)據(jù)塊進(jìn)行并行處理。圖形處理器(graphic processing unit，GPU)支持大規(guī)模的并行計(jì)算，被廣泛用于圖形圖像的加速處理中。在當(dāng)今的桌面系統(tǒng)與移動(dòng)終端上，GPU已經(jīng)成為了基本配置。因此如何利用GPU的計(jì)算能力來加速現(xiàn)有的壓縮與解壓縮算法成為了研究熱點(diǎn)。為了簡化GPU的編程模式，NVIDIA開發(fā)了統(tǒng)一計(jì)算設(shè)備架構(gòu)(compme unified device architecture，CUDA)平臺(tái)，使得CPU與GPu能夠協(xié)同處理。然而因?yàn)榛贕PU的CUDA是在單指令多數(shù)據(jù)(single instruction，multiple data，SIMD)模式下實(shí)現(xiàn)的，所以將常規(guī)的塊級并行壓縮技術(shù)直接移植到GPU上并非易事。
本文探究了基于字典的兩種無損壓縮技術(shù)：有狀態(tài)(statefu1)的壓縮與無狀態(tài)(stateless)的壓縮。這兩種壓縮技術(shù)的區(qū)別在于在壓縮或解壓縮的過程中是否需要維持相關(guān)的內(nèi)部狀態(tài)(即字典)。無狀態(tài)的壓縮/解壓縮算法，例如簡單的字典壓縮方法 、哈弗曼編碼(Huffman coding)等，是基于預(yù)先計(jì)算好的字典進(jìn)行數(shù)據(jù)的壓縮與解壓縮。而有狀態(tài)的算法，如LZW(Lempe1.Ziv—Welch)和算術(shù)編碼，在壓縮/解壓縮過程中需要?jiǎng)討B(tài)地構(gòu)建字典(或相似的數(shù)據(jù)結(jié)構(gòu))。無狀態(tài)的壓縮/解壓縮技術(shù)明顯更加簡單和快速，而有狀態(tài)的壓縮/解壓縮技術(shù)雖然較慢，但往往能產(chǎn)生更好的壓縮結(jié)果。
由于基于字典的壓縮算法需要頻繁地訪問字典，而通常字典又是存放在全局內(nèi)存中，這就使得壓縮過程的全局內(nèi)存訪問負(fù)載很大。高代價(jià)的非合并內(nèi)存訪問(non—coalescing memory access)模式帶來的延遲損失，將會(huì)使得在單個(gè)warp(warp是GPU執(zhí)行程序時(shí)的調(diào)度單位)下利用多線程處理不同數(shù)據(jù)塊帶來的改進(jìn)效果優(yōu)勢無存。傳統(tǒng)的塊級并行處理方式往往會(huì)帶來不好的'內(nèi)存訪問模式。除此之外，每一個(gè)并行的壓縮塊采用的字典內(nèi)容不同，由于CUDA平臺(tái)的SIMD特性，在遇見條件分支的時(shí)候?qū)⑹沟玫却刂品种Щ?control divergence resolution)的時(shí)間變得很長，并行的GPU計(jì)算將串行執(zhí)行，大大影響GPU的性能。因此開發(fā)出一種能充分利用GPU的計(jì)算能力和內(nèi)存帶寬，而不犧牲性能的高效壓縮技術(shù)是當(dāng)前的一大挑戰(zhàn)。本文提出了一種有效的GPU并行壓縮/解壓縮框架，這種框架可以應(yīng)用到有狀態(tài)和無狀態(tài)壓縮技術(shù)中，并結(jié)合了常規(guī)的塊級并行方法與GPU體系結(jié)構(gòu)的特性優(yōu)勢。
本文組織結(jié)構(gòu)如下：第2章介紹了并行壓縮與解壓縮算法的相關(guān)工作;第3章提出了一個(gè)GPU友好的并行壓縮/解壓縮框架及其相關(guān)技術(shù);第4章詳細(xì)介紹了利用前述框架的基于字典的壓縮技術(shù)和LZW的實(shí)現(xiàn);實(shí)驗(yàn)結(jié)果在第5章進(jìn)行了介紹;第6章對本文進(jìn)行了總結(jié)。
2 相關(guān)工作壓縮/解壓縮技術(shù)的并行化已經(jīng)被廣泛地研究。
Franaszek等人口 提出了一種基于塊引用壓縮算法和字典協(xié)作構(gòu)建的并行壓縮技術(shù)，采用多個(gè)壓縮器共同構(gòu)建出字典。雖然該方法對壓縮性能有著巨大的改善，但是在壓縮率上不如LZ77方法。Nagumo等人 提出了基于兩個(gè)靜態(tài)字典壓縮策略的并行化算法。Smith等人 引進(jìn)了一種基于文本替代的數(shù)據(jù)無損壓縮并行算法。這種算法可以很容易地實(shí)現(xiàn)為n—MOS電路。Storer等人描述了一種針對Nagumo方案的大型的并行體系結(jié)構(gòu)。Henriques等人 也提出了一種并行算法和體系結(jié)構(gòu)來實(shí)現(xiàn)LZ數(shù)據(jù)壓縮技術(shù)。Lee等人研究了怎樣將數(shù)據(jù)壓縮技術(shù)應(yīng)用到科學(xué)數(shù)據(jù)集的遷移中。Farach等人 從一些非�；A(chǔ)的問題考慮并行性，如字典匹配和字符串壓縮。這也對并行多媒體數(shù)據(jù)壓縮產(chǎn)生了相當(dāng)大的影響。Shen等人 對這個(gè)研究領(lǐng)域進(jìn)行了調(diào)研綜述。在解壓縮時(shí)，并行化方法通�？梢栽黾咏獯a的帶寬。根據(jù)底層編碼系統(tǒng)的不同，該領(lǐng)域已有的相關(guān)工作可以被大致分為兩類：第一類是基于定長的編碼。對于這一類壓縮技術(shù)而言，因?yàn)檫B續(xù)編碼的邊界是固定的，所以并行解碼的過程相對非常容易。相對于變長編碼而言，定長編碼的唯一缺陷在于壓縮效率不高。第二類方法處理了變長編碼的并行解碼問題n 的并行粒度，這些方法可以進(jìn)一步劃分為塊級并行和編碼級并行。第一類方法常常將壓縮的數(shù)據(jù)組織成塊，并且將塊標(biāo)識(shí)符存儲(chǔ)在文件頭或索引表中。利用這種方法，并行解碼器可以被應(yīng)用在每一個(gè)塊上。這些方法對于媒體數(shù)據(jù)如JPEG、MPEG.2 或H.264[131而言是十分適合的，因?yàn)榇蠖鄶?shù)壓縮的媒體數(shù)據(jù)已經(jīng)按塊結(jié)構(gòu)(宏塊)表示出來了。然而這些方法的缺點(diǎn)在于，常用的塊標(biāo)識(shí)技術(shù)如塊頭、字節(jié)對齊或索引表等方案會(huì)引入一些開銷，使得壓縮效率降低。Klein等人 利用自動(dòng)塊邊界檢測方法詳述了這一問題。基本思想是每個(gè)解碼器對應(yīng)不同的塊起始點(diǎn)，而這個(gè)起始點(diǎn)也與準(zhǔn)確的邊界值足夠接近。正確的編碼邊界的檢測是通過檢驗(yàn)重疊區(qū)域上處理器的輸出來實(shí)現(xiàn)的。利用這種方法，可以有效地避免存儲(chǔ)部分的塊邊界信息。
編碼級別的并行目前也可以用在多解碼器解壓縮多個(gè)連續(xù)壓縮數(shù)據(jù)塊的過程中。與之前的方法不同，這種方案下的并行解碼十分有挑戰(zhàn)性，因?yàn)椴恢老乱粋�(gè)編碼將從何處開始。目前已有多種方法能夠很好地解決這個(gè)問題。比如Nikara等人n 在輸入緩沖的每個(gè)可能的位置上，采用多個(gè)推測的并行解碼器進(jìn)行操作，并只輸出正確的解碼結(jié)果。但這種方法對于大的輸入緩沖區(qū)會(huì)引入顯著的硬件開銷。
Qin等人對這個(gè)問題則引人一個(gè)位置協(xié)議來預(yù)測不同解碼器要處理的代碼起始地址。然而，這些編碼級別的方法需要解碼器間的深度同步，目前的GPU還沒有相關(guān)的有效支持。在這種情況下，適當(dāng)?shù)慕Y(jié)合塊級別和編碼級別的并行可能會(huì)更有效地解決這個(gè)問題。
【GPU平臺(tái)的論文】相關(guān)文章：
gpu是什么_gpu相關(guān)問題01-11
GPU -電腦資料01-01
什么是GPU -電腦資料01-01
學(xué)生自主學(xué)習(xí)的平臺(tái)論文09-21
如何與學(xué)生構(gòu)建合作平臺(tái)的論文06-09
大學(xué)美育綜合平臺(tái)建構(gòu)論文06-29