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