多层次细粒度并行HEVC帧内模式选择算法

张　峻　代　锋　马宜科　张勇东

1(中国科学院智能信息处理重点实验室 (中国科学院计算技术研究所)　北京　100190)2(中国科学院大学　北京　100049) (zhangjun01@ict.ac.cn)

多层次细粒度并行HEVC帧内模式选择算法

张峻1,2代锋1马宜科1张勇东1

1(中国科学院智能信息处理重点实验室 (中国科学院计算技术研究所)北京100190)2(中国科学院大学北京100049) (zhangjun01@ict.ac.cn)

摘要在众核平台上并行加速是解决高效视频编码(high efficiency video coding, HEVC)标准编码复杂度高的有效方法.传统的粗粒度并行方案如Tiles和WPP未能在并行度和编码质量之间取得较好的平衡，对编码质量影响较大或者并行度不高.充分挖掘HEVC帧内模式选择中的并行性，提出了一种在CTU内使用的多层次细粒度的帧内模式选择算法.具体说来，对帧内模式选择过程进行了子任务划分，分析并消除了相邻编码块之间多种阻碍并行计算的数据依赖关系，包括帧内预测参考像素依赖、预测模式依赖和熵编码依赖等，实现了同一个CTU内所有层次的细粒度编码块的代价计算和模式选择并行进行.将算法在Tile-Gx36平台上实现，实验结果表明此并行算法与HEVC参考代码HM相比能获得18倍的整体编码加速比而且编码质量损失较小(码率上升3%).

关键词高效视频编码；帧内预测；众核；并行模式选择；细粒度

高效视频编码(highefficiencyvideocoding,HEVC)[1-2]标准的压缩效率超越以往所有标准，比目前最流行的H.264AVC提高1倍.虽然HEVC仍然属于基于块的混合编码框架，但是其各个编码阶段都有了增强和改进，其中最重要的变化就是采用了更加灵活的编码结构和高级的编码工具，这也导致HEVC的编码模式搜索空间非常大.为了保证编码质量，编码器要进行大量的计算以寻找率失真代价较小的编码模式，即模式选择(modedecision,MD)，编码复杂度非常高.随着多核和众核处理器的发展[3]，在并行计算平台上并行化HEVC编码将是满足其计算能力需求实现实时编码的有效手段[4-12].与以往所有标准不同，HEVC标准本身就采纳了多种便于并行编解码的工具，如WPP(wavefrontparallelprocessing)[9]，Tiles[10]，MER(motionestimationregion)[11]，可见并行计算对于HEVC及今后视频编码领域的重要性.

目前HEVC并行相关的研究工作主要集中于计算量较大的帧间MD尤其是运动估计(motionestimation,ME)模块[7-8,11]，对帧内MD并行的研究则相对较少.随着帧间MD的并行化，帧内MD逐渐成为了速度瓶颈.在文献[13]中，在帧间MD被加速了近15倍之后，I帧的平均编码时间大大超过了PB帧的平均编码时间，是其4～5倍，限制了编码器的整体效率，因此对帧内MD的并行加速同样重要.

现有的对HEVC帧内MD并行的研究较少，而且算法的并行度不够高[14-16]，HEVC标准支持的Tiles和WPP也未能在并行度和编码质量取得较好的平衡.针对这些问题，本文提出了一种在编码树单元(codingtreeunit,CTU)内使用的并行帧内MD算法：本文对帧内MD过程进行了子任务划分，深入分析并解除了各个子任务在相邻编码块之间存在的数据依赖性，包括帧内预测参考像素依赖、PU预测模式依赖、熵编码概率模型依赖和概率建模依赖，实现了每个子任务对整个CTU里面多层次细粒度的编码块并行处理，最终实现了CTU内并行帧内MD.

1背景及研究现状

本节介绍与本文工作相关的一些背景.首先介绍HEVC帧内模式选择基本概念，然后对已有的一些并行帧内模式选择算法进行了介绍和分析.

1.1HEVC帧内模式选择

在HEVC编码标准中，一帧视频图像被均匀地划分成CTU，CTU的大小可以为64×64,32×32或16×16，典型且不失一般性，本文以下默认CTU大小为64×64.如图1所示，每一个CTU四叉树递归地划分为4个相同大小的子单元，该四叉树的每一个叶子节点叫作一个编码单元(codingunit,CU)；每个CU也会采用四叉树递归划分，每一个叶子节点叫作变换单元(transformunit,TU).此外，从图1可见，每个CU有多种预测单元(predictionunit,PU)划分模式，能更灵活地进行预测编码.HEVC的帧内预测模式也比H.264复杂很多，共35种模式.CTU,CU,PU,TU包含的单一亮度或色度分量信息分别记为CTB(codingtreeblock),CB(codingblock),PB(predictionblock),TB(transformblock).

Fig. 1　Flexible coding structures in HEVC.图1　HEVC标准中灵活的编码结构

在HEVC帧内MD过程中，对于一个CTU来说，它可以采用四叉树递归划分的方式划分出更小的CU，最小为8×8.对于8×8CU有2N×2N和N×N两种PU划分方式，其他CU只有2N×2N的PU划分.N×N划分情况下包含4个亮度PB和1个色度PB，2N×2N划分时包含1个亮度PB和1个色度PB，每个PB有一个预测模式.对一个帧内编码CU来说，色度PB和亮度PB的预测模式可以是不同的，TU划分模式对亮度和色度是相同的，因此一个帧内编码CU的模式可由亮度PB预测模式、色度PB预测模式和TU划分模式来表征，如式(1)所示.帧内MD即对CTU里面的每个CU从式(1)所表示的模式空间中寻找率失真代价最小的模式组合，并且据此决策出整个CTU的最佳CU四叉树划分方式.在HEVC的参考软件HM中,一个CTU里面CU的MD计算是按深度优先遍历顺序进行的，如图2所示，为简便起见只画了3层，每个节点表示一个CU.

CU模式(亮度PB预测模式,色度PB预测模式,

(1)

Fig. 2　Depth-first serial processing order of CUs in a CTU of HM.图2　HM中一个CTU里CU的深度优先串行处理顺序

1.2相关研究工作

由于采用了灵活的编码结构和复杂的预测模式，帧内MD计算量非常大.为了加快帧内MD，许多研究工作[17-19]提出了快速算法.快速算法能在一定程度上减小计算复杂度，但是获得的加速比有限，距离实时编码仍然有很大的差距.

并行计算是提高HEVC编码速度的有效手段，标准本身采纳了几种粗粒度的并行化工具.Tiles将一帧图像纵横划分成若干可以独立进行编码的子图像，子图像之间无依赖关系，所以可以并行处理.Tiles划分对并行编码比较容易实现且并行度比较灵活，缺点是对编码效率影响较大，经测试[20]，将1080p的视频均匀划分成6×3的Tiles用于帧内MD,在intra_main配置下实际平均加速比为12，BDBR[21]达到5%左右.HEVC采用的另一种并行方案为WPP，由于其尽可能地保持了数据依赖关系，所以对编码质量影响较小，但是并行度却不高.对一个宽度为W个CTU、高度为H个CTU的视频帧来说，如果满足条件2(H-α-1)

(2)

对于720p和1080p的视频序列满足α=2，所以1080p的视频TPD只能到8[22].

在另外一些并行帧内MD的研究中，文献[14-15]都使用前向无环图描述CTU之间的依赖关系，实现了CTU之间的并行处理，但本质仍属于WPP，文献[14]平均获得了5倍的加速比，文献[15]则使用分类器决策出最佳CTU的大小，通过较小的CTU大小能获得较高的加速比，平均达到10倍.在文献[16]中，该文作者提出了一种在TU四叉树划分时4个子节点并行帧内预测的算法，但是由于帧内预测仍依赖于重构像素，理论并行度只能达到4.

从以上内容可以看出，现有的帧内MD并行算法主要是粗粒度并行(Tiles,WPP)，文献[16]属于细粒度并行但是并行度不高.针对它们存在的问题，本文提出了一种在CTU内使用的多层次细粒度的并行帧内MD算法，在保证编码质量的前提下获得了更高的并行度.多层次体现在不同深度的CU，PU，TU可以并行处理，细粒度则体现在最小计算单元为一个TB.

2多层次细粒度并行帧内模式选择

本节提出了一种在CTU内使用的多层次细粒度并行帧内MD算法.本文首先对CU帧内MD过程进行了子任务划分，深入分析并解除了各个子任务在相邻CU，PU，TU间存在的数据依赖关系，实现了各个子任务在整个CTU范围的并行处理，最终实现了各个层次的所有CU并行模式选择.

2.1子任务划分

对于一个CU的模式选择，为了减小计算量，HM对式(1)表示的模式空间的搜索分阶段进行，先选择亮度PB预测模式，然后选择TU划分模式，再选择色度PB的预测模式，如图3所示.

Fig. 3　The flowchart of intra MD for a CU in HM encoder.图3　HM编码器中对一个CU的帧内MD流程图

对于亮度PB预测模式选择，先对所有35种模式进行代价粗算(roughmodecostcomputation,RMCC)，代价记作RMC，包括PB预测值与原始值之间的残差变换绝对值(sumofabsolutetransformeddifferences,SATD)和预测模式编码位数，从中选择一定数量RMC最小的预测模式，与当前PB的最可能预测模式(mostprobablemode,MPM)一起构造候选模式列表(candidatemodelistconstruction,CMLC),记作CML,对CML里的每一个模式都去计算率失真代价(predictionmodecostcomputation,PMCC)，代价记作PMC,选择PMC最小的预测模式作为当前PB的最佳预测模式(PBbestpredictionmodeselection,PBBPMS),记作PBBPM.然后对TU划分模式进行决策，主要计算量是亮度TB的率失真代价计算(TBcostcomputation,TBCC)，代价记作TBC，使用TBC进行TU四叉树决策(quad-treedecision,QTD).最后选择色度预测模式，主要计算是色度TB的TBCC计算.为便于后续引用，在表1对上述子任务以及相应的计算结果进行了归纳.

Table 1　Sub-Tasks and Their Output Results

如图2所示，在串行帧内MD时，由于CU的MD计算是按照深度优先遍历顺序去串行进行的，所以对于表1中的每个子任务，在串行MD时它们在CTU范围内的执行路径也是按四叉树深度优先遍历顺序去进行的.本文提出的并行算法将每个子任务在CTU范围内进行多层次细粒度的并行，每个子任务都能并行处理一个CTU里面的所有CU，PU或TU，即并行处理四叉树中的所有节点,一个节点对于不同的子任务表示一个CU，PU或TU.

2.2数据依赖性分析与消除

对于每个子任务，要在一个CTU范围内进行并行MD计算，而相邻块之间有多种数据依赖关系，这些数据依赖会阻碍子任务在CTU范围内的并行计算.经过本文的分析，有4种数据依赖需要解除：

1) 帧内预测时重构像素依赖.此依赖关系出现在帧内预测时，如图4所示，在一个PB或TB进行代价计算时，需要进行帧内预测，即参考相邻块已经重构出来的像素对自身进行预测.对于一个M×M的TB来说，需要参考周围的4M+1个重构像素，分别来自于其左、上、左下、右上和左上方向已经编码重构完成的相邻图像区域.

Fig. 4　Reconstructed pixels dependencies during intra prediction.图4　帧内预测时重构像素依赖

在本文的并行算法中，RMCC,PMCC，TBCC在一个CTU里面要对所有PB或TB并行进行代价计算，需要进行帧内预测，如果一个PB或TB要参考的重构像素跟它位于同一个CTU，那么重构像素是不可用的，因为相邻块也同时在进行模式选择，并未重构完成.如图4所示，blockL,blockA和当前块位于同一个CTU进行并行处理，那么当前块所依赖的blockL和blockA的重构像素不可用.要想并行计算，帧内预测参考像素的依赖关系必须要解除.

为了解除这种相关性，本文提出使用原始像素代替重构像素进行帧内预测.为了更准确地模拟实际的编码过程，在对一个PB或TB进行参考像素构造的过程中，虽然所有原始像素都是可用的，但依然按照标准遵循Z扫描顺序来决定某一个像素是不是可用，对于不可用的像素则调用替换(substitution)过程去生成.另外，对参考像素的滤波操作也同样按照标准进行.由于原始像素是始终可用的，相邻PB或TB之间不会再有重构像素的依赖问题，所以同一个CTU里面所有PB和TB都可以并行地进行帧内预测.

2) 编码预测模式时MPM计算依赖.为了提高压缩效率，HEVC在编码帧内预测模式时需要参考相邻(左边和上边)PB的预测模式，构造出一个长度固定为3的MPM列表，如图5(a)所示.如果左PB(leftPB,LPB)和上PB(abovePB,APB)的预测模式不可用或者相同，则还会加入DC、planar、垂直、水平等模式.令(xc,yc)表示当前PB的左上角在当前图像帧中的坐标，LPB定义为覆盖点L(xc-1,yc)的PB，APB定义为覆盖点A(xc,yc-1)的PB.

Fig. 5　Prediction mode dependency among adjacent PUs and the proposed dependency removing method.图5　相邻PU预测模式依赖和本文提出的依赖性消除方法

在本文的并行算法中，RMCC,CMLC，PMCC要对CTU内所有PB并行地进行MPM计算，如果当前PB与参考的LPB或APB位于同一个CTU里面，即如式(3)所示，其中(xn,yn)对于LPB或APB分别为(xc-1,yc)或(xc,yc-1)，那么LPB和APB的预测模式是不可用的，因为它们也同时在进行模式选择，预测模式还未得到.

为了解除此依赖关系，如果当前PB和LPB或APB位于同一个CTU，那么本文使用已经编码过的CTU里面距离LPB和APB最近的对应PB来代替它，记作LPB′和APB′,如图5(b)所示，用LPB′和APB′的预测模式代替LPB和APB的预测模式去构造MPM.LPB′定义为覆盖点L′(xc-xc% 64-1,yc)的PB,APB′定义为覆盖点A′(xc,yc-yc% 64-1)的PB，其中“%”表示取余运算，64表示CTU大小.由于CTU是按照扫描顺序进行编码的，所以左CTU和上CTU里面的信息一定是可以使用的，这样，同一个CTU里面PU的预测模式依赖关系就被解除了，可以并行进行预测以及代价计算:

(3)

3) 概率模型(contextmodel,CM)继承依赖.HEVC中使用上下文自适应的二进制算术编码(contextadaptivebinaryarithmeticcoding,CABAC)进行语法元素的熵编码.CABAC的主要过程包括语法元素的二进制化、概率建模、算术编码和CM更新.为了提高编码效率，在编码的过程中CM会自适应动态更新，以更好地反映图像的局部区域特性，获得更高的压缩比.在HM模式选择过程中，熵编码器会使用CM去估计编码产生的位数以计算编码代价，CM是模拟实际编码过程动态更新的，Z扫描顺序更小的块的MD完成之后会将CM传递给Z扫描顺序大于它的块使用，如图6(a)所示，TU1使用的CM是TU0计算之后的结果，这样就在相邻块之间产生了CM的继承依赖.

Fig. 6　CMs inheritance in HM and our proposed method.图6　HM中的CM继承依赖和本文提出的方法

在本文的并行算法中，RMCC,PMCC,TBCC，QTD任务要并行地对一个CTU内的所有CU,PU或TU进行代价计算，而由于相邻CU，PU，TU之间存在CM的继承依赖问题而导致无法并行，要想实现并行代价计算，必须要解决此依赖关系.

为了解除同一个CTU内CM继承依赖，本文提出以下解决方法：同一个CTU内的所有CUPUTU使用同一套CM，该CM来自于上一个已编码的CTU经过训练之后的结果.如图6(b)所示，为了简洁，一个CTU内只画出4个TU.通过这种CM继承方式，一个CTU里面所有的CUPUTU都有了自己的CM，所以可以并行处理.

Fig. 7　Coding depth dependency among adjacent CUs and our proposed dependency removing method.图7　CU之间依赖和提出的依赖性消除方法

4) 概率建模依赖.为了提高编码效率，CABAC编码二进制符号(binarysymbol,bin)时需要进行概率模型选择(也叫概率建模)，概率模型即当前bin是01的概率，概率建模即从可选的概率模型里选择出最能反映当前bin概率估计的模型.为了能得到较精确的概率估计，概率建模会依赖于当前bin序号、编码深度、色度或亮度、周围编码信息等.HEVC在编码语法元素split_cu_flag时，会根据当前CU的深度和其左CU、上CU的划分深度进行概率模型选择，如图7(a)所示.假设左CU编码深度为depthL,上CU编码深度为depthA,当前CU的深度为depth,那么当前CU的split_cu_flag的概率模型序号如式(4)所示，其中“>”为逻辑运算符.cu_skip_flag的概率建模与此类似.在本文的并行算法中，QTD要对CTU内所有CU并行地进行代价计算和模式选择，由于相邻CU之间在概率建模时有编码模式依赖，所以要并行处理，这种依赖关系必须要解除.为了解除此类数据依赖性，本文采用和解除MPM计算依赖性类似的方法，即如果参考的CU和当前CU位于同一个CTU，则使用已编码的相邻CTU中的对应CU来代替它，如图7(b)所示.另外，TB的语法元素cbf在概率建模时会依赖当前TB在CU中的划分深度信息，但是在本文的算法中，整个CTU里面的所有TB会并行计算代价TBCC，并无CU概念，所以TB在CU中的深度无法得到.对于这个依赖关系，本文的解决方法是：对于4×4的TB，深度设置为1，其他TB的深度设置为0.

(4)

以上对阻碍并行计算的多种数据依赖关系进行了分析和消除.需要注意的是本文提出的数据依赖性消除算法只在模式选择阶段使用，为了保证编码结果符合标准且保证编码质量，当一个CTU的模式选择完成之后，即确定了CU划分方式、PU划分方式、PU预测模式和TU划分方式之后，在进行实际熵编码的过程中需要对量化系数和预测模式编码进行修正，即按照标准规定去参考相邻块的重构像素进行帧内预测，对残差重新进行变换和量化得到量化系数，MPM的构造也按标准规定参考相邻的PB，CABAC的概率模型继承和概率建模也按标准规定进行.这个修正的过程是需要串行计算的.

2.3并行策略

在解除了以上多种数据依赖关系之后，下面给出本文提出的多层次细粒度并行算法的并行策略，为了便于表达，进行如下符号定义：

CU,PU,TU分别表示在一个CTU里面的编码单元、预测单元、变换单元；CB,PB,TB分别表示一个CU,PU,TU包含的亮度或色度分量块;depthi表示当前单元(CU,PU,TU)或分量块(CB,PB,TB)相对于CTU的四叉树划分深度，其中0≤i≤4;zorderj表示第depthi层深度的某一个单元的Z扫描顺序序号，其中0≤j≤4i-1;modek表示一个帧内预测模式，其中0≤k≤34.

对表1中的各子任务，分别在CTU内进行如下数据级划分和并行：

1)RMCC.对于亮度PB的RMCC任务，主要工作是计算PB的帧内预测和SATD的计算.本文提出的并行策略：一个CTU里面所有的亮度PB的所有预测模式都并行进行RMCC，表示为RMCi,j,k=RMCC(PB(depthi,zorderj),modek)，其中0≤i≤4,0≤j≤4i-1,0≤k≤34,i,j,k并行.

2)CMLC.在一个亮度PB的RMCC完成之后，需要从中选出一定数量RMC最小的模式，然后与当前PB的MPM一起组成该PB的候选模式列表CML.本文提出的并行策略：CTU内所有亮度PB并行进行CMLC操作，表示为CMLi,j=CMLC(PB(depthi,zorderj)),其中0≤i≤4,0≤j≤4i-1,i,j并行.

3)PMCC.当一个亮度PB的CML构造之后，要从中选出一个最好的模式作为当前PB的预测模式.当前PB在其CML里面的每一个模式都计算出一个率失真代价PMC，为了减少计算量，只有64×64的PB进行一层TB划分，其他的PB都直接作为一个TB计算.本文提出的并行策略：CTU里面所有的PB在其CML里面的所有模式并行,表示为PMCi,j,k=PMCC(PB(depthi,zorderj),modek),0≤i≤4,0≤j≤4i-1,k∈CMLi,j,i,j,k并行，其中对于PB(depth0,zorder0)，划分为4个子块并行计算.

4)PBBPMS.当一个亮度PB的PMC计算完成之后，需要从中选择最小PMC对应的预测模式作为PB的最终预测模式，记为PBBPM.本文提出的并行策略：CTU内所有亮度PB并行进行PBBPMS操作，记为PBBPMi,j=PBBPMS(PB(depthi,zorderj)),0≤i≤4,0≤j≤4i-1,i,j并行.

5)TBCC.选出亮度PB最佳预测模式之后，需要决策每个CU的最佳TU划分，因此要计算一个CU所包含的所有TB的率失真代价.本文提出的并行策略：整个CTU里面所有TB并行地进行率失真代价TBC计算，表示为TBCi,j,k=TBCC(TB(depthi,zorderj),modek)，由于亮度TB最大为32，所以1≤i≤4,0≤j≤4i-1,k∈TBPMi,j,i,j,k并行，其中TBPMi,j表示TB(depthi,zorderj)所需计算的预测模式.由于本文使用原始像素取代重构像素来进行帧内预测，所以任何一个TB对于同一个预测模式其预测值是完全相同的.因为同一个TB可能会被多个PB同时覆盖，所以同一个TB在一个模式下只需要计算一次即可，减少了计算量.假如最大TU划分层次为3层，那么TB(depthi,zorderj)会被PB(depthi,zorderj),PB(depthi-1,zorder)和PB(depthi-2,zorder)同时覆盖，故TBPMi,j是它们最佳模式的并集，即：

TBPMi,j={PBBPMi,j,PBBPM,PBBPM}.

(5)

对于色度PB的预测模式选择，色度PB在亮度PB预测模式一定的情况下有5种预测模式需要计算，如表2所示.本文直接将这5种模式全部并行计

Table2TheRelationshipofPredictionModeBetweenLuma

andChromaComponentsinaCU

表2　色度分量预测模式与亮度分量预测模式的对应关系

算：TBCi,j,l=TBCC(TB(depthi,zorderj),model),其中1≤i≤3,0≤j≤4i-1,l=0,1,2,3,4,model表示需要计算的预测模式,i,j,l并行.

6)QTD.此任务的主要工作是根据前面所述任务的计算结果，决策出CU的最终模式.因为在PBBPMS中已经得到了亮度PB的预测模式，在TBCC中已经得到了亮度和色度的TBC，所以QTD的主要工作就是决策出当前CU最优的TU划分和最优色度预测模式，并且计算出当前CU的率失真代价，完成模式选择过程.本文提出的并行策略：一个CTU里面的所有CU并行进行QTD:QTD(CU(depthi,zorderj)),其中 0≤i≤3,0≤j≤4i-1,i,j并行.

2.4理论并行度分析

为了对所提并行帧内MD算法的理论并行度进行近似分析，进行2点假设：1)对于RMCC，PMCC，TBCC子任务，主要计算量是帧内预测和变换量化，它们的计算时间与计算单元的面积成正比，且与预测模式无关；CMLC,PBBPMS，QTD的主要操作是结果的比较和选择，计算量较小且与计算单元面积无关.2)对于同一类子任务由于解除了相邻数据单元之间的数据相关性，所有的数据单元都可以同时被计算，因此理论并行度由整个CTU串行计算时间和计算量最大的数据单元的计算时间决定.基于以上2点假设，各子任务分析如下：

1)RMCC阶段.令CTi,j,k表示RMCC(PB(depthi,zorderj),modek)的计算时间，令T=CT0,0,0，那么整个CTU里所有PB的RMCC串行计算时间近似为

2)PMCC阶段.令CTi,j,k表示PMCC(PB(depthi,zorderj),modek)的计算时间，令T=CT1,0,0,经统计亮度PB的CML里面平均含有5个模式，所以整个CTU里所有PB的PMCC的串行计算时间近似为

最大计算量任务的计算时间为T，所以TPD=100.

3)TBCC阶段.令CTi,j,k表示TBCC(TB(depthi,zorderj),modek)的计算时间，令T=CT1,0,0,假设TU最多划分3层，在串行MD过程中整个CTU里所有TB的TBCC串行计算时间为

最大计算量任务的计算时间为T，所以TPD=44.

从以上分析可以看出，本文提出的并行帧内MD算法的理论并行度很高，适用于众核平台.

3实现和实验结果

基于HEVC参考代码HM13.0[23]，本文使用多线程实现本文所提出的并行模式选择算法.本文修改了代码中模式选择模块(TEncCu∷xCompressCU及相关函数)使之并行化，其他的模块保持不变.本文重点是提出一种适用于众核平台的高并行度算法，主要关注算法的并行度和对编码质量的影响，所以并未对单核性能进行指令、内存等任何优化.实验采用的计算平台为TILE-Gx36众核平台，共有36个处理核心，单核主频1.2GHz.

3.1实现方法

为了减少频繁创建和销毁线程带来的开销，本文使用线程池实现本文算法.在编码器刚启动时创建一定数量所需线程，线程池中所有的线程在编码器整个生命周期内一直存在.为了减小线程切换带来的性能影响和增加实验的可重现性，所有的线程都绑定在一个固定的核上且每个核只绑定一个线程.0号核不予使用，1号核绑定主线程，其余34个核用于线程池里的工作线程.线程池中维护一个任务链表，所有需要处理的任务都插入链表，空闲的工作线程自动从链表首取走任务进行处理.主线程的主要工作就是往链表里面放任务，实际去完成任务计算的是工作线程.

在本文的实现中，定义了6种类型的任务：RMCC,CMLC,PMCC,PBBPMS,TBCC,QTD，由于这些任务之间对于同一个数据单元存在先后处理顺序的依赖关系，所以本文定义了任务的优先级，如表3所示.优先级越大的任务表示越应该优先被计算，因为其他类型的任务可能会使用它的计算结果，在放入任务链表时会根据优先级大小顺序存放，优先级越大的任务在任务链表中排序越靠前.另外，为了保证块越大的任务先被计算，在每一种任务类型里面，块越大的任务即深度越小的任务优先级越大.对于不同数据单元，计算任务之间则没有依赖关系，不同种类的子任务之间可以并行.

Table 3　Sub-Tasks with Their Parallel Hierarchy and Priority

3.2实验结果

为了验证本文提出的并行帧内MD算法的有效性，包括编码加速比和对编码质量的影响，本文用基准编码器HM和本文并行化的编码器分别对6个1080p和2个1600p的高分辨率视频使用HM提供的配置文件intra_main进行了编码，每个序列使用了前100帧，根据文献[20]对每个序列分别使用4个不同的量化参数(quantizationparameter,QP):22,27,32，37.加速比按照式(6)计算，其中Enc_Timer和Enc_Timep分别表示基准编码器HM和并行编码器的编码时间，编码效率的下降使用BDBR[21]来衡量.为了验证并行算法的可伸缩性即加速比与核数的关系，对每个序列都使用了不同数量的工作线程进行编码.实验结果如表4所示，其中的核数是用于工作线程的核数，加速比是对4个QP取平均的结果.从表4可以看出,本文提出的并行帧内模式选择算法在使用34个核时对所有序列平均能获得18以上的加速比，平均BDBR为 3.04%.部分序列的率失真曲线如图8所示.

(6)

Fig. 8　Rate distortion curves for some test sequences.图8　部分序列的率失真曲线图

Fig. 9　Speedup vs number of cores for our proposed method and WPP (TPD).图9　算法加速比和WPP(TPD)与核数关系

图9给出使用不同数量的核数(2,4,8,16,24,32,34)得到的所有序列的平均加速比与核数之间的关系曲线图，并且与1080p和1600p的WPP的理论值进行了对比.从图9可以看出，本文所提出的算法在核数增多时有更高的加速比，适用于众核计算平台；当核数较少时加速效果比较明显，但是随后曲线逐渐趋于平坦，且加速比与核数之比远小于1，离算法的TPD有较大的差距.造成这种现象的原因可能有3点：

1) 并行计算数据单元划分不均衡.在本文的算法中，不同大小的PU和TU计算量相差较大，如果假设计算量与块面积成正比，那么第0层TU的TBCC计算量近似是第1层TU的TBCC的4倍.任务划分不均衡会导致处理器核的计算负载不均衡，造成CPU核的饥饿等待，影响并行度.

2) 由于所有的并行任务都放在一个公共链表里面，所有线程都会竞争此资源以取得任务.随着核数的增加，线程之间在取任务和放任务的竞争会越来越激烈，势必会造成很大的线程同步开销.

3) 算法只进行了模式选择计算的并行化，其他的部分仍然串行执行，虽然占的比例很小，但是会对整体的并行度造成上限制约.另外，编码阶段的修正过程也是串行执行，也会影响实际的加速比.

对于编码质量的下降，主要原因是代价计算的准确性不高，这是本文所采取的多种数据依赖性消除算法的综合作用结果.

由于本文提出的并行算法是在局部区域CTU内进行，所以可以和其他全局粗粒度并行方法如WPP和Tiles结合使用，能进一步提高并行度.

4总结

本文提出了一种在CTU内使用的多层次细粒度的并行HEVC帧内模式选择算法，一个CTU内所有不同层次的CU,PU，TU以及所有预测模式可以并行地进行代价计算和模式选择.本文分析了存在的多种数据依赖性并提出了有效的依赖性解除方法.实验结果表明本文提出的方法能达到18倍以上的编码加速比并且编码质量损失较小，比传统的粗粒度并行方案更能适用于众核平台.

参考文献

[1]BrossB,HanWJ,OhmJR,etal.JCTVC-L1003:Highefficiencyvideocoding(HEVC)textspecificationdraft10 (forfdis&lastcall)[C/OL]. 2013 [2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/12_Geneva/wg11/JCTVC-L1003-v34.zip

[2]SullivanGJ,OhmJR,HanWJ,etal.Overviewofthehighefficiencyvideocoding(HEVC)standard[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2012, 22(12): 649-1668

[3]PengXiaoming,GuoHaoran,PangJianmin.Multi-coreprocessor-technology,tendencyandchallenge[J].ComputerScience, 2012, 39(11A): 320-326 (inChinese)(彭晓明, 郭浩然, 庞建民. 多核处理器——技术、趋势和挑战[J]. 计算机科学, 2012, 39(11A)：320-326)

[4]YanChenggang.Researchonkeytechniquesforparallelvideocodingonmany-coreprocessor[D].Beijing:InstituteofComputingTechnology,ChineseAcademyofSciences, 2014 (inChinese)(颜成钢. 面向众核处理器的并行视频编码关键技术研究 [D]. 北京: 中国科学院计算技术研究所, 2014)

[5]ChoiK,JangES.Leveragingparallelcomputinginmodernvideocodingstandards[J].IEEEMultimedia, 2012, 19(3): 7-11

[6]ZhangYongdong,YanChenggang,DaiFeng,etal.EfficientparallelframeworkforH.264/AVCdeblockingfilteronmany-coreplatform[J].IEEETransonMultimedia, 2012, 14(1): 510-524

[7]YanChenggang,ZhangYongdong,DaiFeng,etal.HighlyparallelframeworkforHEVCmotionestimationonmany-coreplatform[C] //Procofthe23rdDateCompressionConf(DCC2013).Piscataway,NJ:IEEE, 2013: 63-72

[8]YanChenggang,ZhangYongdong,XuJizheng,etal.EfficientparallelframeworkforHEVCmotionestimationonmany-coreprocessors[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2014, 24(12): 2077-2089

[9]ClareG,HenryF,PateuxS.JCTVC-F274:WavefrontparallelprocessingforHEVCencodinganddecoding[C/OL]. 2011 [2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/6_Torino/wg11/JCTVC-F274-v2.zip

[10]FuldsethA,HorowitzM,XuS,etal.JCTVC-F335:Tiles[C/OL]. 2011[2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/6_Torino/wg11/JCTVC-F335-v2.zip

[11]ZhouMinhua.JCTVC-H0082:ConfigurableandCU-grouplevelparallelmerge/skip[C/OL]. 2012[2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/8_San%20Jose/wg11/JCTVC-H0082-v2.zip

[12]ChiCC,MauricioAM,JuurlinkB,etal.ParallelscalabilityandefficiencyofHEVCparallelizationapproaches[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2012, 22(12): 1827-1838

[13]ZhangJun,DaiFeng,MaYike,etal.HighlyparallelmodedecisionmehtodforHEVC[C] //Procofthe30thPictureCodingSymp(PCS2013).Piscataway,NJ:IEEE, 2013: 281-284

[14]ZhaoYanan,SongLi,WangXiangwen,etal.EfficientrealizationofparallelHEVCintraencoding[C]//Procof2013IEEEIntConfonMultimediaandExpoWorkshops(ICMEW2013).Piscataway,NJ:IEEE, 2013: 1-6

[15]YanChenggang,ZhangYongdong,DaiFeng,etal.EfficientparallelHEVCintra-predictiononmany-coreprocessor[J].ElectronicsLetters, 2014, 50(11): 805-806

[16]JiangJie,GuoBaolong,MoWei,etal.Block-basedparallelintrapredictionschemeforHEVC[J].JournalofMultimedia, 2012, 7(4): 289-294

[17]ChoiK,ParkSH,JangES.JCTVC-F092:CodingtreepruningbasedCUearlytermination[C/OL]. 2011[2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/6_Torino/wg11/JCTVC-F092-v3.zip

[18]ChoS,KimM.FastCUsplittingandpruningforsuboptimalcupartitioninginHEVCintracoding[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2013, 23(9): 1555-1564

[19]LealdaSilvaT,daSilvaCruzL,AgostiniLV.HEVCintramodedecisionaccelerationbasedontreedepthlevelsrelationship[C]//Procofthe30thPictureCodingSymp(PCS2013).Piscataway,NJ:IEEE, 2013: 277-280

[20]BossenF.JCTVC-L1100:Commontestconditionsandsoftwarereferenceconfigurations[C/OL]. 2013 [2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/12_Geneva/wg11/JCTVC-L1100-v1.zip

[21]BjontegaardaG.VCEG-M33:Calculationofaveragepsnrdifferencesbetweenrd-curves[C/OL]. 2001 [2014-11-01].https://github.com/gabrieldiego/tg/blob/master/ref/VCEG-M33.doc

[22]ZhangShaobo,ZhangXiaoyun,GaoZhiyong.ImplementationandimprovementofwavefrontparallelprocessingforHEVCencodingonmany-coreplatform[C] //Procof2014IEEEIntConfonMultimediaandExpoWorkshops(ICMEW2014).Piscataway,NJ:IEEE, 2014: 1-6

[23]JCTVC.HEVCtestmodel:HM13.0[CP]. [2014-11-01]https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/branches/HM-13.0-dev

ZhangJun,bornin1987.ReceivedhisBEdegreefromXidianUniversityin2009andreceivedhisPhDdegreefromtheInstituteofComputingTechnology,ChineseAcademyofSciencesin2015.Hisresearchinterestsincludevideocodingandimageprocessing.

DaiFeng,bornin1979.ReceivedhisMSandPhDdegreesfromtheInstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China,in2008.AssociateprofessorwiththeMultimediaComputingGroup,AdvancedResearchLaboratory,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing.MemberofChinaComputerFederation.Hisresearchinterestsincludevideocoding,videoprocessingandcomputationalphotography(fdai@ict.ac.cn).

MaYike,bornin1980.ReceivedhisMSandPhDdegreesintheInstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China,in2011.MemberofChinaComputerFederation.Hisresearchinterestsincludecomputerarchitecture,parallelalgorithmandcomputationalphotography(ykma@ict.ac.cn).

ZhangYongdong,bornin1973.ReceivedhisPhDdegreeinelectronicengineeringfromTianjinUniversity,Tianjin,China,in2002.ProfessorwiththeInstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China.SeniormemberofChinaComputerFederation.Hisresearchinterestsincludemultimediacontentanalysisandunderstanding,multimediacontentsecurity,videocoding,andstreamingmediatechnology(zhyd@ict.ac.cn).

Multi-LevelandFine-GrainedParallelHEVCIntraModeDecisionMethod

ZhangJun1,2,DaiFeng1,MaYike1,andZhangYongdong1

1(Key Laboratory of Intelligent Information Processing (Institute of Computing Technology, Chinese Academy of Sciences), Chinese Academy of Sciences, Beijing 100190)2(University of Chinese Academy of Sciences, Beijing 100049)

AbstractThe coding mode space of high efficiency video coding (HEVC) is extremely large so it needs huge amount of computations for HEVC encoders to do mode decision (MD). Parallelizing HEVC encoding on many-core platforms is an efficient and promising approach to fulfill the high computational demands. Traditional coarse-grained parallelizing schemes such as Tiles and wavefront parallel processing (WPP) either cause too much quality loss or can’t afford a high parallelism degree. In this paper, the potential parallelism in HEVC intra MD process is exploited, and a multi-level and fine-grained highly parallel intra MD method which works in a coding tree unit (CTU) is proposed. Specifically, the intra MD process in a CTU is divided into six types of sub-tasks, and the data dependencies among adjacent blocks that hinder parallel processing are analyzed and removed, including intra prediction dependency, prediction mode dependency and entropy coding dependency; consequently the MD computation for all fine-grained coding blocks of different levels within the same CTU can be computed concurrently. The proposed parallel MD method is implemented on Tile-Gx36 platform. Experimental results show that the proposed parallel MD method gets an overall speed up of more than 18x with acceptable quality loss (about 3% bit-rate increasing), compared with the non-parallel baseline HM.

Key wordshigh efficiency video coding (HEVC); intra prediction; many-core; parallel mode decision; fine-grained

收稿日期：2014-12-31；修回日期：2015-04-27

基金项目：国家自然科学基金项目(61379084,61402440);中国科学院科研装备研制项目(YZ201321)

中图法分类号TP391

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61379084,61402440)andtheInstrumentDevelopingProjectoftheChineseAcademyofSciences(YZ201321).