（计算机应用技术专业论文）分布式多媒体同步与并行编码技术研究.pdf

摘要 摘要 分布式多媒体系统中，采取基于并行处理结构的媒体服务器是解决服务端处理能力 不足的主要方法。与单机媒体服务器相比，基于并行处理结构的媒体服务系统工作流程 复杂，各媒体对象间的时域约束关系难以维护：系统的服务能力与采用的调度算法息息 相关：而服务端采取自适应编码的方式服务时，不适宜的并行编码策略将降低系统的性 能。因此，论文对分布式多媒体系统中的同步约束关系，服务器端的调度算法和服务器 端的并行编码技术进行了分析和研究，并给出了提高服务端处理能力的解决方案。具体 包含以下内容： l 、为了完整地描述和分析多媒体系统中的时域约束关系，提出了多媒体同步模型 m h p n ( m u l t i m e d i ah i e r a r c h i c a lp e t r in e t ) 。 相比其它模型，m h p n 模型简洁、清晰、提供强大的交互控制能力，能够清楚地描 述多媒体系统内部的时域约束关系，及时地捕获用户的交互信息，完整地刻画不同对象 间的同步关系，分析并验证多媒体的同步行为，提供同步运行方案，并且针对不同层次 的同步要求，m h p n 可以为其分层建模。 根据分布式多媒体交互系统中服务端和客户端之间的时域约束关系和用户交互需 求，提出了d m h p n ( d i s t r i b u t e dm h p n ) 分布式多媒体同步模型，该模型以m h p n 模 型为基础，统一描述分布式多媒体系统中的同步关系和交互行为，提供更加完整地信息 捕获能力和控制能力。 2 、基于对分布式多媒体系统中服务器端调度算法的分析，针对并行任务提出了面 向质量自适应方式的调度算法。 在分布式多媒体系统中，当服务端提供质量自适应服务时，单个任务可能需要多个 结点并行处理，采用原来只针对串行任务的服务端调度算法将会降低系统性能。面向质 量自适应服务方式的调度算法针对视频并行处理的特点，以及并行任务和串行任务混合 调度的情况，尽量减少分派给并行任务的结点数目，以降低任务并行执行时各结点间的 通讯费用，提高系统的性能，从而进一步提高了服务端任务的处理能力。 3 、根据对分布式多媒体同步模型的分析，针对m p e g 4 压缩标准提出了基于不同 粒度的并行策略，给出了服务器端处理能力不足的解决方案。 提出了基于v o 的对象自适应调度算法，该算法估算待编码视频对象所需的计算能 力，将其划分为并行子任务或串行子任务，调度时尽量将串行子任务分配到权值低的结 点上。相比之下，该算法不仅能提高并行任务的处理量，合理利用现有结点的计算能力， 还能减少重新调度的次数和所需的额外费用； 为了及时在较短的时间内响应用户的操作，减少调度本身所产生的费用。提出了基 于g o v 的滑动调度算法，该算法借助于可变滑动窗口协议的部分思想，考虑用户的交 中国科学院博士学位论文一分布式多媒体同步与并行编码技术研究 互行为在一定的时间段内具有一定的连续性，在并行编码时，逐渐增加分配给各结点的 数据量直至窗口上限，当发生用户交互后，分配数量则减至窗口下限，随后再逐步增加。 该算法能及时响应用户交互需求，调度费用相对较小： 针对m p e g 一4 基于形状编码的特点，提出了启发式的任务划分方法，以宏块作为数 据划分的最小单位，启发式地将需要编码的区域划分为与结点数目相同的多个子区域， 在保证各个结点负载基本均衡的前提下，整个系统所需存储的数据量最小； 论文最后给出了针对m p e g 一4 第十部分一h 2 6 4 提出的基于s l i c e 的并行算法。该 算法在s l i c e 的语法层次上进行数据的并行处理，将一帧划分为若干与结点数目相同的 s l i c e 。从而减少了各结点间的依赖关系。在满足用户播放需求的同时，充分挖掘各个结 点的计算能力，各结点间的负载平衡得到保证。 k e y w o r d s ：分布式多媒体系统同步模型p e t r in e t 并行编码m h p n i i a b s t r a c t i nd i s t r i b u t e dm u l t i m e d i as y s t e m ，t h ea d o p t i o no fm e d i as e r v e rb a s e do np a r a l l e l a r c h i t e c t u r e si st h em a j o rm e t h o dt od e a lw i t ht h ei n c r e a s eo fu s e r sa n di m p r o v et h eq o s c o m p a r e d w i t hs i n g l ep r o c e s s o rm e d i as e r v e r , t h em e d i as e r v e rs y s t e mi sc h a r a c t e r i z e db yi t s c o m p l i c a t e dt e c h n o l o g i c a lp r o c e s s a n d d i f f i c u l t y t om a i n t a i nt h e t e m p o r a l c o n s t r a i n t r e l a t i o n s h i p s b e t w e e nd i f f e r e n tm e d i ao b j e c t s ；i n a p p r o p r i a t e s c h e d u l i n ga l g o r i t h m s w i l l r e d u c et h ee f f i c i e n c yo ft h es y s t e m ；m e a n w h i l ew h e nm e d i a s e r v e rt a k e st h ea d a p t i v es o u r c e c o d i n gt e c h n i q u e s ，u n s u i t a b l ep a r a l l e lc o d i n gs t r a t e g y w i l lr e d u c et h es y s t e mp e r f o r m a n c e f h e r e f o r e ，t h i sd i s s e r t a t i o nm a k e s as t u d yo ft h es y n c h r o n i z a t i o na n dc o n s t r a i n tr e l a t i o n s h i p s i nd i s t r i b u t e dm u l t i m e d i as y s t e m ，t h es c h e d u l i n ga l g o r i t h ma n dt h ep a r a l l e lv i d e oc o d i n g t e c h n i q u e so f m e d i a s e r v e r s 1 1 1 ec o n t e n ti sm a i n l ya sf o l l o w s ： l 、i no r d e rt od e s c r i b ef u l l yt h et e m p o r a lc o n s t r a i n tr e l a t i o n s h i p so fd i s t i n c tm e d i a si n d i s t r i b u t e dm u l t i m e d i as y s t e m ，w ep r o p o s ean e wp o w e r f u ls y n c h r o n i z a t i o nm o d e l m h p n ( m u l t i m e d i a h i e r a r c h i c a lp e t r in e t ) c o m p a r e dt o o t h e rm o d e l s ，t h e p r i o r i t i e s o fm h p ni n c l u d es i m p l i c i t y , c l a r i t ya n d p o w e r f u li n t e r a c t i v ec o n t r o l l i n ga b i l i t y t h e s ep r o p e r t i e s e n a b l et h ed y n a m i cc h a r a c t e r i s t i c so f m u l t i m e d i am e s s a g ei nm u l t i m e d i as y s t e mt ob ed e s c r i b e dc o m p l e t e l ya n da l s ot h et e m p o r a l c o n s t r a i n ta n ds y n c h r o n i z a t i o nr e l a t i o n s h i p sa m o n gd i f f e r e n tm u l t i m e d i ao b j e c t s t ob e d e s c r i b e dc l e a r l ya n df u l l v i na c c o r d a n t ew i t ht h ed i s t i n c td e m a n d s a td i f f e r e n tl e v e l s ，m h p n i sa b l et ob u i l dh i e r a r c h i c a lm o d e l s i nl i g h to ft h et e m p o r a lc o n s t r a i n tr e l a t i o n s h i p sa n di n t e r a c t i o n sd e m a n d sb e t w e e ns e r v e r a n dc l i e n to ft h ed i s t r i b u t e di n t e r a c t i v em u l t i m e d i as y s t e m ，w ep r o p o s e das y n c h r o n i z a t i o n m o d e l ：d m h p n ( d i s t r i b u t e dm h p n ) w h i c h i sb a s e do nm h p na n dc a l lu n i f o r m l yd e s c r i b e t h e s y n c h r o n i z a t i o nr e l a t i o n s h i p s a n di n t e r a c t i o n si nd i s t r i b u t e dm u l t i m e d i as y s t e ma n d p r o v i d em o r ep o w e r f u l a b i l i t i e so f m e s s a g e c a p i t a t i o na n d c o n t r o l sa sw e l l 2 、b a s e do nt h ep e r f o r m a n c ea n a l y s i so fs c h e d u l i n ga l g o r i t h m so fm e d i as e r v e r , a q u a l i t y o r i e n t e da d a p t i v es c h e d u l i n ga l g o r i t h m ，w h i c h f o c u s e so np a r a l l e lm e d i as i g n a l p r o c e s s i n ga n dt r a n s m i s s i o n ，i sp r e s e n t e d i nt h i sd i s s e r t a t i o n w h e nt h em e d i as e r v e rp r o v i d i n ga d a p t i v eq o s ，t h es c h e d u l i n ga l g o r i t h m sa p p l i e dt o s e q u e n t i a lp r o c e s s i n g t a s ka r en o ts u i t a b l ef o r p a r a l l e l m e d i ap r o c e s s i n g ，b e c a u s et h a t m u l t i n o d e sm a yb ed e v o t e dt oo n es a m et a s k i na c c o r d a n c ew i t ht h e c h a r a c t e r i s t i c so f p a r a l l e lv i d e op r o c e s s i n ga n d t h er e q u i r e m e n t so nm i x e ds c h e d u l i n go fs e q u e n t i a la n dp a r a l l e l d a t ap r o c e s s i n gt a s k s ，t h eq u a l i t y o r i e n t e da d a p t i v es c h e d u l i n ga l g o r i t h ma s s i g nt h ep a r a l l e l t a s kt of e w e rc o m p u t i n gn o d e sa sf a ra sp o s s i b l e t h i sl e a d st oo v e r h e a dr e d u c i n go f d a t a i h 、 中国科学院博l 学位论文分布式多媒体同步0 并行编码技术研究 c o m m u n i c a t i o na n d t h r o u g h p u ti m p r o v e m e n to f m e d i a s e r v e r 3 、h a v i n ga n a l y z e dt h ep a r a l l e lv i d e oc o d i n gt e c h n i q u e so f m e d i as e r v e r , w ei n t r o d u c e d i s t i n c tg r a n u l a r i t i e sb a s e d p a r a l l e ls t r a t e g i e so f m p e g 一4 v i d e o c o d i n g i nt h ev o o r i e n t e da d a p t i v es c h e d u l i n ga l g o r i t h m ，t h ev i d e oo b j e c t sa r ed i v i d e di n t o p a r a l l e ls u b t a s k sa n ds e q u e n t i a ls u b t a s k sa c c o r d i n g t ot h e i re s t i m a t e dc o m p u t i n g r e q u i r e m e n t s t h es e q u e n t i a ls u b t a s k sa r ea s s i g n e dt ot h el o w e rp r i o r i t yn o d e s ；w h i c hl e a d st ot h eh i g h e r t h r o u g h p u to f t h ep a r a l l e ls u b t a s k sa n dr a t i o n a lu s eo ft h ec o m p u t i n gr e q u i r e m e n t so fu s a b l e n o d e sa n dr e d u c e st h eo v e r h e a do f r e s c h e d u l i n ga sw e l l i no r d e rt os h o r t e nt h es y s t e mr e s p o n s et i m eo f u s e s o p e r a t i o n sa n d r e d u c et h eo v e r h e a d o f s c h e d u l i n g ，as l i d i n ga l g o r i t h mw h i c hi n c o r p o r a t e ss o m ei d e a so f t h ep r o t o c o l so fv a r i a b l e s l i d i n gw i n d o w si sd i s c u s s e di nd e t a i li nt h i sd i s s e r t a t i o n b e c a u s eo f t h ec o n t i n u i t yo fu s e r s i n t e r a c t i o n ，t h es l i d i n ga l g o r i t h mg r a d u a l l yi n c r e a s e st h el o a dt h a ti sa s s i g n e dt ot h en o d e s t i l l i tr e a c h e st h eu p p e rl i m i t s a n dt h e nr e s e t st h ew i n d o ws i z et ot h ef l o o rl e v e la f t e ru s e r s i n t e r a c t i o n b u t g r a d u a l l y i n c r e a s e si t a g a i na f t e r w a r d s 1 1 1 ea l g o r i t h m i sa b l et o t i m e l y r e s p o n s e t h ed e m a n d so f t h eu s e r s ，t h e r e f o r eb o a s t i n gc o m p a r a t i v e l yl o w e ro v e r h e a d s a c c o r d i n gt o t h e p r o p e r t i e s o fs h a p e b a s e dv i d e oc o d i n g ，ah e u r i s t i ct a s k d i v i s i o n m e t h o di sa l s op u tf o r w a r di nt h i sd i s s e r t a t i o n w i 血m a c r o b l o c ka si l sm i n i m u m d i v i s i o nu n i t o fd a t a ，t h ec o d i n gr e g i o ni sd i v i d e di n t om a n ys u b r e g i o n s ，t h en u m b e ro fw h i c hi se q u a lt o t h en u m b e ro f c o m p u t i n g n o d e s 、i t l lt h ep r e r e q u i s i t eo fe n s u r i n gt h el o a db a l a n c eo fn o d e s ， t h ed a t as t o r e di n i ew h o l es y s t e mr e a c h e si t sm i n i m u m l a s t l y , t h e d i s s e r t a t i o ni n t r o d u c e st h es l i c e - b a s e d p a r a l l e l a l g o r i t h m sp r o p o s e d i n a c c o r d a n c e 谢t l lm p e gp a r t1 0 一h 2 6 4 t h ea l g o r i t h mc o n d u c t sp a r a l l e lp r o c e s s i n go f d a t aa t t h el e v e lo fs l i c ea n dd i v i d e so n ef r a m ei n t os e v e r a ls l i c e sw h o s en u m b e ri se q u a lt ot h a to f c o m p u t i n gn o d e s ，t h e r e f o r er e d u c i n g t h ed a t a d e p e n d e n c i e sa m o n g t h e s en o d e s i n c o n c l u s i o n s ，t h ea l g o r i t h mi sa b l et om e e tu s e r s d e m a n d sa n dm e a n w h i l ef u l l ym i n et h e c o m p u t i n gr e q u i r e m e n t so f e a c h n o d es oa st om a i n t a i nt h eb a l a n c ea m o n gn o d e s k e y w o r d s ：d i s t r i b u t e d m u l t i m e d i a s y s t e m ，s y n c h r o n i z a t i o nm o d e l ，p e t r in e t ，p a r a l l e l lc o d i n g ， m h p n i v 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并 表示、r 谢意。 作者签名： 彳华 日期： 2 粥唧罗口 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允 许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影 印、缩印或其它复制手段保存该论文。 储虢字华翩豁锄f 耘蹴聊岁 第一章绪论 第一章绪论 在分布式多媒体系统中，发展基于并行处理结构的媒体服务器是解决网络带宽、媒 体分发、磁盘读耿等制约单机媒体服务器发展瓶颈的有效途径。然而，与单机媒体服务 器相比，基于并行处理结构的媒体服务系统工作流程复杂；各媒体对象间的时域约束关 系难以维护；系统的服务能力与采用的调度算法息息相关：当服务器采取自适应编码的 方式提供服务时，不适宜的并行编码策略将降低系统的性能。 1 1 论文研究背景 多媒体数据是由在内容上相互关联的文本、图形、图像、动画、语音和活动图像等 媒体数据构成的一种复合信息实体。目前，多媒体应用已经涉及到生活的方方面面，而 随着计算机速度和网络带宽的提高，分布式多媒体服务如交互式v o d 视频点播、远程 会议系统、基于内容的数据库访问等得到了长足的发展。在这些服务系统中，信源( 信 息发送端) 和信宿( 信息接收端) 相处异地，需要用网络相连接，并且可能存在交互行 为( 如暂停、快进等) 。当用户数量较少和用户要求较低( 5 6 k b p s 的视频流) 时，分布 式多媒体系统中的媒体服务器大都以单机形式存在，与用户进行连接以及对所有媒体文 件的分发都在一台机器上进行，工作流程简单，实现容易。然而，随着用户需求的大量 增长和对点播质量的要求( 3 5 0 k b p s ) 越来越高，网络带宽、媒体分发能力、磁盘读取 能力等成为制约单机服务器性能的瓶颈，发展基于并行结构的媒体服务器是解决该问题 的一个方向。与单机媒体服务器相比，基于并行结构的媒体服务器在计算能力、磁盘读 取能力、带宽等方面进行了扩展。但相关的问题也应运而生，分散处于各个节点的媒体 数据的约束关系更为复杂；系统服务能力的高低与采用的调度算法息息相关；当服务器 采取自适应编码的方式提供服务时，不适宜的并行编码策略将降低系统的性能。 通常多媒体数据内部存在三种约束关系：基于内容的约束关系、空域约束关系和时 域约束关系。其中时域约束关系最为重要，如果时域特征遭到破坏，用户会遗漏或误解 多媒体数据所要表达的信息内容。如何表示多媒体数据的时域约束关系，以及在处理多 媒体数据的过程中如何维持时域特征，是多媒体同步研究的主要内容。而在分布式多媒 体系统中，除了媒体对象内的时域约束，媒体对象间的时域约束和用户交互的同步也是 分布式多媒体同步必须考虑的内容。 在基于并行结构尤其是基于高性能机群的媒体服务系统中，服务器通常由多个处理 结点组成，包含调度结点( 数目比较少，通常只有一个) 、计算结点两类，它们之间通 过一个高速内部网络互相连接，构成多结点的视频服务器结构。调度结点接收用户请求， 决定下一要处理的任务，并决策分派哪些计算结点处理该任务。计算结点则读取数据， 中国科学院博士学位论文一分布式多媒体同步与并行编码技术研究 进行处理。系统的性能是否良好，各结点阃的负载是否平衡，很大程度上取决丁r 调度的 策略如何。而大量网络接入方式的共存，导致用户有不同的带宽限制和不同的质量要求， 因此服务器有必要采取质量自适应的方式为用户提供服务。质量自适应的方式又可分为 多版本数据切换，扩展编码、自适应源端编码等方式，其中，自适应源端编码是最理想 的服务方式。但视频处理尤其是编码是一个复杂的计算过程，对处理器的能力要求很高， 利用多个结点并行处理视频是必然趋势。因此，服务端必须考虑并行任务的特点，采纳 合理的调度策略，才能保证系统处理能力的充分使用。 另一方面，多媒体标准的发展日新月异，从较低码率的h 2 6 1 、h 2 6 3 、逐步提高到 现在具有较高编码质量的m p e g - 4 、h 2 6 4 。但压缩比越高、所采用的编码技术越复杂、 编码所需的计算能力也就越高。而多媒体应用的绝大多数范围，如v o d 视频点播系统、 视频会议、交互式的视频游戏，基于内容的视频检索服务、基于内容的数据库访问、基 于压缩流的非线性编辑系统等大都有实时和交互要求。以视频点播系统为例，用户一般 希望够在一定的时间延迟内开始接收数据，随后可以实时地进行欣赏，网络状况较好时， 尽可能要求较好的质量，反之可能仅要求播放流畅或要求每帧的质量较好。在播放过程 中，还会有暂停、快迸等交互要求。然而，视频的编解码技术复杂，在现有技术条件下， 尽管处理器的性能在不断的提高，但单机的计算能力还是不能达到实时编码的要求；而 基于硬件的方式又不能随着标准的更新而与时俱进，无法满足多媒体用户的各种要求， 这就严重阻碍了视频标准的推广应用，并且进一步阻碍了整个多媒体产业的发展。 近年来，我国超级服务器领域成果迭出，其技术和产品已趋近成熟。曙光并行计算 机作为国家8 6 3 计划和中科院知识创新工程的重大成果。是一种通用的超级并行计算机 系统，是目前性能较高的国产超级服务器。它兼顾大规模科学计算、事务处理和网络信 息服务，是国民经济信息化建设的重大装备。基于曙光并行计算机，可生产出满足用户 各种需求的超级服务器产品。但总的来说，目前国内的高性能计算机主要还是应用在科 学计算上，在媒体服务方面的应用研究还比较少。因此，在曙光并行计算机上，开发分 布式媒体服务系统，提供如视频点播等媒体服务，以满足日益增长的用户需求，将解决 目前单机服务器所遇到的种种瓶颈。另一方面，自适应编码作为最理想的服务方式，需 要较高的计算能力，而曙光并行机作为基于高性能机群的超级服务器，其计算能力不仅 非常高，而且是可扩展的，这就为提供自适应编码服务的分布式多媒体系统提供了最好 的技术支持。 1 2 所面临的挑战 为分布式多媒体数据的同步关系建立合适的模型，有助于更好地、更准确地理解多 媒体同步问题：支持多媒体应用的行为验证；有利于正确描述和分析不同对象在整个系 统中的时空关系，使系统功能得到尽可能精确的描述。然而，对于分布式多媒体系统， 仅刻画服务端和客户端媒体对象内部的同步约束是不够的，同步模型还需要进一步提供 第一章绪论 描述客户端和服务端媒体对象之间时域约束关系和用户交互同步的能力，以约定同步机 制，维持分布式系统的时域特征。 现有的同步模型主要有基于时间间隔的同步描述。n 1 9 8 3 眦1 9 9 3 t w a h l l 9 9 4 。分层同步 描述【8 “。p “。1 9 9 0 1 。参考点同步模型8 “”2 l m e 9 9 0 1 ，以及p e t r in e t s 【m ”8 1 9 8 9 v u o n 9 1 9 9 5 等。 构建基于时间间隔模型的基本原理是描述对象的播出周期。两种时间削隔可以以十 三种不同的类型同步。如“b e f o r e ”，“a f t e r ”等。一种扩展的基于时间间隔的模型是基 于时间间隔关系，定义了2 9 种时间间隔关系，作为与多媒体播出相关的基本的时间问 隔关系。这是一个灵活的模型，允许播出的详细说明中带有许多运行播出变化。然而， 模型的定义过于复杂，不能直接描述媒体对象子单元问的关系。 在分层同步模型中，多媒体对象被认为是一个树，包含指示串行或并行外出子树的 节点，这样的模型运行对分层的自然支持，和交互对象的合成。然而，不适于描述媒体 对象内容的提取，需要对时间独立的媒体对象进行额外的定义。 参考点同步模型【b “”6 1 基于一个媒体对象播出的开始和结束时间。这样的描述允 许在个对象的播出期间的任何时刻进行同步：此外，具有不可预测周期的对象播出可 以被容易的集成。这种模型的缺点是遇到未知周期的对象将变得复杂。 o c p n ( o b j e c tc o m p o s i t i o np e t r in e t ) l i t t l e l 9 9 0 ，一个扩展的时间p e t r in e t 模型， 采用结构的方法使用整套的原语，足以刻画两个时间间隔间所有可能的时序行为关系。 然而，o c p n 没有提供描述对象内同步关系的能力：此外，在对多个数据流的同步关系 进行描述时，会引入大量的中间结构：在对多媒体数据进行演播时，可能引起数据的抖 动，并且不能描述用户交互、分布系统中的抖动以及细粒度的同步需求等。作为一个粗 粒度的同步规范，有待改进。 在o c p n 的基础上，国内外的许多研究者继续进行了进一步的扩展，其中，扩展的 对象合成p e t r i 网x o c p ne w 。1 9 9 4 】是一个精细粒度( 流内) 的同步规范，能够在较细粒度 上进行建模；时间流p e t r i 网t s p n 【“9 9 3 】能处理细粒度的同步和抖动要求；动态时间 p e t r i 网模型d t p n 9 胁“a k 8 1 9 9 习弥补了o c p n 模型没有动态描述用户交互控制能力的不 足，支持并描述典型的用户交互控制动作等。 尽管上述提到的同步模型具有各自的优点，但它们都没有提供统一描述分布式多媒 体系统中的时域同步和交互同步的能力，没有完整地描述分布式多媒体系统中多媒体消 息的动态特性，也没有考虑服务器端多结点并行处理同一任务时的同步关系，并且它们 提供的信息和控制能力都非常有限。 因此，为了模拟分布式环境下的多媒体对象的行为，有必要建立一个新的多媒体同 步模型，以正确描述和分析媒体对象在整个系统中的时域约束关系，支持多媒体应用的 行为验证，尽可能精确地描述系统功能，为产生合理的任务调度和并行处理方案而提供 强有力的支持。 与单机媒体服务器相比，基于高性能机群媒体的服务器在计算能力、存储能力等各 方面进行了扩展，而在服务器端进行自适应编码，为用户提供服务，能最大程度上适应 中国科学院 撙 学位论文，分布式多媒体同步与并行编码技术研究 用户带宽的不同和传输中的抖动，如果结点的计算能力足够，应该是最理想的服务方式。 但视频处理的复杂性较高，要达到实时的编码通常需要多个结点并行进行。那么在任务 到达时，系统应该根据其需要为其分配结点。但目前服务器的调度算法大都是针对单一 码流任务的，并没有考虑并行任务和串行任务混合的调度情况。在计算能力需求一定的 情况下，并行任务所分配给的计算结点越多，任务越零散，通讯和调度费用就越高。因 此，合理的任务调度算法，将分配给并行任务合适数目的结点，以充分利用系统的计算 能力，提高并行任务的处理能力，满足系统的需要。 在调度程序分派给并行任务一部分结点后，必须为该任务提出进一步的并行策略， 以决定任务在这些结点间如何并行执行，才能满足用户的要求。在分布式多媒体系统中， 若想保证客户端连续播放接收到的码流，服务端数据的发送速度不能低于客户端播放速 度。并且，当服务端采取自适应源端编码的方式为客户端进行服务时，编码的速度也不 能小于发送的速度。有了这些时域约束关系，可以利用同步模型，根据并行处理的具体 任务，分析决定所要采取的并行策略。 另一方面，提高视频的压缩编码速度，可以采取基于硬件的方法或基于软件的方法 【6 “2 0 0 2 】【a h m 柚2 0 0 2 】。前者速度快，造价低，但不灵活，不能适应编码系统新的开发要求； 而基于软件的方法相对灵活，便于升级，且在编码时。可以针对不同的应用配置不同的 参数，但编码速度较低。由于基于硬件的方式大都是面向专门的应用，并且灵活性较差， 因此，采取基于软件的方法并行实现视频的压缩编码，提高编码效率，将是必然的和可 行的。 通常执行速度的提高往往来源于处理器速度的提高。然而串行计算的性能总是有限 的，尽管单个处理器的性能在不断地提高，但要在短时间内达到视频的实时处理，远不 是单个串行处理器所能做到的，并行则利用了比单台计算机更优的性能。因此，在分布 式系统上采取基于软件的方式并行编解码是必然的，但由于新标准m p e g 一4 引入了对象 的概念，具有基于形状编码的特点，无法直接将m p e g 一2j o l l y ”9 9 9 1 等的研究成果应用于 m p e g 一4 的编码实现上。因此，不少学者根据m p e g 4 的自身特点，在调度策略、数据 划分方案、i o 调度等方面提出了许多新的方法。“。n 2 0 0 2 “】【“”0 3 触4 i 3 1 9 9 8 】 h a m o s f a k l m 8 1 9 9 9 l h e l 9 9 9 1 ”9 2 0 “j ，但研究的大多是基于硬件的并行方式或多线程并行方式，此外，随着新标准 h 2 6 4 的推出，针对h 2 6 4 的并行研究还是空白。 1 3 论文主要贡献 论文主要针对分布式多媒体系统中的同步约束关系，服务器端的调度算法和服务器 端的视频并行编码作了研究。具体包含以下内容： 1 3 i 多媒体同步模型m h p n 为了完整地描述多媒体系统中的时域约束关系，提出了一个新的多媒体同步模型 4 第一章绪论 m h p n ，该模型能够清楚地描述多媒体系统内部的时域约束关系，及时地捕获用户的交 互信息，完整地刻画不同对象间的同步关系，并可对模型的状态进行分析，验证多媒体 应用的行为，产生多媒体应用的同步运行方案：并且针对不同层次的同步要求，提供分 层建模的能力。 1 3 2 分布式多媒体同步模型d - m h p n 根据分布式多媒体交互系统中服务端和客户端之间的时域约束关系和用户交互需 求提出了d m h p n 分布式多媒体同步模型，该模型以m h p n 模型为基础，统一描述 分布式多媒体系统中的同步关系和交互行为，提供更加完整地信息捕获能力和控制能 力。 1 3 3 面向质量自适应的调度算法 基于对现有调度算法的分析，提出了面向质量自适应方式的调度算法。该算法考虑 到视频并行处理的特点，以及并行任务和串行任务混合调度的情况，在调度时尽量减少 分派给并行任务的结点数目，以降低任务并行执行时各结点间的通讯费用，提高系统的 性能，从而进一步提高了服务端任务的处理能力。 1 3 4m p e g - 4 并行编码技术研究 在对多媒体并行处理进行分析的基础上，针对m p e g 一4 标准媒体的并行编码策略进 行了研究，基于不同粒度的并行算法被提出，不同的算法既可以单独使用，也可以组合 使用： 提出了基于v o 的对象自适应的并行算法，该算法估算待编码视频对象所需的计算 能力，将其划分为并行子任务或串行子任务，调度时尽量将串行子任务分配到权值低的 结点上。相比以前提出基于v o 的并行算法，该算法不仅提高并行任务的处理量，合理 利用现有结点的计算能力，还能减少重新调度的次数及费用。 为了及时在较短的时间内响应用户的操作，减少调度本身所产生的费用。提出了滑 动调度算法，该算法借助于可变滑动窗口协议中的部分思想，考虑用户的交互行为在一 定的时i n 段内具有一定的连续性，在并行编码时，逐渐增加分配给各结点的数据量直至 窗【_ _ 】上限，当发生用户交互后，分配数量则减至窗口下限，随后再逐步增加。该算法能 及时响应用户交互需求，调度费用相对较小。 针对m p e g 一4 基于形状编码的特点，提出了启发式的任务划分方法，以宏块作为数 据划分的最小单位，启发式地将需编码的区域划分为与结点数目相同的多个子区域，在 保证各个结点的负载基本均衡的前提下，整个系统所需存储的数据量最小。 最后给出了针对m p e g - 4 第十部分提出的基于s l i c e 的h 2 6 4 并行算法。该算法在 s l i c e 的语法层次上进行数据的并行处理，将一帧划分为若干与结点数目相同的s l i c e 。 从而减少了各结点间的依赖关系。在满足用户播放需求的同时，充分挖掘了各个结点的 s 中囤科学院博】一学位论文一分布式多媒体同步t j 并行编码技术研究 计算能力，保证各结点间的负载平衡。 1 4 论文组织 论文章节安排如下 第一章即本章，介绍分布式多媒体系统中同步技术和并行编码技术的研究背景、 所面临的问题及论文的贡献。 第二章综述现有的多媒体同步技术、服务器端的体系结构、并行编码技术。 第三章提出多媒体同步模型m h p n ，用以描述多媒体系统中客户端和服务端内部 的时域约束关系。 第四章提出分布式多媒体同步模型d m h p n ，用以描述分布式多媒体系统中客户 湍和服务端间的时域约束关系，并给出用户交互行为模型。 第五章研究了分布式多媒体系统中的调度问题，提出了新的调度策略，并对任务 内部的并行处理做了分析。 第六章提出针对视频标准m p e g 4 和h 2 6 4 的多项并行编码策略：基于v o 的对 象自适应的并行编码算法、基于g o v 的滑动调度算法、启发式的数据划 分方法和基于s l i c e 的并行编码算法。 第七章总结及展望。 6 第二章分布式多媒体同步与并舒编妈技术概述 第二章分布式多媒体同步与并行编码技术概述 信息技术的革命引导了大量的创新应用和服务，如数字电视、广播，i n t e m e t 上的 声音传输、视频流、网络多媒体会议、虚拟课堂，个性化视频记录、基于内容的数据检 索等。与传统的文字、图像一样，多媒体数据在生活中不可或缺。然而，多媒体引入了 时问相关的媒体类型，必须在数据的处理中维持各种媒体对象间和对象内的时域约束关 系，才能保证数据不会遭到误解。另一方面，多媒体的数据量非常庞大，不采用压缩技 术，媒体数据的存储和传输都将成为严重的问题。而在数据的压缩过程中，不仅要保证 媒体数据间的同步约束关系，还要满足对处理能力的高需求，因此，采取并行的方式处 理多媒体数据成为必然。 2 1 分布式多媒体同步技术 通常将信息获取、处理、存储和播放都在一台多媒体计算机中进行的系统称为单机 系统。而将信息的提供者( 信源) 和接收者( 新宿) 相处异地、需要由网络相连接的系 统称为分布式多媒体系统。分布式多媒体系统中的同步问题远比单机系统复杂。 2 1 1 多媒体同步 多媒体数据是由在内容上相互关联的文本、图形、图像、动画、语音和活动图像等 媒体数据构成的一种复合信息实体，所包含的各种媒体对象间存在的约束关系可概括为 三种，基于内容的约束关系、空域约束关系和时域约束关系。其中时域约束关系最为重 要，如果时域特征遭到破坏，用户会遗漏或误解多媒体数据所要表达的信息内容。通常 多媒体同步所研究的主要内容就是如何表示多媒体数据的时域约束关系，以及在处理多 媒体数据的过程中如何维持时域特征，并称完成此项工作的机制为同步机制。 按同步涉及的对象，多媒体同步分为三类：媒体内同步、媒体间同步和人机交互同 步； 1 ) 媒体内同步：指时间相关媒体内各个媒体元素间的时间同步关系。如视频 序列中各个图像之间的时间关系。若速率为2 5 帧，秒，则每帧的显示时间为4 0 m s 。 2 ) 媒体间同步：指不同媒体间的时间同步。可以是不同的时间相关媒体间的， 如音频与视频的“唇同步”；也可能是时间无关媒体与时间相关媒体通过后来建立的