（计算机软件与理论专业论文）基于压缩域的并行视频处理.pdf

s p e c i a l t y ：c o m p u t e rs o f t w a r ea n dt h e o r y t i t l e ：p a r a l l e lv i d e om a n i p u l a t i o n b a s e do n c o m p r e s s e d d o m a i n m s s t u d e n t ：c h e l l 胁一 a d v i s o r ：p r o f s h i x i ns u n a b s t r a c t w i t ht h e h i g h - s p e e dd e v e l o p m e n t o f c o m p u t e r n e t w o r ka n dm u l t i m e d i a t e c h n o l o g y , v i d e oi sp l a y i n ga ni n c r e a s i n g l yi m p o r t a n tr o l e 船i n t e r n e tm e d i ad a t a t y p e i n t e r a c tv i d e ou s e ，h o w e v e r , t y p i c a l l ym e a n ss t r e a m i n g l i v eo ro n - d e m a n d j m a t e r i a lw i t h o u t m a n i p u l a t i o n i nm o s to ft h e a b o v ea p p l i c a t i o na r e a s , v i d e oi s i j c m a t e di nt r a d i t i o n a l w a y s ，e d i t e d w i t h s p e c i a lp u r p o s eh a r d w a r ；a n df i n a l l y d i g i t i z e da n dc o m p r e s s e df o ri n t e r a c tp u r p o s e s m a n ya d v a n c e dv i d e oa p p l i c a t i o n s r e q u i r em a n i p u l a t i o n so fc o m p r e s s e dv i d e os i g n a l s ，s u c h 船o v e r l a p ，s c a l i n g ，l i n e a r 黔 f i l t e r i n g ，r o t a t i o n ，a n dc o m p o s i t i o n t h e r ea r et w o p o s s i b l ew a y s t om a n i p u l a t e c o m p r e s s e d v i d e o t h ef i r s ta p p r o a c h f u l l yd e c o d e se a c hc o m p r e s s e di n p u tv i d e oa n d t h e nm a n i p u l a t e st h e mi nt h es p a t i a l d o m a i n t h e o u t p u tv i d e on e e d s t 0b er c e n c o d e da g a i ni ft h ec o m p r e s s e df o r m a ti s r e q u i r e d a l t e r n a t i v e l y ，w ec a nd e r i v e e q m v a l e n tm a n i p u l a t i o na l g o r i t h m s i nt h e c o m p r e s s e dd o m m na n dm a n i p u l a t ec o m p r e s s e dv i d e od i r e c t l y i nt h ec o m p r e s s c d d o m a i n d u et oam u c h l o w e rd a t am t ca n dt h er e m o v a lo ft h eu n n e c e s s a r y d e c o d i n g c o d i n gp a i r ，t h ec o m p m s 时d o m a i na p p r o a c h h a s g r e a tp o t e n t i a l i n r e d u c i n g t h ec o m p u t a t i o n a lc o m p l e x i t y m p e g ，m o t i o nj p e g ，a n dh 2 6 1a r ep o p u l a rc o m p r e s s i n gs t a n d a r d w ed e r i v ea s e to f a l g o r i t h m s f o rs o m em a n i p u l a t i o nf u n c t i o n si nt h ed c td o m a i n w ea l s o p r o p o s e as o l u t i o nf o rm o t i o nc o m p e n s a t i o nf r a m e s t h ea c t u a l c o m p u t a t i o n a l s p e e d u pd e p e n d s o nt h e s p e c i f i cm a n i p u l a t i o n f u n c t i o n sa n dt h e c o m p r e s s i o n t - c h a r a c t e r i s t i c so ft h ei n p u tv i d e o ，s u c ha st h ec o m p r e s s i o nr a t ea n dt h en o n - z e r o m o t i o nv e e t o r p e r e e o t a g e i - t h ek e yt os o f t w a r es o l u t i o nf o rr e a l t a m ev i d e om a n i p u l a t i o ni se x p l o i t i n g p a r a l l e l i s m b e c a u s eo fh i g hc o s t p e r f o r m a n c e ，s c a l a b i l i t y , a n da v a i l a b i l i t y , c l u s t e r i su s e da sap l a t f o r mt o p a r a l l e lv i d e om a n i p u l a t i o n t w ot y p e so fp a r a l l e l i s ma r e e x p l o i t e d ：c r o s s - f r a m el e v e la n di n - f r f i m el e v e l w eg e tr e s u l t s ：c r o s s f r a m el e v e l p a r a l l e l i s mh a s t h el e a s te o m r r t u r f i e a t i o no v e r h e a da n dt h eg r e a t e s tl o a di m b a l a n c e ； i n - f r a m el e v e lp a r a l l e l i s mh a st h eg r e a t e s tl o a db a l a n c e ，b u tm o r ec o m m u n i c a t i o n o v e r h e a d k e y w o r d s ：c o m p r e s s 。v i d e o m a n i p u l a t i o n p a r a l l e lc o m p u t a t i o n 上 基于压缩域的并行视频特效处理 第一章绪论 随着网络技术和多媒体技术的飞速发展，视频作为一种多媒体数据类型在网 络应用中扮演着越来越重要的角色。即使在缺乏高速访问网络能力的情况下甚 低速率编码的视频仍有应用。i s d n 、x d s l 以及c a b l em o d e m 等技术为家庭提供 了高速访闯网络的能力，更增加了市场对网络视频的需求。网络视频能够蓬勃发 展，得益于标准化的压缩技术和处理器性能的提高，使得软件解码成为可能。 今天，网络视频应用已经相当广泛，甚至可以把它单独看成种数据类型， 正如浮点数成为数据类型的历程，c o m e l l 大学计算机学院正在研究把音频、视 频作为一种数据类型来操作 1 。目前网络视频应用在：新闻实况转播、视频点 播、视频广告、远程教育、视频会议等等 2 。 然而以上提到的应用并没有包括对压缩后的网络视频进行操作和处理。一 般的，视频用传统的电影、电视的方法被创造出来。再经过数字化、压缩，才被 应用于网络。一旦基于网络的压缩的视频形成后现在还没有产品雕对它进行操 作和处理。例如：一个家庭在度假期间，拍摄了一段) d p e g 格式的录像，回到家 后他们想给这段录像期j 上字幕。饱识瑰在i 丕没有办法 来自电影、电视工业的经验表明，对视频迸行特殊的操作；编辑和处理，是 与观众进行交流，引发观众兴趣的有效手段【5 】。上面提到的例子就是一种特效 处理我们在电视节目中经常可以看到再举一个铡子说明视频处理还可为网络 视频适应网络带宽提供一种解决方法例如：有的一个用户连接个低速网络， 他通过一个视频两关访阅高速瞬络的足球实况转播而高速网络上的视频具有大 尺寸的画面和高清晰度韵画质，显然这个用户会不堪忍受圈像的延迟和跳跃，如 果我们让这个视频网关能穆对网络视频实时进行缩小圈像尺寸和降低清晰度的处 理，让他自起够看到连续的图像，也许能够挽回这个顾客。 电影电视工业采用一种被称为视频转换幕统( v i d e op r o d u c t i o n s w i t c h c f , v p s ) 进行槐频处理v p s 是一种特臻的硬件设备，它操缴模拟或数字 的视频静号以怠b 造特璩的视频效累，通常，它被电影电视的专业技术人员和导演 所控槠。我们可以用v p s 米构成一个网络视频处理系统，但v p s 只对模拟的或 ， 一 二二二二= 二二：二：二j 二二二，：- 。釜置i 一 胃气盛暑节遗_ 出一一 苎! 堡墅塑塑苎堑堡塑壁墼竺墨 者未压缩的数字视频进行处理因此我们必须将压缩的网络视频解压缩，再交给 v p s 处理，然后再把处理后的视频再进行压缩。然而这种方式仍然不适合网络上 的基于包的视频，网络上视频包的延迟和丢失，对于v p s 这种有严格时间同步 限制的系统也许足致命的。- 3 t - h 昂贵而专用的硬件设备也会阻碍它的广泛应用。 我们转为用软件方式来解决这个问题。一种方式是先解压缩，再对未压缩的 图像进行处理，然后再压缩【3 。我们知道对未压缩的图像进行处理，具有很高 的计算复杂性，并且压缩操作也是相当耗时的，即使是最高档的图形工作站也难 以满足要求。 本文讨论的基于压缩域的视频处理为这种应用提供了一种现实可行的方法。 基于压缩域的视频处理的提出基于以下事实： 网络上的视频都是经过压缩的 压缩域的视频处理较之空间域的视频处理具有更小的计算复杂性 相对于前一种方式，压缩域视频处理直接对压缩的网络视频进行处理，直接 的好处在于省去了解压缩和再压缩的步骤。并且压缩域的视频处理具有很大的降 低计算复杂性的潜力。 m p f g 。h 6 1 瑚p b o t 4 - 7 l 悬目前流行的椒龋腻啸桴精它们的檀心 离 敞翕馥囊姨囊日f ) ，宠闻域的坤参栅棚 b 囊螺柏钾可以射列t 域肿宁 采用运动补偿技术的噩缩，我们也提供丁一种转换方法，使得我们自e 够处理运动 补偿的图像帧。 基于压缩域的视频处理是一种新的技术，一些学者也在从事这方面的研究。 s m i t h 和r o w e 研究了d c t 域的一些处理方法【8 】，例如：线性操作、点乘。l e e 提出了压缩域的滤波算法 9 】。l e e 和w o o d s 研究了画中画、字幕叠加的算法【1 0 】。 本文综合了这些学者的研究成果，进行了严密的理论推导，扩展了一些视频处理 方法，对压缩域内运动补偿块重构进行了深入地研究。 基于压缩域的视频处理技术为我们构建一个实时的软件网络视频处理系统提 供了技术基础，见图l - i 。这个软件处理系统的作用就象前面提到的v p s 。 从图i - i 可以看到，这个系统的输入可以是预先录制并存储在视频数据库的 电影电视，也可以是来自摄像机的实时视频数据。运用这个模型，可以提供一些 2 苎士曼塑壁堕茎堑堡塑堑塑丝翌 新的有趣的应用。例如：在远程学习应用中，运用画中画的处理，我们可以在主 画面显示教授的演讲，而在次画面显示一些背景材料。我们还可以通过导播控制 切换画面的内容，实时叠加一些说明性的文字。 虽然，基于压缩域的视频处理相对于空间域的处理能够大幅降低计算复杂 性，但当前的处理器的性能还不能够满足这个需求。并行处理是实现实时软件网 络视频处理系统构想的必经之路。 圈l - i 软件弼：络视频处理系统 从2 0 世纪9 0 年代以来，昂贵而特制的并行超级计算机向网络工作站集群转 换的趋势越来越强。高性能的工作站和网络部件的商品化成为这种转换的驱动因 素。集群是为了迸 亍并行计算，由高速网络连接起来的高性能的工作站或p c 扎 组成的系统【1 l 】。许多研究者投入刭利用集群进行大规模和具有高度挑战性的计 算任务。集群较之专用的并行计算机优秀的原因有下 1 2 1 s 1 , 单个工作站越来 越强大，处理器性能以惊人的速度提升；随着新的网络技术和协议在l a n 上的 使用，工作站间的网络带宽正在增加，延迟正在减小；工作站的开发工具比并行 计算机的专用解决方面要成熟和丰富；工作站集群比高性能专用计算机更便宜， 更易于获得；集群可以方便的扩展。 正是由于网络工作站集群具有的高性能价格比，我们用最普通的设备，构建 了一个小型的集群，探索集群如何应用于压缩域视频特效处理。幸运的是，基于 压缩域的视频处理具有较高的并行度可以有不同层次的粒度划分方式可供选 3 扛 苎主堡塑苎堕苎堑型塑量塾竺型 择，不同粒度划分方式对并行性能有不同的影响。 本文的第二章讨论了并行计算的体系结构、并行算法的设计方法、并行计算 的模型、并行算法的性能指标等内容；第三章讨论了当前最为流行的视频压缩标 准m p e g ，它的核心足离散余弦变换和运动补偿；第四章阐述了压缩域视频处理 的理论基础，推导了多种操作处理算法，并对运动补偿帧的处理提出了解决办法； 第五章详细讨论和试验了在压缩域内重构运动补偿块这使得我们能够对m p e g 等采用运动补偿的视频同样进行处理，并且试验了放缩处理操作；第六章我们探 讨了压缩域视频处理的并行实现，包括计算模型、任务划分和任务调度等等，试 验了两种不同任务划分方式的并行视频处理。 4 基于压缩域的并行视频特效处理 第二章并行计算概论 2 1 并行计算机系统的体系结构 2 1 1 并行计算机系统的分类 f l y n n 1 4 把计算机系统按指令流和数据流分为以下几种类型t s i s d ：单指令流单数据流。 s 1 m d ：单指令流多数据流。 m i s d ：多指令流单数据流。 m 玎讧d ：多指令流多数据流。 s i s d 仅用于串行计算，而m i s d 目前尚没有这方面的产品。因此并行计算 机主要分为sm d 和m i m d 两大类 1 5 ，l q 。 。 2 1 1 1 s l 模型 作为计算机历史上体系结构的一个重要分类，它有强大的指令系统【1 5 ，1 6 1 。 单指令多数据计算机能同时在多个数据流上执行一条指令，通常是中闻主机执行 逻辑程序并将指令广播给其它处理器。对如数据并行这类问题这种类型的体系 结构能够很好的达到很高的处理速度，这是因为数据可以被分成许多不同的、独 立的块，并且多个指令单元可同时对它们进行操作。其主要特征有： 1 1 ) 同步的。这种类型的系统通常都是同步的，也就是说系统保证所有指令 单元同时接收到同一指令，因此它们能够阿时执行同一操作。 2 ) 确定的。s i m d 体系结构是确定的，因为在任何时间点只有一条指令在执 行，尽管可能有多个单元在执行。所以，每次同一个程序在同样的数据 上运行，采用同样数目的执行单竞，在每步保证正确地得到相同的结果。 3 ) 适合于指令，操作级并行。单指令中的“单”并不是象s i s d 中只有一个 指令单元，而是只有一个指令流，并且是由多个处理单元在不同的数据 l 一二；_ 二，- _ - _ _ _ - l _ - _ - _ _ 一一 ，* i n 瀣i 莹 j 基于压缩域的并行视频特效处理 第二章并行计算概论 2 1 并行计算机系统的体系结构 2 1 1 并行计算机系统的分类 f l y n n 1 4 把计算机系统按指令流和数据流分为以下几种类型t s i s d ：单指令流单数据流。 s 1 m d ：单指令流多数据流。 m i s d ：多指令流单数据流。 m 玎讧d ：多指令流多数据流。 s i s d 仅用于串行计算，而m i s d 目前尚没有这方面的产品。因此并行计算 机主要分为sm d 和m i m d 两大类 1 5 ，l q 。 。 2 1 1 1 s l 模型 作为计算机历史上体系结构的一个重要分类，它有强大的指令系统【1 5 ，1 6 1 。 单指令多数据计算机能同时在多个数据流上执行一条指令，通常是中闻主机执行 逻辑程序并将指令广播给其它处理器。对如数据并行这类问题这种类型的体系 结构能够很好的达到很高的处理速度，这是因为数据可以被分成许多不同的、独 立的块，并且多个指令单元可同时对它们进行操作。其主要特征有： 1 1 ) 同步的。这种类型的系统通常都是同步的，也就是说系统保证所有指令 单元同时接收到同一指令，因此它们能够阿时执行同一操作。 2 ) 确定的。s i m d 体系结构是确定的，因为在任何时间点只有一条指令在执 行，尽管可能有多个单元在执行。所以，每次同一个程序在同样的数据 上运行，采用同样数目的执行单竞，在每步保证正确地得到相同的结果。 3 ) 适合于指令，操作级并行。单指令中的“单”并不是象s i s d 中只有一个 指令单元，而是只有一个指令流，并且是由多个处理单元在不同的数据 l 一二；_ 二，- _ - _ _ _ - l _ - _ - _ _ 一一 ，* i n 瀣i 莹 j 茎主墨塑苎塑堑堡堡塑堑塑些型 块上同时执行的，这就达到了并行。 c m - 2 ，m a s p a rm p - 1 ( d e c m p p 1 2 0 0 0 ) ，m p 2 ，i c ld a p ，i b m9 0 0 0 ，c r a y y m p ，c r a y1 ，n e cs x - 2 ，f u j i s t uv p ，h i t a c h i $ 8 2 0 等都属于这种类型的体系 结构。这种并行计算机利用流水线的技术，通过时间重叠实现并行加速，加速比 一般可达到4 8 。但是，单纯依靠单机提高计算机性能的潜力毕竟有限，对于 超大型计算问题，人们追求的加速比是以数量级为单位的，并行化则转向“多指 令流多数据流”方向发展。 2 1 1 2_ l 模型 这种体系结构将多个处理器连在一起达到并行，每个处理器在各自唯一的数 据流上执行各自的指令流，与其它处理器无关。其主要特征如下： 1 ) 同步或异步。m i m d 指令流可以同步或异步地执行，一些算法要求同步 而另一些可能要求异步。不同类型的m i m d 系统更好地适合其中一种， 最适宜的效率依赖于运行的系统是否自b 反映出代码所需要的同步性。 2 ) 确定性和不确定性。mm d 系统可以有确定的行为，即是说每次一个程 序对同样的数据操作时能再产生和以前相同的处理步。然而一些其它的 因素如一个接收者如何处理多个消息会在实际情况中决定这一特征。 3 ) 适合块、回路或子程序级的并行。一般的，在m i m d 集合中每个处理器 分发的代码越多，整个系统地运行效率也越高。这主要是因为在面向指 令的并行中，通信和同步需求不是很迫切的。 4 ) 多指令或单程序。m 1 m d 类型的系统能够真正按“多指令”模式运作， 即每个处理器做不同的事，或者每个处理器分发相同的代码。后者被称 为s p m d ( 单程序多数据) ，是s i m d 类型并行的一般化，其同步需求比 s i m d 松得多。 ， 属于这种类型体系结构的实例主要包括：s e q u e n t ，n c u b e i n t c li p s c 9 6 0 ， i b mr s 6 0 0 0 c l u s t e r ，c r a y2 ，c m yx - m p , y - m p n e cs x 3 ，f u j i s t uv p 2 0 0 0 ， c o n v e xc 2 ，i n t e l i p s c 2 ，c m5 ，i b ms p l ，i b m s p 2 m i m d 系统根据存储结构的不可再分为：共享存储m 1 m d 和分稚式存储 m i m d 。共享存储多处理机每一个处理器都访问统一的内存，它存在的一个主要 6 l 苎= 丝塑苎堕茎笪堡塑堂塾丝堡 问题是可扩展性较差，当多处理机需要同时访问共享内存时，由于产生内存争用 现象而严重影响效率。分布式存储m i m d 每一个处理机都有自己可直接访问的 内存，称为局部存储器，能够避免共享存储带来的内存竞争问题，并且具有良好 的可扩展性。 + 分布式存储m i m d 多处理机体系成为当今并行计算的主流。许多的专用大 规模并行计算机( m p p ) 均采用这种体系。随着工作站性能的飞速提高和网络技术 的飞速发展，网络工作站集群( c l u s t e r ) 系统越来越受到人们的关注，下一节我们 将着重介绍这种系统。 2 1 2 网络工作站集群系统 网络工作站集群系统是属于分布式存储m i m d 多处理机体系，相对于大规 模并行计算机，集群一般由高速网络连接高性能的工作站或p c 机组成 1 7 。l s 欧从2 0 世纪9 0 年代以来，由于工作站性能和网络通信速度的飞速提升，昂贵而 特制的大规模并行计算机向工作站网络转换的趋势越来越强。 2 1 2 1m p p 与c i u s t e r 的比较 c l u s t e r 系统与m p p 系统相比，它们除具有分布式存储系统的共同特点外， 主要不同点表现在以下几个方面 1 9 ，2 0 。 c l u s t e r 体系中的每一个节点都是一个完整的计算机。c l u s t e r 体系的节点 机往往依赖于现有的、成熟的技术，如常见的工作站甚至p c 等等，运行u n i x 、 l i n u x 等成熟操作系统，有一大批现有的应用可进行并行忧 典型的c l u s t e r 体系常常依赖于通用的网络体系( 如以太网等) ，这样节点 机之问的通信效率要低于专用的) a p p 体系，因此c l u s t e r 体系比较适用予中、粗 粒度的并行。 此外c l u s t e r 与好p 相比，具有以下优点： 系统开发周期短：由于c l q s t e r 体系的节点机、操作系统、网络遥信全采用 成熟的技术，因而节省了大量研制时间。 用户投资风险小：机群系统的每个节点都是一台独立的工作站或高档p c 机， 相比于m p p 系统而言，系统性能的发挥可得到保证避免资金的浪费。 7 1 f _ 专镱守繁黼群蠹l _ 篡泣t - 。 l 苎= 丝塑苎堕茎笪堡塑堂塾丝堡 问题是可扩展性较差，当多处理机需要同时访问共享内存时，由于产生内存争用 现象而严重影响效率。分布式存储m i m d 每一个处理机都有自己可直接访问的 内存，称为局部存储器，能够避免共享存储带来的内存竞争问题，并且具有良好 的可扩展性。 + 分布式存储m i m d 多处理机体系成为当今并行计算的主流。许多的专用大 规模并行计算机( m p p ) 均采用这种体系。随着工作站性能的飞速提高和网络技术 的飞速发展，网络工作站集群( c l u s t e r ) 系统越来越受到人们的关注，下一节我们 将着重介绍这种系统。 2 1 2 网络工作站集群系统 网络工作站集群系统是属于分布式存储m i m d 多处理机体系，相对于大规 模并行计算机，集群一般由高速网络连接高性能的工作站或p c 机组成 1 7 。l s 欧从2 0 世纪9 0 年代以来，由于工作站性能和网络通信速度的飞速提升，昂贵而 特制的大规模并行计算机向工作站网络转换的趋势越来越强。 2 1 2 1m p p 与c i u s t e r 的比较 c l u s t e r 系统与m p p 系统相比，它们除具有分布式存储系统的共同特点外， 主要不同点表现在以下几个方面 1 9 ，2 0 。 c l u s t e r 体系中的每一个节点都是一个完整的计算机。c l u s t e r 体系的节点 机往往依赖于现有的、成熟的技术，如常见的工作站甚至p c 等等，运行u n i x 、 l i n u x 等成熟操作系统，有一大批现有的应用可进行并行忧 典型的c l u s t e r 体系常常依赖于通用的网络体系( 如以太网等) ，这样节点 机之问的通信效率要低于专用的) a p p 体系，因此c l u s t e r 体系比较适用予中、粗 粒度的并行。 此外c l u s t e r 与好p 相比，具有以下优点： 系统开发周期短：由于c l q s t e r 体系的节点机、操作系统、网络遥信全采用 成熟的技术，因而节省了大量研制时间。 用户投资风险小：机群系统的每个节点都是一台独立的工作站或高档p c 机， 相比于m p p 系统而言，系统性能的发挥可得到保证避免资金的浪费。 7 1 f _ 专镱守繁黼群蠹l _ 篡泣t - 。 苎! 堕塑篁堕茎堑! ! 塑竺竺些墨 系统性价比高：传统巨型机或m p p 的价格都比较昂贵，工作站或高档p c 机 由于是批量生产出来的，因而售价较低，且由近十台或几十台工作站组成的机群 系统可以满足多数应用的需求，所以c l u s t e r 系统的性价比较m p p 系统高。 节约系统资源：可以充分利用现有设备，将不同体系结构、不同性能的工作 站连在一起，包括原有的一些性能较低或型号较旧的机器在群集系统中仍可发挥 作用。 系统可扩展性好：从规模上说，群集系统大多使用通用网络，系统扩展容易； 从性能上说对大多数中、粗粒度的并行应用都有较高的效率。 系统容错性好：c l u s t e r 的一个重要发展方向是作为应用服务器、数据库服 务器等等。因此，c l u s t e r 体系在软件的功能上下了很多工夫，一个重要的贡献 就是失效切换技术，它是指当系统中的一个节点出错时，这个节点上的任务可转 移到其它节点上继续运行，用户本身感觉不到这种变化。这也因此导致这种机型 的发展前途非常之好，特别是可以用作超级服务器或服务器聚集。 应用面较广：由于c l u s t e r 是建立在成熟的技术基础之上的，因此，与m p p 系统相比，c l u s t e r 往往能获得更广泛的应用。 显然，群集系统在性能价格比( c o s t p e r f o r m a n c e ) 、可扩展性 ( s c a l a b i l i t y ) 、可用性( a v a i l a b i l i t y ) 等方面都显示出了很强的竞争力，尤其 是它对现有单机上的软、硬件产品继承和对商用软、硬件最新研究成果的快速运 用，从两方面表现出传统肝p 无法比拟的优势。 目前，群集系统已在许多领域获得应用。可以预见，随着s i v i p 产品的大量 使用和高性能网络产品的完善以及各种软硬件支持的增多和系统软件、应用软件 的丰富，新一代高性能集群系统必将成为未来高性能计算领域、商务计算和网络 信息服务的主流平台之一，未来的超级服务器将大量采用群集技术。 2 1 2 2 集群计算机体系结构 集群中的计算节点可以是一个单处理器或多处理器的系统( p c 、工作站、 s m p ) ，拥有各自的内存、y o 设备和操作系统。节点往往通过l a n 连接在一起。 一个连接在一起的计算机集群对于用户和应用程序来说象一个单一的系统。 以下是集群计算机的重要组成部分： l 一 苎坚塑堕堕苎! ! 塑塑堑塾些型 多个高性能计算机( p c 、工作站、s m p ) 优秀的操作系统( 分层或基于为内核) 高性能的网络( 如千兆以太网或m y r i n e t ) 网络接口卡 快速的通信协议和服务( 如活动消息和快速消息) 集群中间件 并行编程环境和工具( p v m ，m p r ) 网络接口硬件担当通信处理的任务，负责在节点间通过网络传送和接收数据 包。通信软件提供了快速而可靠的节点间以及与外界数据通信的手段。一些使用 专门网络的集群，通过绕过操作系统来避开对系统性能影响很大的额外通信开 销，并提供对用户层的直接接口访问网络。集群备节点可以象集成的计算资源一 样工作，或者说集群各节点象一台计算机一样工作。集群中间件负责为独立但互 连的计算机对外提供统一的系统映像( 单一系统映像) 和易用性。 2 2 并行计算软件环境 操作系统( 如u n i x 、w i n d o w s 、a i x 等) + 工具语言( 如c 、c + + 、f o r t r a n ) + 并行计算环境是目前实现并行算法的常用软件环境。其中的并行计算环境随着 近年来分布式m p p 系统与工作站群集系统的蓬勃发展而得到了迅速发展，相继出 现了p 、m 、m p i 、e x p r e s s 、l i n d a 、p j a m c s 、p 4 、n x 和z i i ) c o d e 等基于消息传递 的并行计算环境，目前常用的是p w 和m p i 。 2 2 1p v m 、 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 即并行虚拟机系统 2 1 2 2 ，是美国国家基 金会资助的公开软件系统，具有通用性强及系统规模小的特点，既适合t c p i p 网络环境，又适用于瓣p 大型并行系统现在所育的并行机公司都已宣布支j 畴 p v m 3 ( p v m 的当前版本) ，一些大公司还针对自丑产积自辱特点推出高效率的p v m 声 品。 p v m 属于显式消息传递系统。其特点可以总结为： l 一 苎坚塑堕堕苎! ! 塑塑堑塾些型 多个高性能计算机( p c 、工作站、s m p ) 优秀的操作系统( 分层或基于为内核) 高性能的网络( 如千兆以太网或m y r i n e t ) 网络接口卡 快速的通信协议和服务( 如活动消息和快速消息) 集群中间件 并行编程环境和工具( p v m ，m p r ) 网络接口硬件担当通信处理的任务，负责在节点间通过网络传送和接收数据 包。通信软件提供了快速而可靠的节点间以及与外界数据通信的手段。一些使用 专门网络的集群，通过绕过操作系统来避开对系统性能影响很大的额外通信开 销，并提供对用户层的直接接口访问网络。集群备节点可以象集成的计算资源一 样工作，或者说集群各节点象一台计算机一样工作。集群中间件负责为独立但互 连的计算机对外提供统一的系统映像( 单一系统映像) 和易用性。 2 2 并行计算软件环境 操作系统( 如u n i x 、w i n d o w s 、a i x 等) + 工具语言( 如c 、c + + 、f o r t r a n ) + 并行计算环境是目前实现并行算法的常用软件环境。其中的并行计算环境随着 近年来分布式m p p 系统与工作站群集系统的蓬勃发展而得到了迅速发展，相继出 现了p 、m 、m p i 、e x p r e s s 、l i n d a 、p j a m c s 、p 4 、n x 和z i i ) c o d e 等基于消息传递 的并行计算环境，目前常用的是p w 和m p i 。 2 2 1p v m 、 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 即并行虚拟机系统 2 1 2 2 ，是美国国家基 金会资助的公开软件系统，具有通用性强及系统规模小的特点，既适合t c p i p 网络环境，又适用于瓣p 大型并行系统现在所育的并行机公司都已宣布支j 畴 p v m 3 ( p v m 的当前版本) ，一些大公司还针对自丑产积自辱特点推出高效率的p v m 声 品。 p v m 属于显式消息传递系统。其特点可以总结为： l 一 苎坚塑堕堕苎! ! 塑塑堑塾些型 多个高性能计算机( p c 、工作站、s m p ) 优秀的操作系统( 分层或基于为内核) 高性能的网络( 如千兆以太网或m y r i n e t ) 网络接口卡 快速的通信协议和服务( 如活动消息和快速消息) 集群中间件 并行编程环境和工具( p v m ，m p r ) 网络接口硬件担当通信处理的任务，负责在节点间通过网络传送和接收数据 包。通信软件提供了快速而可靠的节点间以及与外界数据通信的手段。一些使用 专门网络的集群，通过绕过操作系统来避开对系统性能影响很大的额外通信开 销，并提供对用户层的直接接口访问网络。集群备节点可以象集成的计算资源一 样工作，或者说集群各节点象一台计算机一样工作。集群中间件负责为独立但互 连的计算机对外提供统一的系统映像( 单一系统映像) 和易用性。 2 2 并行计算软件环境 操作系统( 如u n i x 、w i n d o w s 、a i x 等) + 工具语言( 如c 、c + + 、f o r t r a n ) + 并行计算环境是目前实现并行算法的常用软件环境。其中的并行计算环境随着 近年来分布式m p p 系统与工作站群集系统的蓬勃发展而得到了迅速发展，相继出 现了p 、m 、m p i 、e x p r e s s 、l i n d a 、p j a m c s 、p 4 、n x 和z i i ) c o d e 等基于消息传递 的并行计算环境，目前常用的是p w 和m p i 。 2 2 1p v m 、 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 即并行虚拟机系统 2 1 2 2 ，是美国国家基 金会资助的公开软件系统，具有通用性强及系统规模小的特点，既适合t c p i p 网络环境，又适用于瓣p 大型并行系统现在所育的并行机公司都已宣布支j 畴 p v m 3 ( p v m 的当前版本) ，一些大公司还针对自丑产积自辱特点推出高效率的p v m 声 品。 p v m 属于显式消息传递系统。其特点可以总结为： 苎主堡塑堡堕茎塑塑塑堑塑竺型 支持多用户及多任务运行，多个用户可将系统配置成相互重叠的虚拟机，每 个用户可同时执行多个应用程序； 提供一组便于使用的通信原语。可实现一个任务向其它任务发消息、广播消 息以及阻塞和非阻塞收发消息等功能。实现了用户编程与网络接口分离。系 统还实现了通信缓冲区的动态管理机制，每个消息所需的缓冲区由p v m 运行 时动态申请，消息长度只受节点上可用空间的限制： 提出了进程组的概念，可以把多个进程一起组成一个g r o u p ，同一个进程可 属于多个不同的进程组，而且可以在执行时动态改变： 可无差别地运行在多种操作系统上，因而支持异构计算机联网构成并行虚拟 计算机系统； 具有容错功能当发现一个节点出故障时，p v m 会自动将之从虚拟机中删除。 p v m 的上述特点使之非常适合于用作并行算法的并行支撑软件，也是我们 采用它作为编程工具软件的原因。 2 2 2m p i m p i 2 3 ，2 4 是消息传递界面( m e s s a g ep a s s i n gi n t e r f a c e ) 的简称，它和p v m 一样，都提供了一组可用于消息传递的通信原语。 m p i 是为了统一不同的m p p 厂家的消息传递a p i ，由来自高性能计算领域的 专家和m p p 厂家的代表组成的委员会制定的工业标准它的目标是开发一个广泛 用于编写消息传递程序的标准，要求编程界面实用、可移植、高效、灵活，能广 泛用于各类并行机，特别是分布存储并行机。m p i 的现在版本是m p i 一2 ，是1 9 9 7 年2 月颁布的。 m p i 是在利用以前成熟和先进技术的基础上发展起来的标准，相对于目前广 泛使用的p v m ，除了具有p v m 的大部分优点，还具有以下特点： m p i 的实现方式多样化，统一编程界面可有多种开发工具： m p i 能实现完全的异步通信，发送与接收完全能与计算重叠进行； m p i 能有效地管理消息缓存区； 苎主堡塑堡堕茎塑塑塑堑塑竺型 支持多用户及多任务运行，多个用户可将系统配置成相互重叠的虚拟机，每 个用户可同时执行多个应用程序； 提供一组便于使用的通信原语。可实现一个任务向其它任务发消息、广播消 息以及阻塞和非阻塞收发消息等功能。实现了用户编程与网络接口分离。系 统还实现了通信缓冲区的动态管理机制，每个消息所需的缓冲区由p v m 运行 时动态申请，消息长度只受节点上可用空间的限制： 提出了进程组的概念，可以把多个进程一起组成一个g r o u p ，同一个进程可 属于多个不同的进程组，而且可以在执行时动态改变： 可无差别地运行在多种操作系统上，因而支持异构计算机联网构成并行虚拟 计算机系统； 具有容错功能当发现一个节点出故障时，p v m 会自动将之从虚拟机中删除。 p v m 的上述特点使之非常适合于用作并行算法的并行支撑软件，也是我们 采用它作为编程工具软件的原因。 2 2 2m p i m p i 2 3 ，2 4 是消息传递界面( m e s s a g ep a s s i n gi n t e r f a c e ) 的简称，它和p v m 一样，都提供了一组可用于消息传递的通信原语。 m p i 是为了统一不同的m p p 厂家的消息传递a p i ，由来自高性能计算领域的 专家和m p p 厂家的代表组成的委员会制定的工业标准它的目标是开发一个广泛 用于编写消息传递程序的标准，要求编程界面实用、可移植、高效、灵活，能广 泛用于各类并行机，特别是分布存储并行机。m p i 的现在版本是m p i 一2 ，是1 9 9 7 年2 月颁布的。 m p i 是在利用以前成熟和先进技术的基础上发展起来的标准，相对于目前广 泛使用的p v m ，除了具有p v m 的大部分优点，还具有以下特点： m p i 的实现方式多样化，统一编程界面可有多种开发工具： m p i 能实现完全的异步通信，发送与接收完全能与计算重叠进行； m p i 能有效地管理消息缓存区； 苎主! ! 塑苎塑鲞堡垫塑壁塾丝些 ： m p i 能在m p p 与工作站群集上有效运行； m p i 异步执行时能保护用户的其它软件不受影响； m p i 是完全可移植的标准平台。 实际上，无论是p v m 还是m p l ，它们都提供了一组函数，通过这些函数的调 用，子任务可加载到多个节点机上，并且节点机之问可进行消息的传递与接收， 协同完成计算任务。 2 3 并行算法设计与性能评估 2 3 1 并行计算模型 迄今为止，已有多种并行计算模型存在，如p r a m 模型、l o g p 模型、e 模 型、b d m 模型等，但其中的每一种只抽象了实际并行机的一个或几个方面，尚 无一种适用于所有并行机。 p r a m 模型 2 5 1 是对一类共享存储并行机的特征提取假设了网络带宽无 限，可直接开发原始算法内在细粒度并行。g p 模型( 1 2 6 1 ) 是对一类分布式并 行计算机的特征提取，基于点对点通信的计算模型，集中分析了处理机与网络之 间的瓶颈。p 模型( 【2 7 】) 是对一类基于消息传递的分布式粗粒度系统的特征提 取，集中反映的是网络拥挤和路由影响。b d m 模型( 2 s 】) 是共享存储编程模 式与消息传递的分布式存储系统之间的一个桥粱模型，反映的是存储系统中流水 线预取等方面的影响。 1 由于本文基于分布式系统研究并行算法，因此报据上述各模型特点，本文选 用l o g p 模型作为并行算法设计与分析的依据。下面对