基于PAAG的H.264整数DCT变换的并行化实现

田小平，刘 帆

（1.西安邮电大学 电子工程学院，陕西 西安710121； 2.西安邮电大学 通信与信息工程学院，陕西 西安710121）

H.264／AVC（Advanced Video Coding）［1］是国际电信联盟 （International Telecommunication U－nion，ITU）和国际标准化组织 （International Organization for Standardization，ISO）共同制定的新一代视频编码标准，离散余弦变换 （Discrete Cosine Transform，DCT）是 H.264标准中的重要模块之一。由于DCT变换具有快速算法以及良好的数据压缩性和去相关性［2－3］，因此 DCT算法在多种结构设计中被应用［4－7］。DCT变换的对象，是帧内预测或者运动估计后所得到的残差数据，基于4×4块为单位进行整数离散余弦变换和量化，最后经过熵编码后输出［8－9］。由于 H.264整数 DCT变换运算规则十分简单，并且使用的都是整数的加法、乘法和移位操作，所以特别适合用于硬件的实现。面向图形的多台阵列架构 （Polymorphic Array Architecture for Graphic，PAAG）是针对于视频处理而设计的新的专用体系结构，为了验证PAAG结构对于H.264整数DCT并行化的性能，本文着重研究一种基于PAAG的整数DCT算法的并行化实现。

1 H.264的整数DCT变换

在H.264视频编码标准中，是以4×4图像块为单位进行变换编码，优化思想是定义中间变量，减少运算［10］。整数 DCT变换公式为［10］

式中X为帧内或帧间预测后的4×4图像残差数据，Cf为核心变换矩阵，W 为对应DCT变换后的4×4图像残差块。

按照式（1）算法，4×4的矩阵相乘需64次乘法和48次加法，时间耗费的比较多，而在H.264标准官方源代码JM中，对式（1）进行了改进，得到了蝶形快速变换算法［11］，如图1所示。通过利用矩阵的整数性和对称性将全部乘法运算转化为加法运算，减少运算次数。

图1 蝶形快速变换算法

图1 中r＝1为Hadamard变换，r＝2则为整数DCT变换。由于矩阵Cf的特殊性，残差图像块数据X左乘Cf，采用传统方法计算，得到结果

式（2）计算需要16次乘法和12次加法，由于矩阵乘1和乘－1的运算可以去除，所以式（2）可优化为只需4次乘法和12次加法。再利用其相关性，设置中间变量将空间代价转换为时间代价，可减少计算次数。经反复推算，将式（2）分为两步，提取的中间变量值M为

用这些中间变量来组合，就可以得到对传统蝶形变换优化后的结果

由式（3）和式（4）可以看出，通过以中间变量将式（2）运算分为两步，可使得运算量减少至2个乘法和8个加法，最后叠代这个算法即可完成整数DCT变换。

2 全系统仿真平台PAAG

PAAG提供一套完整的集成开发环境（Integrated Develop Environment，IDE），用于对视频各种算法并行化的硬件实现进行仿真。PAAG IDE集成了硬件时钟精确仿真平台、指令集编译器、程序性能统计与分析、完整的编辑器以及完整的调试模块。其体系结构是以簇为单位，每个簇由4×4的处理元 （Processing Element，PE）阵列构成，由于视频算法中数据的处理基本都是对4×4或者16×16的宏块进行处理，所以这种专用体系结构相比其他结构可以更有效的对视频并行化算法进行硬件映射，其结构如图2所示。

图2 PAAG簇结构

PAAG最多可支持4096个PE（PE数量是可配置的），具有层次结构，并且有可配置的片上网络 （Network on Chip，NoC）架构、PE的架构、以及簇控制器的体系结构。CR0－CR3为行控制器，CW0－CW3为列控制器，数据和程序存储在簇存储Cluster memory中，由簇控制器协调整个执行。簇控制器是可编程，微型操作系统 （Tiny Operating System，TOS）通过它来管理所有PAAG的资源，包括内存管理、线程调度以及其他资源。每个PE都有4个方向的共享存储，即 RFn、RFe、RFs、RFw，通过它们可以向PE周围的4个方向共享数据，从而实现数据的通信。PE之间的通信结构如图3所示。

图3 PE互联结构

3 基于PAAG的DCT算法并行化

H.264采用新的整数变换算法，以4×4像素子块为单位，在变换过程中只包含整数运算，这也是H.264标准区别于其他标准的重要不同之处。在H.264标准源代码中，DCT算法是串行化的，其主要核心是两个变换［11－12］：水平变换和垂直变换，相当于左乘和右乘变换矩阵。每个变换都有两个嵌套循环，每个嵌套循环共要顺序执行32次操作，需耗费大量时间。本文主要思想是利用PAAG体系结构的空间优势，采用细粒度的任务分配方式，最大限度的将嵌套循环的每个操作配置到各个PE中，由于此体系结构数据传输类型为临接互联，所以在配置的过程中充分考虑到两个PE间数据的共享问题，使各PE间共享数据的传递距离最优，最终达到基于PAAG的DCT算法并行化的最优实现。

假设一个4×4块残差数据为

首先进行水平变换，为了之后的计算过程中数据能以最小的传输代价在PE间共享，将4×4的残差数据按照图4的配置方式加载到PE0至PE15中，根据式（3）配置各个PE的指令，计算出各中间变量M［0］、M［1］、M［2］、M［3］。

图4 残差数据加载方式

在各PE计算出中间变量M后，根据图5的数据共享方式，将各中间变量传送至共享存储RFn、RFe、RFs、RFw中，然后，通过共享存储，将中间变量传送至指定的PE中，再根据式（4）进行计算，就完成了整数DCT变换中的水平变化。此方案将H.264标准源码中嵌套循环的32次操作减少到只要两次操作即可完成。

图5 水平变换的中间变量共享方式

水平变换后得到的4×4矩阵中X00、X01、X02、X03分别在 PE0、PE4、PE8、PE12中；X20、X21、X22、X23分别在 PE1、PE5、PE9、PE13中；X10、X11、X12、X13分别在 PE2、PE6、PE10、PE14中；X30、X31、X32、X33 分别在 PE3、PE7、PE11、PE15中。为了进行垂直变换，此变换后的4×4数据必须经过PE间的通信共享数据，数据共享方式如图6所示。

图6 水平变换后的数据共享方式

水平变换得到的数据共享之后，再进行的垂直变换。垂直变换与水平变换基本一致，通过得到中间变量、共享、再计算之后就得到了整数DCT变换后的数据。图7为垂直变换的中间变量共享方式。

图7 垂直变换的中间变量共享方式

至此，分别通过水平变换和垂直变换后，就完成了整数DCT变换的并行化映射。

4 仿真验证与分析

以4×4残差块为例，通过汇编语言实现H.264标准的整数DCT算法并行化程序，并使用PAAG仿真工具对算法程序进行仿真。图8为PAAG IDE仿真界面。

图8 PAAG IDE仿真界面

整个程序共包含16个部分，分别储存在16个PE（相当于16个核）中，通过对这16个PE加载4×4残差数据执行PE中预存的指令（每个PE初始加载2个残差数据）。在仿真过程中，通过对程序的优化改进，这里取的是所有16个PE中程序最为耗时的执行时间。图9为并行整数DCT的性能统计，经过单步调试，最终整个程序的执行时间仅为66个时钟周期，实现了整数DCT的并行化计算。通过仿真对比，在单个PE中（单核）实现串行整数DCT变换，程序的执行时间为295个时钟周期，并行运算相比于串行运算提高了77%，加速比为4.47。图10为串行整数DCT的性能统计。仿真结果表明，此并行算法可以充分利用PAAG结构的特点，有效提高整数DCT的计算速度。

图9 并行整数DCT的性能统计

图10 串行整数DCT的性能统计

5 总结

针对多核阵列结构PAAG，提出一种整数DCT变换的并行化算法。通过PAAG仿真工具对算法程序进行仿真，结果表明该并行算法的计算速度相比于串行计算提高了77%，验证了PAAG结构适合于整数DCT的并行化。

［1］Wiegand T，Sullivan G J，Bjontegaard G，el at.Overview of the H.264／AVC Video Coding Standard［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7）：560－576.

［2］许静，田小平，谭铁牛.一种基于DCT域的数字图像置乱程度衡量方法［J］.西安邮电学院学报，2009，14（1）：80－83.

［3］田小平，吴成茂，谭铁牛.利用DCT变换进行图像置乱及其效果评价［J］.计算机工程与应用，2008，44（35）：174－178

［4］Joshi A M ，Patrikar R M，Mishra V.Design of low complexity video watermarking algorithm based on Integer DCT［C］／／Signal Processing and Communications（SPCOM），2012International Conference on，2012：1－5.

［5］郑玉，刘文杰，高文.AVS整数DCT变换和量化方法的设计和实现［J］.淮海工学院学报：自然科学版，2006，15（3）：22－25.

［6］邓磊，高文，胡铭曾，等.基于 AVC／AVS标准高效运动估计硬件结构设计［J］.计算机研究与发展，2006，43（11）：1972－1979.

［7］Shin I，Yu J，Ryu W.Visually improved DCT based down－sampling method for H.264SVC［C］／／Consumer Electronics（ICCE），2010Digest of Technical Papers International Conference on，NV：Consumer Electronics，2010：369－370.

［8］侯金亭，马思伟，高文.AVS标准综述［J］.计算机工程，2009，35（8）：247－249.

［9］Zhao Liang，Zhang Li，Ma Siwei，et al.Fast mode decision algorithm for intra prediction in HEVC［C］／／Visual Communications and Image Processing（VCIP），2011IEEE，harbin：ieee press，2011：1－4.

［10］Wiegand T，Sullivan G，Luthra A.JVT－G050r1，Draft ITU－T recommendation and final draft international standard of joint video specification （ITU－T Rec.H.264／ISO／IEC 14496－10AVC）［S／OL］.（2011－12－14） ［2014－02－25］.http：／／www.doc88.com／p－90727922095.html.

［11］毕厚杰.新一代视频压缩编码标准：H.264／AVC［M］.3版.北京：人民邮电出版社，2005：103－106.

［12］Puri Atul，Chen Xuemin，Luthra Ajay.Video coding using the H.264／MPEG－4AVC compression standard［C］／／Signal Processing：Image Communication，2004（19）：793－849.