（计算机应用技术专业论文）h26l视频编码器并行性算法研究与实现.pdf

西南交通大学硕士学位论文第顷捅要if 多媒体视频编码技术是诸多计算机研究领域中发展最为活跃的领域之一，其发展前景也非常好。在众多的视频编码标准中，h 2 6 l 是由i t u 和i s o i e c联合制定的面向无线通信和多播的低码率视频传输标准的最新版本。该标准具有压缩率高、适用范围广等优点。为达到理想的数据压缩率，h 2 6 l 编码器采用了很多新的编码算法，这些算法极大地增加了编码器的运算量。在h 2 6 l 的实际应用中，很多情况都需要进行视频的实时压缩编码，这对编码器的运算性能要求很高。而要实现h 。2 6 l 的实时编码和传输，用单处理器目前还很难达到要求。在高性能并行计算机上进行视频压缩编码具有很大的发展潜力，应用前景很广。目前基于这方面的研究正越来越引起人们的重视，也有了一定的研究成并行资源进行了详细的分析和性能测试，并在此基础上实现了编码的并行计算。本论文主要包含以下内容：( 1 ) 、简要介绍了视频编码的基本方法和h 2 6 l 编码标准的主要特点和新引进的算法：并行计算相关的基本理论和加速性能评测方法。这部分知识是进行本论文研究的基础。( 2 ) 、从并行设计的基本原理出发，结合h 2 6 l 视频编码的特点，针对测试模型t m l 8 0 提出了几种可行的并行实现方法。并根据通用的加速性能评估方式对它们进行性能分析和测试。( 3 ) 、根据以上提出的几种并行实现方式和性能测试结果，选择其中两种方法，用m p i 进行并行实现，并对在曙光一2 0 0 0 上进行的仿真试验结果进行了分析和对比。分析和试验表明，通过并行处理的方式可以很大程度的提高h 2 6 l 视频编码的处理速度，使得该标准可以更好的适用于多种不同的视频应用环境。关键词：h 2 6 l ；视频编码；并行计算；并行视频处理、夕多违莩钵簸籴j西南交通大学硕士学位论文第ll 页a b s t r a c tm u l t i m e d i av i d e oc o d i n gi so n eo ft h em o s ta c t i v ef i e l d si nc o m p u t e ra p p l i c a t i o n ，a n di ti sd e t e r m i n e dt oh a v eb e t t e rf u t u r e sf o rt h ep o p u l a r i t yo fv i d e oe n t e r t a i n m e n t h 2 6 li sav i d e oc o d i n gs t a n d a r dp r o p o s e db yi t ua n di s o i e c ，i ti st h ee m e r g i n gs t a n d a r df a rv i d e oc o m m u n i c a t i o na n dm u l t i c a s ti nl o wb i tr a t ec o n d i t i o n s h 2 6 lh a st h ea d v a n t a g e so f h i g hc o m p r e s s i o nr a t e ，g o o da d a p t a t i o na n de t c i no r d e rt og a i ng o o dc o d i n gr e s u l t ，h 2 6 la d o p t sm a n yn e wa l g o r i t h m s ，w h i c hi n c r e a s et h ec o m p u t i n gq u a n t i t yg r e a t l y i nm a n yp r a c t i c a la p p l i c a t i o n so fh 2 6 l ，r e a l t i m ee n c o d i n gi so f t e nr e q u i r e d ，b u tn o w a d a y sr e a l - t i m ec a l lh a r d l yb ea c h i e v e do nas i n g l es t a t e - o f - t h e - a r tc o m p u t e r p r o c e s s i n gv i d e oo nh i g hp e r f o r m a n c ep a r a l l e lc o m p u t e r sh a sg o o dp o t e n t i a la n dw i d ef o r e g r o u n d s t h es t u d i e si nt h i sf i e l da r eg e t t i n gm o r ea n dm o r ep o p u l a ra n ds o m ea c h i e v e m e n t sw e r ec o m eo u t i t so fg r e a ts i g n i f i c a n tt os t u d yt h ep a r a l l e l i s mi nh 2 6 le n c o d e rf o ri t sa d v a n t a g e s t h es t u d yo ft h i sp a p e ri sb a s e do nt h et e s tm o d e ll o n g t e r m8 o ( t m l 8 0 ) o fh 2 6 l i nt h i st h e s i s ，d e t a i l e dp a r a l l e la n a l y s i sa n dp a r a l l e lp e r f o r m a n c et e s t i n gf o rt h ee n c o d e ra r eg i v e n ，a n dp a r a l l e li m p l e m e n t a t i o ni si n c l u d e dw i t hs i m u l a t i o nr e s u l t s t h em a i nc o n t e n t so ft h i st h e s i sa r el i s t e di nt h ef o l l o w i n g ：( 1 ) b a s i cw a y so fv i d e oc o d i n g ，t h em a i nf e a t u r e so fh 2 6 lv i d ee n c o d e r ,p r i m a r yt h e o r i e sa n ds p e e du pp e r f o r m a n c ee v a l u a t i n gm e t h o d so fp a r a l l e ld e s i g na r ei n t r o d u c e db r i e f l y , t h e ya r et h ef o u n d a t i o n so f t h i sp a p e r ( 2 ) b a s e do nt h ep r i m a r yp r i n c i p l ei np a r a l l e lc o m p u t i n g ，m a n yp a r a l l e li m p l e m e n t a t i o nm e t h o d sa r eb r o u g h tf o r w a r dc o n s i d e r i n gt h em a i nf e a t u r e so fh 2 6 l t h ep a r a l l e lp e r f o r m a n c e so ft h e s ei m p l e m e n t a t i o nm e t h o d sa r ea n a l y z e da n dt e s t e da c c o r d i n gt ot h en o r m a lm e t h o d s ( 3 ) a e c o r d i n gt ot h ea n a l y s e sa n dt e s tr e s u l t sa b o v e ，t w op a r a l l e lm e t h o d sa r es e l e c t e da n di m p l e m e n t e db yu s i n gm p i t h es i m u l a t i o nr e s u l t so nd a w n i n g - 2 0 0 0m p pm a c h i n e so f t h et w op a r a l l e lm e t h o d sa r ea n a l y z e da n dc o m p a r e d t h ea n a l y s i sa n ds i m u l a t i o nr e s u l t ss h o wt h a tp a r a l l e lc o m p u t i n gc a ng r e a t l ys p e e du pt h ep r o c e s s i n go fh 2 6 le n c o d e r , a n dm a k ei tp o s s i b l ef o rt h eh 2 6 lt ob eu s e di nm a n yv i d e oc o n d i t i o n s ：堕塑窑望盔堂塑主堂丝笙塞芝! 要第1 章绪论1 1 问题的提出随着多媒体视频应用的广泛普及。实时的视频编码传输近年来已经成为视频发展的一个热点。在视频的实时应用中，一个主要的矛盾是有限的网络带宽资源和视频的大数据量之间的矛盾；因此要想在网络上得到较好的视频，就需要对视频数据进行较好的编码压缩。然而，在获得好的视频编码的同时，也极大的增热了视频编码计算的复杂性，这就引出了另一个矛盾：郧庞大编码计算和有限的计算资源之间的矛盾。例如对h - 2 6 l 编码器丽言，目前在单个的通用串行计算机上就很难达到对视频的实时压缩。视频编码并行处理是提高视频处理速度的一种有效技术，其研究发展水平在业界也很受关注。其原因主要在于两个方面：一是视频并行处理技术的难度较大，这种难度不仅存在于视频并行处理系统的硬件及系统结构本身，而且存在于对视频压缩处理标准及算法的理解和实现，以及实际应用的复杂性和系统价格等方面：二是视频的并行处理技术发展产生的效益将是很大的，其实际的应用系统也将产生很大的经济效益和社会效益。h 2 6 l 是由i t u - t 制定的新一代视频编码标准，子2 0 0 2 年底正式命名为h 2 6 4 ，并且作为i t u t 和m p e g 联合专家组7 v t ( j o i n tv i d e ot e r m ) 制订的下一代视频编码标准a v c ( a d v a n c e dv i d e oc o d i n g ) 的基础，它具有很多以往同类标准没有的优点，适用范围广泛，发展潜力巨大。但是其编码过程的计算量很大，目前很难在单个串行机上达到实时处理。本论文就是在此背景下通过对h 2 6 l 编码标准进行分析理解，对其编码器进行研究，实现并行处理，加快编码的处理速度，以使该标准能更好她适用于多种环境。1 2 国内外研究现状对视频编码的并行处理并不是一个很新的课题，在最近几年内也有不少的研究成果出现，这些研究基本上都是围绕m p e g 标准而做出的。包括由m i g u e lr i b e i r o 和o li v e rs i n n e n 等人对m p e g 一4 校验模型的并行性的研究和实现【2 】，他们针对视频对象提出了几种任务调度策略并进行试验和分析对比。k es h e n 和l a w r e n c ea r o w e 等人对m p e g l 的并行研究和实现【3 】，该成果主要对视频编码并行i o 进行了研究和探讨，使其在大量的i o 操作中不再成为并行加速的西南交通大学硕士学位论文第2 页瓶颈。在国内，中国科学院计算机应用研究所也对m p e g - 4 的并行性作了一些研究【4 】。对于h 2 6 l 的并行性研究，因其是一个很新的视频编码标准，在本论文的工作开始和进行中。其制订工作还在继续，所以关于h 2 6 l 的并行处理的相关文献或者成果还没有出现。本论文所作的工作就是在该领域的个尝试。1 3 本文研究的主要内容、目标与方法本论文从并行处理的一般性原理出发，结合多媒体视频压缩编码的特点，对h ，2 6 l 视频编码器测试模型t m l 8 0 进行并行分折、测试和实现，以期能够利用这种方式加快编码器的处理速度，达到实时视频处理的目的，为今后对h 2 6 l进行并行处理的研究和软硬件开发打下基础。本论文的主要内容包括对h 2 6 l视频编码标准的介绍和分析、并行处理的相关知识，对编码器测试模型t m l 8 0的并行性进行分析和钡试，以及并行实现和仿真结果分析等。要塞奎堕盔耋堕主兰焦燕塞墼墨第2 章视频编码概述2 1 视频编码的必要性当今。人们对通过计算机来获取和处理信息的依赖性越来越大。而通过数字化的媒体信息也越来越多，这些数字化信息在具有很多优越性的同时，也存在一个很大的问题，那就是其数据量的急剧增加对它的存贮和传输带来的极大不便。数字化规频数据的海量性与当今的计算机硬件技术所能提供的网络传输带宽和存储资源之间都有很大的差距：因而对视频信息的传输和存储造成了很大的困难，成为了妨碍人们快速有效的利用媒体信息的一个瓶颈问题。而对于这类问题的解决，只是靠单纯的扩大存储器容量，增大通信干线的传输速率的办法是不现实的，进行数据压缩处理才是一个切实可行的有效方法。研究发现，视频图像的表示中存在大量的冗余信息。而通过去除冗余信息就可以极大的减少原始视频图像的数据量，从而达到解决海量数据问题的目的，因此对视频图像进行压缩处理是非常必要和可行的。视频图像的冗余信息主要包括以下几个方面；空间冗余：空间冗余主要由图像色彩的连贯性产生。比如一幅图像记录了画面上可见的物体的颜色，而同一景物在颜色的分布上往往都具有很大的空间连贯性；但是基于离散采样而获得的图像数据通常是没有充分的利用物体表蕊颜色的这种空间连贯性而对数据量进行压缩处理。例如：图像中有块颜色很均匀的部分，在此区域中所有的像素点的光强和色彩以及饱和度都是一样的。则此图像中，就可以只用一个像素值通过一定的手段来有效的表示周围的像素值。这种冗余是由在弱一图像中画面前空间稻似性形成的，所以称为空间冗余。时间冗余；这是动态视频图像通常包含的冗余信息。动态视频图像通常为位于一时间轴区间内的一系列的连续画面，其中相连的一帧或几帧画面往往会包含同样的背景或物体。他们之间的差别只是位置上有所不同；所以后一帧图像与它的前帧图像有许多共同的地方，而这种共同性是由于相邻帧记录了相邻时刻的同场景画面，故称为时间冗余。视觉冗余：事实和研究表明，人们对于图像场的敏感性是非均匀和非线性的。比如：视觉系统对图像的亮度和色彩度的敏感性相差很大，对亮度的敏感度远远大于对色度的敏感度。由于人眼的辨别能力与物体周围的背景亮度成反西南交通大学硕士学位论文鼾页比，在亮度的增加过程中，人们的视觉系统对量化误差的敏感度降低。但是，摄影机在记录原始的图像数据的时候。通常都是假定视觉系统对图像的敏感程度是均匀的和线性的。对于人眼的敏感区和不敏感区都同等对待，从而导致了视觉冗余。图像区域的相同性冗余：这种冗余是指在图像的两个或者多个区域对应的像素值相同或者相近，而产生的数据重复性冗余。另外，根据不同的情况，在原始的视频图像中还可能存在别的冗余，比如结构冗余、知识冗余、纹理统计冗余等。对于不同的冗余信息，可以通过不同的方法来达到较好的冗余去除效果。从以上的讨论可以看出，对于视频的传输和存储来说，我们面临的最大困难就是其数据量的处理问题。而数字视频图像数据通常都具有以下的特征：1 ，数据量庞大，使得视频数据的处理变得困难；2 ，数据中存在大量的冗余信息。而这些冗余信息都可以通过一定的编码方式去除。这两个特征为视频压缩编码处理提供了必要性和可能性。庞大的视频数据经过压缩处理后就可以只对编码后的少量的数据进行存储或传输，在视频的接收端只要对收到的数据进行解码就可以得到原始视频图像了。这样，当前的网络资源和存储资源就可以在一定的程度上满足用户的需求。因此，只要在编码过程中采用适当的方式来去掉其视频图像的冗余信息，让保存的数据都尽可能的含有最大的信息量。那么视频的数据量就可以大大地减少。2 2 视频编码的基本原理视频编码的基本原理就是采用一系列的变换技术减少视频中的冗余信息，在一定的需求和应用条件下，尽量用最少量的数据来获得最好质量的视频图像。由前面的内容可知，原始视频数据含有不同类型的冗余信息，这些冗余信息包括空间冗余、时间冗余和视觉冗余等。对于空间冗余，可以根据相邻像素间的相似性，由相邻的像素来编码当前像素，这样就可以充分的利用相邻像素之间的相关性而达到消除或者减少其空间冗余的目的；这种消除空间冗余的图像压缩编码方式通常用于静态图像的编码或者动态视频的帧内编码图像中。时间冗余通常都是出现在动态的视频图像中。对于时间冗余信息，我们可以用预测的方式来予以消除。比如在一段动态视频中，有一个物体的作平移运动，他在一系列的动态图像中只是位置发生了变化，在剔的方面基本上没有变化，那么这时我们只器将其在前一帧的信息直接搬迁到其后一帧的相应位置就西南交通大学硕士学位论文簟5 页可以了。这样图像的信息并没有任何的损失，但是在视频的数据表示上面就减少了很多数据量。这毒中利用帧阆预测来消除视频图像时间冗余的方法是动态视频编码的基本方法。视觉冗余的产生主要来源于人眼和机器视频捕获设备之间的差别。机器视频捕获设备对于进入其“视觉”范围的所有图像信息都一视同仁，不存在对那个物体或区域更感兴趣的问题。而人眼是有差别的对图像进行处理，可以只注意其感兴趣的物体或区域。对于视觉冗余的消除，可以通过正交变换将图像从空间域转换到频率域，然后根据人眼对于不同频率的不同敏感程度对其进行不同的处理，从而减少视觉冗余。对于视觉冗余的消除，现在很多的图像压缩编码都用到了，主要的正交变换有离散余弦交换( d c t ) 和小波变换( w a v e l e t )等。视频编码的基本结构可以用图2 - 1 表示如下：蚣鸥牾菇面斗蛎磊鬲n 西蓊i 蓟1 撕蕊渺流【一l ，一【一1 一图2 - 1 视频编码流程示意图其中，图像预处理包括图像的格式转换和图像分割，这一过程首先将获得的视频图像格式转换为亮度、色度分离的分量形式，并根据具体编码和应用情况对色度信息进行适当的简化，再将幅完整的大图像分成多个易于编码的小图像块。预测编码可以是多幅图像间进行的帧间预测，也可以是一幅图像内部的帧内预测，主要用于消除图像的时间冗余和空间冗余。正交变换用来将图像由空间域转换成频率域。它通常与量化一起使用以减少图像的视觉冗余，量化是图像失真的主要来源。熵编码是将量化后的系数按变长编码( v l c ) 方式编成一串码流后输出，这过程可以极大的减少视频图像的信息表示量。编码后的视频数据发送给接收端，接收端在收到数据流后进行解码，然后上屏显示。解码过程基本上就是编码过程的逆过程，就是将编码的图像块经过编码的逆处理后组合成帧完整的图像。另外，从信息论观点来看，图像作为一个信源，描述信源的数据是信息量( 信源熵) 和信息冗余量之和1 7 1 。信息冗余量就包括我们刚讲到的空间冗余、时间冗余、视觉冗余等。可见减少冗余量可以达到减少数据量的目的而不减少信源的信息量，它对于视频图像的质量是无损的。从数学上讲，一可以把图像看作一个多维函数，压缩就是减少描述这个函数的数据量，而其实质是减少其相关性。另外很多情况下。我们都允许视频图像有一定的失真，即允许在一定条件下的图像质量降低。而这并不妨碍视频的实际应用，这样视频数据量的压缩西南交通大学硕士学位论文蕈6 页空间就更大了。西南交通大学硕士学位论文筹1 页第3 章h 2 6 1 视频编码标准3 1 视频编码标准概述数字视频的应用已经或者正在为诸多领域所接受，这些领域包括视频电话、视频会议、数字化视频光盘以及数字电视等。基于数字视频的大量应用，针对不同的应用领域的视频编码标准也就应运而生了，这些视频编码标准为不同的视频产品生产厂商提供一个通用的交互手段，极大的促进了视频应用的发展。最为著名的国际视频标准组织有i t u - t 移i s o t e c ，前者锚定的标准通常被称为建议，冠名h 2 6 x ( 例如h 2 6 1 ，h 2 6 2 ，h 2 6 3 和h 2 6 l 等) ；后者制定的标准被称为m p e g - x ( 例如m p e g ，1 ，m p e g 2 和m p e g 4 等) 。i t u t 的建议标准主要面向实时通信，例如视频电话和视频会议：而m p e g标准主要是面向视频存贮、视频广播等应用领域。大多数情况下这两个标准组织独立制定不同的标准，一个例外就是h 2 6 2 和m p e g 2 是他们联手制定的，属于同一个编码标准。最近，这两个标准组织再度携手在h 2 6 l 的基础上共同致力于m p e g - 4 框架下a v c 的制定，h 2 6 l 最初是由i 下u t 提出来的，后来i s o i e c 也加入了标准的制定。h 2 6 l 能为两个标准组织共同接受的一个主要原因就是它代表了当前视频编码的最高水平，在同等压缩信噪比条件下，其数据量仅为其他压缩标准的4 0 6 0 ，在同等数据蟹情况下，其信噪比可以比其他方法提高1 3 d b 口”，它所采用的很多技术已经成为视频编码标准上的一个里程碑。图3 1 总结了i t u t 组织和i s o i e cm p e g 制定的视频编码标准以及发展历程：图3 - 1 视频编码标准发展历程各个编码标准虽然并不完全一样，但是它们在处理上有很多思想是一致的，主要的共同点有：1 ，图像格式。它们编码的图像格式都是y u v ( 或y c r c b ) ，在编码之前西南交通大学硕士学位论文第8 页需要将获得的其他格式图像转换成n ( 或y c r c b ) 格式。2 ，基于图像块的编码。所有的标准都是基于将一帧图像分成较小的图像块来进行编码，编码的基本单位都是宏块，宏块是由1 6 x1 6 像素缎成的方形区域。m p e g 4 虽然支持基于不规则形状的视频对象编码，但其v o p 的描述仍然是以宏块为基本单位来表示的【2 4 】。3 ，帧问运动预测与运动补偿。各标准减少时间冗余的措施都是进行图像的帧间预测，这一部分的处理是各个标准处理的核心部分，处理措施的好坏直接影响到编码的效率和图像的质量。4 ，正交变换与量化。各标准都是通过正交变换来将图像从空间域向频率域转换，然后通过量化来减少视觉冗余。正交变换通常都采用d c t 变换，有的标准也引入了其它变换方法比如小波变换和整数变换等。5 ，“z ”字形扫描。对量化后的系数进行z i g z a g 扫描，以使获得的编码数据更加具有规律性，通常使用的是单z i g - z a g 扫描，在h 2 6 l 中也出现了双z i g z a g 扫描。6 ，不定长熵编码。图像编码的控制信息、运动向量信息和量化过后的图像系数，各标准都采用不定长熵编码的方法来进行编码。具体的编码方法有通用不定长编码( u v l c ) 和基于内容的二进制自适应算术编码( c a b a c ) 两种，前者几乎在所有的编码标准中采用。而后者只是在h2 6 l 中才引入，作为一个选择模式而存在。以上所举的是对各编码标准都采用的一些技术，对于不同的标准在具体的处理上会有差别，而正是这些处理上所采用的不同技术使得不同的编码标准有不同的编码效率和不同的应用领域。3 2h 2 6 l 视频编码标准h 2 6 l 是i t u t 和i s o i e c 联合制定的一种高效的视频压缩编码标准，它集中了以往标准的优点，吸收了标准制定中积累的经验，并在此基础上采用了很多的新技术和新算法。在与别的视频编码标准相比的基础上，h 2 6 l 具有以下的一些特点：1 ，约5 0 的码率节省。与h 2 6 3v 2 ( h 2 6 3 + ) 或m p e g 4 简单类( s i m p l ep r o f i l e ) 相比，h 2 6 l 在使用与上述编码方法类似的最佳编码器时，最多可节省5 0 的码率1 2 5 】。2 ，高质量的视频。h 2 6 l 在较大范围内的传输码率下都能持续提供高质量的视频，包括在低比特率的情况下提供较高质量的视频。西南交通大学硕士学位论文翦顷3 ，适用予不同延时的网络应用。h 2 6 l 能工作在低延时模式以适应实时通信的应用( 如视频会议) ，同时又能很好地工作在没有延时限制的应用环境，如视频存储和以点播服务为基础的视频流式应用。4 ，较好的差错恢复能力。h 2 6 l 提供包传输网中处理包丢失所需的工具，以及在误码率较高的无线网中处理比特误码的工具。5 ，良好的网络适应能力。h 2 6 l 在系统层面上提出了一个新的概念，在视频编码层( v i d e oc o d i n gl a y e r , v c l ) 和网络适配层( n e t w o r ka d a p t a t i o nl a y e r , n a l ) 之间进行概念性分割，前者是视频内容的核心压缩内容之表述。后者是通过特定类型网络进行数据传输之表述。这样的结构便于信息的封装和对信息进行更好的优先级控制。h 2 6 l 编码器的编码处理结构框图可以表示如图3 2 ：图3 - 2h 2 6 l 编码器结构框图h 。2 6 l 将编码图像分为三种类型：i 帧、p 帧和b 帧，i 帧是独立编码的视频图像，其编码不依赖于前面已经编码的图像数据，也称为帧内编码帧。p 帧和b 帧的编码需要前面已经编码好的图像数据来进行预测，也称为帧间编码帧。用来对编码图像进行预测的图像也称为参考帧，在h 2 6 l 中，只有i 帧和p 帧可以用来作为参考帧对后面编码的图像进行预测。三种类型的图像在编码过程中的参考关系可以用图3 3 表示，图中的箭头表示参考关系，它由参考帧指向编码帧。西南交通大学硕士学位论文第伯页圈3 - 3h 2 6 i 编码图像参考关系为了获得理想的编码效率和较好的视频质量，h 2 6 l 引入了很多的新算法，这些算法包括在编码的各个方面，下面就编码器的结构框图对这些新的算法特点作一简单的介绍。标准规定对于帧内编码和帧闻编码两种编码方式，在编码前都要进行预测以尽最大可能的提高编码效率。对帧内预测和帧间预测，h 2 6 l 与以前的标准相比都有了改进。对于帧内预测，一个宏块可以有两种尺寸的预测方式，即对1 6 个4 4 或者1 个1 6 1 6 的方形块进行像素的帧内预测。通过对不同的像素按照不同的方向进行预测，对每一个不同大小的预测区域又可以划分为不同的帧内预测模式。比如对于4 4 的方形块区域，就有6 种不同的预测方式，对于不同的预测模式，针对不同图像特征的视频图像在预测效果上具有各自的优点。宏块的帧内预测，对每一个4 4 的块，它的预测方式可以用图3 - 4 加以表刁斥：45( a )( b )图3 4 宏块的帧内预测方式图中的a 图显示的是一个4 x 4 块和它周围已编码的像素，其中大写字母表示该块周围已经编码后的像素值，框内的小写字母表示待编码的像素值，预测过程就是由周围已经编码后的像素值来预测框内待编码的像素值。b 图显示的是不同的预测方式，其中只列出了5 种，还有一种是d i r e c t 方式，就是框内的像素均以框外像素的平均值来预测，这种方式对于比较平缓的图像很有效。对西南交通大学硕士学位论文第1 顶图b 中画出的5 种方式，框内的像素就按照划线的方向由框外的对应像素进行预测，例如对方式2 ，像素a 就用来对其正下放的a 、e 、i 、m 等4 个像素进行预测。这几种不同的预测方式对于不同纹理和内容的图像有各自的优点。h 2 6 l 在算法上对于帧间预测也有重大改进。帧间预测用来去除存在于相邻帧相应像块间时间方向的相关性。使得只有相邻帧间两个相应像块的变化部分才需要编码。标准增加了帧间预测的模式，对预测像素的精度也进一步进行了提高，傲到了1 8 像素精度的预测。对于预测模式，可以分为不周彤状和大小的7 种，用图3 5 加以表示：模式1 t1 个1 6模式2 ，2 个8模式3 ，2 个模式4 ，4 个8x 1 6 块1 6 块1 6 8 块8 块田目田模式s b 个4模式6 ，8 个8横式7 ，1 6 个x 8 块4 块4 4 块困田圈图3 - 57 种帧间编码模式每个帧间宏块在编码之前，都会用这7 种预测模式进行预测编码，然后从中选出编码效率最高的模式进行正式编码。这样的处理方式可以保证对于每个宏块的编码都做到尽最大可能的冗余去除，但是也给编码器带来了巨大的计算量，对编码器的运算处理能力的要求很高。对于h 2 6 l 的宏块的预测方式，针对不同类型的宏块有些差别，对标准中允许的三种宏块的编码类型可用表3 1 予以总结：表中的帧内编码m b 对所有的宏块都适用，帧问编码的宏块也会进行帧内预测；前向预测m b 适用于所有的帧间编码宏块，包括p 帧图像和b 帧图像中的宏块；双向预测m b 只在b 帧图像的宏块中适用，它与前向预测不同的是增加了后向预测。西南交通大学硕士学位论文第1 2 页表3 - 1 不同编码宏块的可用编码方式类勋可用编码模式帧内编码m bl n 订a 4 x 4 ，i n t r a l 6 1 6i n w a 4 x4 ， n t r a l 6 x1 6 ，s k i p , 1 6 x1 6 , 1 6 x 8 。8 1 6 ，3前向预测m b8 ，8 4 ，4 x 8 4 4i n l r a 4 4 ，i n n a 1 6 1 6 ，b i d i v e c t d i r e c t 。f o r w a r d l 6 1 6 ，f o r w a r d1 6 8 。f o r w a r d8 x1 6 。f o r w a r d8 x 8 。f o r w a r ds x4 f o r w a r d 4 x 8 。f o r w a r d 4 x4 双向预测m bb a c k w a r d l 6 x1 6 ，b a c k w a r d1 6 8 。b a c k w a r d8 x1 6 b a c k w a r d8 8 ，b a c k w a r d8 x 4 ，b a c k w a r d4 x 8 ，b a c k w a r d 4 x 4另外，h 2 6 l 标准对于帧间预测还有一个较大的改进就是采用了多参考帧预测模式t 就是相对子以前的编码标准只将前面紧靠当前编码帧的图像作为参考帧而言，h 2 6 l 允许图像在编码器从前面多至5 帧的多帧图像中进行预测和补偿编码。该模式的引进不但使得编码效率在只用一个参考帧的基础上进一步提高，而且能够实现更好的码流误码恢复，但该模式的使用需要增加额外的延时和存储容量。标准采用的不同的算法对于编码效率的贡献分别为2 】：使用7 种不同的大小和形状的帧间预测和只使用1 6 1 6 模式的帧阃预测相比，能节省相当于2 0 的码宰数据；使用1 8 象素空间精度与不使用1 b 象素空问精度所得的数据量相比，能节省大约1 2 的码率数据；使用5 个参考帧预测与只使用一个参考帧相比，能节省大约15 的码率数据。可见，这些算法的加入对于提高编码效率还是很有帮助的。现在，很多大学、科研机构和商业部门都展开了对h 2 6 l 的研究和应用开发，因此对h 2 6 l 的研究具有极其广泛的的应用前景。亘妻奎壅盔兰堡主兰焦迨塞坚! ! 夏第4 章并行计算概述4 1 并行计算简介随着计算机应用的日趋复杂，其应用范围也越来越广，处理的问题规模也越来越大，对计算机的处理速度和运算能力的要求也越来越高。但另一方面由于受到材料物理特性的限制，单机的处理速度是有极限的，该极限大概为1 0亿次每秒。解决这一矛盾的办法就是用多个处理器来组成并行机以突破单机的速度限制。在视频的处理过程中，也同样面临器要高性能的计算机来进行计算处理的问题，下面首先对并行计算作些介绍。并行是指两个或多个事件在同一时刻或同一时间段内发生。并行处理是种有效的信息处理方式，它在信息的处理过程中着重于开发计算过程中的并发( c o n c u r r e n c y ) 事件。弗发性的橛念有三种含义：同时行( s i m u l t a n e i t y ) 、并行性( p a r a l l e l i s m ) 和流水线( p i p e l i n i n g ) ；因此并发事件也分为三类【3 0 】：同时事件：即同一时刻发生的事件，通过多个资源同时处理相同的事件。并行事件：即在同一时间段内发生的事件，这种情况包括我们通常所说的多任务处理，严格来说多个任务并非在同一时刻同时处理。流水线事件：即在重叠的时间段内发生的时间，指在同一时刻由不同的资源进行不同的处理。其中同时性是利用资源的重复来实现并行，它是最严格的并行过程。多处理机系统就是这样的一种并行方式，只有这种计算机系统才能算得上严格意义上的并行处理机，本文中后续部分提到的并行处理，如无特殊说明均指这种在同一时刻发生的并行方式。在并行处理中，并行粒度( g r a n u l a r i t y ) 是一个非常重要的概念。并行处理的粒度足指参与并行处理的基本单元的大小。并行粒度一般可以分为三级：粗粒度( c o a r s ec r r a n u l a r i t y ) ：以大块的程序为并行处理单元。细粒度( f i n eg r a n u l a r i t y ) ：以语句、表达式或者一个简单的算术或逻辑操作作为并行处理单元。中粒度( m e d i u mo r a n u l a r i t y ) ：介于粗粒度和细粒度之间。粒度是并行处理技术中的一个基本要素，粒度的大小对于并行机系统的效率有非常重要的影响。只有并行粒度选择适当，计算问题的并行算法与硬件结构相适应时，才能够充分发挥并行机的潜力，使并行计算获得较好的加速性能。西南交通大学硕士学位论文第1 4 页4 1 1 当代并行机系统从2 0 世纪7 0 年代到现在，并行机的发展已经有接近3 0 年的历史了在这期间，出现了多种不同类型的并行机，包括向量机、s i m d ( s i n g l ei n s t r u m e n t ，m u l t i p r o c e s s o r s ) 计算机和m i m d ( m u l d ，i n s t r u m e n t s ，m u l t i p r o c e s s o r s ) 计算机。随着计算机的发展，向量机和s i m d 计算机已经逐渐退出了历史舞台，而m i m d 类型的并行机占据了主导作用。当代主流的并行机是可扩放的并行机。包括共享存储的对称多处理机( s m p ) 、分布存储的大规模并行机( m p p ) 和工作站机群系统( c 0 w ) 。对称多处理机s m p ( s y m m e t r i cm u l f i p r o c e s s o r ) 系统属于u m a ( u n i f o r mm e m o r ya c c e s s ) 机。共享存储的s m p 系统具有对称性、单地址空间、高速缓存及其一致性和低通信延时等优点。大规模并行处理机m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 是属于n o r m a( n o r e m o t em e m o r ya c c e s s ) 模型的机器，指由多个处理器组成的大型并行计算机系统。m p p 的每个节点有一个或多个处理器和高速缓存( p 妃) 、一个局部存储器和网络接口电路，磁盘可有可无。系统的各个计算节点之间通过高速网络相连，这样可以在很大的程度上减少节点间的通信开销。m p p 具有很好的可扩放性、通用性和较低的通信开销等很多优点。工作站机群c o w ( c l u s t e ro fw o r k s t a t i o n s ) 是实现并行计算的一种新主流技术，属于分布式存储的m i m d 并行计算机结构，由工作站和互连网络两部分组成。这种并行计算机用于计算的主要的资源是工作站，他的主要优点有投资风险小、编程方便、系统结构灵活、性能价格比高和可扩放性好等。4 1 2 超级并行计算机系统：曙光- 2 0 0 0曙光天潮系列“曙光一2 0 0 0 ”是基于分布式存储和消息传递体协结构的通用可扩放并行计算机系统i ，其节点数目为4 1 2 8 个，节点c p u 采用p o w e rp c微处理器，通过高速以太网和虫蚀路由芯片组成的二维网孔相连。每个结点上都运行完整的i b ma i x 操作系统，该系统与i b m r s 6 0 0 0 二进制兼容，可以广泛的应用于多种计算领域。曙光一2 0 0 0 的节点可以分为计算节点、i o 与登录服务节点两种，前者用于执行用户提交的任务，后者用于支持用户作业在计算节点上的运行。用户可以使用批处理方式或者交互方式使用曙光2 0 0 0 。在批处理方式中，作业通过网络作业调度程序提交。在交互方式中，用户使用u n i xd o g i n t e l n e t登录到踞光- 2 0 0 0 系统上，通过相应的网络地址就可以访问某个特定的节点。西南交通大学硕士学位论文第1 5 页曙光2 0 0 0 的资源管理器的主控服务运行在控制台上，它将相应的节点分配给并行作业，当并行作业提交时，用户通过函数或者命令向资源管理器申请作业所需要的节点。当节点分配确定后，分区管理进程就在分区内的每个节点上加载一份作业的可执行代码，并通知该结点上的守护进程启动代码的执行。当作业完成后，分区管理进程负责清除和终止工作，并交回分区内的所有节点。本论文的主要实验工作就是在曙光2 0 0 0 上进行的。4 2 并行计算性能评测概述在并行计算机上进行计算的主要目的就是要加速整个计算过程，所以研究并行计算的加速性能是最根本的研究并行效果的途径。但随着计算负载的增加和机器规模的增大，研究并行计算的性能是否能够随着处理器数目的增加而按比例的增加也是很重要的，这就是并行计算的可扩放性问题。下面就并行程序加速比和可扩放性评测的基本标准和方法给予介绍：4 。2 1 加速比性能评测简单的说，并行系统的加速比是指对于一个给定的应用，并行算法或程序的执行速度相对于串行算法的速度加快了多少倍。常用的加速比定律有三种：a m d a h l 加速比定律、g u s t a f s o n 加速比定律以及s u n 和n i 加速比定律【3 3 l 。a m d a h l 加速比定律1 3 4 的基本出发点是：对于很多的计算，实时性要求很高，在这些应用中时间是个关键因素，而计算的负载是不变的。为此在一定的计算负载下，为达到实时，可以采用增加处理器的个数来提高计算速度；该定律的一个条件就是固定负载可以分布到多个处理器上进行并行运算。据此，a m d a h 在1 9 6 7 年推出了如下具有固定负载的加速公式：s=i要而(4-uf(1 + p l 、+ p w o w其中，s 为加速比。p 为处理器个数，厂为整个程序中串行执行代码所占的比重，为问题的总开销，问题规模确定时它为个常量，肋为通信开销，主要源于进程间通信。当处理器数目p 趋于无穷大时，公式可以变为：s =万瓦而之可见，串行分量越大和并行通信开销越大，则加速性能越差，在此公式表示的加速比定律中，串行计算分量是提高加速比的个瓶颈。g u s t a f s o n 加速比定律的基本出发点是：对很多大型计算，精度的要求很高，。- 。_ 。_ - _ _ 。- - _ - _ - _ _ _ _ - _ _ ii - - _ _ - - _ _ - - _ _ - 。_ _ - - _ _ _ _ _ 。- 。_ _ i 一西南交通大学硕士学位论文第1 日页即这些应用中精度是关键因素，而计算的时间是要求固定不变的。此时为了提高精度，必须加大计算量，相应地就应该增加计算的处理器数目来维持原来的计算时间。该加速比定律主要应用予问题规模可增大的场合。据此，g u s t a f s o n在1 9 8 7 年给出了放大问题规模的加速公式：。 + pl l j )o2 = = 一( 4 3 )1 + 形、7公式中各参数的物瑾意义同公式( 4 1 ) ，在公式的描述申因为问题的规模是可以扩大的，所以串行执行的分量不再成为问题的瓶颈。s u n 和n i 加速比定律是一种存储受限的加速定律。基本思想是：只要存储空间允许应尽量增大问题的规模以产生更好或更精确的解。即在具有足够的存储空间，而且问题的可扩放规模满足规定的时间要求时，就有可能通过进步的增大问题的规模来获得更好的解。据此，x i a n - h es u n 和l i o n e ln i 在1 9 9 3年提出了如下的加速定律：s ：塑二笠丝l阵。1+ ( 1 - f ) g ( p ) p + g o w”。其中因子g 例反映存储容量增加p 倍时工作负载的增加量，别的参数与前面公式一致。当g 例= j 时，式( 4 4 ) 就变成了a m d a h l 定律：当g 例印时，公式就变成了g u s t a f s o n 定律：当g 6 0 ) p 时，它相应于计算负载比存储要求增加的快，此时公式( 4 4 ) 加速性能最好。在实际应用中，可供参考的加速比范围的经验公式是：p l o gp ssp “5 )可见在最理想的情况下，加速比上限为参加计算的处理器数目。4 2 2 可扩放性评测标准除了上西讨论的加速比以辨，芳行计算的可扩教性也是评价并行程序性能的主要指标之一。可扩放性的基本含义是指在确定的应用背景下，计算机系统、并行算法或程序性能随处理器的增加而按比例提高的能力”1 。该指标被越来越广泛的应用来评述并行算法( 并行程序) 能否有效利用可扩充的处理器的能力。进行可扩放性研究的主要目的是：l 、确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效的利用大量的处理器。2 、对运行于某种体系结构的并行计算机上的某种并行算法，根据算法在西南交通大学硕士学位论文第1 8 页第5 章t m l 8 0 并行性分析进行并行程序的设计，主要有三种方