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