多核處理器構(gòu)架的高速JPEG解碼算法

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

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

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