2. 西安邮电大学 电子工程学院, 西安 710121;
3. 西安邮电大学 计算机学院, 西安 710121
高效视频编码（HEVC）标准中引入的不对称分割模式导致运动估计算法中绝对差值和（SAD）运算量成倍增加.为了提高运动估计算法的执行效率，方便用户进行自主选择，设计了同时支持不对称分割模式开启和关闭2种执行模式以及执行模式间自由切换的可重构阵列结构.为了满足用户要求编码速度的同时，最大限度地利用可重构阵列处理器的资源，在阵列结构为16×16个处理元中通过加载16×8、16×4以及16×2个处理元的指令来进行阵列规模的动态重构，采用指令下发的方式将不同的指令发送到对应处理元进行相应配置.实验结果表明，所提出的可重构实现方式在硬件资源占用量接近条件下，相较于流水化实现处理时间减少了约35%，吞吐量提高了约0.4倍.该实现具有较高的执行效率，能够进行执行模式与阵列规模的切换，具有较好的灵活性.
2. School of Electronic Engineering, Xi'an University of Posts and Telecommunications, Xi'an 710121, China;
3. School of Computer Science and Technology, Xi'an University of Posts and Telecommunications, Xi'an 710121, China
The asymmetric partitioning mode introduced in the high efficiency video coding (HEVC) standard results in a double increase of the sum of absolute difference (SAD) operation amount in the motion estimation algorithm. In order to improve the efficiency of motion estimation algorithm, it is convenient for users to choose independently, a reconfigurable array structure is designed which supports both the opening and closing of an asymmetric partitioning mode and the free switching between execution modes. In order to satisfy the user's requirement for coding speed, and maximize the use of the resources of the reconfigurable array processor, 16×8, 16×4, and 16×2 processing elements are loaded in an array structure of 16×16 processing elements. The instruction is used to dynamically reconfigure the array size, and different instructions are sent to corresponding processing elements for corresponding configuration by means of the instruction issuance manner. The experimental results show that the proposed reconfigurable implementation approach reduces the processing time by about 35% and the throughput is improved by about 0.4 times compared with the streamlining under the condition that the hardware resource occupancy closely. The implementation has high execution efficiency, and can switch between execution mode and array size, and has better flexibility.
目前，高效视频编码(HEVC, high efficiency video coding)中，运动估计计算量巨大，消耗超过50%的编码时间，是视频编码压缩效率的决定性因素[1].而绝对差值和(SAD, sum of absolute difference)运算占据了整数运动估计运算的大部分时间，占用资源较多，影响运动估计整体性能.目前，SAD的普遍实现方式分为3种：通用处理器实现，专用集成电路(ASIC, application specific integrated circuit)实现和可重构体系结构实现.通用处理器本质上是通过串行的软件编程实现不同的算法，具有较高的灵活性，但其运算能力有限难以适应高清实时编码.相比通用处理器，专用集成电路可以很好地解决计算效率低的问题，黄卫锋等[2]采用16个处理元(PE, processing element)计算大小为4×4的参考块和预测块的SAD值，仅计算全部SAD4×4需要4 096个处理元.该并行方案虽然效率较高，但占用硬件资源较多. Tung等[3-6]提出的结构，可以完成4×4至16×16分块模式SAD值计算，运算效率较高，但难以满足HEVC中整数运动估计可变块和不对称分割模式(AMP, asymmetric method partition)划分要求. Byun等[7]提出了一种能够计算4×4至64×64分块模式的SAD累加模块，支持AMP模式.该结构的局限性在于使用和最大编码树单元(CTU, code tree unit)相同的规模阵列导致硬件开销急剧上升. Alcoer[8]在SAD运算模块把编码单元(CU, code unit)划分和SAD运算相结合，导致相同模块重复计算，降低运算效率的同时也增加了硬件消耗.因此，专用硬件实现方式虽然提升了运算效率，但若应用发生改变，则需重新设计电路结构，灵活性差、成本较高.可重构阵列处理器作为一种高效的体系结构，兼顾专用硬件的高效性和通用处理器的灵活性，满足了视频算法的需求[9].在可重构系统上实现运动估计算法，与专用硬件相比，在时钟频率接近范围内，可重构阵列处理器能够根据不同视频图像处理需求，灵活配置处理元逻辑功能和处理元之间互连方式，提升计算性能.韩佳[10]在提出的可重构阵列结构上实现SAD算法.该结构簇内通信通过路由访问相邻的8个处理元来完成导致资源占用量大，支持32×32的搜索区间，以及8×8到64×64全部对称编码块划分方式.该结构的局限性在于没有根据用户需求提供AMP模式开启和关闭两种执行模式，没有充分体现可重构系统的优越性.
在此背景下，参考HEVC测试模型HM，在SAD运算中提供两种执行模式.设计了一种针对AMP开启模式的重构机制，默认执行AMP关闭模式，若用户对视频质量有较高要求，可修改配置文件，通过指令下发的方式将配置文件发送到对应处理元进行配置.为了最大限度地利用可重构阵列结构，设计了可对阵列结构进行2×2，4×4，8×8以及16×16个PE规模的动态重构.可根据用户的不同需求，对阵列结构的规模、执行模式重新调度.
1 研究动机HEVC视频编解码标准中SAD值用来表示在预定搜索区域内当前帧与参考帧的绝对差值和，SAD值越小匹配度越好. SAD值的定义为
| $ {\rm{SAD}}\left( {i, j} \right) = \sum\limits_{m = 1}^M {\sum\limits_{n = 1}^N {\left| {{f_k}\left( {m, n} \right)-{f_{k-1}}\left( {m + i} \right), n + j} \right|} } $ | (1) |
其中：fk(m, n)为当前帧中亮度块的像素值，fk－1(m+i, n+j)为参考帧中亮度块的像素值.
由于HEVC不对称分割模式AMP的引入，使得PU由原来的681个增加至849个，编码质量提高的同时降低了编码效率.笔者对BUS_176x144，BasketballPass_416x240，BQSquare_416x240，Cactus_1920x1080，PoznanStreet_1920x1088这5种典型测试序列的AMP开启模式和AMP关闭模式，通过HEVC测试模型HM15.0进行测试.测试结果如表 1.
|
表 1 QP=32，全搜索模式下统计结果 |
五组测试序列在AMP开启(AMP=1)执行模式下较AMP关闭(AMP=0)执行模式下的比特率略有下降，Y分量的峰值信噪比基本相同，但执行时间增加了约1.7倍.实验结果表明，AMP开启执行模式编码质量较高但计算复杂，编码效率低；AMP关闭执行模式编码效率较高但编码质量较低.因此针对用户对视频速度和质量的不同要求实现一种同时支持AMP开启和关闭两种执行模式以及执行模式间可切换的计算结构是非常有必要的.
2 动态可重构阵列处理器及其指令下发网络可重构阵列处理器由全局指令存储器(IM)、输入存储器、输出存储器、阵列处理器和全局控制器5部分组成.全局指令存储器用于存储阵列处理器工作的操作指令和调用指令；输入存储器负责从外存中加载相应的测试序列；阵列处理器为核心计算部分由16×16个簇(PEG, processing element group)组成.全局控制器为可重构机制的核心部分.主处理器只需要向全局控制器发送任务指令和必要的数据或数据存储地址，全局控制器便会控制指令传输网络分配指令给不同的PE执行相应的操作.如图 1所示.
|
图 1 动态可重构阵列处理器 |
全局控制器用于实现对阵列计算资源的控制与管理，包括操作指令的广播、调用指令的分发、计算资源信息的收集等.其上层为主机接口，下层为16×16个PE组成的阵列处理器.主要功能是在主机接口和阵列处理器之间形成一个层次化编程网络，利用层次化编程网络来实现对阵列计算资源的控制与管理.为了取址简单，寻址的过程中位宽可以逐级递减以及确保每一条指令都同时到达PE，层次化编程网络设计为通过H型网络进行指令加载.主机接口访问阵列处理器时，全局控制器接收来自主机接口的总线信息.总线宽为40 bit，其中bit[31:30]用于判断是进行对数据进行反馈(00)、指令下发(01)、指令广播(10)还是指令调用(11).当全局控制器监控特定处理元的状态时，会接收到一条总线信息，然后根据寻址信息判断出所要监控的具体PE，并对相应PE的数据存储器进行访问，得到监控数据信息.当进行指令下发操作时，接收一条总线信息，根据总线信息中对应的寻址信息判断出所要访问的具体PE. bit[39:32]用于寻址，寻址方式为到达节点0的40 bit信息通过对bit[39]进行检测，如果是1则丢弃bit[39]，将bit[38:0]发送到右节点；如果是0则丢弃bit[39]，将bit[38:0]发送到左节点.然后对bit[38]进行检测，如果是1则丢弃bit[38]，将bit[37:0]发送到下节点；如果是0则丢弃bit[38]，将bit[37:0]发送到上节点.
以此类推，左上寻址为1，右下寻址为0，以此方式，最终完成对256个轻核处理元(TCPE, thin-core processor element)的寻址. bit[29:0]为下发到指定PE的指令.例如寻址PE0000的总线为：0000_0000_01_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.当进行指令广播操作时，需接收两条总线信息并将第1条的掩码信息进行保存，然后再根据第2条的寻址信息判断出所要访问的多个PE，并对这多个PE进行指令广播.第1条指令中bit[39:32]用来判断是否进行广发操作，0为单发，1为广发.第2条指令bit[39:32]用于寻址，寻址方式如指令下发，bit[15:0]用来定位到PE的某一行.例如同时启动PEG00、PEG01、PEG10、PEG11，从各PE的17条开始执行的总线为第1条00111111_10_00000 0000000000000000000000000；第2条：00000000_11_000000000000000000000_000010001.
阵列处理器由1 024个PE组成. PE之间采用邻接互连共享寄存器的方式进行数据交互，每个轻核处理元东、南、西、北4个方向均有与相邻轻核处理元进行数据交互的接口信号. 4×4个PE为一个簇，簇与簇之间通过共享存储或路由网络实现通信.
3 SAD算法的可重构实现 3.1 SAD算法并行化设计在SAD运算核心模块中，大小为64×64的编码单元可以被分成256个4×4预测块[11]，各SAD4×4值之间相互独立，因此可并行处理实现.不同分块模式的SAD值之间存在数据关系，当前分块模式的SAD值可由上一级合并得到[12].因此可以利用数据间的相互关系提高算法并行效率.通过重复利用不同规模的PE阵列来完成所有SAD值的计算.首先通过输入存储把64×64的当前块和参考块加载到PE阵列并将算法指令初始化到指令存储器中，然后多个PE同时执行SAD4×4的计算，接着通过加法树模块，获取所有SAD值和运动矢量，最后把运算后的SAD值传递给下一个模块.
以16×16规模为例.基础模块采用和4×4预测单元相同的PE个数来实现对SAD4×4的计算可以提高数据复用率减少以算法运行时间.该模块的执行过程如下：第1步，从外存中获取当前编码块中亮度块的像素值和搜索窗中左上角的参考块的像素值，存放在输入存储中.然后，PE阵列中的每个PE通过缓存区得到相同大小的4×4亮度块和色度块；第2步，PE阵列接收到来自输入存储数据后，位于SAD运算核心模块中的256个PE同时对4×4分块模式的预测单元进行SAD值的计算；第3步，将计算得到的SAD值存放在阵列对应的PE中，等待加法树模块的调用.经过基础模块计算后，阵列中每一个PE都存储了SAD4×4的值. SAD4×4为加法树的根，通过加法树的拓扑结构可以得到SAD4×8至SAD64×64之间的SAD的值.
根据分块模式，该加法树模块可分3个部分来实现.其中4×4至16×16分块模式的SAD值通过4×4个PE阵列计算，如图 2所示；16×16~32×32分块模式的SAD值通过8×8个PE阵列计算，32×32~64×64分块模式的SAD值通过16×16个PE阵列计算，每行分块模式的SAD值在统一时刻执行.计算得到的SAD值根据分块模式的不同分别存储.通过判断该SAD值是否被后续使用来选取存储PE的位置.若该值被后续使用则优先选择PE阵列中右下方的PE存储，反之则选择左上方PE存储.以图 3中PE10 SAD8×4为例：首先将PE00 SAD4×4中的SAD4×4通过邻接互连加载到PE10中，并将PE10 SAD4×4中SAD4×4从内存中取出与从PE00中加载的SAD4×4值相加得到SAD8×4，由于SAD8×4需要被后续使用来计算SAD8×8，所以SAD8×4存入PE10中.
|
图 2 4×4至16×16 SAD分块模式的数据流 |
|
图 3 规模重构指令存放 |
动态重构机制主要核心为指令下发网络.笔者采用指令下发网络的指令广播、反馈和指令下发操作.指令广播和指令反馈操作负责本文重构中的规模重构，该重构是将指令预先存放在阵列结构中每个PE自带的指令存储器中，然后通过指令广播操作同时开启全部或部分PE.指令下发操作主要负责重构中执行模式重构，该重构是将全局指令存储器中的指令通过指令下发操作下发到指定PE中.
规模重构具有256个PE，128个PE，64个PE和32个PE四种规模，重构的依据为PE是否在空闲状态，指令下发格式中bit[31:30]为00是开始收集计算资源信息，当检测到PC(program counter)值停留在511时，表示当前PE为空闲状态，此时指令下发网络格式bit[31:30]设置为10开始指令广播操作.最大限度的利用每个PE，如图 3所示.
算法指令配置如下：PEG00、PEG01同时按顺序存放16×16、16×8、16×4和16×2规模的指令；PEG00、PEG01、PEG10、PEG11同时按顺序存放16×16、16×8和16×4规模的指令；PEG00、PEG01、PEG02、PEG03、PEG10、PEG11、PEG12、PEG13同时按顺序存放16×16和16×8规模的指令；其他PEG中存放16×16规模的指令. PE的执行方式为给定一个初始地址定位到指定指令行数后顺序执行.以规模4×4切换8×8规模为例：假设8×8规模的指令开始于PEG00、PEG01、PEG02、PEG03、PEG10、PEG11、PEG12、PEG13中各PE的本地指令存储器中第17行，则切换8×8规模的指令广播操作指令为：10111111_10_0000000000000000000000 00000000；00000000_11_000000000000000000000_000010001，PE便会以17行指令开始顺序执行.
执行模式重构为AMP开启和AMP关闭模式的重构，数据流程图如图 4.由于各SAD值之间相互独立，当前分块模式的SAD值可由上一级合并得到，并且AMP分块模式的各SAD值不需要进行后续操作.为了提高算法运行效率，以及数据复用率，默认执行AMP关闭模式后将各个对称分块模式的SAD值存放在相应的本地存储中，从而执行AMP开启模式时将不必要对称分块模式的指令重新下发，仅对AMP分块模式进行指令下发操作.对称分割模式的指令代码，存储在PE的指令存储器；AMP分块模式的指令代码存储在全局指令存储器.电路上电复位后默认执行对称分割模式的SAD值计算.当用户需要执行AMP执行模式时，则通过指令下发网络将全局指令存储器中的AMP别从PE0011，PE0013，PE0013中加载出来然后下发到PE0000中进行SAD12×16的计算.执行模式重构的原则是默认执行AMP关闭操作若用户对视频质量不满意可进行指令下发操作，发送AMP分块模式计算指令到PE0000进行附加计算.下发到PE0000中的指令形式为：0000_0000_01_xxxxxxxxxxxxxxxxxxxxxxxxxx xxxx.
|
图 4 执行模式重构数据流程 |
为了验证可重构方案的可行性，基于提出的可重构阵列结构进行验证.方法如下：首先修改测试模型HM15.0的配置文件，获取测试数据，存入片外存储，然后将并行方案的指令初始化到指令存储器中，最后在可重构阵列结构上通过ModelSim进行仿真验证.在SAD运算并行化方案功能仿真后，通过BEE4自带的Virtex-6 FPGA开发板对设计进行综合.实验结果表明阵列规模为256个PE的工作频率为156 MHz，电路规模为481152LUTs和156992Flip-flops；阵列规模为128个PE的工作频率为156 MHz，电路规模为240576LUTs和78496Flip-flops；阵列规模为64个PE的工作频率为156 MHz，电路规模为124848LUTs和39248Flip-flops；阵列规模为32个PE的工作频率为156 MHz，电路规模为65424LUTs和19624Flip-flops.
图 5统计了3组测试序列在规模为256个PE，128个PE，64个PE和32个PE下的SAD运算仿真验证周期数及运行时间.其中对于高清序列Cactus_1920x1080_50执行周期最长为1 125 900，时间为7.217×10-3 s，帧率为138 f/s.通过图 5数据可以看出笔者提出的可重构方案能适应高清视频图像.
|
图 5 SAD运算核心模块仿真验证 |
对于SAD算法的实现，表 2统计了不同电路规模下资源占用量和运行时间.
|
|
表 2 不同电路规模下SAD计算时间统计 |
可以看出随着PE阵列的增多，电路规模呈递增状态，运行时间呈递减状态.在阵列规模为16×2个PE时，资源占用量和文献[8]中的占用量接近.此时，运行时间为7.217×10-3 s，文献[8]中的运行时间为1.305×10-2 s，执行速度相比文献[8]中的执行速度提高了约81%.
表 3列出了3种实现方式下的性能比较结果.软件实现方面：通过HEVC官方测试软件HM15.0进行实验，以Cactus_1920×1080_50为测试序列，搜索窗大小为64×64，AMP模式开启情况下运行时间为79.4 s，同等条件下所提出的可重构阵列结构使用Virtex-6实现时16×16PE规模下运行时间为2.265×10-3 s，16×8PE规模下运行时间为2.836×10-3 s，16×4PE规模下运行时间为4.299×10-3 s，16×2PE规模下运行时间为7.217×10-3 s，Virtex-7实现时16×2PE规模下运行时间为6.008×10-3 s，对比软件处理高清图像优势明显.专用硬件实现方面：不支持AMP模式.虽然支持多层次数据复用，但只支持4×4~16×16的块尺寸，不符合HEVC标准[6].支持可变换块尺寸和AMP模式，工作频率高达250 MHz，但是整个设计规模占用356万门，资源占用过高[7]. Alcocer等[8]将SAD的计算的执行周期与搜索窗大小一致，随着搜索窗的增大运算周期呈指数增长.
|
|
表 3 SAD运算性能比较结果 |
与软件及专用硬件实现方式相比，笔者提出的可重构阵列结构主要优势在于：对于SAD的计算，参照了软件HM15.0的执行方式，可对2种执行方式进行切换，也可在需求的执行速度下动态调整阵列处理器的PE使用量，最大限度的发挥每个PE的作用.相比于软件的串行执行，笔者对于SAD算法中对称分割模式的SAD值进行并行化计算，使得算法执行效率明显提升.相比于专用硬件的单一执行模式，可对SAD算法的2种执行方式进行切换操作，对于SAD算法中的AMP分块模式的计算可根据用户对运行时间、比特率和视频质量的不同要求来自行选择开启或关闭操作，具有较高的灵活性.
5 结束语基于可重构阵列处理器结构，针对实现新一代HEVC编解码器运动估计中SAD算法引入的AMP模式，提出了一种新的重构方案.该方案能够进行AMP模式的开启和关闭切换，并且在给定的速度前提下，该结构能够进行动态调整阵列处理器规模，能够最大限度地利用可重构阵列处理器.对HEVC官网提供的三组典型序列176×144、416×240、1 920×1 080进行测试，实验结果表明：对于SAD算法的实现，该结构能够达到实时处理的要求；对于SAD算法的模式切换以及动态调整处理器规模，该结构能够正确调度.对比文献[8]笔者在资源占用量相当的情况下，吞吐量提高了约0.4倍，执行时间减少了约35%，最突出的优点是该可重构结构以方便不同用户为出发点具有较好的灵活性，更适合市场应用.
| [1] | Kibeya H, Belghith F, Loukil H, et al. TZSearch pattern search improvement for HEVC motion estimation modules[M]. 2014 1st International Conference on Advanced Technologies for Signal and Image Processing (ATSIP), Sousse , 2014: 95-99. |
| [2] | 黄卫锋, 桑红石, 郑兆青, 等. 用于H. 264的高性能整像素运动估计VLSI的设计[J]. 微电子学, 2007, 37(2): 260–264. doi: 10.3969/j.issn.1004-3365.2007.02.027 |
| [3] | Tung D M, Dong T L T. A VLSI architecture for H. 264/AVC variable block size motion estimation[J]. Journal of Automation & Control Engineering, 2015, 3(1): 51–55. |
| [4] | Grellert, M, Sampaio, F, et al. A multilevel data reuse scheme for motion estimation and its VLSI design[C]//ISCAS. Rio de Janeiro: Circuits and Systems(ISCAS), 2011 IEEE International Symposium of Circuits and Systems (ISCAS), Rio de Janeiro, 2011, 583-586. |
| [5] | Mariusz Jakubowski. Optimization of the adaptive computationally-scalable motion estimation and compensation for the hardware H. 264/AVC Encoder[J]. Journal of Signal Processing Systems, 2016, 82(3): 391–402. doi: 10.1007/s11265-015-1021-5 |
| [6] | Chao-Yang Kao. A memory-efficient and highly parallel architecture for variable block size integer motion estimation in H.264/AVC[J]. IEEE Transactions on Very Large Scale Integration Systems, 2010, 18(6): 866–874. doi: 10.1109/TVLSI.2009.2017122 |
| [7] | Byun J, Jung Y, Kim J. Design of integer motion estimator of HEVC for asymmetric motion-partitioning mode and 4K-UHD[J]. Electronics Letters, 2013, 49(18): 1142–1143. doi: 10.1049/el.2013.0936 |
| [8] | Alcocer E, Gutierrez R, Lopez-Granado O, et al. Design and implementation of an efficient hardware integer motion estimator for an HEVC video encoder[J]. Journal of Real-Time Image Processing, 2016, 11(1): 1–11. |
| [9] | 李涛, 蒋林, 刘镇弢, 等.一种新型阵列视频信号处理单元结构[P], 中国, (中华人民共和国国家产权局)20012中国公开, 201110046537. 8. |
| [10] | 韩佳. 基于可重构系统的HEVC运动估计算法实现[J]. 信息技术, 2016, 40(11): 12–17. |
| [11] | Gary J. Overview of the high efficiency video coding (HEVC) standard[[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2012, 22(12): 1649–1668. |
| [12] | Il-Koo Kim. Block partitioning structure in the HEVC standard[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2012, 22(12): 1697–1706. |