（信息与通信工程专业论文）基于mpsoc针对媒体应用的可变粒度并行化方法研究.pdf

浙江大学硕士学位论文摘要 摘要 近几年多核处理器获得了飞速发展，广泛应用在个人电脑、嵌入式系统和高 性能计算等领域。多处理器片上系统( m p s o c ，m u l t i p r o c e s s o rs y s t e m o n c h i p ) 集成了多个处理器核，通过应用程序的并行执行获得较高的执行效率，能够满足 多媒体、通信、网络安全等嵌入式领域在高性能、实时性和有限存储空间等方面 的需求，代表了片上系统( s y s t e m o i l c h i p ，s o c ) 在多核时代中的最新发展方 向。 m p s o c 的硬件发展较为迅速，但相关的软件编程问题，特别是针对具体硬 件开发串行c 代码中的并行性的问题日益突出。目前尚不存在一种完全自动化 的并行编程模型，大多是通过开发人员重新编写并行程序或者修改已有串行程序 产生可执行的并行代码。这种方法开发成本较高、周期较长，对开发人员的要求 也较高。 针对上述问题，本文提出一种源到源的并行化方法，将串行c 程序转化为 并行c 程序。该方法具有丰富而强大的分析、变换能力，并在通用模型的基础 上专门针对媒体应用进行优化，不仅降低了程序开发人员的工作量，而且能较大 程度地开发出媒体应用的并行性。 本文提出的并行方法首先对原始串行c 程序进行静态、动态相结合的依赖 分析，并以一种新的可变粒度数据流图s g d f g ( s c a l a b l eg r 血d a t af l o wg r a p h ) 的形式保存；然后实施层次化的任务调度，采用逐步求精的方法获得多种不同粒 度的并行方案；并通过评估产生满足目标硬件结构约束和媒体应用需求的最终并 行方案。最后，本文以广泛采用的t 2 6 4 为对象，通过对其串行程序的并行化对 所提出的方法进行测试和验证。实验表明，本文提出的方法在包含三个处理器核 的硬件平台上可以获得高达1 9 3 的加速比，具有良好的并行化能力。 关键词并行编程，可变粒度，任务调度，媒体应用，m p s o c 浙江大学硕士学位论文a b s t r a c t a b s t r a c t r e c e n t l y , m u l t i c o r ep r o c e s s o r sk e e pi n c r e a s i n gd e v e l o p m e n t ，a n dh a v eaw i d e r a n g eo fa p p l i c a t i o n si np e r s o n a lc o m p u t e r , e m b e d d e ds y s t e m ，h i 曲p e r f o r m a n c e c o m p u t i n g ，e t c m p s o c ( m u l t i p r o c e s s o rs y s t e m o n c h i p ) h a sm u l t i p l e c o r e s e x e c u t i n gc u r r e n t l yt oi m p r o v ee f f i c i e n c yo fs o m ea p p l i c a t i o n s ，a n ds a t i s f i e st h e r e q u i r e m e n to fm u l t i m e d i ac o m m u n i c a t i o n ，n e t w o r ks e c u r i t y , e t c m p s o ci s c o n s i d e r e da st h en e ws o l u t i o ni ns o c c o n t r a r yt ot h eh a r d w a r ed e v e l o p m e n ti nm p s o c ，t h es o f t w a r ep r o g r a m m i n gp r o b l e m , e s p e c i a l l yt h ep a r a l l e l i z a t i o no fs e q u e n t i a lcc o d e sf o rs p e c i f i ch a r d w a r eh a sb e c o m ei n c r e a s i n g l y p r o m i n e n t t h e r ei sn oa u t o m a t i cp a r a l l e lp r o g r a m m i n gm o d e ln g h tn o w i n s t e a d , t h ec o m m o n w a yi st od e v e l o pn e wp r o g r a mo rm o d i f yt h ee x i s t i n gl e g a c ys e q u e n t i a lcc o d et og e n e r a t e p a r a l l e lr o u t i n e ，w h i c he x t e n d st h ed e v e l o p m e n ta n dc y c l eh e a v i l y , a n dh a sah i 曲r e q u i r e m e n to f p r o g r a m m e r t a r g e t i n gt h ea b o v ei s s u e s ，t h i st h e s i sp r o p o s e sas o u r c e t o - s o u r c ep a r a l l e l i z a t i o n m e t h o d ，w h i c ht r a n s f o r m sc c o d ef r o ms e q u e n t i a lt op a r a l l e l n l i sm e t h o dd e f i n e s n u m e r o u sa n dp o w e r f u la n a l y s i s ，t r a n s f o r m a t i o nm o d u l e s ，a n dm a k eo p t i m i z a t i o nf o r m e d i aa p p l i c a t i o n ss oa st or e d u c et h ei n v o l v e m e n to fp r o g r a m m e r sa n de x p l o r em o r e p a r a l l e l i s mo fm e d i aa p p l i c a t i o n s t h ep r o p o s e dm e t h o d ，f i r s t l yp e r f o r ms t a t i c d y n a m i ca n a l y s i so nt h eo r i g i n a l s e q u e n t i a lcc o d et og e n e r a t es g d f g ( s c a l a b l eg r a i nd a t af l o wg r a p h ) t h e n ， s c a l a b l eg r a i nt a s k sa r eh i e r a r c h i c a l l ys c h e d u l e dt og e n e r a t ev a r i o u sp a r a l l e l i z a t i o n p l a n so fd i f f e r e n tg r a i n sb ys u c c e s s i v er e f i n e m e n t a n dt h ef i n a lp a r a l l e l i z a t i o nr e s u l t i sc h o s e nt os a t i s f yt h ec o n s t r a i n t sa n dr e q u i r e m e n t so ft a r g e th a r d w a r ea r c h i t e c t u r e a n dm e d i aa p p l i c a t i o n s a tl a s t ，t 2 6 4i sc h o s e nt ob ep a r a l l e l i z e df o rv e r i f y i n gt h e p r o p o s e dm e t h o d n l ee x p e r i m e n ts h o w st h a tt h es p e e d u p1 9 3i sg a i n e do nt h e m u l t i c o r ep l a t f o r mw i t ht h r e ep r o c e s s o r s ，w h i c hp r o v e st h a tt h ep a r a l l e l i z a t i o n m e t h o dp r o p o s e dc a na c h i e v eag o o dp e r f o r m a n c e k e yw o r d s ：p a r a l l e lp r o g r a m m i n g ；s c a l a b l eg r a i n ；t a s ks c h e d u l i n g ；m e d i aa p p l i c a t i o n s ；m p s o c i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得浙江大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：警虱吱j 灸 签字日期： 7 t o 年3 月7 日 学位论文版权使用授权书 本学位论文作者完全了解浙江大学有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以 将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：i j 幻丢氙 导师签名： 头卟 签字日期：砂卜年3 月7 日 签字日期：如，。年岁月夕日 浙江大学硕士学位论文致谢 致谢 研究生生活就要结束了，在此我要特别感谢敬爱的导师史册副教授，感 谢她对我的谆谆教诲和悉心关怀。两年来，无论是研究工作还是日常生活，史老 师都给予我很多关心和指导。在史老师言传身教的影响下，我逐步学会了科学研 究的基本方法，建立起严谨的科研精神和实事求是的科研态度。史老师兢兢业业 工作和严谨治学的高尚品格给我留下了极为深刻的印象，而且史老师对我在为人 处世和未来发展方面提供了许多非常宝贵的建议，让我终身受用。 这里我还要向尊敬的姚庆栋教授表示崇高的敬意和诚挚的感谢。姚老师虽年 事已高，但不辞劳苦，在研究工作中亲临指导，给予我极大的帮助。姚老师深厚 的学术底蕴，一丝不苟的工作作风，对科研方向的高瞻远瞩使我高山仰止。姚老 师坚韧的科研品质，高尚的道德情操将是我永远学习的榜样。 同样感谢刘鹏老师、王维东老师给我的指导和帮助。两位老师的严谨的治学 态度、对科研的热忱都给我留下了极为深刻的印象。 感谢与我奋战了两年多的姚懿鹏、李橙、徐志远同学，在与他们合作的过程 中我感受到了“头脑风暴 对思维启迪的重要作用。感谢王小航师兄在并行化编 程软件设计方面对我的帮助，感谢顾雄礼师兄在硬件平台方面对我的指导，感谢 海冰师兄分享c 语言和仿真器设计经验，感谢蔡卫光博士、夏冰洁博士和其他 朋友对我的关怀。 此外要特别感谢我的家人，感谢父母的鼎立支持。没有你们的鼓励和无私奉 献，我的人生道路将变得暗淡无光，曲折坎坷。 感谢所有关心、支持、帮助过我的良师益友! 陶文质 2 0 1 0 牟1 月于术是圄 浙江大学硕士学位论文绪论 1 绪论 随着多核处理器的飞速发展，m p s o c ( m u l t i p r o c e s s o rs y s t e m o n - c h i p ) 已经 成为片上系统( s y s t e m - o n c h i p ，s o c ) 发展的新方向。m p s o c 在硬件上将多个 异构处理器核心集成在同一块芯片上，提供了并行计算的能力，有助于提高程序 的执行效率。硬件结构的变化要求传统的串行软件编程模型转化为并行编程以适 应新的硬件环境。遗憾的是，与硬件并行系统的成熟相比，软件并行化技术较为 滞后。目前学术界和工业界虽然已经提出了多种并行化方法，但自动化程度较低， 而且缺乏通用模型。 媒体程序作为嵌入式系统的一种重要应用，具有丰富的潜在并行性，但同样 缺乏高效的方法来充分发挥m p s o c 的优势。为了突破落后软件模型对并行计算 能力的束缚，本文对基于m p s o c 的媒体程序并行化方法进行研究，希望有助于 并行编程模型的发展和完善。 本章将对多核处理器，并行编程模型，以及基于m p s o c 的媒体应用的并行 化技术进行介绍。此外，通过对国内外的相关研究现状的阐述，指出目前并行化 中存在的问题，同时针对这些问题提出一种可变粒度的并行化方法，并对该方法 的模块和基本流程进行概括阐述。 1 1 多核处理器简介 并行编程问题主要考虑如何安排软件的组织结构和实现方式以充分利用硬 件的并行计算能力从而提高执行效率。实现并行程序设计的四要素是：并行体系 结构、并行系统软件、并行程序设计语言和并行算法。其中并行体系结构是一切 并行编程问题的基础【1 】。 自上世纪七十年代末以来，并行体系结构发展很快。从早期的向量机，到基 于局域网的工作站集群( w o r k s t a t i o nc l u s t e r ) ，再到上世纪九十年代末基于因特 网的分布并行计算系统，以及目前的多核处理器，并行处理机的性能越来越高， 结构也越来越复杂。不同的硬件结构要求使用不同的软件并行技术，因此对并行 编程模型的研究必须首先明确硬件的并行体系结构。 1 9 7 2 年，m i c h a e lf l y n n 根据计算机系统中的数据流和指令流的数量将计算 机的体系结构分成了四类：s i s d ( s i n g l ei n s t r u c t i o ns i n g l ed a t a ) ，单指令流单数 1 浙江大学硕士学位论文绪论 据流；m i m d ( m u l t i p l ei n s t r u c t i o nm u l t i p l ed a t a ) ，多指令流多数据流；s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l ed a t a ) ，单指令流多数据流；m i s d ( m u l t i p l ei n s t r u c t i o ns i n g l e d a t a ) ，多指令流单数据流。这就是著名的f l y n n 分类。 其中s i m d 技术在多媒体领域中的应用非常广泛，存在于多数通用处理器 中，且已有多个扩展版本，如i n t e l 推出的s s e ( s t r e a m i n gs i m de x t e n s i o n s ) 2 、 s s e 2 、s s e 3 1 3 、s s e 4 1 4 ，a m d 的3 d n o w ! 5 】，s u nu l t r a s p a r c 处理器的v i s 6 】 等等。s i m d 属于细粒度( f i n eg r a i n ) 指令级并行( i l p ，i n s t r u c t i o nl e v e l p a r a l l e l i s m ) 。i l p 的技术目前已经非常成熟，除了s i m d 之外还有深度流水( d e e p p i p e l i n e ) 、投机( s p e c u l a t i o n ) 、分支预浸j j ( b r a n c h p r e d i c a t i o n ) 、超标( s u p e rs c a l a r ) 7 等。但成熟的同时也意味着进一步发展的空间不大，而且受到了m e m o r y 和 c p u 之间速度差异日益增大的严重制约。 而多核处理器的诞生带来了并行体系结构新的发展：多处理单元不再基于局 域网或者电路板通信，而是可以直接集成在同一个处理器上。这大大降低了处理 器核间的通信开销，同时也提供了粗粒度( c o a r s eg r a i n ) 并行的新方向。下面 将首先介绍多核处理器的发展现状，然后总结当前多核处理器的并行编程技术。 1 1 1 多核处理器的发展现状 半导体工艺技术的飞速发展和计算机体系结构的不断进步是推动徽处理器 性能不断提高的两个重要因素。传统的单核处理器，为了提高性能采用增加逻辑 设计复杂度和c p u 主频的方法，但却面临着功耗上升的难题，而且c p u 和存储 体工作频率的差距导致处理器不得不耗费大量时钟周期用于存储体访问 8 】。因 此需要在体系结构的框架内进行创新以便推动微处理器的进一步发展。 目前有两种新的解决办法：同时多线程( s i m u l t a n e o u sm u l t i t h r e a d i n g ，s m t ； i n t e l 称之为h y p e r - t h r e a d i n g ，超线程) 和芯片级多重处理技术( c h i p - l e v e l m u l t i p r o c e s s i n g ，或c h i pm u l t i p r o c e s s i n g ，c m p ) 9 。 实现s m t 的处理器称为多线程处理器，比如i n t e l 的f o s t e r x e o n 系列芯片。 s m t 处理器在硬件上增加独立的一套指令指针、寄存器别名表、返回栈指针、 高级编程中断控制器。这种特殊的硬件结构，在软件和操作系统的角度来看，单 c p u 表现为两个或更多的逻辑c p u 。逻辑c p u 间共享c a c h e 、总线等重要资源。 当一个线程在执行过程中遇到长延时( 1 a t e n c y ) 的情况，如：对内存数据进行读 浙江大学硕士学位论文 绪论 写操作、访问i o 、出现c a c h e m i s s 等，该线程将被挂起；而另一条线程开始执 行。这样，可以隐藏c p u 为等待数据而进行的空转，充分利用了计算资源。 采用c m p 技术的处理器又称为多核处理器( m u l t i c o r ep r o c e s s o r s ) ，即在 一块芯片上集成多个运算核心。核心又称内核( c o r e ) ，c p u 所有的计算、接受 存储命令、数据处理都由核心完成。核心有其固定的逻辑结构，包括一级缓存、 二级缓存、执行单元、指令集单元和总线接口等。多核处理器相对于传统的超标 量( s u p e r s c a l a r ) 和超长指令字( v l i w ，v e r yl o n gi n s t r u c t i o nw o r d ) 具有更好 的并行度，处理器内部的多个核心可以并行运行线程，提高了线程级并行 ( t h r e a d 1 e v e lp a r a l l e l i s m ，t l p ) 的程度。此外，多核处理器与多线程处理器模拟 多个逻辑c p u 有本质的不同：多核处理器的多个核心是物理上真实存在的，每 个核心都可以单独执行一个线程，可以实现真正意义上的多线程并行执行，而非 多线程处理器那种通过线程调度来模拟多个内核。多核处理器主要有两个优点： ( 1 ) 不需要依赖复杂的功能部件，逻辑结构比较简单。晶体管的利用率高。同 等规模的集成电路，多核处理器与单核相比可以得到更大的并行度。( 2 ) 由于多 核的频率较低，因此功耗比使用相同晶体管数目的单核处理器低。多核处理器按 照其核心结构可以分为异构和同构两种。异构多核处理器是在同一芯片上集成两 种及其以上的内核，比如i b m 公司的c e l l 1 0 处理器；同构多处理器是在同一芯 片上集成多个结构相同地位对等的内核，比如m o n t e c i t o 处理器 1 1 。 结合s m t 和c 技术的处理器称为多核多线程处理器( m u l t i c o r e m u l t i t h r e a dp r o c e s s o r s ) ，即一块芯片上集成多个处理器内核，每个内核具有多 线程的特点，能够并行执行多个线程。这种处理器兼具s m t 和c m p 技术的优 势，不仅具有多核处理器结构简单、并行性高的特点，又可以利用多线程技术来 消除内核之间的通信延迟以及过长的指令执行延迟。s u n 公司的u l 仃a s p a r c t 2 1 2 是这类处理器的杰出代表。 m p s o c 则是多核处理器在片上系统领域的发展方向，也是本文研究的并行 化方法面向的目标硬件。下节将对m p s o c 硬件的发展现状进行详细介绍。 1 1 2m p s o c 研究现状 嵌入式的传统应用领域，比如移动通信，要求处理器以单芯片形式实现以便 在尽可能低的硬件成本和功耗达到应用需求。s o c 能够很好的满足这种要求。但 浙江大学硕士学位论文绪论 现今的嵌入式应用除了复杂度显著提升，对可编程能力的要求也目渐增高，比如 j a v a 语言驱动的微型设备的广泛流行等。提供可编程能力的唯一方法就是保证系 统有一定的时间开销用于处理可编程组件( c o m p o n e n t ) 。而单芯片的s o c 由于 计算资源的限制根本无法满足这种需求，可行的解决途径就是提供多个处理器核 心，能够在同一时刻处理多个不同的任务。这也是m p s o c 出现的基本原因。 m p s o c 将多个处理器核集成在同一块处理器上，是v l s i 技术在当今嵌入 式领域的重要应用之- - 1 3 ，1 4 。由于面向嵌入式应用，因此其设计过程中必须 解决以下问题：满足实时性需求，而非简单提高计算能力低功耗低成本。 这三个问题与具体应用的特点密切相关，m p s o c 在设计过程中必须根据性能需 求仔细考虑硬件模块的搭建，尽可能裁减掉无用的硬件模块以降低功耗和成本。 而普通的多核处理器在设计过程中主要考虑如何增加晶体管密度以将更多的处 理器核集成在同一块芯片上，应用需求的限制则放在次要地位。这种差别导致 m p s o c 与普通多核处理器相比具有若干特有的属性： 1 、应用驱动系统设计 m p s o c 设计是市场导向的，即目标市场的特点、利润率限制了硬件的成本 并提出了性能的要求。目前m p s o c 的主要应用领域有三块：多媒体、网络和通 信。这些应用领域具有很高的灵活性，相关软件的算法设计通常会有较为频繁的 变动，而且对功耗、实时性和吞吐量( 单位时间数据信息的处理数量) 要求较高。 这些特点要求m p s o c 必须具有可编程、实时处理等能力。 2 、复杂的存储体系结构 m p s o c 具有异构的内存系统：每个处理器可以具有私有的片上存储空间， 也可以在硬件系统中开辟若干存储空间允许某一个或几个处理器共同访问。存储 体也是多种多样的，可以将c a c h e 、s r a m 、s d r a m 、硬盘、光驱、磁带等结构 集成在同一个系统内部。而且处理器对存储体的访问方式也是多样的，可以通过 总线、d m a ( d i r e c t m e m o r y a c c e s s ) 或者片上网络( n o c ，n e t w o r k s o n c h i p ) 通信。不同存储体的带宽、时延也可以不同。这种复杂的存储可以提供较高灵活 性、降低硬件成本，但增加了硬件和软件的设计难度。开发人员不得不考虑不同 存储结构之间的通信、同步、时延等问题。 3 、特殊的处理单元 浙江大学硕士学位论文绪论 应用程序通常是多样的，某些应用也许可以通过特殊的c p u 指令进行加速。 如果能够提供可编程的处理器，或者针对应用将多种不同指令的处理器集成起来 则能够有效地提高程序的执行速度。所以m p s o c 通常是异构的，这些处理器会 在指令集、字宽、c a c h e 大小等方面有所差别，甚至会集成多种不同的硬件加速 器，具体的选择则应根据应用特点而定。 4 、软硬件协同设计 由于m p s o c 的硬件设计由软件驱动，那么必须为m p s o c 提供嵌入式软件 和硬件之间的接口，并最终实现软硬件协同设计( h w s wc o d e s i g n ) 。该接口具 有以下能力：实现软硬件的并发设计，缩短开发周期实现软硬件的模块化设 计，提供可扩展性及灵活性便捷的验证能力，验证硬件设计的正确性和软件的 服务质量( q o s ，q u a l i t yo f s e r v i c e ) 。 上述特点要求m p s o c 将多种不同类型的处理模块集成起来，以降低硬件复 杂度和功耗，同时具有较高的可配置型和灵活性。目前m p s o c 的种类较多并且 繁杂，主要是根据具体应用领域进行划分。比如 1 5 1 提出一种异构的m p s o c ，由 一个r i s c 主控核与一个m b e ( m a c r ob l o c ke n g i n e ) 组成，用于加速m p e g - 4 的 解码工作。a r m 公司推出的c o r t e x a 9m p c o r e 可集成l 或4 个单核c o r t e x a 9 处理器，适合于复杂操作系统和用户应用程序处理的需求 1 6 。 1 1 3m p s o c 媒体应用并行编程 m p s o c 的并行体系结构要求有相应的并行软件系统与之相适应。并行软件 系统可分为以下两大类：并行系统软件和并行应用软件。 ( 1 ) 并行系统软件。并行系统软件指挥、协调并行计算机运行，包括并行操作 系统和并行编译系统两大部分。操作系统提供高层软件与底层硬件之间的接口， 实现程序执行所需的基本操作，如任务的创建和终止、锁同步、两点之间的消患 传递等。并行编译系统则基于操作系统提供的底层支持来实现对程序并行执行的 高层支持，包括任务划分、调度，任务组机制和处理器拓扑机制等。 ( 2 ) 并行应用软件。即解决实际应用问题且能够并行执行的程序。应用软件种 类很多，比如：科学计算库软件、图形软件、可视化软件、数据库软件等。 本文选择媒体程序作为目标并行应用软件，主要研究基于m p s o c 的针对媒 体程序的并行化方法。其中并行编译系统是本文的主要研究对象。下面分别介绍 浙江大学硕士学位论文绪论 媒体应用的基本特点，以及媒体程序并行化的研究现状： l 、媒体程序的基本特点 媒体处理是嵌入式系统的重要应用领域。人们对多媒体需求的增长促进了各 种媒体处理技术的产生，而随着数字电视、网络流媒体和d v d 视频技术的普及， 视频压缩已经成为广播、娱乐媒体中至关重要的问题。视频压缩技术历经十多年 的发展，先后推出了m p e g 1 、m p e g 2 、m p e g _ 4 、h 2 6 4 和a v s 等标准。这 些标准为数字电视的信息压缩和传输提供了越来越高效的实现方法，但结构也越 来越复杂【1 7 】。总结起来媒体处理的主要特点 1 8 有： 以数据流的形式进行处理，存在丰富的流水并行性； 较小的数据类型，一般媒体数据类型只有8 位( 如图像) 或1 6 位( 如声音) ； 较强的实时性要求： 多个并发的媒体流； 2 、媒体程序并行化的研究现状 当今很多媒体应用己经超越了传统处理器的处理能力，媒体处理系统需要更 大的灵活性和计算能力以充分支持多媒体应用。一方面，媒体处理器可以进行多 媒体扩展( m u l t i m e d i ae x t e n s i o n ，m m e ) ，比如通过s i m d 技术来提高指令并行 的能力，该技术目前的发展已经日臻成熟。另一方面，媒体处理器可以使用 m p s o c 在粗粒度级别提高媒体程序的执行效率。但m p s o c 体系结构灵活性较 大，而且使用了复杂的存储结构，导致细粒度并行引起的频繁数据交互会产生较 大的通信开销，从而影响并行性能。粗粒度线程级并行的数据传输、同步开销小， 对并行性的提高非常有利。 应用程序的并行性开发包括程序内部依赖关系分析、任务划分、调度及代码 生成 1 9 】等部分。m p s o c 的并行编程模型目前通常采用编译器静态自动分析，或 人工干预下的动态剖析来获得依赖关系，然后采用多线程、或并行编程语言、或 并行化编程接口来开发循环级、基本块级或函数级的并行性。如 2 0 研究了多核 处理器上针对m p e g 2 、m p e g - 4 和h 2 6 4 编码程序的线程级并行，来减少功耗 和动态指令的数量。 2 1 1 提出了一种面向嵌入式领域的并行化集成开发环境，采 用源到源的方法，针对c 源程序开发粗颗粒度的并行性。通过静态动态分析与 剖析相结合的方法获得程序的基本结构信息，并在硬件目标抽象的基础上完成代 浙江大学硕士学位论文 绪论 码划分最终产生并行化的c 代码。 2 2 针对嵌入式异构多核处理器提出了一种软 件设计流程，采用从高到低逐层抽象的方法，对应用程序和硬件进行表示，最后 产生面向具体硬件的软件实现。 3 、媒体程序并行化存在的问题 虽然上文介绍了媒体程序在m p s o c 环境下的多种并行化方法，但其大都要 求开发人员根据目标硬件体系结构和应用程序特点重新编写代码或者对已有串 行代码做大量改动，而且缺乏统一有效的编程方法，导致开发周期较长、成本较 高。此外媒体处理的算法实现多采用c c + + 语言，并且已经存在大量的应用代 码，如果将这些代码全部重新编写，手工并行化，其工作量将是非常巨大的。总 结起来目前针对嵌入式媒体处理程序的并行化开发存在以下问题： c c + + 对指针和动态内存管理的支持导致依赖关系分析复杂。因此，主要针 对f o r t r a n 的p o l a r i s 2 3 、s u i f 2 4 等并行分析工具及其方法，不能直接用于 c c + + 。目前尚缺乏能自动提取c c + + 程序并行性的分析工具及方法 2 5 】。 嵌入式系统在存储方面存在着非常苛刻的要求，适用于科学计算、数据库、 互联网等领域的分析工具和方法不能直接用于嵌入式媒体处理应用领域。 在信息表达与显示方面，缺少一种统一、综合和可视化的方法，能将散布在 数据流图、控制流图和任务图中的各种依赖关系、计算代价、通信代价等信 息综合起来，并显示给开发人员。 依赖分析多采用静态分析在编译阶段进行，而动态剖析方法通常发生在评估 测试阶段。静态分析与动态分析的割裂，使开发人员不能尽早获得程序内部 精确的数据依赖关系，无法在并行化处理的早期进行有目的的引导。 所以有必要研究一种并行化方法，以较高的自动化程度将已有的媒体处理程 序从串行执行转化为并行执行，且应具有良好的可扩展性和并行化能力。 1 2 可变粒度并行编程简介 1 2 1 并行编程简介 基于上述讨论，本文主要研究针对m p s o c 的媒体程序的并行化方法。并行 编程的目的是设计、研究并行软件系统的实现方法和组织结构，确定并行应用软 件和并行系统软件的交互关系 1 】。并行编程所涉及到的主要问题有以下几点： 浙江大学硕士学位论文绪论 ( 1 ) 并行模式。即是否支持s i m d ，m i m d 或数据并行、控制并行等，此外还 要注意程序设计语言所支持的并行模式的适用范围，也就是说要注意编程语言所 支持的并行体系结构。另外目标应用自身的特点也直接决定了所应实施的并行模 式。比如媒体应用特点如果是数据源以流的形式依次经过不同的处理环节而产生 最终结果，那么较适合流水并行。 ( 2 ) 并行操作的粒度。粒度是并行执行的任务大小的度量。目前并行操作的粒 度按照程序结构元素划分，从粗到细可分为：程序级( a p p l i c a t i o n 1 e v e l ) ，子程 序级( 又称任务级，t a s k 1 e v e l ) ，线程级( t h r e a d 1 e v e l ) ，循环级( l o o p 1 e v e l ) ， 块级( b l o c k 1 e v e l ) 和语句级( s t a t e m e n t 1 e v e l ，或称为指令级i n s t r u c t i o n 1 e v e l ) 。 但程序计算量以时间开销体现，而在c 语言中函数由语句调用实现，函数调用 语句的执行开销其实与被调函数相同。所以单纯从程序结构元素角度划分粒度是 欠妥的。本文认为应以计算量为粒度衡量的准则，具体划分方法请参考后续说明。 ( 3 ) 并行任务之间的通信模式。并行任务之间的通信模式包括：共享变量和消 息传递。消息传递模式又包括同步通信和异步通信。多线程、o p e n m p 2 6 属于 共享变量模式，m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 2 7 是一种编程接口标准，是基 于消息传递的并行编程技术。 对上述三种问题解决方法的不同就导致了不同并行编程模型的产生，总结起 来可以分为以下几类：1 、改变或扩展已有的编程语言，建立并行编程接口。如 p t h r e a d 2 8 ，m p i ，o p e n m p 等。2 、开发新型并行编程语言，如s t r e a m l t 2 9 ， c i l k 5 1 3 0 等。上述两种方法需对已有的串行程序进行大量改动，甚至重新编写， 开发成本较高。3 、使用事务型存储器( t r a n s a c t i o n a lm e m o 巧，t m ) 。t m 的存 在可简化并行过程中的数据同步和有效性问题，但技术尚不成熟，其正确性和性 能有待于进一步研究【3 1 。4 、自动化并行编译技术。目前除了科学计算中的循 环并行，尚无其它成熟技术。这主要是因为缺乏集成化的分析和优化工具，同时 串行的程序设计模式增加了并行化思考的难度【3 2 】。5 、人工分析、使用汇编或 其它语言编写通信同步接口。如使用汇编、c 混合编程开发并行程序，这种方法 在嵌入式系统得到广泛应用。6 、将多种分析和变换技术结合起来，建立起集成 开发环境，以人机互动的方式实现程序的并行化。如m a p s 2 1 基于l a n c e 编 译器 3 3 ，对串行c 源代码进行动态和静态相结合的依赖分析生成耦合块 浙江大学硕士学位论文 绪论 ( c o p u l e db l o c k ) ，然后将耦合块聚合为任务并生成对应的并行c 代码。 3 4 】提 出了针对多媒体和网络应用的编程模型，该框架基于a g a s s i z 并行编译器，可以 将c o m p o n e n t c 流语言编写的代码转化为传统c 代码，再由g c c 编译各子c 程 序产生符合目标机要求的可执行程序。m u l t i f l e x 3 5 , 系统由分布式系统对象组件 ( d i s t r i b u t e ds y s t e mo b j e c tc o m p o n e n t ，d s o c ) 和对称式多处理器( s y m m e t r i c a l m u l t i p r o c e s s o r ，s m p ) 模型构成。该模型需要开发人员重新编写代码，根据具体 应用使用c c + + 将并行性以d s o c 和s m p 的形式表示出来。 并行编程的难点在于如何针对目标应用，选择合适的并行模式，并在此基础 上识别和划分对应的并行粒度。无论是使用新的并行编程语言开发，还是把已有 的串行程序转化为并行程序，都需要解决这些问题。本文的重点在于把串行c 代码编写的媒体程序转化为针对m p s o c 的可并行执行的c 代码，是一种源到源 的并行化方法。下面分别介绍本方法所面向的硬件模型以及软件编程方法。 1 2 2 目标硬件模型 m p s o c 种类繁多，本文面向的目标硬件模型具有异构和主从式的特点，由 1 个主控r i s c 核与n ( n 1 ) 个d s p 核组成；存储则以分布式为主，辅以少量 共享内存，因此属于混合式存储结构；各个核通过片上网络( n o c ) 互连，但目 前使用的平台通过总线互连，通过d m a 进行数据传递的。如图1 1 ( a ) 所示。 i b 图1 1 目标硬件平台 浙江大学硕士学位论文绪论 图1 1 ( a ) 中所有的处理器核均有自己的片上存储空间。片上存储空间是私 有的，不能被其它处理器核直接访问。r i s c 作为主控核可以通过总线访问外接 设备，i o 设备以及片外存储空间。片外存储可以作为各个处理器的共享存储空 间，允许各处理器通过d m a 访问，提供了各个处理器进行数据交互的能力。d m a 只要经过处理器的初始化配置，就可以独立完成数据搬运，而无需处理器的参与， 因而可以实现数据处理和传输的并行化。图1 1 ( a ) 所示的平台具有较强的扩展 性，可以根据实际需要改变d s p 的种类和数量。当d s p 数量较多时可以通过 n o c 实现处理器的互连，如图1 1 ( b ) 所示。 1 2 3 软件模型 1 2 3 1 并行编程的基本问题 针对上1 1 3 节提到的m p s o c 并行编程存在的种种难题，本文针对1 2 2 节 描述的异构m p s o c 硬件模型提出综合使用多种技术的并行化方法，来解决媒体 程序并行化过程中所涉及到的三大主要问题：并行粒度选择，任务调度和任务通 信方法确定。 1 、并行粒度的选择 即确定并行程序的执行单元，粒度的选择涉及到以下几个问题：1 、分析源 程序内部的依赖关系。2 、根据程序依赖关系，选择粒度的粗细，选择可以放在 同一任务内的程序结构元素( 语句，函数，模块等) 。然后将源代码划分为若干 子代码域，每个子代码域代表一个任务。任务具有原子性：即任务整体必须全部 分配在一个处理器上，不可分割；在执行过程中不可中断。其中依赖分析是并行 粒度选择的基础。 数据依赖是程序依赖关系最重要的基本属性。编译技术为了进行后续的优化 一般需要采用保守的方法对数据依赖进行估计【3 6 】，这会造成虚假依赖的存在从 而影响并行性的开发。因此本文采用静态和动态相结合的分析方法，在静态情况 下确定程序的控制依赖和调用图( c a l lg r a p h ) 。而过程间的依赖关系以及条件分 支的选择则使用动态剖析进行统计。 目前并行粒度大致可以分为四类：指令级并行( i l p ) 【3 7 ，块级并行( b l p ) 【3 8 ，函数级并行( f l p ) ，线程级并行( t l p ) 3 9 】。这四种粒度都可以在多核 处理器中以线程的形式实现。后两种的计算模块较大因此又属于粗粒度并行的范 1 0 浙江大学硕士学位论文绪论 畴。i l p 较为成熟，但是可能会产生较高的通信开销。f l p 分析和实现方式较易， 但颗粒太大，负载不平衡现象较严重。b l p 粒度适中，但是如果块内部存在多个 函数调用，而且被调函数的复杂度很高，那么也会出现负载不均衡的现象。 媒体程序具有丰富的内在数据并行性，其数据处理方式基本上是从一个数据 堆中读取数据，进行处理后再写如另一个数据堆中。本研究考虑开发函数级别的 可变粒度并行，以粗粒度流水并行为主，在负载均衡以及硬件资源空闲的情况下 开发其它细粒度并行性。为了准确记录程序的依赖关系，并方便后续的任务调度， 本研究提出可变粒度数据流图( s c a l a b l eg r a i nd a t af l o wg r a p h ，s g d f g ) ，用 于保存程序逻辑结构和任务调度。 2 、任务调度 并行粒度确定后，如何将生成的各任务分配在处理器上，并决定这些任务的 执行顺序和方式，是任务调度确定所要解决的问题。任务调度的选择要考虑任务 间的依赖关系，任务的计算和通信开销和硬件体系结构。在m p s o c 环境下还要 特别考虑存储空间的限制，以及实时性的需求。而且任务调度和并行粒度选择是 相互依赖的。初始的粒度划分方案经过任务调度后，经过评估也许并未实现理想 并行性能，那么可以对粒度划分方案进一步改进。所以并行粒度和任务调度是一 个循环过程，并行粒度的划分应以任务调度的结果为反馈，不断修正和完善。 1 2 3 2 可变粒度并行化方法简介 针对上述并行编程的三个问题，本方法以串行c 代码为输入，在交互处理 的方式下针对目标硬件的资源特点将源代码分割，转化成可以在不同处理器单元 上并行执行的代码。本文提出了各个模块间的接口和实现的基本步骤，并以 4 0 】 提出的由1 个r i s c 与2 个m e d i a d s p 组成的异构多核处理器平台做为验证平台。 如图1 2 所示，本方法提出的可变粒度并行方法共包括5 个部分： 硬件描述。为目标多核处理器构建硬件模型( h a r d w a r em o d e l ，h m ) ，主要 包括处理器核的个数、指令集、运行速度、存储空间和处理器间互连方式等信患， 可以作为后续的调度模块和并行代码生成模块的输入参数。 依赖分析。用于确定并行化的操作粒度，包括粒度大小的确定以及针对目 标代码的粒度划分。依赖分析采用动态静态相结合的方式，确定候选并行化区 域(