（信号与信息处理专业论文）h264并行编码算法的研究和优化.pdf

上海交通大学硕士学位论文 ii h.264 并行编码算法的研究和优化 h.264 并行编码算法的研究和优化 摘摘 要要 2001 年，iso 的运动图像专家组(mpeg)和 itu/vceg 成立了联 合视频组(jvt)共同发展和研究h.26l标准， 并将研究草案纳入itu-t 视频技术建议 h.264 和 iso/mpeg 组织制定的 mpeg-4 标准的 part 10(即 avc)中。 h.264/avc 作为新一代视频编码算法吸收了以往编码 方案的优点，在视频压缩性能和网络接口友好性上得到了很大的提 高，但是这些优点都是以引入复杂度为前提的。分析 h.264 编码器的 结构可知，其高复杂度的计算量主要来源于两个方面，一是帧间编码 的 1/4 像素精度运动搜索，多种可变大小的块模式及多参考帧的运动 估计；二是帧内编码的多种预测模式。如何快速的实现编、解码成了 h.264 目前急需解决的问题。 目前几乎所有的 cpu 架构都在向多核化方向发展，例如 intel、 amd 的 x86、ibm 的 powerpc 等。跟传统的单核 cpu 相比，多核 cpu 带来了更强的并行处理能力和更高的计算密度。可以预见，多 核 cpu 必将成为未来处理器市场上的主流产品。 针对 h.264 编码的复杂性，人们提出了很多并行优化的方法。一 种是基于指令级的并行(ilp)，例如很多 dsp 平台提供的单指令多数 据流(simd)指令；另一种是基于线程级的并行(tlp)，这种方法需要 上海交通大学硕士学位论文 iii 和多核技术相互配合来实现。试验证明，单纯使用任何一种方法都不 能实现编码的最大并行化。 考虑到 x264 本身已经实现了 x86 平台下 的指令级并行，因此本文使用 x264 编码器作为研究对象，并在其 simd 指令级并行优化的基础上进行线程级并行优化， 配合 intel 的双 核处理器平台，在 linux fedora core 5 操作系统下获得了较高的编码 加速比提升。 x264当前采用基于fork-join模型的slice级并行算法。 测试结果表 明：该模型开销较大，在低分辨率的编码应用中严重限制了slice级并 行算法所获得的编码加速比。为了避免fork-join模型带来的开销，本 文在传统线程池的基础上提出了自适应线程池模型， 并使用该模型对 x264进行优化。 对码流质量要求严格的非实时编码的应用场景，本文选取gop级 并行对x264编码器进行并行优化并获得接近线性的加速比。 对码流质量要求严格的实时编码的应用场景， 本文使用frame级并 行和slice级并行相结合的方法，该算法避免了单纯使用frame级并行 获得的加速比低以及slice并行会降低目标码流质量的缺点， 在几乎不 影响目标码流质量的前提下，获得了较高的加速比。 关键词：关键词：h.264/avc，指令级并行，线程级并行，多核，自适应线程 池模型 上海交通大学硕士学位论文 iv parallel algorithm design and optimization for h.264 video encoding abstract in 2001, the moving picture experts group (mpeg) of iso and the video coding experts group (vceg) of jvt developed the h.26l standard together. the latest video coding standard significantly improves in both the coding efficiency and network adaption. in order to achieve the best coding efficiency, the h.264 encoder introduces a lot of complexity. analyzing the structure of h.264 encoder, it is clear that the complexity is derived from two aspects, one is the inter prediction technology, including the multiple reference frames, the other one is the intra prediction technology. how to encode the h.264 stream more quickly is one of the most important things for now. in order to avoid the worse power consumption, almost all cpu architectures are on their ways toward multi-core technology, compared with the single core cpus, multi-core cpus can provide more powerful computing ablilty and real parallel processing. 上海交通大学硕士学位论文 v there are mainly two parallel methods to optimize the h.264 encoder, one of which is instruction level parallelism(ilp), we can see it on many dsp platforms, the other one is thread level parallelism(tlp), this method must cooperate with the multi-core technology. this thesis optimizes the h.264 encoder using both methods, and got much speedup improvement under linux fedora core 5 operating system on intel dual-core platform. x264 encoder uses “fork-join” model for its parallel algorithm, but this model is costly especially in low resolution encoding. in order to avoid this penalty, this thesis introduces a new model“adaptive threading pool” model. for the non-real-time applications, we choose the gop level parallel algorithm, the tests results show that the speedup can achieve up to about 2 on the intel dual-core architecture. for the real-time applications, we choose the combination of the frame level parallel and the slice level parallel algorithms. it is quicker than the frame level parallelism and the quality is much better than slice level parallelism. key words: key words: h.264/avc，instruction level parallelism，thread level parallelism，multi-core，adaptive threading-pool model 上海交通大学硕士学位论文 viii 缩略语 缩略语 ilp ： instruction level parallelism 指令级并行 tlp ： thread level parallelism 线程级并行 smp： symmetric multi processing 对称多处理器 vcl： video coding layer 视频编码层 nal： network abstraction layer 网络抽象层 mpeg：moving picture experts group 运动图像专家组 vceg：video coding experts group 视频编码专家组 jpeg：joint photographic experts group 联合图像专家组 sisd：single instruction single data 单指令单数据流 simd：single instruction multiple data 单指令多数据流 misd：multiple instruction single data 多指令单数据流 mimd：multiple instruction multiple data 多指令多数据流 sse： stream simd extensions 单指令多数据流扩展 mmx：multimedia extensions technology 多媒体扩展 gop： group of pictures 图像组 avc：advanced video coding 高级视频编码 rdo：rate distortion optimized 率失真优化 atp：adaptive threading pool 自适应线程池模型 psnr：peak signal to noise ratio 峰值信噪比 cavlc：context-adaptive variable length coding 上下文自适应的可变长编码 cabac：context-based adaptive binary arithmetic coding 上下文自适应二进制 算术编码 上海交通大学硕士学位论文 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得 的成果。 除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：蒋兴昌 日期： 2008 年 1 月 31 日 上海交通大学硕士学位论文 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、 使用学位论文的规定， 同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。 本人授权上海交 通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密保密，在 年解密后适用本授权书。 本学位论文属于 不保密 不保密。 （请在以上方框内打“” ） 学位论文作者签名：蒋兴昌 指导教师签名：周军 日期：2008 年 1 月 31 日 日期：2008 年 1 月 31 日 上海交通大学硕士学位论文 1 第一章 绪论第一章 绪论 1.1 引言1.1 引言 近年来，数字电视得到飞速发展。和传统的模拟电视相比，数字电视具有 如下优点13： ? 失真小，噪声低、质量高。因此数字电视的收视效果好，图像清晰度高， 音频质量高，更能满足人们日益增长的感官需求。 ? 抗干扰能力强。数字电视不易受外界的干扰，因此易于处理和容易纠错， 避免了串台、串音、噪声等影响。 ? 容量大、节目多、传输效率高。利用有线电视网中的模拟频道可以传送的 数字电视节目约为模拟电视节目的 11倍9。 ? 兼容现有模拟电视机。通过在普通电视机前加装一台机顶盒就可以收看数 字电视节目。 ? 提供全新的业务。借助双向网络，数字电视不但可以实现用户自点播节目、 自由选取网上的各种信息，而且可以提供多种数据增值业务。 数字电视的优越性是公认的，但是它的广泛应用还有赖于高效的压缩技术。 2001 年，iso 的运动图像专家组(mpeg)和 itu/vceg 成立了联合视频组(jvt) 共同发展和研究 h.26l 标准，并将研究草案纳入 itu-t 视频技术建议 h.264 和 iso/mpeg 组织制定的 mpeg-4 标准的 part 10(即 avc)中110。一方面， h.264/avc 由于压缩效率高和网络接口友好，成为普及各种视频传输服务的重 要工具。另一方面，h.264/avc 作为新一代视频压缩算法吸收了以往编码方案 的优点，在视频压缩性能上得到了很大的提高910。例如，利用 mpeg-2 压缩 一路高清电视节目约需要 20mbit/s 的带宽，而如果利用 h.264 来压缩，则只需 要约 5mbit/s 的带宽9。为更好地适应网络传输，h.264/avc 在系统层上提出了 一个新的概念，即在视频编码层（video coding layer，vcl）和网络抽象层 （network abstraction layer，nal）之间进行概念性分割91015，这样的结构 便于信息的封装和对信息进行更好的视频流优先级分类控制。但是它的这些优 点都是以引入成倍的复杂度为前提的，为了最大程度地提高编码效率，在 h.264 上海交通大学硕士学位论文 2 中编码器采用了基于全局搜索的算法，针对各种不同的编码模式，循环计算各 种模式下的 rdo(rate distortion optimized)代价函数，比较并选择最小 rdo 代 价函数所对应的编码模式作为最优的编码模式，从而造成 h.264 在算法复杂度 和计算量上急剧增加27。因此如何快速地实现编、解码成了目前 h.264 急需解 决的问题。 本章首先介绍了 h.264 基本的编码框架、主要的优化方法，然后简要介绍 了并行算法的基本理论，最后给出了本文的内容安排。 1.2 h.264 编解码框架及其新特性1.2 h.264 编解码框架及其新特性 h.264 并不明确规定一个编、解码器如何实现，而是规定一个编码完成的视 频比特流的句法，以及该比特流的解码方法，各个厂商的编码器和解码器在此 框架下可以互通，因而具有较大的灵活性，并且有利于各个厂商之间相互竞争 910。 图 1-1 和图 1-2 分别给出了 h.264 编码器和解码器的结构框图。由图中可以看 出，h.264 和以前标准(h.261、h.263、mpeg-2、mpeg-4)中的编、解码器功能 块组成没有什么区别，主要区别在于各个功能模块的细节设计。h.264 采用自 适应技术来克服视频内容的多变性和信道的多变性，因而带来了明显的性能改 善。 当前帧 变换 编码 量化 重排 序 熵编 码 运动 估计 运动 补偿 参考帧 重建帧 环路 滤波 帧内预 测选择 帧内 预测 反变 换 反量 化 帧间 帧内 帧间 帧内 nal dn dn 图 1-1 h.264编码器结构图9 上海交通大学硕士学位论文 3 fig. 1-1 structure of h.264 encoder. 熵编码重排序反量化反变换 帧内预测 运动补偿参考帧 滤波重建帧 nal 帧间 帧内 帧间 帧内 图 1-2 h.264解码器结构图9 fig. 1-2 structure of h.264 decoder. h.264/avc 作为最新的编码国际标准是由 itu-t vceg 和 iso/iec mpeg 共同开发19，并于 2003 年 3 月正式公布的，它着重于解决压缩的高效率和传 输的高可靠性。为了提供了很多灵活性和客户化特性，h.264/avc 设计方案包 含两个层次，视频编码层（vcl，video coding layer）和网络抽象层（nal， network abstraction layer） ，如图 1-3 所示。视频编码层主要致力于有效地表示 视频内容，包括具体的视频编码算法和流程，网络抽象层格式化 vcl 视频表示， 提供头部信息，适合多种传输和存储媒体。 图 1-3 h.264/avc视频编码器结构10 fig. 1-3 structure of h.264/avc video encoder. h.264 作为最新的视频压缩标准，与以前视频压缩标准如 mpeg-2/4， h.261/263 等相比引入了很多新的特性： 1. 在图像内容预测方面提高编码效率，改善图像质量的主要特点如下91018： ? 可变块大小运动补偿：h.264 采用更加灵活的运动补偿块大小，最小运 动补偿块可采用 44 大小的块。 上海交通大学硕士学位论文 4 ? 1/4 像素运动补偿：h.264 采用 1/4 像素运动补偿提高运动补偿的精度， 同时与 mpeg-4 相比，降低了内插的复杂度。 ? 运动矢量可跨越图像边界：运动矢量不再限制在已编码参考图像的内 部，图像边界外推法在 h.264 中被采用。 ? 多参考图像运动补偿：h.264/avc 使用高级图像选择技术，可以用以前 已编码过且保留在缓冲区的大量的图像进行预测，大大提高了编码效 率。 ? 消除参考图像顺序和显示图像顺序的相关性：在以前的标准中，参考图 像顺序依赖显示图像顺序，h.264/avc 消除了该限制，可以任意选择。 ? 消除参考图像与图像表示方法的限制：在以前的标准中，b 帧图像不能 作为预测图像，h.264/avc 在很多情况可以利用 b 帧图像作为参考。 ? 加权预测：h.264/avc 采用新技术，允许加权运动补偿预测和偏移一定 量。在淡入淡出场景中该技术极大提高编码效率，该技术还可用于其他 多种用途。 ? 改善“跳过”和“直接”运动推测：h.264/avc 对“跳过”区的运动采用推测 方法。对双预测的 b 帧图像，采用高级运动预测方法，称为“直接”运动 补偿，进一步改善编码效率。 ? 帧内直接空间预测：将编码图像边沿进行外推应用到当前帧内编码图像 的预测。 ? 循环去块效应滤波器：基于块的视频编码在图像中存在块效应，主要来 源于预测和残余编码。自适应去块效应滤波技术是非常著名的技术，能 有效消除块效应，改善视频的主观和客观质量。 2. 除改善预测方法外，其他改善编码效率的特性如下： ? 小块变换：h.264/avc 主要使用 44 块变换，使编码器表示信号局部适 应性更好，更适合预测编码，减少“铃”效应。另外图像边界需要小块变 换。 ? 分级块变换：h.264/avc 通常使用 44 块变换，但有些信号包含足够的 相关性，要求以大块表示，h.264/avc 有两种方式实现。低频色度信号 可用 88；对帧内编码，低频亮度信号可用 1616 块。 上海交通大学硕士学位论文 5 ? 短字长变换：所有以前标准使用的变换要求 32 位运算，h.264/avc 只 使用 16 位运算。 ? 完全匹配反变换：所有以前标准反变换和变换之间存在一定容限的误 差，因此，每个解码器输出视频信号都不相同，产生小的漂移，最终影 响图像的质量，h.264/avc 实现了完全匹配。 ? 基于上下文的算术熵编码： h.264/avc 使用两种熵编码方法， cavlc （上 下文自适应的可变长编码）和 cabac（上下文自适应二进制算术编码） ， 两种都是基于上下文的熵编码技术。 3. h.264/avc 具有强大的纠错功能和各种网络环境操作灵活性，主要特性如 下： ? 参数集结构：h.264/avc 参数集结构设计了强大、有效的传输头部信息。 在以前的标准中，如果少数几位关键信息丢失，可能解码器产生严重解 码错误。h.264/avc 采用很灵活、特殊的方式，分开处理关键信息，能 在各种环境下可靠传送。 ? nal 单元语法结构：h.264/avc 中的每一个语法结构放置在称为 nal 的单元中，以前的标准采用强制性特定的位流接口。nal 单元语法结 构允许很自由的客户化，几乎适合所有的网络接口。 ? 灵活的像条大小：在 mpeg-2 中，规定了严格的像条结构，头部数据 量大，降低预测效率，编码效率低。在 h.264/avc 可采用非常灵活的 像条大小。 ? 灵活宏块排序（fmo） ：h.264/avc 可以将图像划分为像条组，又称为 图像区，每个像条可以独立解码。fmo 通过管理图像区之间的关系， 具有很强的抗数据丢失能力。 ? 任意像条排序：因为每个像条几乎可以独立解码，所以像条可以按任意 顺序发送和接收，在实时应用中，可以改善端到端的延时特性，特别适 合于接收顺序和发送顺序不能对应的网络中，如使用 internet 网络 协议的应用。 ? 冗余图像：为提高抗数据丢失的能力，h.264/avc 设计中包含一种新的 能力，允许编码器发送图像区的冗余表示，当图像区的主表示丢失时仍 上海交通大学硕士学位论文 6 可以正确解码。 ? 数据划分：视频流中的编码信息的重要性不同，有些信息（如运动矢量、 预测信息等）比其他信息更为重要。h.264/avc 可以根据每个像条语法 元素的范畴，将像条语法划分为 3 部分，分开传送。 ? sp/si 同步/切换 图像：h.264 设计了一种新的特性的图像格式，提供 额外的同步机制，允许解码器在不重新发送 i/idr 帧的情况下在不同的 视频流之间切换。这样就使得解码器可以在同一视频节目的不同码率的 重现之间切换，恢复丢失数据或者错误，同时也可以使用在快进或快退 的工作模式。 1.3 并行理论基础 1.3.1 并行算法概念 并行理论基础 1.3.1 并行算法概念 并行是指在某一个时刻同时完成多个任务。从硬件的角度来看，一个程序 执行可以分成指令流和数据流两个部分。flynn 在 1972 年提出了 flynn 分类法 78，根据处理数据流和指令流的方式不同，可以将并行平台分为： 单指令单数据（sisd） 7111213：这种计算机平台就是传统的串行化计算机， 在硬件上不能提供并行处理的能力。即程序的指令按照顺序执行，并且在任意 时刻只能处理单个数据单元。 多指令单数据（misd） ：这种计算机平台虽然在某一个时刻只能处理一个 数据单元，但是它允许多条指令同时执行。由于多条指令并发执行需要多个数 据流，因此这种平台在实际中并没有价值，仅在理论上存在。 单指令多数据（simd） ：这种计算机平台支持向量运算，即一条指令可以 作用于多个数据单元， 例如 x86 系列中带有 mmx、 sse 指令的计算机， powerpc 中带 altivec 指令的计算机等。这种计算机存在于数字信号处理、图像处理以及 多媒体应用等领域。 多指令多数据（mimd） ：这种平台支持多个数据流，每个数据流可以处理 一个到多个数据流。例如 power4、power5、ultrasparc t1、intel core2-dual 等 都属于 mimd 计算机。 flynn 分类法如图 1-4 所示。 上海交通大学硕士学位论文 7 multiple instruction, single data misd multiple instruction, multiple data mimd single instruction, single data sisd single instruction, multiple data simd data instruction 图 1-4 flynn分类法7 fig. 1-4 flynns taxonomy 从软件的角度看，并行可以分为数据并行和任务并行8。数据并行非常简单， 它是指您有大量数据需要处理例如图像中的像素，大量工资支票等。把这 些数据进行分解并交给多个处理器进行处理，这就是一种数据并行方法。 任务并行性则是指有多个任务需要完成。例如求一个数据集的最小值、最 大值和平均值，就可以让不同的处理器针对同一个数据集分别计算其最大、最 小和平均值的答案。 从并行的层次上看，还可以把并行分为指令级并行和线程级并行7 8。指令 级并行是指在单个 cpu 中，利用流水线、超标量、乱序执行等方法，使得多条 指令在同一个 cpu 上同时运行，以提高系统的吞吐率4。线程级并行是指在多 cpu 结构中，将多个线程分别分配到不同的 cpu 上执行。指令级并行和线程级 并行的一个很重要的区别在于，指令级并行对于程序员来讲是透明的，相反， 线程级并行则需要程序员自己来分配执行单元，受到程序员的控制,因而更加灵 活。 1.3.2 微处理器的发展方向1.3.2 微处理器的发展方向 1965 年，莫尔提出了著名的莫尔定律42021：硅片上晶体管的数目每 12 个 月翻一倍，1975 年莫尔将这个定律修正为每 18 个月翻一倍。从 1971 年 intel 推 出的第一块芯片 4004（108k hz，2300 个晶体管）开始，到 2004 年的 pentium 4 3.8g hz（1.25 亿个晶体管） ，微处理器一直严格遵循莫尔定律发展。在集成电 路行业里， “莫尔定律”的实现方法是把支持硅技术的器件参数等比例缩小，这 样就可以在同样的面积下集成更多的晶体管，获得更高的时钟频率。而理论上 上海交通大学硕士学位论文 8 芯片的功耗和芯片的面积成正比，这样一来，每一代微处理器性能都比上一代 高一倍，而功耗却差不多。 现代的微处理器都是采用 cmos 数字电路构造，其中有一种关键结构，叫 栅极氧化层，它的一个重要作用就是绝缘。在半导体工艺里要求栅极氧化层的 厚度不能超过理论值，并且要求栅极氧化层表面非常平整，不能有缺陷，否则 会导致严重的漏电流效应4。 然而，随着微处理器主频的提升，集成电路集成度的提高，工艺上遇到的 首要问题就是如何减小栅极氧化层的厚度并且同时保证其没有缺陷。现在的工 艺对于原子大小数量级的加工还没有很好的解决方案，缺陷率非常高。在90nm 工艺里，栅极氧化层的厚度仅为1.2nm，相当于45个原子的厚度，在这种情 况下，一旦有缺陷，哪怕仅仅相差一个原子，都会引起10100倍的漏电流4。 由功率和电流的平方成正比的关系，将导致微处理器成百上千倍的发热。 除了功率和散热的原因之外，促使微处理器向多核方向发展还有另外两个 重要因素。一个是指令级并行获得的性能提升越来越小，通过流水线、超标量、 乱序执行，指令级并行已经发展到了尽头4。另一个是内存和处理器速度之间 的差异越来越大，cpu的运行速度受到了内存访问延迟的制约。因此，并非莫 尔定律失效，而是由于功耗的限制和超标量发展的瓶颈使得传统单纯依靠提升 主频的方法变得不切实际。而且由于目前没有更好的可以代替cmos的方法， 研究人员只好转而发展多核技术，以此来达到微处理器性能的提升。 1.3.3 微处理器架构1.3.3 微处理器架构 按照内部核心的连接方式可以将微处理器分为4类72021。 1 单核心处理器。这种架构的特点是：处理器内部的逻辑控制寄存器只有一套， 运算单元也只有一套，因此在每一个特定时刻，只能有一个线程使用cpu， 多线程只能依靠操作系统提供的分时调度来实现，对于单个任务来说，并行 并不能带来实际的加速。单核心处理器架构如图1-5所示： cpu state register file execution unitscache 上海交通大学硕士学位论文 9 图 1-5 单处理器结构图7 fig. 1-5 single-core processors architecture. 2 多处理器。这种架构的特点是：通过总线将多个单核心处理器连接在一起构 成多处理器系统31。因此可以将一个任务划分为多个子线程，每个处理器可 以运行其中一个子线程来达到并行加速。由于系统中存在多套控制逻辑和多 个运算单元，因此多个线程在同一时刻可以同时运行，但由于核与核之间是 通过总线实现互连，因此当cpu数目较大时（比如16甚至更多） ，核与核之 间的通信将成为瓶颈。多处理器架构如图1-6所示。 cpu state register file execution unitscache cpu state register file execution unitscache mch 图 1-6 多处理器结构图7 fig. 1-6 multi-processors architecture. 3 超线程处理器113039。超线程架构的特点是：处理器拥有两套控制逻辑以及 相应的寄存器组，但是仅仅包含一套执行单元。超线程出现的原因是，很多 任务（特别是i/o相关任务）执行时，执行单元的利用率非常低。如果处理 器包含两套控制逻辑，那么每套控制逻辑就可以运行两个不同的线程，同时 两个线程共享同一个执行单元，这样可以提高执行单元的利用率，获得更好 的性价比。超线程处理器架构如图1-7所示。 cpu state register file execution unitscache cpu state register file 图 1-7 超线程处理器结构图7 上海交通大学硕士学位论文 10 fig. 1-7 hyper-threading processors architecture. 4 多核处理器。多核处理器的特点是：处理器拥有多套控制逻辑及相应的寄存 器组，同时拥有多套执行单元。由于核与核之间的通信完全在芯片内部实现， 并且核与核之间共享cache，这样多核处理器核与核之间的通信开销远小于 多处理器系统，因而多核处理器的扩展性更好。由于每套控制逻辑对应自己 的执行单元，因此对于计算量较大的任务，不会由于竞争执行单元而产生延 迟。多核处理器架构如图1-8所示。 cpu state register file execution units cache cpu state register file execution units 图 1-8 多核处理器结构图7 fig. 1-8 multi-core processors architecture. 5 各种架构cpu资源占用比较。图1-9给出了单cpu、超线程核以及多核运行 时cpu资源占有情况。每一个小方格表示在某一个时刻cpu的某个资源，白 色表示该资源空闲，其他颜色表示该资源被占用，不同颜色表示不同的线程。 从图中容易看出，单核心cpu在一个时间点上只能运行一个特定的线程。 hyper-threading在同一时刻能够运行多个线程，但是由于多个线程可能会竞 争资源，特别是对于运算量较大的线程，会导致每个线程的执行速度相对于 该线程在单线程环境下的执行速度变慢。multi-core则从根本上解决的资源 冲突问题，多个线程可以并行执行，而且线程之间不会竞争资源，因此每个 线程执行的速度和单线程环境下的执行速度是一致的。 上海交通大学硕士学位论文 11 时间时间 t single corehyper-threadingmulti-core 图 1-9 各种架构处理器资源占用对比7 fig. 1-9 3 kinds of architecture of resource utilization. 1.3.4 阿姆达定律1.3.4 阿姆达定律 1967年，阿姆达（amdahl）提出了著名的阿姆达定律（amdahls law）21。 他首先提出了加速比的概念，假设任务p在计算机c1上运行的时间为t1，而在 计算机c2上运行的时间为t2，那么可以定义计算机c2相对计算机c1的加速比 为： 2 1 t t speedup = 对于并行计算，同样可以定义并行计算机相对串行计算机的加速比： _ lg _ lg bestsequentialaorithm parallelaorithm time speedup time = 假设任务t可以分为可并行部分tp和不能并行处理的部分ts，其中ts占整个 任务的比例为s，若并行计算平台的计算单元数目为n，那么加速比可以改写为： nsstsntp tstp nspeedup )1 ( 1 )( + = + + = 阿姆达悲观地预计：并行计算所能获得的加速比严格受限于s，当并行计算 单元n趋于无穷时，加速比达到最大值1/s，换句话说，不管系统如何增加运算 单元，通过并行能够达到的最大加速比为1/s。图1-10给出了串行部分占整个任 务的百分比和加速比之间的关系。例如当串行部分占整个任务的4时，通过并 上海交通大学硕士学位论文 12 行最多只能获得约24倍的加速比。 图 1-10 遵循阿姆达定律的加速比22 fig. 1-10 speedup under amdahls law. 1.3.5 gustafson 定律1.3.5 gustafson 定律 按照阿姆达的预测，多核计算机根本没有发展前景。即使串行部分占整个 任务的5%，利用并行计算最多也只能达到20倍的加速比，用不了几年，多核计 算机就会发展到加速比的极限。1988年，gustafson给出了并行计算的另一个观 点：gustafson认为软件中串行部分的大小是固定的，并不会随着问题规模的扩 大而发生变化22。在这个假设前提下，设并行算法中计算单元的个数为n，并 假设并行单元的执行时间相等，设并行算法中，串行部分执行时间占整个任务 运行时间的比例为s，并行部分执行的时间占整个任务运行时间的比例为p，那 么如果不使用并行算法，需要的处理时间为s+p*n，根据加速比定义，可以得 到： *)1 (*) 1 (* * )(snnnssnps ps nps nspeedup+=+=+= + + = 根据gustafson的假设，随着任务量的增加，串行部分的运行时间并不发生 变化，而随着任务量的增加，处理器单元数目也相应增加，由于并行单元的执 上海交通大学硕士学位论文 13 行时间相等，p也不发生变化，即s值的大小不变。因此加速比和n值呈线性关 系。换句话说，我们可以得到任意大小的加速比。 例如当s的值为5，n为20时，加速比 = 20+(1-20)5% = 19.05 当n增至100时，加速比 = 100+(1-100)5% = 95.05 1.3.6 amdahl 定律和 gustafson 定律的关系1.3.6 amdahl 定律和 gustafson 定律的关系 从表面上看，似乎amdahl定律和gustafson定律是相互矛盾的。其实正好相 反，amdahl定律和gustafson定律是等价的，只是它们基于不同的假设。amdahl 认为：一个任务串行部分占整个任务的比例是一个定值，并不会随着问题规模 的扩大而发生改变。而gustafson则认为随着问题规模的扩大，串行部分是一个 定值，因此串行部分所占的比例会随问题规模的扩大而减小。我们从两个定律 中对串行部分所占整个任务比例的定义可以看出： amdahl 定律： tstp ts s + = gustafson 定律： tsntp ts s + = 将gustafson定律中的s换算成amdahl定律中的s，可以得到： ) 1 (*1 1 ssn s + = 将s值代入amdahl定律，我们得到： *)1 ( )1 ( 1 )(snn nss nspeedup+= + = 也就是说，我们使用amdahl定律和gustafson定律得到的加速比是相同的。 在实际测试中发现，随着问题规模的扩大，很多测试程序都满足gustafson定律 的假设，并在并行处理系统上获得接近线性的加速比23。 1.4 论文主要工作成果及本章小结论文主要工作成果及本章小结 本章首先介绍了视频压缩原理以及目前最新的视频编码标准h.264/avc 上海交通大学硕士学位论文 14 的特点，h.264以其高效的编码效率和友好的网络接口将逐渐取代mpeg-2成为 网络流媒体的标准，但h.264的这些特性都是以非常高的计算复杂度为代价换来 的，因此如何实现快速h.264编码算法就成为一个急需解决的问题。接下来介绍 了多核技术的发展，由于功耗和指令级并行的瓶颈，目前各cpu生产厂商都将 注意力集中在了多核技术上面。本章最后介绍了并行算法的基本理论：amdahl 定律和gustafson定律，为h.264并行算法的可行性提供了理论上的依据。 论文的第二章将根据h.264编码框架特点介绍各种可能的并行算法。通过分 析h.264的结构，按照语法层次可以使用gop级、frame级、slice级和macroblock 级对h.264编码算法进行并行优化。本章还分析了各种方法的优缺点，为后面的 并行优化提供指导方向。 论文的第三章将选取目前应用最多的x264编码器来进行具体分析。测试发 现，x264的fork-join自动多线程模型开销较大，特别是在对qcif、cif等低分 辨率的序列进行编码时获得的加速比非常有限。分析具体代码可知，x264多线 程仅仅是通过slice级并行来实现的，因此在获得一定的加速比情况下会降低目 标码流的质量，这个因素也限制了x264自身并行算法的应用场合。 针对x264本身实现的并行算法的缺点，论文的第四章分别给出了优化算法。 针对fork-join模型开销较大，本章在传统线程池的基础上提出了自适应线程池 模型，通过试验数据证明：使用自适应线程池模型，并行算法能够获得接近最 优情况下的加速比。考虑到slice级并行会降低目标码流的质量，因此对质量要 求严格的非实时编码的应用场景，我们选取gop级并行对x264编码器进行优化 并获得了很高的加速比。对质量要求严格的实时编码的应用场景，我们则使用 frame级并行和slice级并行相结合的方法，该算法避免了单纯使用frame级并行 加速比较低和slice并行会降低目标码流质量等缺点，在几乎不影响目标码流质 量的前提下，可以获得较高的加速比。 本文的第五章将对本文进行全面的总结和展望。 本文的工作成果主要体现在以下几点： 1. 针对x264本身的fork-join多线程模型开销较大的缺点，本文提出了自适应 线程池模型并使用该模型对x264的slice级并行进行了优化。自适应线程池 模型是基于传统的线程池模型，并在每个线程的描述符中加入对应cpu当前 上海交通大学硕士学位论文 15 的状态，使得调度程序可以有条件地分配线程。试验证明，h.264非实时并 行编码算法使用自适应线程池模型可以获得很好的加速比。 2. 对码流质量要求严格的实时编码应用，本文提出了frame级并行和slice级并 行相结合的方法。当帧间不存在相关性时，使用frame级并行实现加速；当 帧间存在相关性时，使用slice级并行实现加速。试验证明，该算法既避免了 帧级并行加速比较小的弊端，又避免了slice级并行导致码流质量下降的缺 点。 3. 对码流质量要求严格的非实时编码应用，本文使用gop级并行算法进行优 化。试验证明，gop级并行可以获得接近cpu个数的加速比，符合gustafson 定律的预测结果。 上海交通大学硕士学位论文 16 第二章 h.264 编码算法可并行化研究第二章 h.264 编码算法可并行化研究 2.1 数据并行和任务并行的选择2.1 数据并行和任务并行的选择 从前面并行理论的介绍我们知道，并行算法可以分为数据并行和任务并行 两大类7。最常见的任务并行就是流水线，即将一个大的任务分解为多个较小 的任务，如果各个子线程都有自己相应的资源，并且这些资源并不冲突，那么 这些子线程就可以并行执行。以h.264并行编码算法为例，可以将编码流程分为 如下几个子任务：运动估计、运动补偿、整数变换、量化和熵编码。最直接的 想法就是将每个子任务以线程的方式独立出来，并运行在一个单独的处理单元 上。这样，原始数据帧依次通过每个子线程，达到并行处理的目的。图2-1给出 了一个通过任务并行加速h.264编码的原理框图。 运动估计运动估计 运动补偿运动补偿 整数变换整数变换量化量化熵编码熵编码pic1 运动估计运动估计 运动补偿运动补偿 整数变换整数变换量化量化熵编码熵编码pic2 运动估计运动估计 运动补偿运动补偿 整数变换整数变换量化量化熵编码熵编码pic3 运动估计运动估计 运动补偿运动补偿 整数变换整数变换量化量化熵编码熵编码pic4 运动估计运动估计 运动补偿运动补偿 整数变换整数变换量化量化熵编码熵编码pic5 图2-1 h.264任务并行编码 fig. 2-1 task parallelism for h.264 encoding 另外还可以通过数据并行来实现h.264的并行编码算法，数据并行指的是将 要编码的数据划分为多个子数据块，每个子数据块分配给一个独立的编码线程， 只要各个数据块之间相互独立，那么多个编码器同时运行编码，达到并行处理 的目的。从理论上来说，任务并行和数据并行都能够实现并行加速，但是数据 并行更适用于h.264编码，主要有下面几个原因： 1 数据相关性。 我们知道， 要保持流水线的效率， 必须使得流水线尽量 “充满” ， 即尽量减少前后的相关性。而影响流水线效率的主要有三种相关性：结构相 关性、控制相关性、数据相关性4。假设并行运算平台的运算单元充足，那 么每个子线程都可以分配到一个独立的运算单元，子线程之间就不存在结构 相关性，而且每个编码步骤之间都是相互独立的（例如运动估计和整数变换 上海交通大学硕士学位论文 17 就是两个独立的过程），因而也不存在控制相关性。但是数据相关性却避免 不了，考虑图2-1中pic2以pic1作为参考帧的情形：当pic2作运动估计时需要 恢复出pic1，但是这个时候pic1还在作运动补偿，为了能正确编码，pic2不 得不等待pic1量化、反量化、反变换一直到重建完成，因此流水线很难“充 满”， 这样会导致流水线的效率低下。 相反通过数据并行， 可以通过gop、sli