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

jpeg（joint photographic 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(tǒng)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ì)相鄰塊之間的直流差值編碼，以達(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)的量化矩陣：

f（u，v）＝c（u，v）×q（u，v）

其中，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)架

fr1000是fujitsu公司生產(chǎn)的主要應(yīng)用于嵌入式系統(tǒng)的多核處理器。fr1000將4個(gè)處理器核（processor element）集成在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ú)立的高速二及緩存，以減小多核處理器在并行訪問(wèn)內(nèi)存時(shí)的瓶頸效應(yīng)。fr1000多核處理器的硬件結(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)性能的目的。

fr1000系統(tǒng)的結(jié)構(gòu)框圖如圖3所示。

從fr1000的架構(gòu)可以看出，為了提升對(duì)于圖形和多媒體數(shù)據(jù)的處理速度，處理器著重于擴(kuò)展其并行處理數(shù)據(jù)的能力。這樣的擴(kuò)展主要表現(xiàn)在兩個(gè)方面：一方面使用vliw架構(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ì)fr1000處理器的特點(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的解碼之后再寫(xiě)入到位圖的相應(yīng)位置。這樣做的好處有兩點(diǎn)：（1）可以做到很好的負(fù)載均衡，使每一個(gè)處理器核都承擔(dān)幾乎相同的負(fù)載。（2）可以使熵解碼和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)存的讀寫(xiě)，由于各個(gè)處理器核需要交錯(cuò)地寫(xiě)入內(nèi)存的同一塊區(qū)域，導(dǎo)致對(duì)于此塊內(nèi)存的寫(xiě)入不能使用寫(xiě)回（copy back）模式，因?yàn)槿绻鱾€(gè)處理器核使用寫(xiě)回模式，會(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ū)域。具體換算公式如下：

nmcu＝[height]/8]×（peid/4）×[width/8]

其中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)樵趂r1000平臺(tái)上，大量的解碼時(shí)間消耗主要在于idct變換和yuv到rgb的顏色空間轉(zhuǎn)換上面。這種處理方式降低了通信的時(shí)間消耗，在一幅jpeg的圖像解碼中只需要兩次處理器核之間的通信。這種處理方式的另外一個(gè)好處在于，每一個(gè)pe在寫(xiě)入結(jié)果的位圖數(shù)據(jù)時(shí)可以對(duì)內(nèi)存的寫(xiě)入采用寫(xiě)回（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è)處理器核的fr1000處理器上，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ā)的讀寫(xiě)操作，而這樣的并發(fā)操作導(dǎo)致對(duì)于內(nèi)存的讀寫(xiě)成為系統(tǒng)的瓶頸。在單核上需要16－20個(gè)周期的1行cache讀入操作，在多個(gè)處理器核同時(shí)運(yùn)行時(shí)，需要30－40個(gè)周期才能完成。

優(yōu)化主要從兩個(gè)方面進(jìn)行：

（1）盡量減少對(duì)內(nèi)存的讀寫(xiě)操作。一般的jpeg解碼程序，會(huì)以行為單位保存熵解碼后的中間結(jié)果，也就是使用存儲(chǔ)1行mcu的空間作為臨時(shí)緩沖區(qū)。這樣的臨時(shí)緩存區(qū)是隨著圖像行的寬度增大而增大的，當(dāng)圖像的寬度變大到一定程度的時(shí)候，這樣的臨時(shí)緩存將很可能大到?jīng)]有辦法駐留在cache中，cache不命中從而導(dǎo)致大量的內(nèi)存讀寫(xiě)和對(duì)于cache的置換。優(yōu)化后將其改為熵解碼完一個(gè)mcu后，立即作反量化、idct和顏色空間變換、直至寫(xiě)入位圖。這樣只需要一個(gè)mcu大小的臨時(shí)緩存。可以保證這樣的緩沖一直保存在cache中，從而避免大量的讀寫(xiě)內(nèi)存的操作，但這樣的方式需要恰當(dāng)?shù)呐袛噙吔鐥l件，如前所述，由于圖像的長(zhǎng)寬不一定是mcu的整數(shù)倍，所以在最下一行和最右一列有填充數(shù)據(jù)，需要在解碼的時(shí)候丟棄掉。

（2）恰當(dāng)?shù)剡x擇內(nèi)存的讀寫(xiě)模式。由于整個(gè)解碼程序中，在最后寫(xiě)入位圖時(shí)需要大量地寫(xiě)入內(nèi)存的操作。如果使用寫(xiě)透（write through）模式，每次均同時(shí)寫(xiě)入cache和內(nèi)存，這樣必然會(huì)造成大量的內(nèi)存讀寫(xiě)操作。所以在寫(xiě)入位圖的區(qū)域使用寫(xiě)回模式，這樣只需要在每次cache行置換的時(shí)候需要寫(xiě)入內(nèi)存，極大地減少了對(duì)于內(nèi)存的讀寫(xiě)操作，但需要注意的是，在多核處理器的環(huán)境下，必須保證該內(nèi)存區(qū)域和各個(gè)處理器核上的cache數(shù)據(jù)之間的一致性。這需要恰當(dāng)?shù)貏澐指鱾€(gè)處理器核的內(nèi)存讀寫(xiě)區(qū)域，并且在讀寫(xiě)各個(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)存的讀寫(xiě)優(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ì)fr1000的多核處理器，但同樣適應(yīng)于其他具有多核構(gòu)架的處理器，此外針對(duì)多核處理器構(gòu)架方面的優(yōu)化方法對(duì)于其他運(yùn)行于多核處理器構(gòu)架上的應(yīng)用也有一定的借鑒價(jià)值。