基于PAAG的H.264整數DCT變換的并行化實現

田小平，劉 帆

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

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

1 H.264的整數DCT變換

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

式中X為幀內或幀間預測后的4×4圖像殘差數據，Cf為核心變換矩陣，W 為對應DCT變換后的4×4圖像殘差塊。

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

圖1 蝶形快速變換算法

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

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

用這些中間變量來組合，就可以得到對傳統蝶形變換優化后的結果

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

2 全系統仿真平臺PAAG

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

圖2 PAAG簇結構

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

圖3 PE互聯結構

3 基于PAAG的DCT算法并行化

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

假設一個4×4塊殘差數據為

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

圖4 殘差數據加載方式

在各PE計算出中間變量M后，根據圖5的數據共享方式，將各中間變量傳送至共享存儲RFn、RFe、RFs、RFw中，然后，通過共享存儲，將中間變量傳送至指定的PE中，再根據式（4）進行計算，就完成了整數DCT變換中的水平變化。此方案將H.264標準源碼中嵌套循環的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數據必須經過PE間的通信共享數據，數據共享方式如圖6所示。

圖6 水平變換后的數據共享方式

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

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

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

4 仿真驗證與分析

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

圖8 PAAG IDE仿真界面

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

圖9 并行整數DCT的性能統計

圖10 串行整數DCT的性能統計

5 總結

針對多核陣列結構PAAG，提出一種整數DCT變換的并行化算法。通過PAAG仿真工具對算法程序進行仿真，結果表明該并行算法的計算速度相比于串行計算提高了77%，驗證了PAAG結構適合于整數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域的數字圖像置亂程度衡量方法［J］.西安郵電學院學報，2009，14（1）：80－83.

［3］田小平，吳成茂，譚鐵牛.利用DCT變換進行圖像置亂及其效果評價［J］.計算機工程與應用，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整數DCT變換和量化方法的設計和實現［J］.淮海工學院學報：自然科學版，2006，15（3）：22－25.

［6］鄧磊，高文，胡銘曾，等.基于 AVC／AVS標準高效運動估計硬件結構設計［J］.計算機研究與發展，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.