多核處理器構架的高速JPEG解碼算法

　　作者：電子科技大學 章承科
　　
　　摘 要：實現(xiàn)基于多核處理器構架的JPEG解碼算法；通過將JPEG算法并行化，在多個處理器核上并行處理，并針對多核處理囂構架進行內存讀取等方面的優(yōu)化，可極大地提高JPEG解碼算法的解碼速度。實測表明，在4核集成的多核處理器上，JPEG圖像的平均解碼周期為單核處理器上的28％左右。
　　
　　JPEG(Joint Photographlc Experts Group)是一個適用范圍很廣的靜態(tài)圖像數(shù)據(jù)壓縮標準，目前廣泛應用于照相機、打印機等方面的圖像處理。在這些應用中，設計出一個高速高效的JPEG解碼器已經(jīng)成為一個重要的研究方向。隨著對嵌入式系統(tǒng)實時性、高性能和可擴展性要求的提高，多核(multi—core)嵌入式處理器的應用場合日益增多。
　　
　　1 JPEG解碼算法原理
　　
　　JPEG壓縮是一種有損壓縮。它利用人的視角系統(tǒng)特性，使用量化和無損壓縮編碼相結合的方式去掉視角的冗余信息和數(shù)據(jù)本身的冗余信息來達到壓縮的目的。JPEG算法可分為基本JPEG(Baseline SYSTEM)和擴展JPEG(Extended SYSTEM)。其中Baseline SYSTEM應用尤其廣泛。本文主要討論Baseline SYSTEM的解碼。JPEG解碼算法框圖如圖1所示。

　　(1)顏色空間變換
　　
　　JPEG算法本身與顏色空間無關，因此“RGB到YUV變換”和“YUV到RGB變換”不包含在JPEG算法中。但由于作為輸出的位圖數(shù)據(jù)一般要求RGB的表示，所以將顏色空間變換也表示在算法框圖中。
　　
　　(2)JPEG的編解碼單元
　　
　　在JPEG中，對于圖像的編解碼是分塊進行的。整個圖像被劃分為若干個8×8的數(shù)據(jù)塊，稱為最小編碼單元(MCU)，每一個塊對應于原圖像的一個8×8的像素陣列; 各行的編解碼順序是從上到下，行內的編解碼順序是從左到右。
　　
　　值得注意的是，由于一幅圖像的高和寬不一定是MCU尺寸的整數(shù)倍，因此需要對圖像的最右邊一列或其最下邊一行進行填充，擴展其高或寬，使得可以將整個圖像劃分為整數(shù)個MCU；而在解碼輸出時，這些復制的行列是要被拋棄的。
　　
　　(3)熵解碼器
　　
　　在JPEG的熵編碼時，首先利用空間相關性對各塊的直流值采用差分編碼，即對相鄰塊之間的直流差值編碼，以達到壓縮碼長的目的。然后對于交流部分以ZigZag方式掃描塊中的元素，對塊內元素采用先游程編碼后哈夫曼編碼的混合編碼方式，得到一維二進制塊碼流。熵編碼過程是由直流部分的差分編碼和交流部分的ZigZag掃描、游程編碼、哈夫曼編碼組成。而相應的熵解碼過程是編碼的逆過程，在解碼端接收到的是由變長碼(VLC)和變長整數(shù)(VLI)組成的數(shù)據(jù)流。為了從此數(shù)據(jù)流中恢復編碼前的DCT系數(shù)，必須根據(jù)哈夫曼編碼的原理及其各級碼表生成的細節(jié)，生成哈夫曼解碼表，再根據(jù)解碼算法來恢復DCT的直流和交流系數(shù)。
　　
　　(4)反量化
　　
　　在JPEG解碼端要利用發(fā)送過來的量化表對量化值進行譯碼。JPEG文件里一般含有兩個量化表：一個亮度分量的量化表，一個色度分量的量化表。反量化就是對熵解碼出來的系數(shù)矩陣乘上相應的量化矩陣：
　　
　　
　　
　　其中，C(u，v)代表熵解碼輸出，Q(u,v)代表相應的量化矩陣。
　　
　　(5)IDCT。變換
　　
　　JPEG解碼算法能否滿足實時應用，關鍵在于8×8的二維IDCT的計算速度。在編碼階段，正向離散余弦變換(FDCT)把空間域表示的圖變換成頻率域表示的圖；相應地在解碼階段，逆向離散余弦變換(IDCT)將頻率域表示的圖變換為空間域表示的圖。
　　
　　在IDCT的實現(xiàn)上，目前有多種算法。傳統(tǒng)的方法是行-列法，即先對每行(列)進行一維IDCT計算，再對每列(行)進行一維IDCT計算。還有多項式變換法和三角函數(shù)公式法，這兩種方法的加法次數(shù)與行-列法相當，乘法次數(shù)僅為行-列法的一半。但這兩種方法的問題在于實現(xiàn)方法復雜，對于目標平臺(VLIW)來說，這樣的結構難以提高指令的并行性，并且對于目標平臺來說，乘法指令的執(zhí)行時間與加法指令相當，因此減少了行-列法實現(xiàn)的代價。
　　
　　2 多核處理器構架
　　
　　FRl000是FUJITSU公司生產(chǎn)的主要應用于嵌入式系統(tǒng)的多核處理器。FRl000將4個處理器核(processorelement)集成在1枚芯片上，各個處理器核之間共享內存和其他外部設備。4個處理器核分別叫作PM(PE0)、PE1、PE2、PE3。其中，每個處理器內核均為一個獨立的VLIW(超長指令集)型架構的處理器，每個處理器核上都設置有獨立的高速二級緩存，以減小多核處理器在并行訪問內存時的瓶頸效應。FRl000多核處理器的硬件結構如圖2所示。
　　
　　
　　FR1000在每一個處理器核上都運行一個獨立的實時操作系統(tǒng)(RTOS)，而各個處理器核之間通過并行擴展庫(MP extended library)進行通信。通過并行擴展庫的擴展，運行在一個處理器核上的任務不僅能和運行在同一處理器核上的任務通信，還能和運行在不同處理器核上的任務通信。這樣，任務間就可以通過協(xié)同通信來完成特定的應用。而通過將應用劃分為不同的可以并行運行的任務而運行在不同的處理器核上，就可以并行地處理數(shù)據(jù)，從而達到提高系統(tǒng)性能的目的。
　　
　　FRl000系統(tǒng)的結構框圖如圖3所示。
　　
　　
　　從FRl000的構架可以看出，為了提升對于圖形和多媒體數(shù)據(jù)的處理速度，處理器著重于擴展其并行處理數(shù)據(jù)的能力。這樣的擴展主要表現(xiàn)在兩個方面：一方面使用VLlW構架的處理器核(這樣的處理器核一次最多能夠并行執(zhí)行8條指令，這樣的并行性主要由編譯器支持，這是一種指令的并行性)；另一方面使用多核處理器(CMP)的構架，使針對應用劃分的任務能夠真正并行地運行在多個處理器核上。(這樣的并行性需要由應用支持，通過恰當?shù)膭澐秩蝿諄韺崿F(xiàn))
　　
　　3 JPEG解碼算法在多核處理器上的實現(xiàn)
　　
　　針對FRl000處理器的特點，需要對JPEG圖像的解碼劃分為適當?shù)目梢圆⑿袌?zhí)行的任務進行處理。比較直觀的想法是，將JPEG圖像劃分為4個部分，分別在4個處理器核上進行解碼。但由于JPEG圖像的數(shù)據(jù)流是變長編碼，根據(jù)現(xiàn)有的數(shù)據(jù)流，難以將其劃分為4個能并行解碼的圖像。(這樣的劃分付出的時間代價過大)
　　
　　根據(jù)前面所敘述的JPEG圖像解碼原理可以看出，解碼的基本單位是MCU，因此在第一步熵解碼之后生成的MCU是可以并行解碼的最小單元。因此對一個JPEG圖像在多核處理器上進行并行解碼的關鍵在于，將此，JPEG圖像所包含的MCU負載均衡地分配到各個處理器核上進行并行解碼處理。
　　
　　由此，處理方法有兩種：一種是以一個MCU作為任務分配的單位，由PM通過熵解碼生成MCU，然后將MCU均勻地分配到各個處理器核(PE)上，由各個處理器核在完成MCU的解碼之后再寫入到位圖的相應位置。這樣做的好處有兩點：①可以做到很好的負載均衡，使每一個處理器核都承擔幾乎相同的負載。②可以使熵解碼和MCU的解碼并行進行。但這種做法的一個很大問題在于處理器核之間通信所消耗的時間代價過大。因為這可以抽象為一種生產(chǎn)者與消費者的模型，生產(chǎn)者在每次生產(chǎn)出一個MCU的時候都需要與消費者進行一次通信或者說更新消費者端的數(shù)據(jù)輸入。經(jīng)過實測以后發(fā)現(xiàn)，這種做法所帶來的通信開銷過大，占到解碼程序運行時間的20％以上。這種做法的另外一個問題在于內存的讀寫，由于各個處理器核需要交錯地寫入內存的同一塊區(qū)域，導致對于此塊內存的寫入不能使用寫回(copy back)模式。因為如果各個處理器核使用寫回模式，會導致各個處理器核中cache的數(shù)據(jù)與內存中的數(shù)據(jù)不一致而出現(xiàn)錯誤。
　　
　　另外一種處理方式是通過劃分圖像塊來實現(xiàn)的。由于MCU是與原始位圖由上到下、由左到右一一對應的，因此將JPEG圖像按高度等分為4個圖像塊，而這樣的圖像塊的高度必須為MCU的整數(shù)倍。然后由各個處理器核分別解碼各個圖像塊，在指定的內存區(qū)域寫入解碼結果以拼接為一幅完整的原始位圖。
　　
　　這種處理方式的關鍵在于，每個處理器核怎樣快速地定位到自己需要解碼的那部分圖像塊。由于JPEG是變長編碼，所以不存在一個O(1)的算法使之能夠通過一定的偏移量進行定位，但可以修改熵解碼部分的代碼，使其能夠跳過不必要的解碼，快速定位到需要處理的區(qū)域。具體來說，定位的過程實際上就是對MCU進行計數(shù)的過程，定位時沒有必要保存MCU的內容，只需要對解出來的MCU進行計數(shù)。由于MCU與原始位圖的一一對應關系，所以可以通過對MCU的計數(shù)來定位到需要處理的區(qū)域。具體換算公式如下：
　　
　　
　　
　　其中Height表示圖像高度，Width表示圖像寬度，PEID表示每個處理器核所對應的編號(1～4)。
　　
　　各處理器核的解碼流程如圖4所示。
　　
　　
　　這種處理方式的問題在于，每一個處理器核都需要花費額外的時間來定位需要解碼的數(shù)據(jù)塊；但實測以后發(fā)現(xiàn)，定位操作所消耗的時間只占5％左右。因為在FRl000平臺上，大量的解碼時間消耗主要在于IDCT變換和YUV到RGB的顏色空間轉換上面。這種處理方式降低了通信的時間消耗，在一幅JPEG的圖像解碼中只需要兩次處理器核之問的通信。這種處理方式的另外一個好處在于，每一個PE在寫入結果的位圖數(shù)據(jù)時可以對內存的寫入采用寫回(copy back)模式，只需要在圖像塊交界的地方作刷新cache的操作就可以保證結果的正確性。在隨后的關于優(yōu)化的討論中可以看到，這種方式對于提高解碼的速度起著相當重要的作用。
　　
　　4 優(yōu)化
　　
　　一般來說，一個程序在多核處理器上的運行時間除上在其中一個單核處理器上的運行時間稱為多核并行度(MP)。在有4個處理器核的FRl000處理器上，MP的極限值(存在必要的通信開銷)應該為25％。但根據(jù)圖3的解碼流程，實測的MP只有43％左右。進一步分析后發(fā)現(xiàn)，由于多個處理器核沿相同的流程進行解碼，從而在相同的時間里對內存有大量并發(fā)的讀寫操作，而這樣的并發(fā)操作導致對于內存的讀寫成為系統(tǒng)的瓶頸。在單核上需要16～20個周期的1行cache讀入操作，在多個處理器核同時運行時，需要30～40個周期才能完成。
　　
　　優(yōu)化主要從兩個方面進行：
　　
　?、俦M量減少對內存的讀寫操作。一般的JPEG解碼程序，會以行為單位保存熵解碼后的中間結果，也就是使用存儲1行MCU的空間作為臨時緩沖區(qū)。這樣的臨時緩存區(qū)是隨著圖像行的寬度增大而增大的，當圖像的寬度變大到一定程度的時候，這樣的臨時緩存將很可能大到?jīng)]有辦法駐留在cache中，cache不命中從而導致大量的內存讀寫和對于cache的置換。優(yōu)化后將其改為熵解碼完一個MCU后，立即作反量化、IDCT和顏色空間變換，直至寫入位圖。這樣只需要一個MCU大小的臨時緩存?？梢员ＷC這樣的緩沖一直保存在cache中，從而避免大量的讀寫內存的操作。但這樣的方式需要恰當?shù)呐袛噙吔鐥l件，如前所述，由于圖像的長寬不一定是MCU的整數(shù)倍，所以在最下一行和最右一列有填充數(shù)據(jù)，需要在解碼的時候丟棄掉。
　　
　　②恰當?shù)剡x擇內存的讀寫模式。由于整個解碼程序中，在最后寫入位圖時需要大量地寫入內存的操作。如果使用寫透(write through)模式，每次均同時寫入cache和內存，這樣必然會造成大量的內存讀寫操作。所以在寫入位圖的區(qū)域使用寫回模式，這樣只需要在每次cache行置換的時候需要寫入內存，極大地減少了對于內存的讀寫操作。但需要注意的是，在多核處理器的環(huán)境下，必須保證該內存區(qū)域和各個處理器核上的cache數(shù)據(jù)之間的一致性。這需要恰當?shù)貏澐指鱾€處理器核的內存讀寫區(qū)域，并且在讀寫各個區(qū)域交界的地方時用指令刷新相應的cache行。
　　
　　值得注意的是，在多核處理器的構架上，由于多個處理器會并行訪問內存，所以內存很容易成為瓶頸，在涉及大量內存操作的圖像處理程序方面表現(xiàn)得尤為突出。因此對于程序的優(yōu)化應該著重將注意力放在對于內存的讀寫優(yōu)化方面。
　　
　　5 實驗結果
　　
　　選取256×256、1024×1024、4096×4096三個JPEG圖像進行解碼，其耗費的周期數(shù)如表1所列。

　　可見對于尺寸越大的圖像，其MP越接近于25％的極限值，因為此時通信所占的開銷越?。煌瑫r隨著內存塊的增大，在每個處理器核處理的圖像塊的邊界處刷新cache行的代價也越小，而平均的MP約為28％左右。
　　
　　6 結論
　　
　　針對多核處理器構架的特點，在其上實現(xiàn)高速的JPEG解碼算法，其多核的并行度(MP)接近于25％的極限值。上述實現(xiàn)雖然只針對FRl000的多核處理器，但同樣適應于其他具有多核構架的處理器。此外針對多核處理器構架方面的優(yōu)化方法對于其他運行于多核處理器構架上的應用也有一定的借鑒價值。