（信号与信息处理专业论文）avs视频编码并行算法的研究与实现.pdf

摘要 摘要 由中国数字音视频编码技术标准工作组制定的新一代视频编码国家标准a v s ( a u d i oa n dv i d e oc o d i n gs t a n d a r d ) ，因其具有很高的编解码性能，比h 2 6 4 要低 的复杂度，以及专利授权费用低等优点，越来越得到广泛的应用和学术研究。但 是由于a v s 采用了最新的视频编码技术，使得编码速度较上一代视频编码标准要 低很多。目前，随着多核处理器的普及，利用多核处理器进行多线程并行编码将 会有效的提高编码速度。而o p e n m p 作为一个面向共享存储多处理器系统的多线 程编程标准，为程序员编写多线程应用程序提供了一个简单而高效应用程序编程 接口。 为提高a v s 视频编码速度，本文在深入了解并行计算理论、a v s 编码标准和 o p e n m p 多线程编程标准的基础上，主要完成了3 方面的工作： 首先使用o p e n m p 在a v s 编码器官方参考模型r m 6 2 f 上完成了g o p 级、s l i c e 级和帧级并行编码算法。这几种算法都在i n t e l 四核处理器平台上进行了测试并给 出了线程数与加速比、p s n r 和码率的关系。实验结果表明，并行算法对a v s 编 码速度的提高非常明显，不过它们还是有各自的缺点。 其次针对帧级并行算法扩展性不够和负载不均衡的缺点，提出了一种基于任 务队列模型的帧级并行编码算法。实验结果证明，此算法在四核平台上的加速比 最高能达到3 9 x ，在信噪比和码率保持不变的基础上，提高了编码速度和c p u 利 用率，有效改善帧级并行算法的不足。 最后，为了进一步提高编码速度，本文利用了i n t e l 多媒体指令集s s e 2 和s s e 4 中的视频编码加速指令，分别实现了a v s 视频编码的s i m d 并行优化，并结合基 于任务队列模型的帧级并行算法在i n t e l 四核处理器平台上进行了测试。实验表明， i n t e l 多媒体指令集对a v s 视频编码速度的提升是非常显著的，尤其是最新的s s e 4 ， 与基于任务队列的帧级并行算法结合，加速比最高能达到1 4 8 x 。 关键词：a v s ，o p e n m p ，并行编码，加速比 a bs t r a c t t h en e w g e n e r a t i o nv i d e oc o d i n gs t a n d a r da v s ( a u d i oa n dv i d e oc o d i n gs t a n d a r d ) w h i c hw a sp r o p o s e db y d i g i t a la u d i ov i d e oc o d i n gs t a n d a r dw o r k i n gg r o u p ”，i s b e i n gm o r ea n dm o r ee x t e n s i v e l ya p p l i e da n dr e s e a r c h e di nt h ef i l e do fi n d u s t r ya n d a c a d e m i cb e c a u s eo ft h ea d v a n t a g e ss u c ha s ：h i g hp e r f o r m a n c e ，l o wc o m p u t a t i o n a l c o m p l e x i t y , a n dl o wl i c e n s i n gc o s t ，e r e u s i n gt h el a t e s tv i d e oc o d i n gt e c h n o l o g y , t h e e n c o d i n gs p e e do fa v si sm u c hl o w e rt h a nt h ep r e v i o u sg e n e r a t i o nv i d e oc o d i n g s t a n d a r d n o w , w i t ht h ep o p u l a r i t yo fm u l t i c o r ep r o c e s s o r s ，m u l t i t h r e a d e dp a r a l l e l p r o g r a m sw i l le f f e c t i v e l yi m p r o v et h ee n c o d i n gs p e e d o p e n m pi s am u l t i t h r e a d p r o g r a m m i n gs t a n d a r df o rs h a r e dm e m o r ym u l t i p r o c e s s o rs y s t e m ，a n dp r o v i d e sa s i m p l e a n de f f i c i e n tm u l t i t h r e a d e da p p l i c a t i o np r o g r a m m i n gi n t e r f a c ef o rp r o g r a m m e r t oi m p r o v et h ea v se n c o d i n gs p e e d ，p a r a l l e lc o m p u t i n gt h e o r y , a v sc o d i n g s t a n d a r da n do p e n m pm u l t i t h r e a d e dp r o g r a m m i n gs t a n d a r da r ed e s c r i b e d ，a n dt h r e e t a s k sh a v e b e e nc o m p l e t e d ： f i r s t l y , u s i n go p e n m e , t h ep a r a l l de n c o d i n ga l g o r i t h m si n c l u d i n gg o p - l e v e l ， s l i c e l e v e l ，f r a m e l e v e la r er e s e a r c h e da n dr e a l i z e d ，b a s e do nt h er e f e r e n c em o d e l r m 6 2 fo fa v se n c o d e r t h e s ep a r a l l e le n c o d i n ga l g o r i t h m sh a v eb e e nt e s t e do ni n t e l q u a d - c o r ep r o c e s s o rp l a t f o r m ，a n dg i v e nt h er e l a t i o n s h i pb e t w e e nt h en u m b e ro ft h r e a d s a n ds p e e d u p ，p s n ra n db i tr a t e e x p e r i m e n t a lr e s u l t ss h o wt h a t ，p a r a l l e la l g o r i t h m sc a n i m p r o v ee n c o d i n gs p e e ds i g n i f i a n t l yc o m p a r e dw i t ho r i g i n a ls e r i a la l g o r i t h m ，b u tt 1 1 e y s t i l lh a v et h e i ro w n s h o r t c o m i n g s s e c o n d l y , af l a m e - l e v e le n c o d i n ga l g o r i t h mb a s e do nt a s kq u e u i n gm o d e li s p r e s e n t e dt oo v e r c o m et h ef l a m e - l e v e l ss h o r t c o m i n g si ns c a l a b i l i t ya n dl o a db a l a n c i n g e x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h es p e e d u po ft h i sa l g o r i t h mc a l lo b t a i n3 9 xo ni n t e l q u a d c o r ep r o c e s s o rp l a t f o r m t h i sp a r a l l e le n c o d i n ga l g o r i t h mc a ni m p r o v ee n c o d i n g s p e e da n dc p u u t i l i z a t i o ng r e a t l y , a tt h es a m et i m es n ra n db i tr a t er e m a i nc o m p l e t e l y u n c h a n g e d f i n a l l y , i no r d e rt of t n t h e ri m p r o v et h ee n c o d i n gs p e e d ，t h i st h e s i sr e a l i z e ss i m d p a r a l l e lo p t i m i z a t i o no fa v sv i d e oc o d i n g ，u s i n gi n t e lm u l t i m e d i ai n s t r u c t i o ns e ts s e 2 a n ds s e 4 e x p e r i m e n t a lr e s u l t so ni n t e lq u a d c o r ep r o c e s s o rp l a t f o r ms h o wt h a t ，a f t e r i n t e lm u l t i m e d i ai n s t r u c t i o ns e t o p t i m i z a t i o n , a v sv i d e oe n c o d i n gs p e e di n c r e a s e s i g n i f i a n t l y e s p e c i a l l y , s s e 4o p t i m i z a t i o nc a nm a k e t h es p e e d u pu pt o1 4 8 x ，c o m b i n e d w i t ht h ef r a m e l e v e le n c o d i n ga l g o r i t h mb a s e do nt a s kq u e u i n gm o d e l k e y w o r d s ：a v s ，o p e n m p , p a r a l l e le n c o d i n g ，s p e e d u p m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：翻垒芝 日期：7 菇年广月7 口日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) r 签名：毖j 垒缸 导师签名： 日期口 一 第一章绪论 1 1 视频编码标准发展概况 第一章绪论 目前，国际上主流的视频编解码标准主要有两个：m p e g x 和h 2 6 x 系列，分 别由i s o i e c 的动态图像专家组( m p e g ) 和i t u 。t 的视频编码专家组( v c e g ) 负 主 贝o 1 9 9 0 年完成的h 2 6 1 标准，是第一个可以实际运用的数字视频编解码标准， 主要用于实现电视电话和电视会议。h 2 6 1 使用了混合编码框架，包括了基于运动 补偿的帧间预测，基于离散余弦变换的空域变换编码，量化，z i g - z a g 扫描和熵编 码。h 2 6 1 的制定非常优秀，因为在此之后的视频编码国际标准，大多是与h 2 6 1 类似的编码框架。 1 9 9 0 年，m p e g 1 视频编码标准制定结束，这个是m p e g 组织制定的首个音 视频编解码标准。1 9 9 2 年，m p e g 1 正式被i s o 接纳成为音视频编解码国际标准。 m p e g 1 也采用了基于块的运动补偿、离散余弦变换、量化等技术。 1 9 9 4 年i s o i e c 发布了m p e g 2 ( 即i t u t 的h 2 6 2 ) 音视频编解码国际标准， 它是在m p e g 1 的基础上改进的，一般用于电视广播、d v d 、h d t v 等。 1 9 9 5 年，u 1 定义了用于视频会议的新标准h 2 6 3 ，它可以替代之前的h 2 6 1 标准。1 9 9 8 年i u t - t 又定义了h 2 6 3 + ，它是h 2 6 3 第2 版，又提升了编解码性 能。 m p e g 4 于1 9 9 8 年1 1 月公布。它主要用在互联网流媒体、光盘分发、视频 电话，以及电视广播等领域。m p e g 4 包含了m p e g 1 及m p e g 2 的大多数功能 及其他一些最新技术，还支持虚拟现实模型语言( v r _ m lf o rv i r t u a lr e a l i t y m o d e l i n gl a n g u a g e ) ，面向对象的合成文件，和数字版权管理( d r a m ) 等。 2 0 0 3 年3 月r r u - t 和i s o i e c 正式发布了h 2 6 4 视频编解码标准，h 2 6 4 也 作为m p e g 4p a r t1 0 收入到m p e g 标准中。相比早期的视频编码标准，h 2 6 4 加 入了非常多的最新技术，包含4 4 整数余弦变换、六抽头的环路滤波器、1 4 象 素精度的运动估计、可以使用最多3 2 个参考帧的运动补偿、变块尺寸运动补偿、 基于上下文的二元算术编码( c a b a c ) 、基于上下文的变长编码( c a v l c ) 和灵 活的宏瑰排列模式等。这些技术产生了很高的编码压缩比，但也极大提升了实现 电子科技大学硕士学位论文 的复杂性。 2 0 0 6 年2 月，a v s ( a u d i ov i d e oc o d i n gs t a n d a r d ) 的第二部分，即信息技术先 进音视频编码第2 部分：视频( g b t2 0 0 9 0 2 2 0 0 6 ) 【1 】被国家标准化管理委员会 正式批准为国家标准，标志着我国建设自主知识产权的音视频编解码标准进入一 个全新的时期。 2 0 0 7 年5 月，a v s 成为p t v 的四个国际标准之一，这对a v s 的国际化发展 具有重要的意义。 a v s 是信息技术先进音视频编码系列标准的简称，它包含系统部分、视 频部分、音频部分、数字版权管理等技术标准和一致性测试等支撑标准。a v s 视 频编解码标准与h 2 6 4 类似，都包含帧内、帧间预测、整数余弦变换，量化、熵 编码、去块效应滤波等技术模块。 与h 2 6 4 相比，a v s 具有以下优点【2 】： 第一，编码效率很高，是m p e g 2 的2 倍以上，与h 2 6 4 差不多。 第二，算法复杂度低，软硬件的实现成本要比h 2 6 4 低。 第三，具有自主知识产权，专利授权模式简单，而且专利费用要比h 2 6 4 低 很多。 a v s 因其具有的这些优势，同时作为我国自主研发的音视频编解码领域的国 家标准，具有很宽阔的研究空间和市场前景。 1 2 微处理器的发展 随着1 9 7 1 年世界上第一款微处理器i n t d4 0 0 4 面世以来，按照摩尔定律的预测， 处理器集成晶体管数量越来越多，主频越来越高，性能也越来越强大。 一直到2 1 世纪，由于半导体工艺的限制，处理器的频率已经很难往上提升了， 摩尔定律就显示出了它的局限性。比如i n t d 公司的p e n f i u m4 处理器最高频率已经 接近4 g h z ，频率再往上提高，对半导体工艺也有极为严格的要求，同时主频的提 高也带来了功耗的提高。 此时，多核处理器的概念被提出，多核就是指在一颗处理器中集成了多个完 整的计算核心，这个计算核心就是内核。每个内核有单独的控制单元、逻辑单元、 运算单元、中断控制器、高速缓存等。 多核处理器的发展最早是从m m 开始的。2 0 0 1 年，i b m 将两个6 4 位的p o w e r p c 处理器内核集成在同一颗芯片上并命名为p 0 w e r4 ，这就是首个多核处理器。 2 第一章绪论 而将多核处理器引入到桌面，是从i n t e l 和a m d 正式发布多核架构处理器开始的。 2 0 0 5 年第二季度，英特尔推出p e n t i u m 双核处理器，几个星期之后，a m d 也 推出了a t h l o n6 4x 2 双核系列产品。再接再厉，2 0 0 6 年英特尔又推出新一代双核 酷睿2 处理器。酷睿2 处理器的为6 5 n m 或4 5 n m 制造，单芯片包含2 9 1 亿个晶体 管，功耗与前一代相比降低4 0 。凭借着优秀的性能和较低的功耗，酷睿2 双核 处理器迅速的普及开了。 继双核之后，i n t e l 又在2 0 0 6 年1 1 月抢先推出4 核处理器，a m d 也推出了代 号为巴塞罗那的4 核处理器。 2 0 0 8 年9 月，i n t e l 发布了首款六核处理器产品_ x e o n ( 至强) x 7 4 6 0 。 今年，i n t e l 与a m d 这两大处理器厂商将发布桌面级的六核处理器，把处理器 发展到一个新的高度。 与单核处理器相比，多核处理器最大的优势就是可以利用多线程并行处理任 务，大大提高了任务处理的效率。除此之外，多核处理器还有控制逻辑简单、高 主频、低通信延迟、低功耗、设计和验证周期短等优点。 1 3 并行理论简介 1 3 1 并行计算机体系结构与分类方法 在计算机内部，从硬件的角度看，一个程序的执行分为取指令、取数据和执 行指令，所以处理器主要是处理指令流和数据流这两部分，所有的计算机系统都 可以根据其处理指令和数据的方法来分类。这种分类方法就是众所周知的f l y r m 分类法【3 1 ，它是f l y r m 在1 9 7 2 年提出来的，如图1 - 1 所示。 8 e| ，r ，3 ：， p：v 。一。r “一? j 一舻 “ ， “ 多指令单数据流( m i s d )多指令多数据流( m i m d ) 亡 箍， v 。 。 i 单指令单数据流( s i s d )单指令多数据流( s i m d ) ， ， p 十 ， ， 一 ：。 ： 纭，氯，：j 。+ j 毫，：它氐 f ，_ 。，。硝， ：， ? 。 避 、：。? 峨，j ：j“，：。，。氆 数据流i _ _ _ _ _ l _ _ 图1 - 1f l y m a 分类法 3 电子科技大学硕士学位论文 f l y n n 根据不同的指令流一数据流组织方式把计算机系统分为以下4 类： 1 单指令单数据流( s i s d ) ：s i s d 就是传统的串行计算机，所有的指令都是 串行执行的，每个时钟周期内也只能处理一个数据流。 2 多指令单数据流( m i s d ) ：这种计算机系统采用多个指令流在同一时刻对 一个数据进行计算，它虽然是多个指令并发执行，但是由于数据流的限制，实际 效率太低，一般只是作为一种理论模型出现。 3 单指令多数据流( s i m ) ：这种计算机系统在执行一个指令流的同时可以 处理多个数据流。曾经在很长一段时间内成为超级并行计算机主流的向量计算机， 除了标量处理单元之外，最重要的就是具有进行向量计算的硬件单元。在执行向 量操作时，一条指令可以对多个数据同时进行运算，这就是单指令多数据流。如 今，几乎所有的计算机都采用了s i m d 技术。例如英特尔处理器中的m m x 、s s e ( s t r e a m i n gs i m de x t e n s i o n s ) 、s s e 2 、s s e 3 和s s e 4 扩展指令集【4 】。这些指令集 都有专用的浮点寄存器用于存储多个数据单元，通过这些寄存器，单个指令就能 对多个数据同时进行计算。s i m d 技术在音视频处理中非常有效，本文将在第六章 介绍在视频编码优化中使用s i m d 技术。 4 多指令多数据流( m i m d ) ：这种计算机系统能够同时执行多个指令流，而 每个指令流又可以对多个数据流进行计算。m i m d 可以说是目前应用最广泛的平 台了，现在所有的多核处理器都可以看做是m i m d ，例如i n t e lc o r e 2d u o 双核处 理器和i n t e lc o r e 2q u a d 四核处理器。 现代，m i m d 类并行计算机又主要分为以下几种【5 】： 共享存储对称多处理机( s m p ) ：这种结构的多处理机系统使用单一编址空间， 在整个主存储器系统中的每一个单元有一个唯一的地址，用此地址每个处理器就 可以访问该内存单元。系统中只有一个o s 驻留在共存储器中，它可以根据各处理 器的负载情况动态的在多个处理器上调度进程。另外，s m p 的每个处理器都有片 上高速缓存c a c h e 。共享存储对称多处理机支持消息传递和共享存储并行程序设 计。 分布共享存储多处理机( d s m ) ：在这种系统中，存储器物理地分布在每个处 理器中，但每个处理器使用单的存储器地址空间对整个存储器进行访问。当一 个处理器要访问的单元不在本地存储器中时，必须使用消息传递的方法在处理器 和其他地方的存储器进行数据交换。此系统支持消息传递和共享存储并行程序设 计。 大规模并行处理机( m p p ) ：这种结构是由很多个节点组成的大规模并行计算 4 第一章绪论 机系统，它通过互联网络连接多台完整的计算机，每台计算机就是一个节点。其 中每台计算机有一个处理器和本地主存储器组成，其他处理器不可访问该本地的 主存储器。系统中的互联网络是供处理器间传递消息的。这种结构具有很好的可 扩展性和低廉的成本。系统的各个节点拥有不同的操作系统，各个节点的局部存 储模块相互独立，不存在全局内存的统一硬件编制。大规模并行处理机支持消息 传递和高性能f o r t r a n 并行程序设计。 机群( c l u s t e r ) ：机群没有明确的定义，一般可以看做是由一定数量的的计算 机构建在局域网环境中的并行系统，比如以太网，采用星型连接，但是网络传输 较慢【6 1 。由于成本低，性能高，这种系统在许多研究单位和高等院校很受欢迎，特 别是u n i x 和l i n u x 操作系统的发展，更促进了机群的发展。 在1 2 节中介绍的多核处理器系统即为共享存储对称多处理机( s m p ) 。在多 核处理器系统中，每个核心都共享一个主存储器，整个主存储器中的单元只有唯 一的地址。同时，每个核心又有自己独立的一级高速缓存，二级高速缓存和三级 高速缓存可能共享也可能独立。 1 3 2 并行计算 并行计算是相对于串行计算来说的，并行就是同时做多件事情。程序设计人 员如果想使用并行计算解决问题，首先应该考虑的就是如何对一个问题进行分解， 即划分阴。 划分是所有并行程序设计的基础，对于现在的所有的并行程序来说，划分主 要有三种方法【3 】： 1 任务分解： 把一个任务分成多个子任务的的过程称为任务分解。任务分解是实现并行的 一种简单方法。根据这种方法，可以将一个大的任务分解成数个子任务，如果这 些子任务中有可以同时执行的两个任务，就可以将这两者并发执行。 例如最经典的华罗庚先生在1 9 6 4 年写统筹方法平话中的“烧水泡茶”。 “烧水泡茶”有五道工序：烧开水、洗茶壶、洗茶杯、拿茶叶、泡茶。这五 道工序就是五个子任务。按照传统的串行程序设计方法可以这样做，先洗茶壶、 洗茶杯和拿茶叶再烧开水，最后泡茶；也可以先烧开水，再洗茶壶、洗茶杯和拿 茶叶，最后泡茶。如果使用并行程序设计思想，我们可以在烧开水的同时洗茶壶、 洗茶杯和拿茶叶，最后泡茶。因为烧开水和另外几个是相互独立的，就可以并行 5 电子科技大学硕士学位论文 执行。很明显，最后一种并行化方法的效率最高。 2 数据分解： 数据分解也称为数据并行，是将一个任务所要处理的大量数据分解成几个部 分，每个部分分别交给不同的处理器进行处理。许多年来，这一直都是超级向量 计算机最擅长的领域。一般来说，能够按照数据分解方法进行分解的应用程序都 包括多个线程，每个线程针对不同的数据进行相同的操作。例如，一个简单的数 学问题，求1 + 2 + + 1 0 0 的和。对于这个问题，使用数据分解可以采用两个线程来 解决，每个线程处理一半的数据，即一个线程求1 + 2 + + 4 9 的和，另一个线程求 剩余数据的和。这种方法显然比传统串行算法效率高。 另外，数据分解在图像处理、多媒体应用和数字信号处理领域也有广泛的应 用。 3 数据流分解： 在很多时候，当分解一个需要解决的问题时，关键不在于应该用什么任务来 完成这个工作，而在于数据在这些任务之间是如何流动的【3 1 。这种时候就需要采用 数据流分解方式，根据任务之间的数据流关系对问题进行分解。 生产者消费者是一个典型的与数据流有关的问题。生产者的输出是消费者的 输入，把生产者和消费者看成是两个任务，这两个任务分为不同的线程并行运行， 那么消费者任务必须要等待生产者任务完成之后才能开始。看起来这种情况只能 串行处理无法并行化，不过流水线模式可以解决这个问题。 现代计算机系统在处理器执行指令时大多采用了流水线。流水线，即管线， 意思是指计算机使用多个步骤来处理一条指令，每个步骤使用一个硬件处理单元 来执行，这样可以并行处理，从而提高指令执行速度。如图1 2 所示。 时间方向_ i _ _ 圜1 圈2 圆3 圃 取指令f 指令| | 指令ii 指令| | 指令4i 矗o 二。：二= 二j e ；二。二立j 毫童_ 匕生。一 分析 执行 圆圆囹 匿翮陌砑 睦：。j 目匕：。：。：翻 图1 - 2 指令流水线 取指令、分析和执行这三部分是分开的，由特定的硬件负责。取指令硬件完 成取指工作后，指令交由分析硬件，这时候取指令部件就可以继续取下一条指令， 6 第一章绪论 同时分析部件分析指令。从图上可以看出，在同一时刻，取指令、分析指令和执 行指令可以同时执行，实现了并行化处理，很大程度上提高了计算效率。 从算法设计和程序开发的角度来看，并行计算可以分为任务并行和数据并行。 运用划分问题的三种方法，使程序实现任务并行计算或者是数据并行计算，这将 大大提高问题解决的效率。在本文的第三章将讨论a v s 视频编码的并行化。 1 3 3 并行算法性能衡量标准 对于一个并行算法，用户往往非常想知道它的性能到底如何。加速比【7 】 ( s p e e d u p ) 就是衡量并行算法性能的一个重要指标，能够准确描述对程序并行化 之后所获得的性能收益。s 代表加速比，p 为处理器或线程个数，加速比公式为： s ( p ) ：墅翼冀燮( 1 - 1 )、， - = - 州 并行算法的执行时间 7 理论上加速比的最大值等于处理器或线程个数，这时称为线性加速比( l i n e a r s p e e d u p ) 。不过一般是很难达到线性加速比的，因为要考虑到各个并行线程或处 理器之间通信消耗的时间。 效率( e f f i c i e n c y ) 是另外一个衡量并行算法性能的指标，它表示处理器在进 行有用计算的时间比，公式为： e ：五錾型冀掣k ( 1 - 2 ) 一 并行算法执行时间x 处理器个数 7 也可以写成：e ：璺：丛1 0 0 ( 1 3 ) p e 的值是一个百分数，如果e = 1 0 0 ，代表处理器的全部时间都用来进行计 算，这个时候加速比等于处理器或线程个数。 在实际的计算系统中，效率不可能达到1 0 0 ，而影响并行算法性能的主要因 素有以下几种： ( 1 ) 程序中串行部分所占据的比例。 ( 2 ) 处理器或线程间通信和同步的代价。 ( 3 ) 负载的不平衡。 ( 4 ) 资源冲突。 ( 5 ) 并行算法的有效性。 7 电子科技大学硕士学位论文 1 3 3 1a m d a hl 定律 a m d a h l 定律的基本出发点，是由于在大多数科学计算中，对实时性要求很高， 而负载是不变的，所以在固定的负载下，可以通过增加处理器的数目来提高计算 速度。因为这个，a m d a h l 在1 9 6 7 年提出了固定负载下的加速比公式【8 】： 跏，2 箍2 砸1 c ， n ，z 假设整个负载为w ，其中w s 为只能串行执行的部分，w p 为可以并行执行的 部分，而f 表示串行执行部分占整个负载的比例，即f = w s w ，所以1 一f 表示并 行部分的比例。n 为处理器个数。 当n - - - - 0 0 无穷大的时候，加速比s = 1 f ，所以，a m d a h l 定律假设处理器的 数量可以无限制的增加，但是这些无限的处理器却不能带来性能上的无限增长， 程序的性能总有一个上限，就是1 f 比如一个程序有2 0 的部分是串行执行的， 当我们无限增加处理器的个数时，最终加速比所能达到的上限也只有5 。在历史上， 这种瓶颈影响了大规模并行计算机系统的发展。 _ u 删 r - r - f 处理器数目 图1 - 3a m d a h l 加速比模型 1 3 3 2g u s t a f s o n 定律 a m d a h l 定律揭示了加速比、串行部分的比例和处理器数量三者之间的关系， 同时这也是一个悲观的定律，根据该定律，无论如何提高处理器数量，计算速度 都有一个极限。其实，a m d a h l 定律有几个假设条件： ( 1 ) 最优串行算法的性能受限于处理器的资源。 ( 2 ) 问题的最佳解决方法是串行算法。 ( 3 ) 在处理器数量增加的时候，总负载即问题的规模并没有发生变化。 上面的每个假设都是有缺陷的，其中第三个假设是a m d a h l 定律的最大缺陷， 第一章绪论 对此g u s t a f s o n 提出了新的观点：在并行机实际使用的过程中，通常是处理器的个 数越多，在一定时间内可以解决的问题规模就越大【6 】。也就是说，问题的规模和处 理器的个数是相关的。g u s t a f s o n 还认为当问题规模扩大后，串行部分的执行时间 还是不变的。另外，当问题的规模增加后，我们可以使用更多的处理器在同样的 时间内完成计算。所以g u s t a f s o n 定律假设并行程序中并行单元计算时间是固定的， 当处理器的个数为1 1 时，并行计算时间t p = s - t - p = 1 ，其中s 和p 分别为串行部分 和并行部分执行时间占整个程序执行时间的比例。当使用一个处理器时，串行执 行时间就为t s = s + n p ，那么加速比的公式就是： s ( n ) = j + 印= n + ( 1 - n ) s ( 1 - 5 ) 可以看出，加速比是线性增加的。 例如，假设s = 0 2 ，当n = 2 时，加速比s ( n ) = 1 8 ； 当1 1 = 1 0 时，加速比s ( n ) = 8 2 。 1 3 3 3a m d a h i 定律与g u s t a f s o n 定律的关系 从上面可以看出，a m d a l d 定律与g u s t a f s o n 定律得出了两个相反的结论，好像 是矛盾的。其实，这两个定律是等效的，这个结论被s h i 在1 9 9 6 年证明了 9 1 。 这两个定律的差别主要是由于它们的假设条件不同造成的。a m d a h l 假设随着 处理器数量增加，问题的规模不变，即串行部分的比值是一个定值。而g u s t a f s o n 则认为随着处理器数量增加，问题的规模也是变大的，串行部分的执行时间则是 不变，因此串行部分所占比值随着问题规模变大而减少。假设t s 为程序中串行部 分的执行时间，t p 为程序中并行部分串行执行时的时间，那么两个定律中串行部 分的比值分别为： a m d a h l 定律：厂2 云杀 g u s t a f s o n 定2 赢 可以得到f 与s 的关系式：厂2 i 写i 石1 而 l 十刀【l jj ，j 将f 带入a m d a h l 定律可以得到： 1 s ( ”) 2 了j 蒜2 n + ( 1 一，1 ) s 可以看到a m d a h l 定律与g u s t a f s o n 定律确实是等价的，但是g u s t a f s o n 定律对 并行计算的未来更加现实和乐观。 9 电子科技大学硕士学位论文 1 4 选题的意义 a v s 作为我国制定的具有自主知识产权的音视频编解码标准，涉及到专利问 题和未来的国家战略，对于我国数字化音视频产业的发展具有重要意义。为了推 广普及a v s ，提高a v s 视频编码器的编码速度，使其更适合实际使用，就具有很 重要的研究意义和很大的应用价值。 目前，随着科技的发展，计算机硬件变得越来越强大，同时微处理器将集成 越来越多的核心，这样也更加方便我们研究在多核处理器平台上的并行计算。a v s 作为一个音视频编解码标准也是非常适合并行计算的，因此将并行计算用于提高 a v s 视频编码器的编码速度是一个很好的研究课题。 1 5 本论文的主要内容 1 5 1 研究内容 为了提高a v s 视频编码器的编码速度，本文首先研究了a v s 的情况和特点， 根据视频编码的特性和多种并行编程语言与接口的特点，找出适合a v s 视频编码 并行化的方法和最合适的并行化语言。然后研究并实现了g o p 级、s l i c e 级、帧级 和基于任务队列模型的帧级并行算法。最后还使用s i m d 技术对a v s 视频编码进 行了c p u 指令级别的并行优化。 本课题主要的工作有： 1 、学习了主要的视频编码标准，了解视频编码的流程和内部技术模块。 2 、熟练掌握工作组提供的参考模型r m 6 2 f , 对视频编码的具体软件程序实现 有了更深入的了解。 3 、研究并行计算理论，掌握多核程序设计技术，主要使用面向共享内存的多 处理器多线程并行编程语言o p e n m p 。 4 、实现了g o p 级、s l i c e 级、帧级并行编码算法。 5 、利用任务队列模型改进帧级并行算法。 6 、使用i n t e l 指令集优化a v s 视频编码 本文所有的算法都是在r m 6 2 f 参考模型和i n t e l 四核处理器平台上研究与实现 的。 1 0 第一章绪论 1 5 2 结构安排 全文共分七章，结构安排如下： 第一章为绪论。介绍视频编码标准和微处理器的发展概况，并对并行理论做 了简介，其中重点介绍了a m d a h l 定律和g u s t a f s o n 定律，这两个定律为a v s 并行 算法的可行性提供了理论上的依据，最后点明了选题的意义和研究内容等。 第二章介绍了a v s 标准的历史与发展，并给出了a v s 视频编码器的整体框架， 最后对a v s 编码器中的几个重要的关键技术做了详细的说明。了解这些技术细节 对之后并行算法的实现是非常重要的。 第三章首先给出a v s 编码并行化的两种模式，重点分析了数据并行的几种方 法，包括g o p 级、s l i c e 级和帧级并行编码算法。之后介绍了几种多线程并行编程 语言和接口，分析它们的优缺点，确定了本文所要用的多线程并行编程语言和接 口为o p e n m e 。 第四章使用o p e n m p 在a v s 官方参考模型r m 6 2 f 上实现了g o p 级、s l i c e 级 和帧级并行编码算法，并在i n t e l 四核处理器平台上测试，测试结果揭示了线程数、 分辨率、加速比与率失真之间的关系。结果表明并行算法是确实有效的，对编码 速度的提高很大。 第五章针对帧级并行编码算法的缺点，给出了基于任务队列模型的帧级并行 编码算法。实验证明此优化算法相比之前的帧级并行算法，保持了图像质量和码 流大小与串行算法相同的优点，有效提高了c p u 使用率和加速比。 第六章使用了s i m d 技术优化a v s 视频编码。在前两章中实现的并行算法都 是属于线程级并行，另外我们还可以利用i n t e lc p u 多媒体指令集来实现指令级的 并行。这种指令级的并行优化与线程级的并行优化结合在一起使用。这章分别使 用了s s e 2 和s s e 4 对a v s 编码器中最耗时的运动估计( m e ) 模块进行了优化。 测试结果表明，指令级与线程级并行优化结合能最大程度的提高加速比。 第七章对本文进行了总结和展望。 电子科技大学硕士学位论文 第二章a v s 视频编码标准 a v s 是信息技术先进音视频编码系列标准的简称，是我国具有自主知识 产权的第二代信源编码标准【l 】。它主要由中国数字音视频编码技术标准工作组( 简 称a v s 工作组) 制定的，工作组成员包括国内外从事数字音视频编码技术和产品 研究开发的一百多家机构和企业。a v s 的特点是在同一个编码框架下，针对不同 的应用场合制定不同的压缩标准，从而降低a v s 产品的成本。 a v s 第二部分( a v s l p 2 ) 为a v s 系列标准中最重要的视频部分，2 0 0 6 年成 为国家标准时只有一个基准档次。目前，信息技术先进音视频编码第2 部分： 视频已经完成所有的修订，在基准档次的基础上，扩展为包括加强档次、伸展 档次和移动档次在内的一共四个档次。基准档次主要针对高清晰度数字电视广播 等应用；加强档次主要针对高清电影等应用；伸展档次是全球范围内首个针对视 频监控需求制定的视频编码标准；移动档次主要针对低比特率、低分辨率的移动 流媒体应用【1 0 】。这四个档次涵盖了视频应用的各个领域。 本文主要研究2 0 0 6 版的信息技术先进音视频编码第2 部分：视频( g b t 2 0 0 9 0 2 2 0 0 6 ) 。a v s l p 2 采用了与之前的m p e g 系列标准中类似的技术来提高视 频编码效率，包括帧内预测、帧间预测、变换、量化和熵编码等。 2 1a v s 编码器框架 图2 - 1a v s 编码器框图【2 】 1 2 第二章a v s 视频编码标准 a v s 编码器的系统结构如图2 1 所示。可以看出，a v s 与h 2 6 4 在编码结构 上很像，都是采用了结合预测和变换技术的混合编码框架。图像类型包括i ，p ，b 三种，i 帧只能使用帧内编码模式，p 帧和b 帧可以使用帧间编码模式也可以使用 帧内编码模式，区别在于p 帧是前向预测，b 帧是双向预测。码流结构语法层次 从高到低依次为：序列、图像、条带、宏块、块【1 】。在这点上，a v s 与m p e g 2 比 较类似。在a v s l p 2 中，块的大小为8 8 像素。 当原始的视频信号进入编码器，编码器会根据配置参数进行判断对当前帧是 进行i 帧、p 帧还是b 帧的编码。 如果当前帧是i 帧，则进行帧内编码。帧内编码无需参考其他帧的已编码信息， 只需要当前帧中重构后的宏块信息。当新的一个块进入编码器，它会与经过帧内 预测出来的预测块相减得到残差，残差再经过变换、量化得到量化系数，然后对 系数进行z i g - z a g 扫描得到一维量化系数，在经过熵编码就可以得到已编码的码流。 另外，熵编码之前，已经量化后的信息再经过反量化和反变换等过程，可以重构 这个块，并将它存储在缓存中为后续的图像或块编码做参考。 如果是p 帧，它的编码模式可以有三种：s k i p 模式、帧内模式和帧间模式。 在官方参考模型中，p 帧将遍历这三种模式，计算率失真代价，得到最优的一种编 码模式。对于p 帧来说，他的帧内模式和i 帧一样，帧间模式是基于视频序列时间 上的相关性，当前待编码宏块将参考最近的解码的i 帧或p 帧，得到残差，再经过 变换量化和熵编码得到码流。在a v s 中p 帧的最大参考帧数量为2 。对于p 帧的 s k i p 模式，块编码后的残差为零，只需要传输代表s k i p 模式的信息，运动矢量 可以由预测得出。 a v s 中，b 帧同样有三种编码模式：s k i p 模式、帧内模式和帧间模式。与p 帧不同的是，b 帧的帧间预测是双向的，包括对称模式( s y m m e t r i cm o d e ) 和直接 模式( d i r e c tm o d e )