基于BWDSPHEVC的向量SIMD哈達(dá)瑪變換并行設(shè)計

佘成龍 段苓麗 汪輝

摘要：針對HEVC中SATD率失真代價計算的特點，本文提出利用向量SIMD（單指令多數(shù)據(jù)流）技術(shù)，設(shè)計哈達(dá)瑪變換的并行化方案。該方案采用多加法器和多乘法器協(xié)同工作模式，發(fā)揮處理器的并行性，通過合理的數(shù)據(jù)安排，很好地實現(xiàn)了多個宏中數(shù)據(jù)的并行計算，增大DSP的數(shù)據(jù)吞吐率，提高數(shù)據(jù)處理速度。實驗結(jié)果表明其在單核BWDSP1041上的并行加速比達(dá)到87.9，證明了優(yōu)化工作的有效性。

關(guān)鍵詞：HEVC；幀內(nèi)預(yù)測；并行化；BWDSP1041處理器

中圖分類號：TP391 文獻標(biāo)識碼：A 文章編號：1009-3044（2018）40-0222-03

A Parallel Algorithm for SIMD Hadamard Transform Based on BWDSP

SHE Cheng-long，DUAN Ling-li，WANG Hui

（School of Computer and Information in Hefei University of Technology，Anhui Province Key Laboratory of Industry Safety and Emergency Technology，Hefei 230009，China）

Abstract： For the characteristics of the SATD rate distortion cost calculation in HEVC， this paper proposes to use the vector SIMD （single instruction multiple data stream） technology to design the Hadamard transform parallelization scheme. The scheme uses a multi-adder and multi-multiplier cooperative working mode to exploit the parallelism of the processor. Through reasonable data arrangement， parallel computing of multiple macros is realized， and the data throughput of the DSP is increased， and the data throughput is improved. Data processing speed. The experimental results show that the parallel speedup of 87.9 on single-core BWDSP1041 proves the effectiveness of the optimization work.

Key words： HEVC；SATD；Parallelism；BWDSP1041Processor

HM算法測試模型基于LCU（Largest Coding Unit）的編碼單元，采用遍歷的方法，塊的尺寸根據(jù)圖像細(xì)節(jié)復(fù)雜度通過劃分自適應(yīng)改變其大小。編碼單元（CU）包括從64×64到8×8的各種大小?；谒牟鏄浣Y(jié)構(gòu)計算全部RDCost來得到最優(yōu)CU大小[1]。幀內(nèi)預(yù)測要對每一種可能的預(yù)測模式都采用SATD對殘差進行計算和比較，從而得到最優(yōu)模式這個過程非常耗時存在著巨大的計算量。其中對計算過程較為復(fù)雜和耗時的角度預(yù)測模式進行并行化設(shè)計，縮短幀內(nèi)預(yù)測的時間，對于實現(xiàn)HEVC的實時性意義很重大?，F(xiàn)在H265幀內(nèi)預(yù)測的加速和優(yōu)化研究重點基本在4個方面： 一是塊類型預(yù)判斷或者提前終止CU塊的劃分[2～4]； 二是縮小模式選擇范圍[5～7]； 三是優(yōu)化率失真代價函數(shù)，率失真代價的計算用更簡單的方法[8～11]；四是從多處理器角度并行實現(xiàn)模式預(yù)測[12]和SATD率失真代價計算。本文對在幀內(nèi)預(yù)測基于SATD率失真代價計算進行并行化探究，提出了適合在多核和多運算部件結(jié)構(gòu)上并行計算的算法，對于加速幀內(nèi)預(yù)測有實際意義，大大縮短幀內(nèi)預(yù)測所需時間。

1 哈達(dá)瑪變換的算法研究

相對于H.264/AVC支持8個預(yù)測方向，HEVC規(guī)定了33種角度方向預(yù)測，進一步細(xì)化了這些預(yù)測方向，方向性預(yù)測的基本原理是：當(dāng)前待預(yù)測的像素沿特定的預(yù)測方向在參考樣本上投影，投影所在的位置對應(yīng)的像素值就是預(yù)測值。預(yù)測角度設(shè)計的傾向是為接近水平和垂直的角度提供更密集的覆蓋。各個模式的格點（角度）分布是不均勻的。越靠近垂直方向，分布越是細(xì)密，越是靠近對角方向越是稀疏。角度中模式都相當(dāng)于做了一個偏移在垂直或水平方向上。在HM編碼器中逐一對35種幀內(nèi)預(yù)測模式采用SATD對殘差進行哈達(dá)瑪變換后的系數(shù)絕對求和。以4?4和8?8大小塊為例，介紹哈達(dá)瑪變換矩陣的計算過程。對于一個32?32矩陣塊的殘差塊，在代碼實現(xiàn)過程中，會將矩陣塊分割成4個8?8大小的矩陣塊，再分別對矩陣塊進行哈達(dá)瑪變化，最后再將4個8?8矩陣的哈達(dá)瑪變換后的值相加，就得到了32?32矩陣塊哈達(dá)瑪變換結(jié)果。

定義[h=111-1]，則[H4×4=hhh-h]，殘差塊[X4×4=-2-4-1-3-4-3-3-2-2-3-4-42-3-1-3]

求得矩陣的絕對值和為：[H4×4·X4×4·H4×4=112]

則SATD = 112/2 =56。

當(dāng)塊大小為8?8時，

[H8×8=H4×4H4×4H4×4-H4×4]，殘差塊[X8×8=-2-4-1-2-3-3-1-2-2-3-4-42-3-3-2-6-5-4-7-3-5-7-3-5-7-6-4-5-2011-1-5-60-5-8-3-2-8-3-5-9-22-3-5-6-4-3-5-1-1-4-5-5-7-6-5-7-61]

求得矩陣的絕對值和為：[H8×8·X8×8·H8×8=1160]

則SATD = 1160/2 =580。

以計算一個8?8殘差塊為例，在對殘差塊進行哈達(dá)瑪變換時需要進行兩次矩陣相乘，矩陣大小都為8?8，需1024次乘法、896次加法，可見計算量是很大的，如果采用傳統(tǒng)的矩陣相乘，主要采用行乘列再進行累加計算，一般采用3重循環(huán)實現(xiàn)，若在DSP上直接采用匯編語言串行計算實現(xiàn)，將大大限制了DSP的數(shù)據(jù)處理能力。通過本文采用向量SIMD設(shè)計方法，充分利用BWDSP1041處理器多加法器和多乘法器協(xié)同工作模式，發(fā)揮處理器的并行性，通過合理的數(shù)據(jù)安排，讓4個宏中的數(shù)據(jù)并行計算，使處理器的計算性能得到充分的發(fā)揮，縮短了計算所用的時間，提高了代碼利用率。

2 向量SIMD哈達(dá)瑪變化的并行化

2.1 BWDSP1041仿真平臺

BWDSP1041是中國電子科技集團公司第38研究所設(shè)計的一款32位靜態(tài)超標(biāo)量浮點DSP處理器。處理器共有13級流水，BWDSP1041核內(nèi)部包含4個基本執(zhí)行宏（Element operation Macro，簡稱宏）。指令主要由數(shù)據(jù)傳輸/調(diào)用，如存儲器同運算部件之間、存儲器之間的數(shù)據(jù)交互、數(shù)據(jù)運算、程序控制及輸入輸出數(shù)據(jù)命令等組成。

1）處理宏

BWDSP1041有4個執(zhí)行宏，分別標(biāo)識X、Y、Z、T，其結(jié)構(gòu)和功能相同，在指令前指定宏標(biāo)識，來說明指令在哪個執(zhí)行宏中運行，指定多個則在多個執(zhí)行宏運行，不指定宏則在 4個執(zhí)行宏同時運行 （ 宏標(biāo)識與 R 緊鄰 ），每個執(zhí)行宏資源有：8 個 ALU， 編號 0～7；8個 MUL，編號 0～7，4個 SHF，編號0～3；1個SPU，128個通用寄存器（參見圖1）。

2）地址產(chǎn)生器及數(shù)據(jù)傳輸通道

BWDSP1041處理器有3個地址產(chǎn)生器，其結(jié)構(gòu)和功能一樣。地址生成器（AGU）產(chǎn)生存儲器與宏之間的數(shù)據(jù)交換所需的地址。地址產(chǎn)生器每個都有1組地址輔助寄存器，用于寄存各種地址變化關(guān)系的參數(shù)值，編號 0～15。

ECS（Efficient Coding Studio）是BWDSP根據(jù)自身硬件結(jié)構(gòu)設(shè)計的一套完整的集成開發(fā)環(huán)境，通過可視化的圖形界面和用戶進行交互，調(diào)試器（Debugger）能夠?qū)⑿阅芙y(tǒng)計信息以圖形化的方式顯示出來，其集成了指令模擬器（Simulator）、硬件仿真器（Emulator），實現(xiàn)了準(zhǔn)確的硬件時鐘周期數(shù)統(tǒng)計。本文提出的并行化方案在ECS上進行驗證。

2.2 哈達(dá)瑪變化并行化

由于BWDSP1041的處理器單元含有4個獨立運算的宏，所以本文中將哈達(dá)瑪變換H8?8矩陣，每列劃分成一個子塊，將每個子塊加載到1個宏中，這樣就可以實現(xiàn)8個子塊的高度并行運算，同時哈達(dá)瑪矩陣關(guān)于行和列是對稱的。

圖2給出了一個H8?8矩陣的每個子塊加載到宏中向量處理單元的映射示意圖。由于在哈達(dá)瑪變換中對殘差塊先進行變換再進行列變換，矩陣殘差塊X8?8行和列都要與哈達(dá)瑪變換H8?8矩陣進行相乘，在本文中將矩陣殘差塊X8?8，每行和列劃分成一個子塊，分別將每個子塊加載到1個宏中的通用寄存器組中，使四個宏同時處理每個子塊，從而達(dá)到了高度并行化計算的目的。圖3給出了一個X8?8矩陣的每個行和列子塊加載到宏中向量處理單元的映射示意圖（[xij]，i，j=0，1，…，7表示殘差塊中的對應(yīng)點）。

SATD列運算SIMD向量實現(xiàn)過程：

第一步，將圖2和圖3中的子塊加載到相應(yīng)向量處理單元的通用寄存器中，xr[10…17]表示將第一列數(shù)據(jù)加載到x宏中xr10到xr17通用寄存器中，其他以此類推。

第二步，將每個向量處理單元中哈達(dá)瑪變換矩陣的子塊和殘差列子塊相乘，達(dá)到了將向量處理器中32個乘法器并行計算，在一個時鐘周期內(nèi)完成了殘差塊前四列的列變換。

第三步，每次計算完之后，4個宏中的運算結(jié)果依次按行存入宏中通用寄存器中，為行運算過程準(zhǔn)備數(shù)據(jù)。單個向量處理器宏中計算數(shù)據(jù)流程如圖4所示。

行變換計算過程與列變換步驟一樣，以此類推，就可以得到行變換的結(jié)果。

驗證與分析：

為了驗證本文提出的并行化方案的并行度和正確性，在BWDSP1041仿真平臺ECS上進行了32?32大小哈達(dá)瑪變換矩陣的驗證。SATD在C語言和匯編優(yōu)化下的時鐘周期數(shù)如表1所示：

由表1看出，在C語言下由編譯器實現(xiàn)的匯編函數(shù)，不做任何優(yōu)化時硬件利用率不高，利用并行算法之后在一個指令行可以同時實現(xiàn)32個數(shù)的乘和累加，利用指令流水在不造成數(shù)據(jù)相關(guān)的前提下，將數(shù)據(jù)進行排流水，提升了各運算部件的利用率和加快了數(shù)據(jù)計算時間上的并行度。并行實現(xiàn)，大大減少預(yù)測所用的時鐘周期數(shù)，并行加速比達(dá)到87.9。

3 結(jié)束語

HEVC視頻編解中加速幀內(nèi)預(yù)測是非常關(guān)鍵的，本文結(jié)合具有優(yōu)越的并行處理能力的BWDSP1041處理器，提出了一種基于向量SIMD技術(shù)實現(xiàn)SATD計算的并行優(yōu)化算法。在HEVC標(biāo)準(zhǔn)算法的基礎(chǔ)上，將沒有相互關(guān)聯(lián)的數(shù)據(jù)計算所需的數(shù)據(jù)提前加載到通用寄存器中，通過填充指令流水將數(shù)據(jù)的讀和寫放在一個指令行，提出了適合并行化的算法。利用4個宏內(nèi)的32個乘法器和加法器進行并行計算，大大提高了計算效率。實驗中發(fā)現(xiàn)指令行大小不能超過16字，寫總線只有256bit等編程資源約束，所提并行算法的時間加速還有很大的優(yōu)化潛力。本文提出的并行算法屬于通用方法。

參考文獻：

[1] Lainema J，Bossen F，Han W J，et al.Intra Coding of the HEVC Standard[J].IEEE Transactions on Circuits&Systems; for Video Technology，2012，22（12）：1792-1801.

[2] Cristina O C，Mihnea U R，Ionut P.HEVC intra partitioning and mode decision using histograms of oriented gradients[C]//Electronics and Telecommunications （ISETC），2016 12th IEEE International Symposium on.IEEE，2016：277-280.

[3] Lu X，Xiao N，Hu Y，et al.A hierarchical fast coding unit depth decision algorithm for HEVC intra coding[C]//Visual Communications and Image Processing（VCIP），2016.IEEE，2016：1-4.

[4] Chen J，Yu L.Effective HEVC intra coding unit size decision based on online progressive Bayesian classification[C]//Multimedia and Expo （ICME）， 2016 IEEE International Conference on.IEEE，2016：1-6.

[5] Tian R，Zhang Y，F(xiàn)an R，et al. Adaptive Fast Mode Decision for HEVC Intra Coding[C]// International Conference on Digital Image Computing：Techniques and Applications，2016：1-6.

[6] Zhou X， Shi G， Zhou W. Perceptual CU Size Decision and Fast Prediction Mode Decision Algorithm for HEVC Intra Coding[C]//Multimedia （ISM）， 2016 IEEE International Symposium on. IEEE， 2016： 375-378.

[7] Jiang W， Ma H， Chen Y. Gradient based fast mode decision algorithm for intra prediction in HEVC[C]//Consumer Electronics， Communications and Networks （CECNet）， 2012 2nd International Conference on. IEEE， 2012： 1836-1840.

[8] Jamali M， Coulombe S. RDO cost modeling for low-complexity HEVC intra coding[C]//Electrical and Computer Engineering （CCECE）， 2016 IEEE Canadian Conference on. IEEE， 2016： 1-5.

[9] 費馬燕， 彭宗舉， 李持航， 等. 融合視覺感知特性的 HEVC 率失真優(yōu)化[J]. 中國圖象圖形學(xué)報， 2015， 20（7）： 857-864.

[10] Yeo C， Tan H L， Tan Y H. On rate distortion optimization using SSIM[J]. IEEE Transactions on Circuits and Systems for Video Technology， 2013， 23（7）： 1170-1181.

[11] Jiang W， Yang J. The rate-distortion optimized quantization algorithm in Compressive Sensing[J]. Optik - International Journal for Light and Electron Optics， 2014， 125（15）：3980-3985.

[12] 謝曉燕，徐衛(wèi)芳，劉帆. HEVC幀內(nèi)預(yù)測Planar和DC模式算法的并行化設(shè)計[J].電視技術(shù)，2015，39（5）：4-8.