基于PAAG的H.264整數(shù)DCT變換的并行化實現(xiàn)

田小平，劉 帆

（1.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安710121； 2.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安710121）

H.264／AVC（Advanced Video Coding）［1］是國際電信聯(lián)盟 （International Telecommunication U－nion，ITU）和國際標準化組織 （International Organization for Standardization，ISO）共同制定的新一代視頻編碼標準，離散余弦變換 （Discrete Cosine Transform，DCT）是 H.264標準中的重要模塊之一。由于DCT變換具有快速算法以及良好的數(shù)據(jù)壓縮性和去相關(guān)性［2－3］，因此 DCT算法在多種結(jié)構(gòu)設(shè)計中被應(yīng)用［4－7］。DCT變換的對象，是幀內(nèi)預(yù)測或者運動估計后所得到的殘差數(shù)據(jù)，基于4×4塊為單位進行整數(shù)離散余弦變換和量化，最后經(jīng)過熵編碼后輸出［8－9］。由于 H.264整數(shù) DCT變換運算規(guī)則十分簡單，并且使用的都是整數(shù)的加法、乘法和移位操作，所以特別適合用于硬件的實現(xiàn)。面向圖形的多臺陣列架構(gòu) （Polymorphic Array Architecture for Graphic，PAAG）是針對于視頻處理而設(shè)計的新的專用體系結(jié)構(gòu)，為了驗證PAAG結(jié)構(gòu)對于H.264整數(shù)DCT并行化的性能，本文著重研究一種基于PAAG的整數(shù)DCT算法的并行化實現(xiàn)。

1 H.264的整數(shù)DCT變換

在H.264視頻編碼標準中，是以4×4圖像塊為單位進行變換編碼，優(yōu)化思想是定義中間變量，減少運算［10］。整數(shù) DCT變換公式為［10］

式中X為幀內(nèi)或幀間預(yù)測后的4×4圖像殘差數(shù)據(jù)，Cf為核心變換矩陣，W 為對應(yīng)DCT變換后的4×4圖像殘差塊。

按照式（1）算法，4×4的矩陣相乘需64次乘法和48次加法，時間耗費的比較多，而在H.264標準官方源代碼JM中，對式（1）進行了改進，得到了蝶形快速變換算法［11］，如圖1所示。通過利用矩陣的整數(shù)性和對稱性將全部乘法運算轉(zhuǎn)化為加法運算，減少運算次數(shù)。

圖1 蝶形快速變換算法

圖1 中r＝1為Hadamard變換，r＝2則為整數(shù)DCT變換。由于矩陣Cf的特殊性，殘差圖像塊數(shù)據(jù)X左乘Cf，采用傳統(tǒng)方法計算，得到結(jié)果

式（2）計算需要16次乘法和12次加法，由于矩陣乘1和乘－1的運算可以去除，所以式（2）可優(yōu)化為只需4次乘法和12次加法。再利用其相關(guān)性，設(shè)置中間變量將空間代價轉(zhuǎn)換為時間代價，可減少計算次數(shù)。經(jīng)反復(fù)推算，將式（2）分為兩步，提取的中間變量值M為

用這些中間變量來組合，就可以得到對傳統(tǒng)蝶形變換優(yōu)化后的結(jié)果

由式（3）和式（4）可以看出，通過以中間變量將式（2）運算分為兩步，可使得運算量減少至2個乘法和8個加法，最后疊代這個算法即可完成整數(shù)DCT變換。

2 全系統(tǒng)仿真平臺PAAG

PAAG提供一套完整的集成開發(fā)環(huán)境（Integrated Develop Environment，IDE），用于對視頻各種算法并行化的硬件實現(xiàn)進行仿真。PAAG IDE集成了硬件時鐘精確仿真平臺、指令集編譯器、程序性能統(tǒng)計與分析、完整的編輯器以及完整的調(diào)試模塊。其體系結(jié)構(gòu)是以簇為單位，每個簇由4×4的處理元 （Processing Element，PE）陣列構(gòu)成，由于視頻算法中數(shù)據(jù)的處理基本都是對4×4或者16×16的宏塊進行處理，所以這種專用體系結(jié)構(gòu)相比其他結(jié)構(gòu)可以更有效的對視頻并行化算法進行硬件映射，其結(jié)構(gòu)如圖2所示。

圖2 PAAG簇結(jié)構(gòu)

PAAG最多可支持4096個PE（PE數(shù)量是可配置的），具有層次結(jié)構(gòu)，并且有可配置的片上網(wǎng)絡(luò) （Network on Chip，NoC）架構(gòu)、PE的架構(gòu)、以及簇控制器的體系結(jié)構(gòu)。CR0－CR3為行控制器，CW0－CW3為列控制器，數(shù)據(jù)和程序存儲在簇存儲Cluster memory中，由簇控制器協(xié)調(diào)整個執(zhí)行。簇控制器是可編程，微型操作系統(tǒng) （Tiny Operating System，TOS）通過它來管理所有PAAG的資源，包括內(nèi)存管理、線程調(diào)度以及其他資源。每個PE都有4個方向的共享存儲，即 RFn、RFe、RFs、RFw，通過它們可以向PE周圍的4個方向共享數(shù)據(jù)，從而實現(xiàn)數(shù)據(jù)的通信。PE之間的通信結(jié)構(gòu)如圖3所示。

圖3 PE互聯(lián)結(jié)構(gòu)

3 基于PAAG的DCT算法并行化

H.264采用新的整數(shù)變換算法，以4×4像素子塊為單位，在變換過程中只包含整數(shù)運算，這也是H.264標準區(qū)別于其他標準的重要不同之處。在H.264標準源代碼中，DCT算法是串行化的，其主要核心是兩個變換［11－12］：水平變換和垂直變換，相當于左乘和右乘變換矩陣。每個變換都有兩個嵌套循環(huán)，每個嵌套循環(huán)共要順序執(zhí)行32次操作，需耗費大量時間。本文主要思想是利用PAAG體系結(jié)構(gòu)的空間優(yōu)勢，采用細粒度的任務(wù)分配方式，最大限度的將嵌套循環(huán)的每個操作配置到各個PE中，由于此體系結(jié)構(gòu)數(shù)據(jù)傳輸類型為臨接互聯(lián)，所以在配置的過程中充分考慮到兩個PE間數(shù)據(jù)的共享問題，使各PE間共享數(shù)據(jù)的傳遞距離最優(yōu)，最終達到基于PAAG的DCT算法并行化的最優(yōu)實現(xiàn)。

假設(shè)一個4×4塊殘差數(shù)據(jù)為

首先進行水平變換，為了之后的計算過程中數(shù)據(jù)能以最小的傳輸代價在PE間共享，將4×4的殘差數(shù)據(jù)按照圖4的配置方式加載到PE0至PE15中，根據(jù)式（3）配置各個PE的指令，計算出各中間變量M［0］、M［1］、M［2］、M［3］。

圖4 殘差數(shù)據(jù)加載方式

在各PE計算出中間變量M后，根據(jù)圖5的數(shù)據(jù)共享方式，將各中間變量傳送至共享存儲RFn、RFe、RFs、RFw中，然后，通過共享存儲，將中間變量傳送至指定的PE中，再根據(jù)式（4）進行計算，就完成了整數(shù)DCT變換中的水平變化。此方案將H.264標準源碼中嵌套循環(huán)的32次操作減少到只要兩次操作即可完成。

圖5 水平變換的中間變量共享方式

水平變換后得到的4×4矩陣中X00、X01、X02、X03分別在 PE0、PE4、PE8、PE12中；X20、X21、X22、X23分別在 PE1、PE5、PE9、PE13中；X10、X11、X12、X13分別在 PE2、PE6、PE10、PE14中；X30、X31、X32、X33 分別在 PE3、PE7、PE11、PE15中。為了進行垂直變換，此變換后的4×4數(shù)據(jù)必須經(jīng)過PE間的通信共享數(shù)據(jù)，數(shù)據(jù)共享方式如圖6所示。

圖6 水平變換后的數(shù)據(jù)共享方式

水平變換得到的數(shù)據(jù)共享之后，再進行的垂直變換。垂直變換與水平變換基本一致，通過得到中間變量、共享、再計算之后就得到了整數(shù)DCT變換后的數(shù)據(jù)。圖7為垂直變換的中間變量共享方式。

圖7 垂直變換的中間變量共享方式

至此，分別通過水平變換和垂直變換后，就完成了整數(shù)DCT變換的并行化映射。

4 仿真驗證與分析

以4×4殘差塊為例，通過匯編語言實現(xiàn)H.264標準的整數(shù)DCT算法并行化程序，并使用PAAG仿真工具對算法程序進行仿真。圖8為PAAG IDE仿真界面。

圖8 PAAG IDE仿真界面

整個程序共包含16個部分，分別儲存在16個PE（相當于16個核）中，通過對這16個PE加載4×4殘差數(shù)據(jù)執(zhí)行PE中預(yù)存的指令（每個PE初始加載2個殘差數(shù)據(jù)）。在仿真過程中，通過對程序的優(yōu)化改進，這里取的是所有16個PE中程序最為耗時的執(zhí)行時間。圖9為并行整數(shù)DCT的性能統(tǒng)計，經(jīng)過單步調(diào)試，最終整個程序的執(zhí)行時間僅為66個時鐘周期，實現(xiàn)了整數(shù)DCT的并行化計算。通過仿真對比，在單個PE中（單核）實現(xiàn)串行整數(shù)DCT變換，程序的執(zhí)行時間為295個時鐘周期，并行運算相比于串行運算提高了77%，加速比為4.47。圖10為串行整數(shù)DCT的性能統(tǒng)計。仿真結(jié)果表明，此并行算法可以充分利用PAAG結(jié)構(gòu)的特點，有效提高整數(shù)DCT的計算速度。

圖9 并行整數(shù)DCT的性能統(tǒng)計

圖10 串行整數(shù)DCT的性能統(tǒng)計

5 總結(jié)

針對多核陣列結(jié)構(gòu)PAAG，提出一種整數(shù)DCT變換的并行化算法。通過PAAG仿真工具對算法程序進行仿真，結(jié)果表明該并行算法的計算速度相比于串行計算提高了77%，驗證了PAAG結(jié)構(gòu)適合于整數(shù)DCT的并行化。

［1］Wiegand T，Sullivan G J，Bjontegaard G，el at.Overview of the H.264／AVC Video Coding Standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7）：560－576.

［2］許靜，田小平，譚鐵牛.一種基于DCT域的數(shù)字圖像置亂程度衡量方法［J］.西安郵電學(xué)院學(xué)報，2009，14（1）：80－83.

［3］田小平，吳成茂，譚鐵牛.利用DCT變換進行圖像置亂及其效果評價［J］.計算機工程與應(yīng)用，2008，44（35）：174－178

［4］Joshi A M ，Patrikar R M，Mishra V.Design of low complexity video watermarking algorithm based on Integer DCT［C］／／Signal Processing and Communications（SPCOM），2012International Conference on，2012：1－5.

［5］鄭玉，劉文杰，高文.AVS整數(shù)DCT變換和量化方法的設(shè)計和實現(xiàn)［J］.淮海工學(xué)院學(xué)報：自然科學(xué)版，2006，15（3）：22－25.

［6］鄧磊，高文，胡銘曾，等.基于 AVC／AVS標準高效運動估計硬件結(jié)構(gòu)設(shè)計［J］.計算機研究與發(fā)展，2006，43（11）：1972－1979.

［7］Shin I，Yu J，Ryu W.Visually improved DCT based down－sampling method for H.264SVC［C］／／Consumer Electronics（ICCE），2010Digest of Technical Papers International Conference on，NV：Consumer Electronics，2010：369－370.

［8］侯金亭，馬思偉，高文.AVS標準綜述［J］.計算機工程，2009，35（8）：247－249.

［9］Zhao Liang，Zhang Li，Ma Siwei，et al.Fast mode decision algorithm for intra prediction in HEVC［C］／／Visual Communications and Image Processing（VCIP），2011IEEE，harbin：ieee press，2011：1－4.

［10］Wiegand T，Sullivan G，Luthra A.JVT－G050r1，Draft ITU－T recommendation and final draft international standard of joint video specification （ITU－T Rec.H.264／ISO／IEC 14496－10AVC）［S／OL］.（2011－12－14） ［2014－02－25］.http：／／www.doc88.com／p－90727922095.html.

［11］畢厚杰.新一代視頻壓縮編碼標準：H.264／AVC［M］.3版.北京：人民郵電出版社，2005：103－106.

［12］Puri Atul，Chen Xuemin，Luthra Ajay.Video coding using the H.264／MPEG－4AVC compression standard［C］／／Signal Processing：Image Communication，2004（19）：793－849.