佘成龍 段苓麗 汪輝

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

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

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

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

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

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

則SATD = 112/2 =56。

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

[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]

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

則SATD = 1160/2 =580。

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

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

2.1 BWDSP1041仿真平臺(tái)

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

1）處理宏

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

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

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

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

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

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

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

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

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

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

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

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

驗(yàn)證與分析：

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

[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] 費(fèi)馬燕， 彭宗舉， 李持航， 等. 融合視覺感知特性的 HEVC 率失真優(yōu)化[J]. 中國(guó)圖象圖形學(xué)報(bào)， 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ù)測(cè)Planar和DC模式算法的并行化設(shè)計(jì)[J].電視技術(shù)，2015，39（5）：4-8.