阵列处理器上一种基于DFGSP的分像素插值算法实现

胡传瞻 蒋 林 朱 筠 谢晓燕 王 萍 杨 坤

1(西安邮电大学计算机学院 陕西 西安 710121) 2(西安科技大学集成电路实验室 陕西 西安 710054) 3(西安邮电大学电子工程学院 陕西 西安 710121)

0 引 言

视频编解码应用具有数据量大、算法各异、标准众多的特点。H.264/AVC、H.265/HEVC是当前应用最为广泛的视频编解码标准，其中分数运动估计(Fractional Motion Estimation，FME)是视频编解码器中计算密集度最高的任务之一，而亚像素精度运动估计是其中最复杂的部分。国内外学者已有很多针对各种分辨率下的FME软、硬件实现方案。文献[1]提出了两个近似的HEVC分数插值滤波器，通过修改插值滤波器系数来进行分数滤波，能耗降低了67.1%，但是以损耗峰值信噪比(Peak Signal to Noise Ratio，PSNR)和增加比特率为代价。文献[2]提出了一种可配置的滤波器的电路结构，虽然提高了硬件资源利用率，但却增加了计算的复杂度。

目前现有的方法可以减少较多的数据计算量，但是分数像素插值计算的硬件实现难度较大，资源消耗过多，采用超大规模集成电路进行视频编码时缺少灵活性，难以满足视频编码质量多标准的要求。可重构阵列处理器在视频方面应用十分广泛，在进行复杂计算时，会将复杂的计算拆分成若干的子任务，将若干子任务合理地映射到可重构阵列处理器中是十分重要的。文献[3]提出了临时数据的寄存器存储和无寄存器存储相结合的可重构算术逻辑单元簇(Reconfigurable ALU Cluster，RAC)间通信方式，设计了计算模型松弛映射调度算法，该方法达到了复杂计算内核运行时间的最大化，缺点是RAC的配置成本较大。文献[4]提出了一种并行度最大化的贪婪算法，虽然获得了较大并行度，但此算法并没有考虑实际存在的硬件碎片问题。文献[5-6]提出了细粒度的划分方法，但并未和粗粒度可重构体系结构(Coarse Grained Reconfigurable Architecture，CGRA)映射技术相结合。

合理的并行映射方案可以解决资源分配不合理、计算复杂等问题，从而提高可重构阵列处理器的计算效率。文献[7]提出了一个双输入神经网络，捕获应用程序中数据流图(Data Flow Graph，DFG)的元素和CGRA元素阵列中特征的过程，建立了自动培训和测试的数据集，实现了基于整个映射流程的卷积神经网络(Convolutional Neural Network，CNN)预测，减少了编译时间。文献[8]为了获得用于CGRA应用程序映射的更好的数据传输路径，提出了一种用于路由资源共享优化的两步蚁群算法，将传统蚁群算法的搜索过程分为两步，执行时间比传统蚁群算法少32%，且数据传输路径也减少4%～6%。由此可看出，任务划分对可重构处理器提高整体执行性能、降低能耗具有重要作用。

因此本文采用了一种基于DFGSP算法[9]，针对亚像素精度运动估计中的计算部分，按深度优先搜索方式，对该算法的DFG图进行合理任务划分，设计并行映射方案，在视频阵列处理器上加速实现。使其兼具软件可编程灵活性和硬件实现的高效性。达到提高计算速度和节约大量硬件资源的目的。

1 分像素插值的DFG

HEVC沿用了H.264中1/2、1/4像素精度运动估计，但使用了更多邻近像素点进行亚像素精度插值，其重点是对亮度分量进行插值计算。1/2像素模板和1/4像素模板如图1所示。亮度分量的1/2像素位置值由离散余弦变化的8抽头滤波器生成，亮度分量1/4、3/4像素位置的值由离散余弦变化的7抽头滤波器生成，抽头系数如表1所示。

表1 亮度差值滤波器抽头系数表

分像素插值的计算过程分为两步：

(1) 以1/2像素点公式为例进行变换，将像素点A0,-3、A0,-2、A0,-1、A0,0、A0,1、A0,2、A0,3、A0,4分别记作a、b、c、d、e、f、g、h，得到式(1)。

h0，0=(-a+4b-11c+40d+40e-11f+4g-h)>>6=

[-(a+h)+4(b+g)-8(c+f)-4(c+f)+(c+f)+

32(d+e)+8(d+e)]>>6=

[(b+g)>>2-(a+h)-((c+f)>>3+(c+f)>>2))+

(d+e)>>5+(d+e)>>3]>>6

(1)

对式(1)进行分析，根据其数据流向画出图2所示的1/2像素点DFG。其中:“+”表示对输入数值进行加法运算；“-1”表示对输入数值取相反数；“<>n”表示对输入数值进行右移位操作，即对输入数值除以2的n次幂。

(2) 以1/4像素点公式进行变换，将A-3,0、A-2,0、A-1,0、A0,0、A1,0、A2,0、A3,0分别记作t、u、v、w、x、y、z, 得到以下分像素点：

a0,0=(-t+4u-10v+58w+17x-5y+z)>>6=

[10(w-v)-5y+4u+(48w+16x)+x+z-t]>>6=

[8(w-v)-4y+4u+2(w-v)-y+16(3w+x)+x+z-t]>>6=

{[2(w-v)-y+u]>>2+(w-v)>>1-y+[(w>>1+w)+

x]>>4+x+z-t}>>6

(2)

由于3/4像素插值计算与1/4像素插值计算是对称的，故可用相同DFG通过反转输入参考像素的顺序来实现，因此不再展开描述。

2 基于深度优先贪婪算法的分像素插值任务划分

本文使用一种基于DFGSP划分方法，基于待划分的插值计算DFG(其中每个节点表示为一个操作符)，分别从各就绪节点出发，沿DFG中的数据流向向下进行搜索。具体实现为：先从待调度的就绪队列中取出队首任务，在给定的硬件面积的约束下，按深度优先搜索方式扫描DFG，逐个划入同时满足下述两个条件的节点。

(1) 本节点的输入数据已经由其他节点处理完并送至该节点输入端口。

(2) 新节点加入后，划分块的输出边数不在原划分块输出边数的基础上增加。

若有其中之一条件不符合时，跳过该计算流程，并将之前跳过流程后的后驱节点划为就绪节点，继续搜索其他就绪节点，直至没有新的节点加入则搜索结束。

图2中a、b、c、d、e、f、g、h八个像素点作为原始输入直接从数据输入存储(Data Input Memory，DIM)中读取。将所有节点分别划分为v1-v16，初始就绪节点为第一层中的v1、v2、v3、v4节点，具体划分步骤如下：

(1) 第一层的v1节点按深度优先流向第二层的v5节点。数据流到第三层的v9节点时，需等待第二层v5、v6的计算结果。

(2) 由于v9节点加入后的块间边数小于当前块的边数，满足DFGSP算法条件，故将v9节点加入v2→v6流程中。因此v1→v5为任务p1，v2→v6→v9为任务p2。

按照算法规则将其他节点加入任务，则图2的DFG划分为如图3中的任务p1、p2、p3、p4、p5。按照相同的划分原则，可将图4所示的1/4像素点的DFG进行划分,如图5所示。

3 基于阵列处理器的分像素插值算法的并行映射

本文所用的视频阵列处理器(DPR-CODEC)[10]是由项目组自主研发的一种可重构视频阵列处理器，支持H.264/AVC、MVC、H.265/HEVC等多种视频编解码标准，逻辑上把阵列结构划分成处理元簇(Process Element Group，PEG)，每个簇由4×4处理元(Process Element，PE)以阵列形式组成。由于视频算法中的数据处理大部分以N×N矩形块进行，因此这种专用体系结构相比其他结构更能满足视频算法的需求，能更有效地对视频算法进行并行化设计。在可重构计算的任务编译过程中，由核心计算转换来的DFG如何被映射到可重构处理单元是实现可重构系统高性能的关键所在[11]。

前期研究的亚像素精度运动估计采用两步搜索完成分数像素运动估计，结合不同分数像素点的位置分布以及所需插值滤波器类型，使用8个PEG进行分像素运动估计算法的映射，将周围搜索候选点分别记为1/2像素候选点0-8(整像素点为4)。将8×8像素块分解为4个4×4像素块进行率失真计算并累加得到8×8像素块的率失真值。

本文经过对亚像素精度运动估计算法的分析，在划分时充分考虑1/2和1/4像素点中可复用的数据，以8×8大小的块为例，仅需分别算出225个1/2像素点和225个1/4像素点，数据复用可以达到44%。如图6所示，只需用2个PEG即可将1/2、1/4和3/4像素的DFG图采用任务并行的方式映射在DPR-CODEC上。PEG00中，任务p1在PE00、PE10、PE30上分别实现加法和“-1”操作；任务p2、p3、p4、p5与p1类似。PE23用于计算比较得到最优1/2像素点，通过邻接互联寄存器输出给PEG01中的PE00、PE10、PE30。PEG01中采用相似处理方式实现1/4、3/4像素点的插值计算。选择数据流水线方式并行执行完8×8的整数点，算出所有的1/2像素点。

4 实验结果分析

4.1 测试方法及结果

为了验证基于DFGSP的分像素插值算法方案的可行性，在DPR-CODEC上进行验证。将测试数据存入阵列处理器的数据存储中，将并行方案的指令初始化到指令存储器，用Modelsim仿真软件分别对阵列结构上实现两步搜索方案和DFGSP进行仿真验证。并在SMIC 90 nm工艺库下进行综合。

图7统计了高清测试序列highway_qcif.yuv(1 920×1 080)选择两种不同算法且不同大小编码块完成一帧图像的运行时间。结果显示本方案完成一帧所用的时间都远低于两步搜索方案的执行时间。32×32块大小所花费时间最长，采用DFGSP方案需要16.5×10-3s，帧率可达60帧/s，满足1 920×1 080@30帧/s视频序列的实时编码需求。

在多核系统中，衡量程序性能的一个重要指标就是加速比，加速比定义如下：

(3)

式中：T1是单处理器最优串行算法计算时间；Tn是使用n个处理器并行计算时间；Sn是加速比。相比两步搜索方案，针对8×8块大小，本方案执行加速比可达4.27；针对32×32块大小加速比可达7.7。需要处理的编码块越大，DFGSP执行速度越快，加速比越高。

4.2 性能分析

本文统计了高清测试序列highway_qcif.yuv(1 920×1 080)以8×8编码块为大小完成一帧所用的时钟周期数为162 000，平均每个时钟周期可以处理12.8个像素。表2为执行时间对比，文献[12]在15个时钟周期可处理8×15个像素值，平均每个时钟周期可处理8个像素，本文方案在1个时钟周期内可多处理4.8个像素值。对比文献[13]，本文方案1个时钟周期可多处理3.8个像素，减少了算法执行的时间。

表2 执行时间对比

表3为SMIC 90 nm工艺库下，各方案执行分像素插值算法的性能对比。本文算法将每个子任务流图划分到阵列处理器上进行映射，在每个子任务进行完后即可开始下一个编码块的计算，16个PE规模的阵列结构可同时处理16个子任务，故并行度为16。硬件实现时最大工作频率可达357 MHz，与文献[14]中的原始HEVC方法相比硬件资源使用减少了72%。与文献[14]相比，硬件资源使用减少了60.1%；与文献[15]所提出的插值滤波器VLSI架构相比，硬件资源使用减少了30.78%。因此，在保证运动矢量精度的同时，本文方案可以快速完成分像素插值算法且节约了大量硬件资源消耗。

表3 性能对比(90 nm工艺库下)

5 结 语

本文提出一种基于DFGSP的分像素插值任务划分映射方法，该方法结合了视频阵列处理器天然并行的特点，采用数据和任务并行的方法，将分像素插值的DFG中的子任务合理映射在视频阵列处理器加速实现。实验表明，本文方案可满足实时实现分像素插值算法的需求，执行时间远低于两步搜索方案。与专用插值滤波器相比，有效降低了资源消耗，提高了资源利用率和并行度。因此，将HEVC算法使用任务划分的方式在阵列处理器上实现是降低计算复杂度和提高资源利用率问题的一种有效方法。