基于Tilera的H.264解码并行算法的性能分析.docx

tilera基于tilera的h.264解码并行算法的性能分析摘 要:多核已经成为当前桌面和超级计算机主流处理器技术，其中tilera多核处理器以其功耗和并行方面的优势在网络视频处理应用中潜力颇大。本文针对高视频质量的h.264解码算法，研究其并行策略，在tilera多核结构实现了两种宏块级并行策略，即任务池和循环行块并行算法。通过实验分析表明，循环块并行算法大大降低了线程间同步开销影响，相对任务池并行程序性能提高了30%以上，在16核规模下获得了11倍的加速效果。关键词:多核，并行，tilera，h.264，高性能1 介绍过去处理器主要依靠提高主频和挖掘指令级并行（ilp）来获得性能提升，但芯片面积和功耗成为制约其继续发展的障碍。当前，多核技术已经成为处理器的主流，无论是工业界还是学术界，多核都是重要的研究热点。在过去的几年中，intel/amd的通用商业多处理器的核心数目已经从2核提高到了12核。但是这些技术很难扩展到众核规模，如片内集成100-1000个核心。在众核规模下，目前通用商业多核技术会引入低效核间通信、共享有限访存带宽等性能瓶颈，更严重的是其高的功耗开销。为了克服上述通用多核处理器技术带来的扩展性问题，目前学术界和工业界正在展开大量研究，提出了许多众核处理器设计技术。ibm cell 1是低功耗的异构的处理器，并且已经成功用于构建全球第一台实测峰值超过1petaflops的超级计算机 2。nvidia、intel和amd都采用了gpgpu的技术路线，设计自己的众核处理器用于加速科学计算，但目前的gpu在功耗方面逐渐显露出其劣势，比如最新的nvidia采用fermi处理器的加速卡，其功耗超过200w。事实上，流处理器技术正成为高性能计算的重要方面，作为其典型代表，tilera 3由于其易用性和高性能，使其能适合多个领域的计算密集型应用，如网络、数字视频和通信领域。随着网络技术与多媒体技术的不断发展，为了能够在较低的带宽上提供高质量的图像传输，h.264 4视频编码技术因其高压缩比、高抗误码效应和良好的网络亲和性的优势而得到广泛的使用。该技术也代表了当今通信行业融合的趋势，如广电、网络多媒体和3g移动网络等方面的需求。然而，h.264技术的高性能是以其算法复杂度为代价的。本文的主要目的是评价h.264解码在tilera上的性能，针对h.264解码应用，以寻求其在tilera扩展到众核的有效途径。我们实现了两种在其它多核结构上主要使用的并行化策略，测试了两种算法在tilera上的扩展性。本论文的组织如下：第二节简要介绍tilera多核体系结构，包括论文的实验平台tilepro是tilera家族中的一款多核处理器。第三节描述了h.264解码算法的基本流程，并分析了其并行化的可能性。第四节重点阐述了论文实现的两种基于宏块级并行策略。第五节结合在tilepro上的实验，给出详细的性能评价。 2 tilera多核体系结构tilera处理器的前身是mit大学的raw体系结构 5，是在学术界称为tile体系结构的典型代表，一个raw 处理器由16个可编程的tile组成。每个tile都有其单独的微处理器、数据cache、存储器以及连接各个tiles的互连网络接口。raw适合于线程级并行，各线程可分空间并行执行。raw把底层的物理资源如门、线、引脚等作为体系结构的实体暴露给程序员，这使得程序员面对线延迟可以更好的安排程序执行从而获得最佳性能，较好的解决线延迟的问题。tilera公司基于raw的研究基础开发了tile64，于2007年发布，它具有64个处理核，采用45 nm工艺，主频达900mhz。tile64使用imesh片上网络连接64个独立的处理核（称为tile），具有4个ddr2控制器、2个网络接口、两个pcie接口。 图1给出了tilera处理器（tile64和tilepro）的硬件体系结构。每个tile都是一个全功能通用处理核，实现了3路超长指令字（vliw）的32位整数处理引擎，包含一个寄存器文件和三个功能单元（一个load-store单元和两个算术逻辑单元），l1和l2级cache，使用非阻塞交叉开关将tile连入imesh。片内互联网络有多个动态网络和一个静态网络组成，比如三个寄存器映射的体系结构定义的用户态动态网络（udn）、输入/输出动态网络（idn）和静态网络（stn），此外tile64和tilepro实现了支持主存通信和tile之间存储映射的硬件管理网络。每个tile可以独立运行一个操作系统，或者多个tile共同运行一个多处理操作系统（如smp）。tile64具有灵活的特点，多个tile可以组成lane，为特定应用提供足够的计算性能。同时，tilera通过每个tile能够运行不需要修改的c代码而获得性能和编程之间的最佳平衡。 3 h.264解码流程介绍h.264是由联合视频组提出的最新数字视频解码器的标准，包含了视频编码层（vcl）和网络提取层（nal）。vcl包括核心压缩引擎和块、宏块和片的语法级别定义，它的设计目标是尽可能地独立于网络进行高效地编解码；而nal层则负责将vcl产生的比特字符串适配到各种各样的网络和多元环境中，它覆盖了所有片级别以上的语法级别，同时支持：独立片解码、起始码唯一保证、支持sei和支持流格式编码数据传送。图2描绘了h.264的解码过程。总体说来，nal解码器负责将符合h.264码流规范的压缩视频流解码，并进行图像重建。视频编码比特流首先经过解析，分离成参数信息和图像残差数据，其中参数信息指明宏块类型和解码方案等，图像残差数据经熵解码，逆zig_zag重排序，反量化和反变换得到时域残差，与此同时，利用已经重建的邻近块作为参考对当前块进行帧内预测或帧间预测，预测的结果加上时域残差即得到当前块的重建值。其中熵解码包括基于上下文的自适应变长编码cavlc和基于上下文的自适应算术二进制编码cabac，这二者应用于h.264的不同档次级别中（本文假设的是cabac编码）。 图1. tile处理器硬件体系结构图2. h.264解码算法流程图3. 编码比特流数据格式h.264视频编码比特流是有若干nal单元组成，图3给出了视频流的结构。第一个单元是序列参数集sps，第二个是图像参数集pps，二个单元共同组成了该段视频的编码特征信息，第三个及以后的nal单元则包含了图像数据，一般一个单元表示一副图像数据，有若干片组成，每个片又是由若干大小为16*16的宏块组成，每个宏块包括了4个8*8的亮度块，一个8*8的cr色度块和一个8*8的cb色度块，其中每一块又分成4个4*4的字块。h.264视频网络流解码过程存在多个级别的并行。最粗粒度的并行在于流级并行，一个流代表了一个视频文件，每个视频文件之间没有任何数据依赖关系。流级并行的问题是每个视频流的大小变化带来的负载平衡，一个小的视频流可能只有20多帧，但一个大能够到200多帧。对于单个流，解码过程中可以开发帧（frame）级并行和片（slice）级并行。从帧级看，视频流包含了b/p/i三种类型的帧，一个帧序列以i帧开始，跟随了若干b帧和p帧。i帧单独解码后，解码p帧，然后解码b帧。i帧和p帧之间通常会有一个或多个b帧，这多个b帧可以并行解码。如前所述，一帧由若干片构成，这些片的解码也能够并行完成。然而，并行的b帧或者片的数量通常相当有限，比如某些视频流的i/p帧之间的b帧只有2-3个，甚至一帧的片数量只有一个。因此，帧、片级并行度有限，不适合规模并行。图4. 宏块之间的依赖关系示图注意到片又有多个宏块组成，通常宏块的数量达到成百上千，自然可以考虑宏块（macroblock, mb）级并行。但宏块级也需要处理块之间的依赖关系。图4给出了一个宏块依赖关系的示例，宏块（1,4）（2,2）（3,0）正在处理解码，必须等其依赖的宏块完成解码，这三个块的解码操作才能执行，而三个宏块解码操作可以完全并行执行。相对于帧/片级，宏块级的并行度具有明显的优势，因此本文重点关注宏块级并行策略的分析。4 宏块级并行解码算法视频流的一帧中的宏块组织成大小为（nhor, nver）的2维网格，由于宏块之间的依赖关系，所有宏块的解码必须按照一定顺序执行。如图4所示，宏块之间并行主要存在对角线上的宏块，表明了宏块级并行受限于水平方向的块数量，即宏块级并行度pmb为：例如，对一个120*67的视频流，其最大并行度为60。根据宏块和处理器之间映射策略的不同，有两种宏块级并行算法：任务池和循环行分配。 图5. 任务池算法模型1. while (1) 2. 等待主线程的开始信号;3. if (帧末尾) 退出；4. while (队列不空) 5. 从任务队列中取一宏块；6. 解码；7. 更新依赖关系表；8. 提交满足依赖关系的宏块；9. 10. 图6. 任务池模式中工作线程算法4.1 任务池任务池算法用主从模式实现宏块级并行 6，图5说明了任务池算法的实现。所有线程协作维护每个宏块（即图中的工作单元）的状态，选择满足依赖关系的宏块调度分配给空闲的工作线程。宏块的状态维护通过依赖关系表实现，调度通过任务队列方式进行。依赖关系表中的每一项的值代表其依赖宏块的数量，当该项的值变为零时，线程将该宏块插入到先进先出的任务队列中，当有空闲的从线程时，从任务队列中取出任务完成解码操作。当线程完成解码操作后，更新依赖关系表：将其右边和下方的邻接项减一。工作线程并行算法流程如图6所示。由于所有线程共享依赖关系表和任务队列，算法中的第5、7、8行需要线程间同步处理多个线程同时更新依赖关系表和任务队列的操作。考虑到单个宏块解码本身的执行时间短，同步操作的开销在一定程度会影响并行解码算法的扩展性。因此降低额外同步开销的影响成为提高扩展性的重要策略，基于这个思想，本文采用了更静态的宏块分配策略。 图7. 循环行分配算法模型4.2 循环行分配对一个二维的宏块矩阵，循环行分配算法循环地分配每一整个宏块行给一个线程 7。假设有p个线程，每个线程i处理宏块行号为：j jmod i =0,1ip2. while (1) 2. 等待主线程的开始信号;3. if (帧末尾) 退出；4. while (队列不空) 5. 从任务队列中取一宏块；6. 解码；7. 更新依赖关系表；8. 提交满足依赖关系的宏块；9. 10. 图7描绘了循环行分配策略的例子，这样，同一行的宏块的依赖关系的更新由一个线程完成，消除了处理一行宏块依赖关系的同步开销。循环行分配算法如图8所示，这里每个线程处于对等模式，每个线程执行的工作一样。第9行多个线程同时更新依赖关系表，第7行读取依赖关系表的状态，这是一个典型生产者-消费者模式，用简单的内存原子操作实现忙等到达线程之间同步。1. while (1) 2. 全局同步;3. if (帧末尾) 退出；4 行号=线程id;/1idp5. while (行号i小于nver) 6. while (列号j小于nhor) 7.等待宏块（i,j）满足依赖关系；8. 解码宏块（i,j）；9. 更新依赖关系表；10. 11. 图8. 循环行分配模式中工作线程算法5 性能评价我们在tilepro上实现了上述的两种宏块级并行算法，编程环境是tilera multicore development environment (mde) 2.1，多线程编程采用了pthread，调用pthread同步互斥函数实现线程间对共享数据（依赖关系表和任务队列）同步，利用tilepro提供的内存原子操作实现了循环行分配算法中的更新依赖关系表操作。实验数据选取了4种不同分辨率大小的h.264视频文件，表1总结了4中视频文件的特点。表1. 实验数据像素大小宏块数量最大并行度325*28818*2211720*57636*45221280*72045*80401920*107267*12060图9. 任务池算法的比特率实验以任务池算法作为基准，比较循环行分配算法的性能改善情况。图9是任务池算法获得的比特率，即文件大小除以解码时间。图示性能表面算法的扩展性和宏块的数量存在直接的关系，像素为325*288的视频每帧有18*22个宏块，而最大并行度为11，当使用的tile核个数超过8时，性能开始呈下降趋势。随着分辨率的增加，并行算法的扩展性逐步提高。图10给出了循环行分配策略相对任务池策略的性能提高，可以看出，对所有的分辨率的视频解码，循环行分配策略均有较大幅度的提升，最高的的提升幅度达到35%。同时，我们分析了循环行分配算法的加速比，图11给出了优化算法的相对单tile核的加速比，在16个核的情况，加速比达到11。在4个tile核的情况下获得了线性加速比。图10. 循环行分配算法相对任务池算法的提高图11. 循环行分配算法的加速比图12. 熵解码部分占的时间比例最后，我们分析限制并行解码算法扩展性能的主要因素。注意到如图2所示，解码算法对每个宏块需要一个熵解码的操作，而熵解码操作不能并行化，根据amdal定律，改部分的时间决定了并行程序的加速性能。实验得到的熵解码时间如图12所示，显然，随着tile核数目使用的增加，熵解码的时间比例明显增加，甚至占了总时间的80%。因此，未来有必要采用特殊硬件加速的方法提高该部分的性能。6 总结论文描述了两种基于宏块级并行h.264解码的并行算法，即任务级和循环行分配策略，并在tilepro上实现了两种算法，通过实验分析表明，循环行分配策略相对任务池分配由于减少了同步开销，性能提高了30%以上，在16核情况获得了11倍的加速性能。致谢：论文得到了国家自然科学基金60803030的支持。references:1 /cell/.2 .3 /.4 thomas wiegand, gary j. sullivan, gisle bjntegaard, and ajay luthra, overview of the h.264/avc video coding standard, inieee transactions on circuits and systems for video technology(2003).5 michael bedford taylor, walter lee, jason miller, david wentzlaff, ian bratt, ben greenwald, henry hoffmann, paul johnson, jason kim, james psota, arvind saraf, nathan shnidman, volk