基于BWDSPHEVC的向量SIMD哈达玛变换并行设计

佘成龙 段苓丽 汪辉

摘要：针对HEVC中SATD率失真代价计算的特点，本文提出利用向量SIMD（单指令多数据流）技术，设计哈达玛变换的并行化方案。该方案采用多加法器和多乘法器协同工作模式，发挥处理器的并行性，通过合理的数据安排，很好地实现了多个宏中数据的并行计算，增大DSP的数据吞吐率，提高数据处理速度。实验结果表明其在单核BWDSP1041上的并行加速比达到87.9，证明了优化工作的有效性。

关键词：HEVC；帧内预测；并行化；BWDSP1041處理器

中图分类号：TP391 文献标识码：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）的编码单元，采用遍历的方法，块的尺寸根据图像细节复杂度通过划分自适应改变其大小。编码单元（CU）包括从64×64到8×8的各种大小。基于四叉树结构计算全部RDCost来得到最优CU大小[1]。帧内预测要对每一种可能的预测模式都采用SATD对残差进行计算和比较，从而得到最优模式这个过程非常耗时存在着巨大的计算量。其中对计算过程较为复杂和耗时的角度预测模式进行并行化设计，缩短帧内预测的时间，对于实现HEVC的实时性意义很重大。现在H265帧内预测的加速和优化研究重点基本在4个方面： 一是块类型预判断或者提前终止CU块的划分[2～4]； 二是缩小模式选择范围[5～7]； 三是优化率失真代价函数，率失真代价的计算用更简单的方法[8～11]；四是从多处理器角度并行实现模式预测[12]和SATD率失真代价计算。本文对在帧内预测基于SATD率失真代价计算进行并行化探究，提出了适合在多核和多运算部件结构上并行计算的算法，对于加速帧内预测有实际意义，大大缩短帧内预测所需时间。

1 哈达玛变换的算法研究

相对于H.264/AVC支持8个预测方向，HEVC规定了33种角度方向预测，进一步细化了这些预测方向，方向性预测的基本原理是：当前待预测的像素沿特定的预测方向在参考样本上投影，投影所在的位置对应的像素值就是预测值。预测角度设计的倾向是为接近水平和垂直的角度提供更密集的覆盖。各个模式的格点（角度）分布是不均匀的。越靠近垂直方向，分布越是细密，越是靠近对角方向越是稀疏。角度中模式都相当于做了一个偏移在垂直或水平方向上。在HM编码器中逐一对35种帧内预测模式采用SATD对残差进行哈达玛变换后的系数绝对求和。以4?4和8?8大小块为例，介绍哈达玛变换矩阵的计算过程。对于一个32?32矩阵块的残差块，在代码实现过程中，会将矩阵块分割成4个8?8大小的矩阵块，再分别对矩阵块进行哈达玛变化，最后再将4个8?8矩阵的哈达玛变换后的值相加，就得到了32?32矩阵块哈达玛变换结果。

定义[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。

当块大小为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残差块为例，在对残差块进行哈达玛变换时需要进行两次矩阵相乘，矩阵大小都为8?8，需1024次乘法、896次加法，可见计算量是很大的，如果采用传统的矩阵相乘，主要采用行乘列再进行累加计算，一般采用3重循环实现，若在DSP上直接采用汇编语言串行计算实现，将大大限制了DSP的数据处理能力。通過本文采用向量SIMD设计方法，充分利用BWDSP1041处理器多加法器和多乘法器协同工作模式，发挥处理器的并行性，通过合理的数据安排，让4个宏中的数据并行计算，使处理器的计算性能得到充分的发挥，缩短了计算所用的时间，提高了代码利用率。

2 向量SIMD哈达玛变化的并行化

2.1 BWDSP1041仿真平台

BWDSP1041是中国电子科技集团公司第38研究所设计的一款32位静态超标量浮点DSP处理器。处理器共有13级流水，BWDSP1041核内部包含4个基本执行宏（Element operation Macro，简称宏）。指令主要由数据传输/调用，如存储器同运算部件之间、存储器之间的数据交互、数据运算、程序控制及输入输出数据命令等组成。

1）处理宏

BWDSP1041有4个执行宏，分别标识X、Y、Z、T，其结构和功能相同，在指令前指定宏标识，来说明指令在哪个执行宏中运行，指定多个则在多个执行宏运行，不指定宏则在 4个执行宏同时运行 （ 宏标识与 R 紧邻 ），每个执行宏资源有：8 个 ALU， 编号 0～7；8个 MUL，编号 0～7，4个 SHF，编号0～3；1个SPU，128个通用寄存器（参见图1）。

2）地址产生器及数据传输通道

BWDSP1041处理器有3个地址产生器，其结构和功能一样。地址生成器（AGU）产生存储器与宏之间的数据交换所需的地址。地址产生器每个都有1组地址辅助寄存器，用于寄存各种地址变化关系的参数值，编号 0～15。

ECS（Efficient Coding Studio）是BWDSP根据自身硬件结构设计的一套完整的集成开发环境，通过可视化的图形界面和用户进行交互，调试器（Debugger）能够将性能统计信息以图形化的方式显示出来，其集成了指令模拟器（Simulator）、硬件仿真器（Emulator），实现了准确的硬件时钟周期数统计。本文提出的并行化方案在ECS上进行验证。

2.2 哈达玛变化并行化

由于BWDSP1041的处理器单元含有4个独立运算的宏，所以本文中将哈达玛变换H8?8矩阵，每列划分成一个子块，将每个子块加载到1个宏中，这样就可以实现8个子块的高度并行运算，同时哈达玛矩阵关于行和列是对称的。

图2给出了一个H8?8矩阵的每个子块加载到宏中向量处理单元的映射示意图。由于在哈达玛变换中对残差块先进行变换再进行列变换，矩阵残差块X8?8行和列都要与哈达玛变换H8?8矩阵进行相乘，在本文中将矩阵残差块X8?8，每行和列划分成一个子块，分别将每个子块加载到1个宏中的通用寄存器组中，使四个宏同时处理每个子块，从而达到了高度并行化计算的目的。图3给出了一个X8?8矩阵的每个行和列子块加载到宏中向量处理单元的映射示意图（[xij]，i，j=0，1，…，7表示残差块中的对应点）。

SATD列运算SIMD向量实现过程：

第一步，将图2和图3中的子块加载到相应向量处理单元的通用寄存器中，xr[10…17]表示将第一列数据加载到x宏中xr10到xr17通用寄存器中，其他以此类推。

第二步，将每个向量处理单元中哈达玛变换矩阵的子块和残差列子块相乘，达到了将向量处理器中32个乘法器并行计算，在一个时钟周期内完成了残差块前四列的列变换。

第三步，每次计算完之后，4个宏中的运算结果依次按行存入宏中通用寄存器中，为行运算过程准备数据。单个向量处理器宏中计算数据流程如图4所示。

行变换计算过程与列变换步骤一样，以此类推，就可以得到行变换的结果。

验证与分析：

为了验证本文提出的并行化方案的并行度和正确性，在BWDSP1041仿真平台ECS上进行了32?32大小哈达玛变换矩阵的验证。SATD在C语言和汇编优化下的时钟周期数如表1所示：

由表1看出，在C语言下由编译器实现的汇编函数，不做任何优化时硬件利用率不高，利用并行算法之后在一个指令行可以同时实现32个数的乘和累加，利用指令流水在不造成数据相关的前提下，将数据进行排流水，提升了各运算部件的利用率和加快了数据计算时间上的并行度。并行实现，大大减少预测所用的时钟周期数，并行加速比达到87.9。

3 结束语

HEVC视频编解中加速帧内预测是非常关键的，本文结合具有优越的并行处理能力的BWDSP1041处理器，提出了一种基于向量SIMD技术实现SATD计算的并行优化算法。在HEVC标准算法的基础上，将没有相互关联的数据计算所需的数据提前加载到通用寄存器中，通过填充指令流水将数据的读和写放在一个指令行，提出了适合并行化的算法。利用4个宏内的32个乘法器和加法器进行并行计算，大大提高了计算效率。实验中发现指令行大小不能超过16字，写总线只有256bit等编程资源约束，所提并行算法的时间加速还有很大的优化潜力。本文提出的并行算法属于通用方法。

参考文献：

[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，Fan 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 率失真优化[J]. 中国图象图形学报， 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] 谢晓燕，徐卫芳，刘帆. HEVC帧内预测Planar和DC模式算法的并行化设计[J].电视技术，2015，39（5）：4-8.