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