浙江大学计算机科学与技术学院硕士学位论文面向多媒体编解码应用的多处理器系统芯片任务并行化方法的研究与实现姓名：孙煦雪申请学位级别：硕士专业：计算机科学与技术指导教师：李莹20100101浙江大学硕I ：学位论文摘要摘要具有高性能、并行处理和灵活的编程性等优点的多核系统芯片M P S O C 已经成为超大规模集成电路研究领域的全球前沿和热点，它的研究和发展给软硬件设计者和系统开发者带来了巨大的机遇和挑战。任务的划分、映射和调度影响多核系统芯片软硬件体系架构的实现，对整体性能有着巨大影响，是多核系统芯片设计待解决的一个关键问题。本文的研究课题针对目前多核系统芯片流程设计中任务并行化的局限性而提出的，解决如何通过有效的算法引导任务划分、软硬件映射和任务调度，实现体系结构设计空间的自动探索工作这一具有研究价值和意义的问题。本文的主要贡献在于提出了多核系统芯片任务级自动并行化的研究方案和系统实现。本文的研究方案对S i m u l i r t kC A A M 计算模型建模的应用进行任务自动并行化，首先提出了改进的带注释的层次任务图模型对任务并行化进行建模，研究基于该新图模型的任务划分方法，然后针对迭代计算和运行不确定任务提出了两阶段任务映射方案，在求得映射初解的基础上，依据开销函数公式，使用智能算法不断对结果进行调整，来求得映射结果近似最优解，接着在映射结果信息的基础上，采用兼容条件任务和通用任务的调度方法，得到了任务节点在时序上的先后执行信息，最终生成了包含任务并行化信息的多线程代码，从而完成了整个任务自动并行化过程。在阐述研究方案后，本文介绍了任务自动并行化方案的系统实现，并通过仿真环境和实验结果，表明本文的研究方案可有效地引导任务的划分、软硬件映射和任务调度，实现体系结构设计空间的自动探索工作。关键词：任务图模型，任务划分，映射调度，并行化，系统芯片浙江人学硕l 二学位论文A b s t r a c tA b s t r a c tM u l t i - p r o c e s s o rS y s t e mo nC h i ph a sb e c o m et h ea t t r a c t i v et o p i ca n dh o t s p o ti nV L S I ( V e r yL a r g eS c a l eI n t e g r a t e dC i r c u i t s ) r e s e a r c hi nr e c e n ty e a r sd u et oi t sm e r i t so fh i g hp e r f o r m a n c e ，p a r a l l e l i z e dp r o c e s s i n ga n df l e x i b l ep r o g r a m m a b i l i t y T h ed e v e l o p m e n to fr e s e a r c ho nM P S O Cd e s i g nf l o wh a sb r o u g h tb i gc h a l l e n g e sa n do p p o r t u n i t i e st ot h es o f t w a r e h a r d w a r ed e s i g n e r sa n ds y s t e md e v e l o p e r s T h et o p i ca b o u tt a s kp a r t i t i o n ，t a s km a p p i n ga n dt a s ks c h e d u l i n gh a sa ni m p a c to nt h ei m p l e m e n t a t i o no ft h eM P S O Cs o f t w a r e h a r d w a r ea r c h i t e c t u r e T h i sr e s e a r c ht o p i ch a ss u c hag r e a ti n f l u e n c eo nt h ew h o l ep e r f o r m a n c et h a ti th a sb e e nak e yp r o b l e mt Ob es o l v e di nt h eM P S O Cd e s i g n T h i st h e s i sp r o p o s e sam e t h o dt os o l v et h ep r o b l e ma b o u th o wt od e s i g ne f f e c t i v ea l g o r i t h m st og u i d et h et a s kp a r t i t i o n , m a p p i n ga n ds c h e d u l i n g ，a n dt oa c h i e v et h eg o a lo fa u t o m a t i ce x p l o r a t i o ni na r c h i t e c t u r ed e s i g ns p a c e 1 1 1 em a i nc o n t r i b u t i o no ft h et h e s i si St oa d d r e s st h ei s s u eo fa u t o m a t i ct a s k 1 e v e lp a r a l l e l i z a t i o nf o rt h ea r c h i t e c t u r eo fM P S O Ca n dt og i v et h es y s t e mi m p l e m e n t a t i o n T h i st h e s i sp r o p o s e sam e t h o dt op a r a l l e l i z et h ea p p l i c a t i o nw h i c hi sm o d e l e db yS i m u l i n kC A A Mt oe x p l o r et a s k - l e v e lp a r a l l e l i s m T h em e t h o df i r s t l yu s e st h ee x t e n d e da n n o t a t e dh i e r a r c h i c a lt a s kg r a p ht om o d e lt h et a s kp a r a l l e l i z a t i o np r o b l e m ，a n ds t u d i e so nt h ep a r t i t i o nm e t h o db a s e do nt h en e wg r a p hm o d e l ，t h e np r o p o s e sat w op h a s em a p p i n gs c h e m ef o ri t e r a t i v ec o m p u t a t i o na n du n c e r t a i n - e x e c u t i o n p a t ht a s k ，t h a ti s ，a f t e ro b t a i n i n gt h ei n i t i a ls o l u t i o n ，t h es c h e m eu s e si n t e l l i g e n ta l g o r i t h ma c c o r d i n gt ot h ec o s tf u n c t i o nt oa d j u s tt h em a p p i n gr e s u l ta n de v e n t u a l l yt og e ta na p p r o x i m a t eo p t i m a ls o l u t i o n ，a n da tl a s t ，t h em e t h o du s e st h es c h e d u l i n ga l g o r i t h mc o m p a t i b l ew i t hc o n d i t i o n a lt a s ka n dg e n e r a lt a s kb a s e do nt h em a p p i n gr e s u l t ，a n df i n a l l yg e n e r a t e st h em u l t i t h r e a dc o d e sw h i c hc o n t a i nt h ep a r a l l e l i z a t i o ni n f o r m a t i o n T h et h e s i sg i v e sa ni n t r o d u c t i o nt ot h es y s t e mi m p l e m e n t a t i o no ft h ep r o p o s e dm e t h o da n du s e ss i m u l a t i o na n de x p e r i m e n t a t i o nr e s u l t st od e m o n s t r a t et h a tt h ep r o p o s e dr e s e a r c hs o l u t i o nc o u l de f f e c t i v e l yi m p r o v et h ep e r f o r m a n c ea n da c h i e v et h e浙江大学硕上学位论文A b s t r a c tg o a lo ft a s kp a r t i t i o n ，m a p p i n ga n ds c h e d u l i n gi nt h ee x p l o r a t i o no fM P S O Cd e s i g ns p a c e K e y w o r d s ：t a s kg r a p h ，t a s kp a r t i t i o n ，t a s km a p p i n ga n ds c h e d u l i n g ，a u t o m a t i ct a s kp a r a l l e l i z a t i o n ，M P S O C浙江人学硕士学位论义图目录图目录图2 1 基于S i m u l i n k 的M P S O C 设计流程图n2 J 1 0图2 2S i m u li n kC A A M 模型层次架构实例1 4图2 3 ( a ) 循环实例( b ) 相关的迭代依赖图1 6图3 1S i m u li n k 建模2 0图3 2C o li fC A A M 的C P U I 子系统实例2 l图3 f 3 ( a ) 层次图( b ) 延伸的层次图2 4图3 4 任务并行化系统体系架构2 5图3 5 简单映射问题2 8图4 1S i m u li n kC A A M 模型解析程序片段3 9图4 2 从S i m u li n kC A A M 模型转换到E A - H T G 图模型的程序片段4 0图4 3 解析出的S i m u l i n kC A A M 模型信息可视化效果4 1图4 4 本文研究基于的S O C 设计流程图引4 4图4 5M o t i o n - J P E G 核心算法的负载信息4 5图4 6 不同体系结构的性能结果4 6图4 7J P E G _ G F I F O _ 3 A R M 架构的性能分析( a ) 手工方案，( b ) 自动并行方案4 6图4 vJ P E G G F I F O _ 2 X T I A R M 架构的性能分析( a ) 手工方案，( b ) 自动并行方案。 7图4 9J P E G _ G F I F O _ 1 A R M 2 X T 架构的性能分析( a ) 手工方案，( b ) 自动并行方案z 7图4 1 0J P E G _ G F I F O _ 3 X T 架构的性能分析4 8图4 1 1J P E G D M S 一3 X T 架构的性能分析4 8图4 1 2 任务自动并行化方案与手工方法相比获得的性能提高4 9l l l浙江人学硕- J 二学位论文表目录表目录表2 1 计算模型分类11浙江大学硕+ 学位论文第l 章绪论第1 章绪论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 mo nC h i p ) 芯片是指包含多个微处理器的系统芯片，拥有多个不同的处理单元和内存以及多层次的片上通信体系和软件体系。M P S O C 在2 0 0 1 年左右提出后，由于其具有并行处理、高性能以及灵活的编程性等优点【1 1 ，目前已经成为超大规模集成电路研究领域的全球前沿和热点。由M P S O C 构建的集成计算系统，可满足市场对于系统在实时性、计算性能、功耗与成本等方面的需求。M P S O C 的研究和发展也给软硬件设计者和系统开发者带来机遇和巨大的挑战。M P S O C 的设计主要存着以下两个困难：首先，应用建模是应用任务分解、融合和并行化的基础，因此，如何构建和优化面向特定应用的数据计算模型，例如采用同步数据流( S D F ，S y n c h r o n o u sD a t a f l o w ) 口j 或进程网络( 1 0 N ，K a h nP r o c e s sN e t w o r k ) 【3 】来显示串行应用的并行性，进而实现原始串行应用算法到计算模型的转换，是M P S O C 设计在应用算法层和并行优化上面临的一个挑战。其次，任务划分的粗细粒度影响M P S O C 架构设计空间( D e s i g nS p a c e ) l 约灵活度和大小，而任务划分调度也决定着多处理器间通信带宽和存储器等资源的负载，因此，如何面向不同处理器，采用有效任务划分策略和调度机制是M P S O C 设计在应用功能任务层面临的巨大挑战。任务的划分和调度影响M P S O C 软硬件体系架构的实现，对整体性能有着巨大影响，是M P S O C 系统设计待解决的一个关键问题。把复杂任务进行分解，将其映射到异构多处理器上，也就是说，将划分后的并行任务合理有效得分配给各个硬件资源以满足实时性、功耗与成本等条件的约束，从而获得最佳软硬件协同效果，有效地挖掘任务级并行性，是值得研究和探索的课题，同时也具有很大挑战性。任务划分和软硬件架构映射是一个相互制约、相辅相成的共同体，最优的软件划分通常是在给定的硬件架构基础上来确定，而最优的软硬件架构映射也是浙江大学硕1 ：学位论文第1 章绪论基于某种软件任务划分结果来评估。随着体系结构设计空间的扩展，任务划分和软硬件架构映射的难度系数也显著增大。因此，最佳的任务划分和软硬件架构映射事实上是一个N P 复杂( N PC o m p l i c a t e d ) I h - 题。针对多处理器体系结构的任务调度是N P 难问题【4 】，M P S O C 结构上的异构性使得任务调度特别需要关注任务在不同体系结构的处理单元上执行时的特点，这在调度器的实现上提出了很多新挑战。国内外对于任务划分和调度已有一些研究和成果。下一节将简述国内外的研究现状。1 2 国内外研究现状当前任务划分策略多种多样，主要目的是为了加大任务的并行处理能力，加快并行处理速度。不同的计算模型显性提供了不同粒度的任务划分策略，例如使用装箱问题建模的任务划分方案采用N F ( N e x tF i t ) 和F F ( F i r s tF i t ) 启发式划分算法【5 】将任务划分成两个子任务并以不同速度执行的M K E r 算法 6 J ，使用模拟退火算法实现的可减少执行时间及通信数据量的划分策略【| 7 1 ，面向可重构系统的基于层次和基于簇的划分算法【8 】以及适用大规模问题求解、融合概论构造算法和遗传算法的划分策略【l0 1 ，面向函数型程序基于任务树模型挖掘大粒度并行性的划分算法【1 1 】等等。在黄凯的论文【1 2 l 中，任务划分采用基于计算负载，流水线( p i p e l i n e )式并行划分的策略，随着划分步数的增加，各个子系统任务的粒度也越来越细，设计的灵活度和难度也相应增大。任务调度的研究很多都是基于抽象模型给出任务的形式化定义，然后进行调度策略与算法的设计。不同体系结构上的任务调度算法已有不少相关研究。对于网格计算环境，陈晓红【l3 】提出了计算网格环境下一种基于代理的面向服务、多级个性化的调度模型；陈锋的论文【1 4 】中，结合对等计算的优势，提出了一种基于P 2 P 的网格调度模型，包括作业运行时、资源选择、数据管理、对等点管理、网格信息等模块，并在此基础上探讨了网格资源发现、网格任务分解及调度算法；苏培【15 】分析认为影响网格调度系统效率的瓶颈主要集中在对任务需求的理2浙江大学硕士学位论文第l 章绪论解方式和对资源信息的组织方式上，为此提出了一种基于分类的调度模型，通过对用户任务和网格资源进行统一分类，用分类号来表征资源的计算力特征，为调度器提供资源匹配参考，同时采用周期性的动态分类策略，该文用实验证明新模型提高了网络资源信息的可管理性和系统执行效率。对于分布式集群计算环境，雷迎春等人【l6 】用排队论方法讨论了W e b 集群整体性能与请求调度策略之间的关系，得出在W e b 集群不过载情况下，分离式调度策略比所有后端服务器既处理静态请求又处理动态请求的混合式调度策略更有性能优势的结论；赵明宇等人【1 7 】提出了可防止同步通信引起死锁的调度算法，降低了同步通信的时延影响；黄金贵等人【】嚣】基于多处理机并行任务调度模型，探讨网络集群计算系统中的并行任务调度问题，分析了最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法这三种不同的启发式算法，并用实验对文中提出的启发式算法和文献中的算法进行了性能比较。对于多处理器系统，钟一文等人【l9 】针对并行多处理器系统的任务调度问题，提出一个新的混合遗传算法，使用拓扑排序表的交叉来保证下代的合法性和搜索空间的全局性；韩建军等人【2 0 】提出了针对实时多处理器计算环境的调度算法，以执行时间最短的任务优先调度为基础，结合共享空闲时间回收技术及检查点技术等，可动态降低整个系统的能量消耗及动态容错，同时满足节能性和容错性；苗蕾的论文【2 1 】中，认为片上多核处理器系统的功耗主要受任务的执行时间及系统的能耗这两个因素影响，文中通过对片上多核系统任务调度和能量消耗的分析建立了新颖的编码策略，使用随机权重适应度以及精华解保留策略对粒子群优化算法进行改进，提出了多目标粒子群算法，并通过仿真实验表明新算法可提高系统任务调度的效率，降低任务运行时间和能耗：兰舟的论文1 2 2 】分析了几个典型的基于任务复制的调度算法，提出了基于动态关键任务的多处理器任务分配算法，调度过程中动态计算任务时间参数来确定处理器的关键任务，以关键任务为核心优化调度；宾雪莲等人【2 3 1 提出了一种新的实时多处理器系统的动态调度算法分组适度算法，包括分组策略和适当选取策略，以期提高资源利用率和处理器的利用率；杨根科等人【2 4 】研究硬实时周期任务在并行等同多处理器下的可调度问题，在浙江大学硕1 ：学位论文第 章绪论任务处理器静态绑定和周期任务静态优先权配置策略下，依据单处理器情形下的最优配置实时策略，给出了以实时任务集合的任务数、利用率作为可调度依据，并通过实例分析说明其有效性；乔颖等人f 2 5 】提出了一种新的实时异构系统的动态调度算法，采用集中式调度方案，并引入一个新的任务分配策略，通过提高任务可行性增大了调度成功率；鉴于任务调度策略是决定可重构计算系统性能的关键，刘勇【2 6 】对实时并行系统的多任务调度理论进行了深入的讨论，分析了表调度算法、任务复制调度算法、任务集群调度算法和随机搜索调度算法的优缺点及适用范围，使用评价参数对调度算法进行了性能分析，同时，文中重新定义了任务粒度，分析了任务划分和任务调度间的关系，提出了一种基于相关任务优化的任务调度算法，在调度长度、处理机数目和算法复杂度方面有一定的结果性能优势。近年来，基于不同任务模型的多处理器片上系统调度算法的研究主要分为三类：周期模型类相关算法、D A G 模型类相关算法及其他扩展模型算法。对于周期模型类相关算法，由于嵌入式计算系统始终关注可靠性与功耗，因此，利用任务冗余提高系统的可靠性和调度成功率是近年来多处理器任务调度研究的一个方向。基于D A G 图模型的任务调度问题可以描述为将任务分配到处理器并协调执行，使得在满足实时性约束条件下，任务的整体执行时间、功耗或其他指标最优【2 7 1 。近年来，有一些研究者引入新的计算方法，来解决多处理器调度问题，如用于多处理器任务调度的遗传算法和基于细胞自动机的多处理器任务调度算法等【2 8 1 。针对不同应用领域，研究人员近几年陆续提出新的任务模型来增强表达实际应用的能力，不断提高系统的可调度性和调度成功率，如对执行时间有变化的任务进行建模的M u l t i f r a m e 2 9 】模型，可以表达条件分支的循环实时任务模型( r e c u r r i n gr e a l t i m e t a s k m o d e l ) 3 0 】，面向流数据的任务模型【3 1 】等等。近年来有不少在任务调度实现框架上的研究进展。S e s 锄e 【3 2 】是一个用于异构多处理器系统进行高效体系结构探索的软件框架，利用多目标非线性整数规划来评估处理时间、功耗和成本等设计约束。F a b i o 等人【3 3 】提出一个基于任务图的M P S O C 仿真器，提供动态电压调度机制，可以对多处理器片上系统设计时在计算能力与整体功耗之间进行权衡。C h u n g 等人的论文【3 4 】中实时调度框架由两部分4浙江人学硕j ：学位论文第1 章绪论组成，包括计算量较大的设计时离线的任务分配，以及运行时任务调度，这种二阶段的任务调度框架增加了系统设计的灵活性，减少了多处理器片上系统的设计时间，降低了整个系统的功耗。M a r t i n oR u g g i e r o 等人在文献1 35 J 中实现了一个基于问题分解的优化调度器。C h o 等人在文献【3 6 】中实现了一个M P S O C 的静态调度器，考虑了同步开销等相关细节。X u e 等人【3 7 】使用离线与在线结合的调度方法来对运行在多处理器片上系统的多个应用的运行时刻进行优化与资源管理。将调度算法的理论成果进一步应用到实际平台上，需要高效、可执行的调度机制与调度器。综上所述，已有的调度算法的研究主要针对分布式集群、网格和多处理机的计算环境，而仅有的一些针对M P S O C 体系结构的任务调度算法的研究仍然停留在调度分析和算法效率改进上，无论是离线调度还是在线实时调度都与实际应用还有不小的距离，还需要结合新的任务模型进一步改进算法效率与实现机制，并在具体的实际应用平台上实现。本文的研究课题就是针对目前M P S O C流程设计中任务调度的局限性而提出的，通过使用合适的任务模型及研究合适的算法，完成了任务调度在实际应用平台上的有效实现。下一节将进一步阐述本文的研究内容和研究目标。l - 3 本文研究内容和目标任务划分，软硬件映射及任务调度是M P S O C 流程平台中的关键步骤，是实现体系结构探索的重要部分。本文的研究是基于论文【1 2 】中提出的M P S O C 流程平台展开的。该流程平台工具未能实现完全自动化，而是依靠人为经验或简单的基于计算负载划分策略来完成任务划分，导致最后的结果和设计的效率都不令人满意。任务划分，软硬件映射和任务调度是一个与性能评估相结合的反复迭代的优化过程，经过任务划分和软硬件映射后得到的软硬件体系架构需要在随后的各层次软硬件仿真中予以性能评估和验证。如何通过有效的算法引导任务划分，软硬件映射和任务调度，实现体系结构设计空间的自动探索工作，是本文研究课题需要解决的问题。本文主要工作是基于M P S O C 流程设计平台【1 2 】，研究对S i m u l i n kC A A M 建模浙江大学硕1 ：学位论文第1 章绪论的应用进行任务自动并行化，包括对提出一种扩展的任务图模型进行并行化方案的前期建模，研究基于该新图模型的任务划分方法，并针对迭代计算和运行不确定任务提出两阶段任务映射方案，在求得映射初解的基础上，依据开销函数公式，使用智能算法不断对结果进行调整，来求得映射结果近似最优解，最后在映射结果信息的基础上，采用兼容条件任务和通用任务的调度方法，得到了任务节点在时序上的先后执行信息，从而完成整个任务自动并行化过程。本文研究并实现了任务自动并行化系统，并通过仿真环境和实验结果，表明本文的研究方案可有效地引导任务的划分、软硬件映射和任务调度，实现体系结构设计空间的自动探索工作。本课题的主要目的是研究和实现面向多媒体编解码应用的多核系统芯片任务自动并行化方案，有效地实现任务的划分、映射和调度，尽可能挖掘任务级并行性，满足性能需求，以此对整个M P S O C 软硬件体系架构的实现产生积极，从而提高M P S O C 设计的整体性能。1 4 论文结构第一章主要介绍了课题的研究背景，对国内外任务并行化的研究，特别是任务调度的研究及发展进行了简单介绍和分析。最后对本文的主要研究工作和目标作了简单描述。第二章对多核系统芯片软件设计流程进行了简单介绍，并着重对设计流程中用来建模应用的S i m u l i n kC A A M 模型和通用映射调度方法所需使用的中间表达式程序图模型进行了相关介绍和分析。第三章主要阐述本文对多核系统芯片任务级并行化的研究方案。章节开始部分对本文研究的问题进行了建模，介绍了应用程序模型以及对任务映射调度的建模，然后重点讲述了针对已建模的应用，改进的带注释的层次任务图的任务划分，和普通任务的调度方法。进行任务自动并行化的方案，包括基于两阶段任务映射方案以及兼容条件任务第四章介绍了本文研究方案的系统实现，并介绍了仿真和实验的体系结构环6浙江火学硕十学位论文第l 章绪论境，针对运动J P E G 应用，给出了本文任务自动并行化方案的实验结果与性能分析。论文最后对本文的工作进行了总结，并指出了目前存在的不足之处及提出了今后工作的目标。7浙江大学硕+ 学位论文第2 章多核系统芯片软件设计流程及模型第2 章多核系统芯片软件设计流程及模型2 1 术语与缩写任务( t a s k ) ：一个任务可以是一条原子指令或操作，也可以是一个线程或一段组合语句，例如循环块，基本块等等。任务的粒度可以从粗到细，可以有很大变化。并行计算粒度：计算的顺序单元的平均大小，可分为粗粒度，中粒度和细粒度。粗粒度表示计算由相对长的顺序片段或线程，循环块、函数、过程调用等组合语句组成。中粒度表示计算由基本块、循环主体、小的函数或过程组成，最多到上百条指令。细粒度表示计算由一条或几条指令组成。迭代计算：在串行编程语言中，迭代计算指代循环或递归函数。迭代计算的每次迭代由一个或多个任务组成，这些任务在同一个迭代中执行。任务处理器映射( m a p p i n g ) ：确定一个任务会在哪个处理器上执行，也就是将任务分配到特定对应的处理器上。调度( s c h e d u l i n g ) ：决定任务间的执行顺序，以及任务启动时间。任务的映射和调度概念并不严格区分，完整的调度包含空间的映射和时序的映射。本文研究方案中提到的调度，专指时序上的映射。2 2 模型阐述2 2 1 设计流程简介本文研究课题的平台是【1 2 】中描述的M P S O C 设计流程平台。基于S i m u l i n k 的M P S O C 设计流程是面向特定应用，从S i m u l i n k 功能模型一步步细化到物理实现的过程【3 8 】。如图2 1 所示，它主要分为六步：第一步是S i m u l i n k 建模，即分析给定的目标应用，提取其算法，然后使用S i m u l i n k 对其进行建模，这是细粒度上对应用进行初步的划分。接着，在第二步中，S i m u l i n k 算法模型被映射到系统的硬8浙江大学硕士学位论文第2 章多核系统芯片软件设计流程及模型件体系结构上，并转化成S i m u l i n kC A A M ( C o m b i n e dA l g o r i t h n l A r c h i t e c t u r eM o d e l ，混合算法体系结构模型1 。在这一步中，S i m u l i n k 算法模型按照任务划分的结果被分割成不同的线程，其中各S i m u l i n k 模块被封装入相应的线程中。在论文【1 2 】中，任务的划分映射和调度主要是人为手工实现，未实现过程自动化。S i m u l i n kC A A M 将软硬件在算法层面上统一于一个模型，它包含处理器类型和通信方式等硬件体系结构模型信息以及软件模型信息( 映射到不同处理器中的多线程软件) 。S i m u l i n k 解析转换器可以将S i m u l i n kC A A M 转换成一种易于数据处理的中间数据格式：C o l i fX M L t 3 9 1 。流程的第三步和第四步将会生成功能层、传输精确层、时钟精确层和R T L 层四种不同层次的硬件体系结构和多线程代码。这两步同时生成不同层次的软硬件仿真平台，用于软硬件系统架构的性能评估，并反馈给第二步的任务划分和体系优化，在这样的循环迭代中，软硬件系统架构逐步优化，性能逐渐提高。流程的第五步和第六步属于物理实现阶段，M P S O C 的R T L代码被分别转换成物理芯片实现和F P G A 原型实现。9浙江大学硕j ：学位论文第2 章多核系统芯片软件设计流程及模型c c A p p + + h “c t 慨i o n ：型i 掣? c 唑- - 1 一一A I g o n U h ma n d”1 一A r c h i t e c t u r e ：TS i m t l i n km “嘲j 霸g ，S i m u l i n k一1 _ 一( S i m u l i n ka p p l i c a t i o nm o d e lf!i!；|i；il!i；iilii；!iI：-一-tA H b 曲s l a 1 C 掣l i o 。n 1L 丽蒜i - 宴z 9 ：f 一蕊蛐酬c 施锄M o d e lS y s t e m CV i r t u a lA t c h i t e c t u r eM o d e lT m n m a i o nA c c u r a t eM o d e l _V i r t u a lP r o t o t y p eM o d e l- -R 1 1潦7 函声盔爱c 幽：手。j ：i ：；莪二。嘶蒯h 姗删佃j 锾，竺A ! 竺弦胁竺o n ，臣习r 巫M o 亟d e l ，匿自皇萝旦竺。F e e d b a c k 卜图2 1 基于S i m u l i n k 的M P S O C 设计流程图“羽2 2 2S i m u l i n kC A A M 模型计算模型( M o d e lo f C o m p u t a t i o n ，M O C ) 可以用来表示一个计算系统，描述其状态转换和数据传输。随着S O C 系统级设计的兴起，计算模型开始进入系统设计研究领域。对应用算法进行建模可以显性暴露算法的并行性和数据流，可以合理有效地映射功能和体系结构。根据同步异步和时序( T i m e d ) 非时序( U n t i m e d ) ，计算模型可以分为四大类，如表2 1 所示。l O浙江大学硕十学位论文第2 章多核系统芯片软件设计流程及模型表2 1 计算模型分类时序非时序同步有限状态机( F i n i tS t a t e同步数据流( S y n cD a t a f l o w ，S D F )M a c h i n e s ，F S M )异步离散事件( D i s c r e t eK a h n 进程网络( K a h nP r o c e s sN e t w o r k s ，K P N )E v e n t )P e t r i 网( P e t r iN e t l通信顺序进程( C o m m u n i c a t i n gS e q u e n t i a lP r o c e s s e s ，C S P )面对不同应用，采用何种类型的计算模型成为S i m u l i n k 建模的关键。当前主要的计算模型有同步数据流( S D F ) 【2 】和K a h n 进程网络( K P N ) f 3 】等。同步数据流属于同步时序的计算模型，可用来描述一个应用算法的数据流程。在S D F 模型中，一个计算进程在输入端口上得到足够的数据后开始工作。在进程工作的过程中，它将消耗每个输入端口上固定数量的数据，然后产生固定数量的数据到每个输出端口上。同步数据流模型在每个单位时间内数据接收、处理和生产数目都是固定的。S D F 模型适用于信号处理应用的建模，但是它不能表示含条件选择分支的应用。K a h n 进程网络是一种异步非时序的计算模型，它静态连接各计算进程。各进程间的通信是通过未限制容量的单向通道实现。当通道中有足够的数据时，它的终端进程将接收这些数据，进程的写操作可立即将数据送到通道中。K a h n 进程网络模型的通道可以显性揭示各线程之间的通信及其通信量。当应用粒度变细，线程和通道逐渐变多时，进程阻塞问题将会加剧。如何平衡各进程执行速度，避免通道中数据累积，是K P N 调度的主要问题。K a h n 进程网络模型适用于粗粒度的应用算法建模。系统建模描述语言主要有系统设计语言( S y s t e mD e s i g nL a n g u a g e ，S D L ) 1 4 0 、S i m u l i n k t 4 1 1 和统一建模语言( U I l i f i e dM o d e l i n gL a n g u a g e ，U M L ) 【蚓等。S D L 是用来描述电信协议的图形化系统描述语言，但不适合数字信号处理和多媒体等应用领域。应用系统建模的一个巨大挑战是如何能采用不同的计算模型，在不同层次上对特定应用进行建模。针对这个挑战，近年来，学术界和工业界将S i m u l i n k 和U M L 建模语言引入到系统级设计流程平台中。S i m u l i n k 能够提供方便有效的算法浙江大学硕士学位论文第2 章多核系统：匕片软件设计流程及模型组件库和友好的建模界面，被广泛用来在算法层次上描述复杂的应用系统，可以处理包括线性系统和非线性系统，离散系统、连续系统和混合系统，以及单任务和多任务离散事件系统在内的各种不同系统。从建模分析研究的角度来说，S i m u l i n k 建模方式不仅能显示具体组件的动态细节，也能清楚体现各个组件、子系统、系统间的信息交互。基于S i m u l i n k 系统描述语言的应用算法建模需要进一步显性揭示算法的并行性和数据流。当前基于S i m u l i n k 的M P S O C 设计工具主要侧重于在给定硬件架构条件下生成多线程软件，或在给定多线程应用下生成硬件架构。与S i m u l i n k 相比，U M L 在描述系统应用架构的需求和约束方面更具优势，同时它能描述更高的抽象层，但S i m u l i n k 在描述应用算法方面具有巨大的优势。鉴于两种建模语言各自的特点和优势，L i s a n 等人【4 3 】于2 0 0 7 年提出U M L 和S i m u l i n k 相结合的流程方法，在S i m u l i n k 算法建模的更高层实现U M L 建模。S i m u l i n k 模型是一个由细粒度功能层的模块所组成的算法模型，它不依赖于任何软硬件架构。基于S i m u l i n k 模型可以实现不同的划分策略和硬件体系，可以更灵活地为细粒度设计空间的探索提供良好的平台。本文研究课题的平台是基于S i m u l i n k 的M P S O C 设计流程，采用抽象时钟同步模型( A b s t r a c tC l o c kA s y n c h r o n o u sM o d e l ，A C S M ) 对系统应用来进行建模。A C S M 模型在功能建模方式上类似于时钟同步模型( C l o c k e d A s y n c h r o n o u sM o d e l ，C S M ) 。时钟同步模型是基于时钟同步假设，即一个全局同步时钟信号可以控制系统中每个运算的开始，整个运算必须在一个时钟周期内完成，然后再经过无时间消耗的通信传给下一次运算。将C S M 模型引申到系统级设计领域，将具体的全局同步时钟抽象化，使得其用于功能系统层的同步，就产生了A C S M 模型。抽象时钟同步和时钟同步这两种模型的主要区别在于同步时钟和模型中组件的粗细粒度。为了更好的描述A C S M 模型，1 12 】采用了S i m u l i n k 工具库的一个子集，它包括模块( B l o c k s ) 、延时( D e l a y s ) 、链接( L i n k s ) 、I g A c t i o n 子系统( I f - A c t i o nS u b s y s t e m s ，I n s ) 和F o r 循环子系统( F o r - I t e r a t o rS u b s y s t e m s ，F I S ) ，还有一个全局抽象时钟来控制各个模块的执行和延时。在基于S i m u l i n k 的M P S O C 设计流程中，应用软件模型和硬件体系模型被最1 2浙江大学硕 ：学位论文第2 章多核系统芯J 软件设计流程及模型终统一成一个模型，即算法和体系结构结合模型( C o m b i n e dA l g o r i t h ma n dA r c h i t e c t u r eM o d e l ，C A A M ) 。应用算法可以通过计算模型进行建模，然后经过任务划分，整个应用算法被划分成几个独立的线程模块，在多线程的算法模型的基础上，进一步进行硬件体系结构的映射，应用的多个线程将被映射到包含处理器子系统和互连通信网络的目标体系架构上，其中处理器子系统中又包括处理器、输入输出接口以及特定硬件模块等。这些硬件体系架构将会与多线程软件体系架构相互结合、协同优化，从而最大程度地实现系统性能最优化。这样，最终就可以得到一个高层软硬件混和模型，即S i m u l i n kC A A M 模型。这个模型是一个高层的软硬件混和架构，主要通过三层架构来描述整个系统的软硬件体系结构。S i m u l i n kC A A M 模型的第一层是对整个系统架构的描述，包括处理器子系统和各子系统之间的通信通道，用于描述系统应用的硬件体系架构。S i m u l i n kC A A M 模型的第二层用来描述处理器子系统体系结构，包括软件线程和子系统内部通信通道。S i m u l i n kC A A M 模型的第三层是线程子系统层，用来描述软件线程，它包括S i m u l i n k 模块和链接。【1 2 】中定义了四种特殊的S i m u l i n k 子系统，包括线程子系统( T h r e a d sS u b s y s t e m ) 、处理器子系统( C P US u b s y s t e m ) 、子系统内部通信( I n t r a S SC o m m ) 以及子系统问通信( I n t e r - S SC o m m ) 。这四种S i m u l i n k 子系统是对任务划分和硬件体系结构映射信息的描述。如图2 。2 所示，是一个S i m u l i n kC A A M 模型层次架构的实例，其系统层描述了一个异构的M P S O C 系统，子系统内部线程问通信被设置成共享存储和软件缓存方式，子系统间通信方式包含分布式存储服务以及全局缓存通道。浙江火学硕十学位论文第2 章多核系统芯片软件设计流程及模型铲u ，s sT h 憎略筠B 譬中1 。广一、C P 啪S S。j 嗽s 叶q 。嘴： 露f f m - r _ _ o r 一图围匿伯一T - o 一WW1 1 、门一rIlll、一11 f七 l嗍：詈l、t石蕊阮胪嘲啪碣焉C O m 惟$ t l r m l i MP 懈$ i m u l 轴kI J n k图2 2S i m u l i n kC 从M 模型层次架构实例为了使通信端口显性化和数据结构易于操控，在基于S i m u l i n k 的M P S o C 设计中，S i m u l i n k 剖析转换器将会把S i m u l i n kC A A M 模型对应转换成协同设计语言独立格式( C o d e s i g nL a n g u a g eI n d e p e n d e n tF o r m a t ，C o l i f ) C A A M 模型。C o l i f 是一种基于X M L 的中间数据模型【3 9 1 ，能提供较好的数据结构和应用程序编程接口，从而使得M P S O C 软硬件体系结构细化过程中的数据操控更为简单。C o l i f 模型和S i m u l i n k 模型几乎是一一映射的关系，两者在模型架构上最大的区别在于，连接到子系统间通信和子系统内部通信的S i m u l i n k 端口被转换成具有方向的发送模块( S e n dB l o c k ) 和接收模块( R e c e i v eB l o c k ) 。在后续的软硬件逐步细化的过程中，发送模块和接收模块将被用于工具的优化和调度，从而有效提高软硬件并行方面的性能。2 2 3 程序图模型在图抽象理论模型中，程序包含两种活动计算和通信。计算和图的顶点相关联，通信与图的边相关联。图的一个顶点叫做节点，和它关联的计算叫做任务( t a s k ) 。一个任务可以是原子操作指令，也可以是一个线程或者复合语句，例如循环、基本块等。一个任务的所有指令或操作顺序执行，任务内没有并行性。通用图模型的粒度不受限制。一般的图模型中不包含分支跳转的概念，程序的控制结构必须包含在一个节点中。这样的图模型，其节点和边结构反映了程序分解成任务以及任务间的通信结构，可以反映数据依赖结构，但不能反映控制依赖。1 4浙江人学硕。二学位论文第2 章多核系统芯I 软件设计流程及模型程序图模型的应用需要知道节点的计算及边的通信开销。一般来说，这些开销通过时间来衡量计算的时间或者通信的时间，以图模型中元素权重的形式呈现。计算和通信开销的定义如下：G = ( VE ，w ，c ) ，是应用程序的图表示，其中，对于每个节点n V ，其非负权重w ( n ) 表示计算的开销，对于每条边e E ，其非负权重c ( e ) 表示通信的开销。比较各种图模型的标准主要有三条：计算类型、并行结构和算法，即何种类型的计算可以有效地使用图模型来表示，图模型通常可用于哪些并行体系结构，以及图模型可用于哪些算法。各种图模型在模型粒度和反映迭代计算及规则计算能力上有很大区别，不同的并行系统的指令和数据流类型、内存结构以及编程模型也各不相同，图模型的表示能力和适用性也会不同，特别的，目前图模型主要用于依赖分析、程序转换、映射和调度等算法。依据这三条主要标准，目前主要的图模型有以下几类：依赖图( D e p e n d e n c eG r a p h ，D G ) ，流图( F l o wG r a p h ，F G ) ，任务图( T a s kG r a p h ，T G ) 以及其他扩展的图模型。依赖图的思想是，将程序的每个任务( 即程序的每条语句) 以节点来表示，将依赖关系表示成有向边，这样就得到了图模型表示的依赖结构。其形式化定义为：对于程序P ，其依赖图可表示为有向图D G = 代E ) ，其中V 集合中的节点表示P 的任务，E 集合中的边表示任务问的依赖关系。从节点n i 到节点n j 的一条边e i j E ，表示n j 依赖于n i 。程序依赖图反映了程序的依赖结构，表明了节点间执行的偏序关系，即对于e i j D G 的每条边，限定了n i 优先于n j 执行。依赖图提供给编译器一种方法，用来考虑优先级约束，防止程序重排序操作。它的一个特例是迭代依赖图，反映了循环中的依赖关系。图2 2 ( a ) 是一个循环的例子，( b ) 显示了其相关的迭代依赖图。浙江火学硕士学位论文第2 章多核系统芯J I 软件设计流程及模型f a r i ：2 协：相畦oS ：磊 i 童泰 2 譬：嚣a 8 2 , 1 = 磊 ：- ：；e i 1 ；e n d f a r( 街渤图2 3 ( a ) 循环实例( b ) 相关的迭代依赖图依赖图是程序依赖结构的一种表示，不与任何特别的计算类型或粒度绑定。这种统一的理论形式在需要论证程序的依赖结构、计算的可用性或者程序转换的有效性时被广泛采用。在实际使用中，依赖图局限于应用在粗粒度或程序的部分表示。有环计算的依赖结构由迭代依赖图表示，图中每个节点和由循环嵌套索引变量跨越的迭代空间相关联。迭代依赖图不仅应用于并行编译器，也用于超大规模集成电路( V e r yL a r g eS c a l eI n t e g r a t e dc i r c u i t s ，V L S I ) 数组处理器设计。迭代依赖图不是表示有环计算的唯一图模型，流图在图中引入了时间信息来区分迭代内和迭代间的通信，能够精确表示一个迭代计算的结构。流图的形式化定义为：对于迭代计算程序，其流图是一个有向图F G = E ，D ) ，其中V 集合中的节点表示程序的任务，E 集合中的边表示任务之间的通信。从节点n i 到n j 的一条边e i i ，表示从节点n i 到n j 的一次通信。每条边e 与一非负整数权重值D ( e ) 相关联，表示一个延迟计数。程序执行中，流图中节点表示的每个任务在每个迭代中执行一次，只有当所有节点执行完成后，新的迭代才能开始。流图不包含迭代次数的信息，这样，在构造流图时，不必知道确切的迭代次数。与依赖图或迭代依赖图相比，流图的节点表示可多次执行的任务，而且流图一般不是无环的。流图是迭代计算的有效表示，计算和通信的重复部分只被建模一次。流图仅限于统一化通信关系( u n i f o r mc o m m u n i c a t i o nr e l a t i o n s ) 的有环计算。流图的粒度由迭代计算类型确定，通常是细粒度到中粒度。除了上述的依赖图和流图外，还有一种图模型，即任务图，主要用于任务调度。一般而言，任务图指有向无环l 蛩( D i r e c t e d A c y c l i cG r a p h ，D A G ) 。任务图形式化定义为：对于程序，其任务图是一个有向无环图G = ( VE ，w ，c ) ，其中V 集合中1 6浙江大学硕r 1 ：学位论文第2 章多核系统芯片软件设计流程及模型的节点表示程序的任务，E 集合中的边表示任务间通信。从节点1 1 i 到n j 的边e i j E ，表示节点r l i 到n j 的通信。与节点n 相关的正权重值w ( n ) 表示其计算开销，与边e i i 相关的非负权重值c ( e i i ) 表示通信代价。在程序执行过程中，每个任务只执行一次。程序中只存在那些任务图中边表示的通信或依赖。任务图模型反映计算的本质，可以充分表示程序的任务和通信结构，以及计算和通信的开销，具有通用、简单等特点，因此最适合用于任务调度算法的建模研究。但是任务图的局限性在于，任务图的边只反映流数据依赖，它不适用有环计算，不能提供任何机制来有效地表示一个迭代计算。对于迭代计算，任务图的大小依赖于迭代次数，这直接影响内存消耗以及任务调度算法的处理时间。因此任务图通常用于粗粒度非迭代计算。任务图不局限于统一迭代间通信，适用于单控制流多数据流( S i n g l eP r o g r a mM u l t i p l eD a t a ，S P 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 ，M I M D ) 的分布式并行系统。以上所述三种图模型提供了有效的程序信息，其中依赖图反映了程序的依赖结构，对于循环的依赖分析及整个循环转换，是一个有价值的工具；流图能够有效表示迭代计算，基于流图表示发展了许多针对迭代程序的并行化技术，如展开( u n f o l d i n g ) ，重定时( r e t i m i n g ) ，软件流水( s o f t w a r ep i p e l i n i n g ) ，映射( m a p p i n g ) 和调度( s c h e d u l i n g ) 等；任务图可以反映迭代和非迭代计算，通常用于粗粒度非迭代计算。除了上述三种基本图模型外，还有一些基于上述三种图模型进行扩展的其他图模型，如任务交互图( T a s kI n t e r a c t i o nG r a p h ，T I G ) ，时序通信图( T e m p o r a lC o m m u n i c a t i o nG r a p h ，T C G ) ，控制流图( C o n t r o lF l o wG r a p h ，C F G ) 及控制依赖图( C o n t r o lD e p e n d e n c eG r a p h ，C D G ) 以及层次任务 蛩( H i e r a r c h i c a lT a s kG r a p h ，H T G ) 。任务交互图是无向图模型，只关注整个进程间的通信关系而不是任务间的通信，主要用于进程到并行处理器的映射分配的建模。时序通信图综合了一个并行程序的任务和进程角度的建模，应用于映射和调度算法。控制流图和控制依赖图均为有向图模型，用来表示程序的控制流和控制依赖，可以反映程序的条件执行路径，主要应用于编译器中分析和处理程序的控制流。层次任务图用于对那些1 7浙江犬学硕士学位论文第2 章多核系统芯片软件设计流程及模型包含迭代和非迭代的计算进行有效地图模型表示，它的一个高层节点表示整个子图。2 3 本章小结本章先简单地介绍了多核系统芯片软件设计流程，然后对设计流程中用来建模应用的S i m u l i n kC A A M 模型进行了介绍，并与其他计算模型进行了对比分析，接着对通用映射调度方法所需使用的中间表达式，即程序图模型进行了相关介绍，分析比较了几种图模型的特点和建模表示的优势。浙江大学硕士学位论文第3 章多核系统芯”任务级并行化方案设计与研究第3 章多核系统芯片任务级并行化方案设计与研究3 1 问题建模我们对多核系统芯片任务级并行化问题进行两层建模。第一层建模，我们利用S i m u l i n kC A A M 计算模型对应用源程序进行建模。第二层建模，我们将S i m u l i n kC A A M 模型转换为用于划分、映射和调度的图模型。3 1 1 应用程序建模对应用程序进行S i m u l i n k 功能建模可以揭示应用程序的深层流水及并行性，同时也能最大化重用有限资源，促进数据解析，简化软硬件模型自动生成的操作。S i m u l i n k 功能建模方法是基于抽象时钟同步模型A C S M 。A C S M 模型可以方便地描述条件模块，利用偏序依赖关系挖掘并行性和流水性。S i m u l i n k 描述语言可以为A C S M 模型提供有效地仿真和离散系统的环境建模。A C S M 模型包含三个基本组件：块( b l o c k ) ，延迟( d e I a ”和连接边( a r c ) 。图3 1 显示了一个应用程序使用S i m u l i n k 来建立A C S M 模型的实例。特定的应用代码可以精化成由几个模块化函数组成。每个函数块可以转换成用户自定义的S i m u l i n k 块，例如特殊操作可转换成S 函数块( S f u n c t i o n ) 或者预定义的S i m u l i n k块。然后，综合集成所有的S 函数块和预定义块就可以构建一个S i m u l i n k 算法模型。S i m u l i n k 模型由S i m u l i n k 块，S i m u l i n k 链接以及S i m u l i n k 子系统组成。如图3 1 所示，C 语言i f - e l s e 代码可以被转换成一个I f - A c t i o n 子系统。1 9浙江大学硕1 ：学位论文第3 章多核系统芯片任务级并行化方案设计与研究? “c a 6 咖c 庀+ + c o d e 8 F o f 盛n 鸳J ：，f F B ( O u t l O , & O m l ) ；挈i = 0 ；i 9 9 j + + ；N ( o 虬J ：芒二土O , & O u l 2 e l s e卜1 日E 二二) 踟刚，：l UF I I ( ，& o I l t 毗P 眦， ；】F 3 ( o 啷，一；E !；：图3 1S i m u l i n k 建模通常，S i m u l i n k 模型不需其他硬件信息或软件信息就可以描述一个应用。然而，体系结构设计者可以向模型中添加软硬件配置信息来构造一个混合模型，以便更清晰地反映体系结构和应用程序的协同设计信息。软硬件混合模型可以在抽象层建模一个多线程异构M P S O C ，无需依赖设计流程的描述语言。也就是说，一个S i m u l i n k 模型和一个硬件体系结构模板可以整合入一个混合模型，其中每个软件线程映射到一个处理器子系统。混合的软硬件模型可以通过抽象处理器节点和通信拓扑关系来表示。C P U 由软件子系统替代，而通信则可以使用一个抽象通信平台来描述。这样就可以获得一个最高层抽象表示的软硬件混合的体系结构模型C A A M 。一个S i m u l i n kC A A M 模型可通过S i m u l i n k 可视化用户接口创建。基于S i m u l i n k C A A M 模型，设计者可在后续阶段手动或自动将任务划分成不同的子系统。一个子系统由一个或多个S i m u l i n k 块构成，支持细粒度或粗粒度的任务划分。根据各个不同抽象层的仿真反馈，C A A M 体系结构模型可以不断更改直到符合设计要求。C o l i f 是一个基于X M L 的中间模型，为数据操作提供了良好的数据结构。C o l i f可以表示一个由模块( m o d u l e s ) ，信道( c h a n n e l s ) 和端口( p o r t s ) - - 种实体组成的通用系统。如图3 2 所示，S i m u l i n k 模型与C o l i f 模型是一一映射关系，例如S i m u l i n k块对应模块，S i m u l i n k 链接对应信道，S i m u l i n k 端口对应端口。除了C A A M 格式的转换外，S i m u l i n k 解析器还将连接子系统间通信( I n t e r - S SC O M M ) 的端口转换成发送块，或将连接子系统内通信( I n t r a S SC O M M ) 的端I S l 转换成接收块。这些发送浙江大学硕十学位论文第3 章多核系统芯片任务级并行化方案设计j 研究块和接收块将与其他块一起进行调度。磐妊：缮矗僦铷勃箩翰触S S ：蜘蛔舅缒舷图3 2C o l i fC A A M 的C P U l 子系统实例【1 2 1经过上述过程，应用程序被建模成原始的未作任务并行化操作的C o l i f C A A M模型，以X M L 文件格式呈现，作为后续任务划分、映射调度的源。以下是一段C o l i f C A A M 模型建模j p e g 解码应用的实例。 ! 一 v a l u en a m e = ”m o d u l e ”A c t i o n k n S u b s y s t e m1 一S1 ”胗a c c e s s = ”r e f d a t a = “C M I f v a l u en a m e = ”n a m e ”a c c e s s 2 ”v a l u e ”d a t a = ”! B l o c k T y p e ”侈 ! t y p e r e fb a s e = ”M O D U L E _ D E C L ”侈 v a l u en a m e = ”v a l u e ”a c c e s s = ”v a l u e ”d a t a = ”I m a i nc t r l ”侈2 l浙江大学硕士学位论文第3 章多核系统芯片任务级并行化方案设计i 研究 v a l u en a m e = ”v a l u e ”a c c e s s = v a l u e ”d a t a = ”! i n t 3 2 ( 1 ) I t 胗 v a l u en a m e = ”v a l u e ”a c c e s s = ”v a l u e ”d a t a = ”! m a i nc t r lw r a D p e rZ ：s i m u l i n k j p e g s r c n o d e _ m a i n _ c t r lZ ：k s i m u l i n k _ j p e g k s r c r a r s eZ ：k s i m u l i n k _ j p e g X s r c t a b l e _ v l dZ ：k s i m u l i n k _ j p e g s r c u t i l sZ ：k s i m u l i n ki p e g k s r c c o m m o nu t i l ”卢 v a l u en a m e = ”n a m e ”a c c e s s = ”v a l u e ”d a t a = ”IM a s k T y p e ”胁 v a l u en a m e = ”n a m e ”a c c e s s = ”V a l H e ”d a t a = ”! M a s k l n i t i a l i z a t i o n ”胗 v a l u en 硼e = ”n a m e ”a c c e s s = ”v a l H e ”d a t a = ”! M a s k D i s p l a y ”胁 i t e m d e ：今 ! 一3 1 2 任务映射调度建模并行化工具通常使用图理论模型来表示一个应用程序。计算和图的节点相关联，而通信则和图的边相关联。也就是说，在一个图理论抽象描述中，一个并行程序包含两类活动：计算和通信。一个任务内的所有指令顺序执行，也就是说，在一个任务内没有并行性可挖掘。图模型根据以下几方面进行分类：可以建模的并行计算，所支持的并行体系结构，以及其适用的算法。有向无环图D A G 是最常用的图模型，但它无法有效处理有环计算。对于那些循环体较大，或者编译时刻无法确定迭代次数的应用计算，无法使用D A G 来建模表示，它主要用于粗粒浙江人学硕J ：学位论文第3 辛多核系统芯片任务级并行化方案设计与研究度计算的表示。迭代任务图I T G 主要用于建模迭代计算，而时序通信图T C G 受其进程和阶段方法的制约。以上图模型没有一种具有通用性，即以上所述的模型没有一种可以用来表示所有类型的应用计算。而现在大部分任务并行化工具都是基于一种图模型，使得只能使用有限的调度和映射算法，限制了应用领域和适用的体系结构。我们的任务并行化方案使用扩展的带注释的层次任务图( A n n o t a t e dH i e r a r c h i c a lT a s kG r a p h ) 来建模。层次任务图H T G 整合集成了各种图模型，可以借鉴各种图模型的优势，它可同时表示粗粒度计算和迭代计算，而且不受进程和阶段制约。层次任务图的主要思想是，图的一个节点本身也可以是另一个图，如图所示。在这个例子中，有向主图包含n l ，n 2 ，n 3 三个节点，n 3 节点本身又是一个包含n 3 l ，n 3 2 ，n 3 3 节点的有向图。子图是一个环，表示一个迭代计算。层次任务图H T G 的形式化定义如下：层次图G 是一个二元组( v ，E ) ，其中V 是顶点的有限集，E 是边的有限集。E的一个元素e _ 沁v ) 定义节点u , v E V 之间的一条边。边( u ，v ) 定义从节点U 到节点v 的一条边，因此( u ，v ) ( V u ) 。一个顶点u V 可以自身是一个层次图G 。，进入顶点U 的边，进入子图G u 的源节点( s o u r c en o d e s ) ，离开顶点U 的边，离开子图G u的汇节点( s i n kn o d e s ) 。对于源节点，移除和其相关的所有表示延迟的边后，没有入边；对于汇节点，移除和其相关的所有表示延迟的边后，没有出边。在图3 3 ( a )所示例子中，节点n 3 l 就是源节点，节点n 3 3 就是汇节点。层次图可以用子图替代节点，从而变为一个简单有向图。如图3 3 ( b ) 所示，节点n 3 由它所表示的子图替代后，层次图变为简单有向图。浙江人学硕士学位论文第3 章多核系统芯片任务级并行化方案设计与研究图3 3 ( a ) 层次图( b ) 延伸的层次图D层次图模型可以在一个图模型中统一表示迭代计算和非迭代计算。层次图模型提供了灵活的表示方法，来建模一系列广领域的应用，所有适合D A G ，I T G 和T C G 的算法都可应用于层次图模型。层次图的每个节点都有一个注释。文字形式的注释可以表示节点所执行的计算。C 代码或V H D L 代码是文字注释的两个例子。注释可用于评估计算的时间或用于并行化工具输出代码的自动生成。另外，任务的文字化描述允许根据目标机器的体系结构来评估任务的执行开销。边的通信也由注释来描述，表示边所传输的数据结构和数据量。边的注释可以用来评估通信开销，或用于代码的输出生成。有了边所传输的数据量信息，并综合考虑目标机器的特征，通信开销就可以通过如下公式计算获得：c o s t ( c o m m ) = 启动开销c o s t ( s t a r t u p ) + 传输速度s p e e d ( t r a n s ) 数据量a m o u n t ( d a t a )3 2 任务自动并行化针对上面所述的的多核系统芯片任务级并行化问题，本文所采用的研究方案及系统框架结构如图3 4 所示。以X M L 文件呈现的使用C o l i f 表达的S i m u l i n kC A A M 模型作为系统的输入，系统将其转化后生成扩展的加注释的层次任务图模型，用来作为后续并行化操作的基础。任务并行化主要分成三大模块，即基于改进的H T G 的任务划分、两阶段任务映射以及兼容条件任务的调度。完成应用计算任务的并行化操作后，将会生成包含划分结果信息的多线程代码。2 4浙江大学硕上学位论文第3 章多核系统芯片任务级并行化方案设计与研究使用C o l i f( 一种基于X M L 的中间表示) 表达的S i m u l i n kC A A M 模型( 己对应用程序进行建模)转化生成扩展的加注释的层次任务图E x t e n d e dA n n o t a t e dH T G基于改进的H T G 的任务划分两阶段任务映射X - y L ，-一任务并行化方案兼容条件任务的调度库专含结果信息的程序图模型上转化生成含结果信息的多线程代码图3 4 任务并行化系统体系架构下面，将详细阐述任务并行化方案中的三大模块和主要算法。3 2 1 基于改进的H T G 的任务划分图划分问题是个N P 难科P c o m p l e t e ) I h 习4 4 , 4 4 J 。近年图划分算法在高质量和计算有效性方面已有一定进展。在图划分算法中，多层次图划分算法【4 5 , 4 6 J 被认为是当前较为经典且被广泛使用的算法。多层次图划分算法的主要目标是将任务图划分成子图，使得各个任务线程可以满足执行时间的性能要求，以及计算负载均衡的性能要求。算法分为粗糙化阶段( C o a r s e n i n gP h a s e ) ，初始划分阶段( I n i t i a lP a r t i t i o n i n gP h a s e ) ，以及反粗糙化( U n c o a r s e n i n gP h a s e ) 和细化( R e f i n e m e n t ) 阶段这三个阶段。在粗糙化阶段，从原始任务图中获取一组更小问题规模的图。应用最大匹配方法从原始图构造产生新图，匹配中两条边上均入射的节点将被折叠f c o l l a p s e d ) 成新图中的新节点，其余原图节点在新图中保持不变。图的一个匹配是2 5浙江大学硕士学位论文第3 章多核系统芯片任务级并行化方案设计j J 研究一组边，其中没有任何两条入射到同一节点上。对于图的匹配，可以通过几种不同的方法计算获得，如随机匹配( R a n d o mM a t c h i n g ，R M ) ，重边匹配( H e a v y E d g eM a t c h i n g ，H E M ) ，最大权重匹配及近似最大权重匹配，其中最常见的是随机匹配R M 和重边匹配H E M 。随机匹配使用一个随机算法来计算最大匹配，其主要思想为：随机顺序访问图的节点，若节点未被匹配，则随机选取一个未被匹配的邻接节点进行匹配，两节点的边将纳入匹配( m a t c h i n g ) d 0 。重边匹配会计算个匹配，使得匹配中的边的权重值足够高。重边匹配也使用一个随机算法，随机顺序访问图的节点，若节点未被匹配，则选取连接边中权重较高的一个节点进行匹配。这样，重边匹配机制较之随机匹配，大大减少了粗糙化图中边的权重总和，也降低了随后的细化过程中所用时间开销。对于折叠操作，其规则如下：若两个节点折叠组合成一个新的节点，则新节点的权重是两原始节点权重的总和，新节点入射边的权重是两原始节点各自所有入射边的权重和，减去两节点间的边的权重得到的结果。若一条边在两个节点上均为入射，则这条边的权重被设为所有这些边的权重总和。在连续的粗糙化过程中，节点和边的权重不断增加。完成粗糙化后，算法将计算粗糙化图的一个平衡划分( b a l a n c e db i s e c t i o n ) 。由于这些子图规模较小，应用简单算法进行划分也能取得理想的性能效果。算法的最后_ 步是根据子图计算获得的划分得到原图的划分。在反粗糙化和精细阶段，粗糙图的划分结果将会映射回原图。在这个反粗糙化过程中，每一层都会使用一个划分细化启发式算法来提高划分的质量。本文的研究方案采用改进的带注释的层次任务图作为图模型基础，划分算法是针对层次任务图模型扩展改进的多层次图划分算法。本文对带注释的层次任务图模型进行了相关改进，整合了传统的条件任务图，增加了任务执行中的控制流信息，可以有效建模有条件分支结构的多媒体应用。扩展的带注释的层次任务图( E x t e n d e d A n n o t a t e dH i e r a r c h i c a lT a s kG r a p h ，E A - H T G ) 是一个四元组( VE ，C a ，c O ，其中V 是顶点的有限集，E 是边的有限集。E A H T G 的一个顶点u V 可以自身是一个扩展的带注释的层次任务图甲u ，其权重通过计算所代表的子图的所有节点和边的权重之和获得。E A H T G 的边有两类，分别是表示延迟的边和表示通信的浙江大学硕J j 学位论文第3 章多核系统心I I - 门1 1 任务级并行化方案设计与研究边。C 旺是任务计算时间的集合，顶点v V 的权重与C a 中的一个元素相对应。C B是任务间( 即一个父任务和其予任务间) 通信属性的集合，通信属性是通信数据大小和执行概率的一对组合，其中，通信数据大小指存在通信的父任务和其子任务间数据传输量的大小，执行概率则表示父任务创建执行的情况下，子任务创建或尝试创建执行的可能性大小。E 中表示通信的每条边均与C B 中的一个元素相关联。上述关于扩展的带注释的层次任务图E A H T G 的描述，可以表示为：d e f i n i t i o no f i n s t a n c eo f亡e q u i v a l e n c eo f甲营E x t e n d e dA n n o t a t e dH i e r a r c h i c a lT a s kG r a p h( y ，E ，e ，G 少甲 z fU - s i n g l et a s kn o d e sAU 一 甲抄V Pe - t a s ki n t e r c o n n e c t i o n s E ( 1 ，) ，V n 今e sS - ，m c r i t i c a l， 口J ，m n o tc r i t i c a l a m所有任务的期限错失偏差和就为：d e v = d e v , ,J = 】根据上面所介绍的两个用于开销函数建模的概念，下面我们将建模本文研究的映射算法方案中作为性能判定参考的开销函数。任务到处理器间的映射可以用开销函数来衡量，开销函数标志着映射效果的好坏。任务映射结果有两个性能目标：一个是尽可能多的任务并行执行；另一个是通信负载尽量减小。但有时这两个目标是相互矛盾的。好的解决方案是在这二者之间进行合适的折衷。因此，在选择开销函数时就需要考虑到上述两个方面的要求。我们将根据任务类别，即普通任务、迭代计算和运行不确定任务，分别建立其各自对应的开销函数，并最终统一于一个完整的应用计算中，建立其对应的开销函数。当处理器数量比任务数量少时，几个任务必须在同一台处理器上执行，将有可能使几个相互独立且原本可以并行执行的任务在同一台处理器上串行执行，这种情况称为“丧失并行量 。它是普通任务的开销函数中的一个组成部分。设M i是映射到处理器P i 上的任务集的子集，其中的任务均为普通任务，集合中一些任务之间有前后约束关系，另一些任务之间是相互独立的。M i 在处理器P i 上的执行时间为t F u m , 2 吼( 弓圳，其中哂为M j 集合中的任务T j 的计算时间。若设M i的关键路径c p i 上各任务执行时间总和为c p , ，则处理器P j 上丧失的并行量定义为z D 吼2 一乞。即当哪2 乞时，处理器P i 不丧失并行量。这样，映射到各处理器上的普通任务组成的系统集合的最大丧失并行量可定义为：M 协2m a X ( ，D 嘞) 。映射所对应的通信负载依赖于处理器间的互连结构，设处理浙江大学硕上学位论文第3 章多核系统芯片任务级并行化方案设计与研究器P i 与P j 间的最短距离为d i j ，任务T - 分配给处理器P i ，T j 分配给处理器P j ，则任务T i 与T j 之间的有效通信量为e i j = l c i j l 木d o ，其中c i j 为任务T i 到T j 的通信量。处理器P i 上的通信负载可定义为o 2 ( 瓦M ，乃M ，) ，其中M i 和M i 分别是映射到处理器P i 和P j 上的任务集，这样，映射到各处理器上的普通任务组成的系统集合的最大通信负载可定义为M m = m a ) ( ( 乙吣) 。至此，普通任务组成的系统的开销函数就可定义为C r I2 + M 。对于迭代计算任务，在虚拟机u 上任务的执行时间总和为t u ( s i ) ，基于动态参数的所有虚拟机任务执行时间的开销为M i t e r - c o m p = m a x ( t 。( s i ) ) ，其中u 为处理器集合中的元素。两台虚拟机u 和v 上任务间通信时间总和为C 。v ( s i ，S i ) ，其中S i为运行在处理器U 上的任务集合中的元素，s i 为运行在处理器v 上的任务集合中的元素，则基于动态参数的虚拟机任务间通信开销为M i 肼m m = m a x ( E C u ，( s i ，s i ) ) 。这样，迭代计算任务的开销函数就可定义为C r ：= M 御一叩+ 鸭”一m 。C ，：y 如v对于运行不确定任务的开销函数，我们将其建模为b-。综合上述不同类别任务的开销函数，我们对一个完整的应用计算的开销函数建模如下：C r = c r 。+ c r 2 + C r ，其中F 1 是普通任务的集合，r 2 是迭代任务的集合，F 3是条件任务的集合，F ln F 2vF ln r 3 。g ，而r 2 厂、r 3 不一定是空集，且r lu F 2k ) F 32F 。根据上面描述的开销函数，下面，我们将重点阐述本文所提的任务自动并行化研究方案中的映射算法。该算法适用于包含迭代任务和运行不确定任务的计算应用。算法的主要思想是，在第一阶段，对划分算法获得的各任务集，使用E C T ( E a r l i e s tC o m p l e t i o nT i m e ) 算法构造初始解，并计算其开销函数，然后，在第二阶段，分别使用模拟退火、遗传算法和禁忌搜索等智能算法，对解空间进行动态探索求解，根据开销函数不断调整映射方案，最后对各智能算法的最优解空间3 2浙江大学硕士学位论文第3 章多核系统芯片任务级并行化方案设计j 研究进行比较，求得任务映射的近似最优解。两阶段任务映射算法的详细描述如下：第一阶段，使用E C T 算法构造初始解，并计算开销函数。E C TA l g o r i t h ma 按如下方法构造一个基于层次的任务列表厶将划分结果中的每个任务集( 没有前驱) 标记为层次1 。对剩下的任务集，若其最高层父节点在层次i 一1 ，则将其标记为层次i 。L 是按任务集层次递增排序的列表。对于同一层的任务集，则将其按子节点数量递减排序。b f o rL 中每个任务集S ；d o ：f o rp = lt oP 。 p 为可用处理器d o ：找到任务集S j 的最早开始时间t 。州使用处理器标记S ；的完成时间。e n d f o r将任务集S i 映射到处理器p 上使得其完成时间最小，更新可用处理器信息。e n d f o r处理器数量、通信带宽等硬件体系结构信息可以从S i m u l i n kC A A M 模型中解析获得。若计算应用中包含迭代任务，且计算获得的P o p t 的值与硬件结构信息中的处理器数量相同，则E C T 算法构造的初始解是有效的。根据初始解中任务映射到处理器的情况，以及从S i m u l i n kC A A M 模型中获得的体系结构信息，我们可以计算出初始解对应的开销函数。第二阶段，使用智能算法对解空间进行探索，寻找任务映射的近似最优解。我们使用三种智能算法，分别对解空间进行探索，根据开销函数不断调整映射方案，最后从三种智能算法的解空间中选择最优解，作为任务映射的近似最优解。下面，我们对使用遗传算法和禁忌算法进行解空间探索的情况作进一步阐述。对于遗传算法，我们首先设计将任务映射所有可能的解编码成染色体( c h r o m o s o m e )组，即一个群体( p o p u l a t i o n ) 。每个染色体包含两个部分：匹配字符串m a t ( i ) = j ，表示任务S i 被映射到处理器类型j ，以及处理器分配字符串a l l o c ( i ) = j ，表示分配给任务S i 的类型为j 的处理器数量，其中a l l o c ( i ) p o p t 。每个字符串是长度为n 的向量，n 为应用经过划分后得到的任务集数。多个任务会被分配到一些相同的处浙江入学硕士学位论文第3 章多核系统芯片任务级并行化方案设计与研究理器上，然后以非抢占方式按照优先级约束( 数据依赖) 定义的顺序来执行。在初始群体产生阶段，染色体组的个预定义的数量按照如下方式随机创建：一个新的匹配字符串通过随机分配每个子任务到一个处理器组来获得。每个染色体初始的分配字符串通过随机选择从1 到p o p t 的一个值作为分配给每个子任务的处理器数量来产生。从E C T 算法得到的原始解也被编码成染色体，包含进初始群体中作为种子( s e e d ) 。在遗传算法G A 中，必须保证初始群体的染色体之间各不相同。产生初始群体后，交叉、变异和选择等遗传算子将应用到新产生的一代代群体上，直至解的质量( 即实现开销函数最小化目标的情况) 在1 5 0 代中都未提高。在遗传算法中，将使用精英主义( E l i t i s m ) 来保证每一代的最优解被显式保护，不被变异和交叉等遗传算子修改。对于禁忌算法，我们也从E C T 构造的初始解开始进行探索，这个最初解被标记为当前最优解。算法为当前解计算其代价函数C r = C r 。+ C r ：+ C r ，。使用一个列表T M 来跟踪被标记为禁忌( T a b u ) 的求解的移动情况，这个列表初始为空。我们使用从当前求解点出发的所有可能的移动的一个子集来构造候选移动( C a n d i d a t eM o v e ) 。定义N ( C M ) 为从当前解c r ts o l 做一次移动可达到的解的集合。对N ( C M ) 中的每个解，根据乙r2 乙r - + 乙r ：+ 乙r ，来计算评估，、，1t ，、t ，、其代价函数。选取候选移动集中的一次移动的过程如下：若j m C M 使得m 珑V m eC M C r ( m ( c r t s 0 1 ) ) g l o a b l b e s t ，则移动m 就被选中。否则，若3 m C M T M 使得m m V m C M T M ，则移动m 就被选中。否则，m T M使得m m V m - T M ，则移动m 就被选中。对当前解应用选中的移动m 就可达到新的解。移动m 的逆( r e v e r s eo f m o v e ) m 被标记为禁忌( t a b u ) ，因为其在后续几步迭代中一般不会被逆转。若新求得的解比当前解的开销小，则新的解成为当前为止的全局最优解。构造候选移动集合以及根据标准选取一步移动的过程是不断重复的。整个过程一直重复直到启发式的迭代超出既定的最大迭代次数为止。这个算法过程将返回产生最小开销代价函数的解。任务映射求解的禁忌算法，其描述如下。3 4浙江大学硕：学位论文第3 章多核系统芯片任务级并行化方案设计与研究T a b uAl g o r i t h mf o ，m a p p i n gc r t s o l = s o l 一：f r o m E C Tg l o b a l b e s t s o l = c r t s o lg l o b a l b e s t = i n i t c o s tT M = s i n c e l a s t _ i m p r o v e m e n t = 0i t e r a t i o n c o u n t = 1C M = s e t o f c a n d i d a t e m o v e s ( c r t s 0 1 )( c h o s e n m o v e ，n e x t _ s o t _ c o s O = c h o o s e m o v e ( C M )w h i l ei t e r a t i o n c o u n t m a x i t e r a t i o n sd ow h i l es i n c e l a s t _ i m p r o v e m e n t Wd on e x t s o l = m o v e ( c r t s o l ，c h o s e n m o v e )T M = T Mu c h o s e n m o v e s i n c e l a s t i m p r o v e m e n t + +i t e r a t i o n c o u n t + +c r ts o l = n e x ts o li fn e x t S O l c o s t g l o b a l _ b e s tc o s tt h e ng l o b a l _ _ b e s t _ c o s t = n e x t s o l c o s tg l o b a l _ b e s t _ s o l = c r t s o ls i n c e l a s t _ i m p r o v e m e n t = 0e n d i fC M = s e t o f c a n d i d a t e m o v e s ( T M ，c r t s 0 1 )忙h o s e n m o v e ，n e x t s o lC O S 0 = c h o o s e m o v e ( C M )e n d w h i l es i n c el a S ti m p r o v e m e n t = 0p h o s e n m o v e ，n e x t _ s o l _ c o s O = d i v e r s i f y ( T M ，c r t s 0 1 )i t e r a t i o n c o u n t + +e n d w h i l er e t u r ng l o b a l _ b e s t _ s o l综上所述，两阶段任务映射算法可描述如下：3 5浙江大学硕士学位论文第3 章多核系统芯片任务级并行化方案设计与研究3 2 3 兼容条件任务的调度库多处理器系统的任务调度挖掘最大并行性是个N P 难问题【4 引。图的调度算法主要有简单及各种变形的列表调度( L i s tS c h e d u l i n g ，L S ) 4 9 , 5 0 l ，改进的关键路径启发式( M o d i f i e dC r i t i c a lP a t h ) 5 1 】，以及各种迭代搜索启发式【5 2 1 ，如遗传算法( G e n e t i cA l g o r i t h m ，G A ) ，模拟退火( S i m u l a t e dA n n e a l i n g ，S A ) ，禁忌搜索( T a b uS e a r c h ，T S ) 和A 木算法等。定义任务图的粒度为节点与其相邻最大权重出边之比的平均率，G r a n u l a r i t y ：上( y J ；b )即一s 。智m a X 【- J 。，其中N 是所有节点，s 是所有汇节点( s i l l kn o d e s ) 。对于任务执行开销远远大于任务间通信开销的高粒度图，K h a n 5 3 1 在论文中通过比较几种调度方法，发现使用改进的关键路径方法可以获得较好性能指标，而对于任务间通信开销远远大于任务执行开销的低粒度图，使用列表调度启发式可以获得较好性能指标。以上调度算法是针对的任务图是不包含条件分支跳转节点信息的图模型，不适用于概率执行的任务节点的调度。针对条件任务图的调度，L o m b a r d i 等人【5 4 】提出了预期的完工时间( m a k e s p a n )约束的概念，使用其随机目标函数的解析公式来指导调度。在条件任务图中，每个节点表示一个任务( 也可称为活动) 。任务是非抢占的，有固定的间隔，在特3 6浙江大学硕士学位论文第3 章多核系统芯片任务级并行化方案设计与研究定的时间窗内执行( 时间窗由最早开始时间和最迟结束时间定义) 。目标函数是最小化预期完工时间。预期的完工时间定义为：E ( m a k e s p a n ) = 芝：p ( c o ) m a x e n d ( t , ) l ，t a s k s ( w ) )一-，p ( c o ) 是执行场景C O 的概率。预帚r I4 _ r 切育卜r I 脑叠1 1 | 1期完工时间约束依赖于两种数据结构：分叉图( B r a n c hF o r kG r a p h ，B F G ) ，它系统地表示了所有可能的执行场景，以及树，它是分叉图的一个子图，选择了一组场景集合，此场景集包含或不包含一组特定节点。B F G 和树提供了一个通用强大的工具来定义其他全局条件约束。L o m b a r d i 【”】在文中提出了对条件任务图的调度方法，使用分叉图B F G 和树作为工具来求解完工时间最小化的目标函数。过程首先通过节点映射，由条件任务图构造分叉图，然后查询分叉图，从而获得图的一个子集，即一组特定执行场景的集合，也就是树，接着通过子图概率( S u b g r a p hp r o b a b i l i t y ) 算法，可以计算出子图分支节点的执行概率，最后通过针对上界的结束变量的剪枝算法( E n dv a r i a b l e sp r u n i n g ) 来执行一个过滤过程( f i l t e r i n gp r o c d u r e ) ，可以有效地计算完工时间表达式( m a k e s p a ne x p r e s s i o n ) 中的权重，便捷地筛选完工时间变量和任务结束时间变量，从而达到目标函数完工时间最小化。我们的任务并行化方案中，设计了兼容条件任务和通用任务的调度库。对于已映射到处理器上的任务节点在时序上的调度，我们采取根据任务集属性的方法，若其包含概率执行的节点，则采用最小化预期完工时间的目标函数来进行调度，否则，就计算任务集的粒度，对于高粒度我们选用改进的关键路径法进行任务调度，对于低粒度我们选用列表调度启发式来进行任务调度。综上所述，从S i m u l i n kC A A M 模型作为起点，经过基于改进的层次任务图的任务划分，两阶段任务映射及兼容条件任务的调度过程后，我们得到了包含划分结果并在空间和时间上有了映射和调度信息的一系列可并行执行的任务，生成了含有划分映射和调度信息的多线程代码，实现了任务的自动并行化。3 3 本章小结本章详细阐述了多核系统芯片任务级并行化的研究方案。引入S i m u l i n kC A A M 计算模型，对所研究的应用进行建模后，再通过对任务映射调度的建模，3 7浙江人学硕上学位论文第3 章多核系统芯片任务级并行化方案设计与研究完成对整个多核系统芯片任务自动并行化问题的建模。然后重点讲述了任务自动并行化的方案，包括基于改进的带注释的层次任务图的任务划分，采用智能算法求取近似最优解的两阶段任务映射方案以及兼容条件任务和普通任务的调度方法。3 8淅大学硕士学也论文第4 章实现与结果分析第4 章实现与结果分析4 1 系统框架与实现本文研究提出的任务自动并行化系统框架包含m o d e l 模块和a l g o r i t h m 模块，分别实现了对应用程序建模相应数据结构，以及对任务映射调度并行化问题进行建模求解。m o d e l 模块包含了从以x m l 文件形式呈现的S i m u l i n k C A A M 模型建立国模型的解析类，以及表示改进的带注释的层次任务图模型的类提供了E A - H T G 相关元素的数据结构以及基本的图算法，例如广度优先搜索B F S ，深度优先搜索D F S ，拓扑排序，连通分量计算等等。图4 1 和圈4 2 是从蛆文件表示的S i m u l i J l k C A A M模型解析出软件应用程序的信息和硬件体系结构信息的功能类的程序片段截圈。- r 【t 一F t _ E 。2g。目目霉E | 目墨( 靴c 一5 。u 1 咖n t e 、t 。ti一m 一一n - j：= + 。j ? “霎_ “_ 目口6 】”t “If 0 7 1 - o H ，i z c I留4lS i m u l i n kc A I I 模型解析程序片段十E 目浙大学碗学位论文第4 章实现结果* 析当竺! ! 霸皇煅耀算一一二三目T m h u _ 。=! i 氇。q # m ”6 【l T “面I ；懋竺黜：譬；怒= ”：勰黜函t ：i 龟=，”“”，：= ：。P n 。”。t h 。f 0j m b t om q 。“”；E mc )l e l e D s e t n d u l 曲，一W 口5 咖C 】g e um ” gF s p o o ) 】s e d u l 一，一r 1 M e u# ，a “ 口 s Y 一【) ” 】；“一t ，f 。w d o ) 1 。E 。啦，I t c 口e 咄) 1 一o r 【】_ !一二一”，巴目J m 如E m 日c m d = 、* x 碴星乒l 乒10 ”t 。口m m 卅“_ 4 l 口d j 川 叫m - 】c * 一h 1 v 州，水l _ U 一删删十”i图4 2 从s i 叫1 i n kc M 模型转换到E - I T G 图模型的程序片段国43 为解析出的包含软件信息和硬件信息的s i n l l l l i n k c A A M 模型的可视化效果图。a l g o r i t h m 模块包含了本文研究设计的两阶段映射方案以及调度方案中相关算法的实现类，包含了用于任务映射的各种智能算法的实现，诸如遗传算法，模拟退火算法，禁忌搜索算法，和任务映射问题的建模求解实现，以及己由其他研究提出的应用于任务映射的E C T 算法，和列表调度启发式算法，改进的关键路径算法等调度算法。淅大学碰t 学位论文薷4 章实现与鲒果分析一，一，- 一。I h 一，J ”，图4 3 解析出的s 1 叫l i n kc A M 模型信息可视化效果经过任务并行化系统处理后将得到包含划分结果信息的多线程代码。如下所示是一多媒体编解码应用经过任务并行化后得到的多线程代码实例的片段：文件C P U S 1cv o i d C P U i _ s 1 ( ) fv e f t o r _ a t t a c h ( A R M _ I R Q , 0 ，_ m a i l b o x _ i s r , N U L L ) ；v c c t o r _ s t a r l ( ) ；w h i l d 】) m a i ni n i t ( m e m 0 ，m e m 6 ，m e t a l ，m e m 3 ，m e l I l 2 ，& m e m l 6 ，m e m l 7 m e m l 8 ，m e m l 9 ) ；d m a _ m e m c p y ( ( ( c h a r ) m e r a 2 0 ) ( ( c h a r ) l T l e m 1 ，0 5 1 2 ，o ) ；m e m O = m e r e l 6 ：1 c m l = m e t a l 7 ：m e r a 3 = m e m l 8 ：s e a d _ d a t a ( & O u t 4 _ C P U IS 10 & m e r e I8 4 ) ；m a i n _ c t r l ( m e m 4 ，m e m 5 ，m e m l 9 ，r e c t a 2 0 ，m e m l 2 ，m e m l 3 ，& m e r e 】4 ) ，d m a _ m e m c p y ( ( ( c h a r * ) r n e m l 5 ) , ( ( c h a r ) t r l c m 2 0 ) , I ，0 ，5 1 2 ，0 ) ：弧j ：m “l = 0 ：j 嗡，j + + )m e m 4 i 】= m e m l 2 i ；s e n d _ d a t a ( & O u t I _ c P U I _ s 1 _ 0 ，& m e m l 4 4 ) ；浙江火学硕士学位论文第4 章实现i 结果分析来分析说明本文研究方案的有效性。4 2果浙江大学硕十学位论文第4 章实现与结果分析4 2 仿真与分析本文研究基于的M P S O C 硬件架构平刽1 2 】，由处理器子系统、通信网络机制和存储器架构三个主要部分组成。处理器子系统硬件架构支持三种不同类型的处理器，包括A R M 7 、C K C O R E 和X t e n s a 。其中，A R M 7 是三级流水架构，可用于简单应用和普通系统的控制，C K C O R E 处理器是浙江大学和杭州中天微系统公司联合自主研发设计的基于M C o r e 指令集的1 6 位指令和3 2 位数据的高性能嵌入式处理器，主要面向信息安全领域及音视频等媒体领域的应用，可用于简单多媒体应用和复杂系统的控制，X t e n s a 处理器是可配置处理器，功耗和面积相对较大，可作为复杂应用的核心处理单元。对于通信网络机制，基于S i m u l i n k 的M P S O C硬件架构平台可提供四种不同的通信机制，包括基于全局共享存储器的软件F I F O ( G F I F O ，S o f t w a r eF I F OV i aG l o b a lS h a r e dM e m o r y ) ，硬件F I F O ( H W F I F O ，H a r d w a r eF I F O ) ，共享存储( S H M ，S h a r e dM e m o r y ) 和分布式存储( D M S ，D i s t r i b u t e dM e m o r yS y s t e m ) 。M P S O C 设计平台的存储系统分为寄存器、高速缓存C a c h e 本地存储、片上共享存储和片外共享存储这四层。本文仿真和实验的架构平台是由四个处理器子系统和存储器子系统组成的共享存储的多核架构。在给定体系架构和约束的情况下，该平台可以利用其I P ( I n t e l l e c t u a lP r o p e r t y ) 库和工具，自动生成所需的寄存器传输级( R e g i s t e rT r a n s f e rL e v e l ，R T L ) 仿真验证平台和元件可编程逻辑门阵3 i t J ( F i e l dP r o g r a m m a b l eG a t eA r r a y ，F P G A ) 平台，从而确保系统集成的正确和高效。如图4 4 所示，系统芯片( S y s t e mo fC h i p ，s o c ) 设计流程开始于应用程序，最后生成一个目标S O C 平台。整个流程主要由四部分组成：体系结构生成、组件生成、设计生成和F P G A 生成。4 3浙江 学硕士学位论文第4 章实现与结晕分析；慝磊司卜 = 飘引蓉萨川| 蓬蚕誉互羞耋鲎；| 熹垂藁驾 i i b | ：罢掌姜娑盛；苌兰型；i 裂i：b 离算! 广：r 一上L 一：二：! 军二i 一二= ! = 。 L 忑。号兰苎掣奎强豳 ：。三兰= F = 二一由因蜜圈函剧4 4 本文研究基于的S O C 设计流程图”1仿真评估器对一个应用进行仿真后，得到各个任务的计算和通信负载。设计流程在S i m u l i n kC A , a M 模型中，建模整合这些计算通信负载信息与应用程序结构信息及处理器硬件体系信息，然后以X M L 文件的形式提供给本文研究实现的系统进行任务自动并行化。本文研究实现的任务并行化系统对建模后的应用进行解析，进一步实现任务划分、任务映射和任务调度，并最终将任务并行化的结果重新以S i m u l i n k C A A M 模型进行建模，反馈给设计流程平台。如果性能不能满足要求，则会重新进行任务并行化过程，接着继续评估性能，直至结果满足设计需求。另一方面，设计者使用硬件架构平台的用户配置文件m s e rC o n f i g u r a t i o nF i l e )来描述整个系统的体系结构，这个文件随后被转化成为三个文件：I P 约柬、整个设计的X M L 和F P G A 数据信息分别输入到组件生成器r C o m p o n e n tG e n e r a t o r ) 、设计生成器( D e s i g nG e n e r a t o r ) 和F P G A 生成器。组件生成器将根据I P 的约束对I P 库中相应的卯进行配置，生成所需疋的寄存嚣传输级R T L 代码、X M L 文件和测试用例。设计生成器将根据设计X M L 文件中的I P 互连和系统配置信息，完成I P 互连和相应的验证平台。F P G A 生成器将会生成设计中所需要的F P G A 模型。在F P G A 平台实现后，可以通过软硬件协同仿真来验证系统性能是否满足设计需求。如果要求不满足，月日么就要返回到体系结构设计阶段，按照F P G A 仿真的性能结果，对处理器、存储和通信体系结构进行修改，进步送代，不断优化，直至F P G A 仿真性能满足设计需求。按照上文所述，就完成了一个系统芯片集成“浙江大学硕士学位论文第4 章实现与结果分析开发的设计流程，生成了目标平台。本文实验采用了视频编解码应用领域的经典标准运动J P E G ( M o t i o nJ o i n tP h o t o g r a p h i cE x p e r t sG r o u p ) 作为特定目标应用。M o t i o n - J P E G 技术是一种把运动的视频序列作为连续的静止图像来处理的压缩技术，可精确到帧编辑和多层图像处理【5 6 】。J P E G 解码器将一个输入的J P E G 比特流文件解压成在屏幕上显示的图像。J P E G 压缩算法的主要思想和流程是，将一帧图像切割成8 x 8 的宏块，然后将各个宏块( m a c r ob l o c k ) 转换到频域上，消除人类视觉不敏感的高频能量数据，再通过H u f f m a n 编码压缩各个宏块的频域数据得到图像的J P E G 比特流文件。对各算法的计算负载进行初步评估，可以发现I Q I D C T 部分算法是M o t i o n J P E G 运算量最大的功能模块，需要着重加以考虑。图4 5 显示了运动J P E G 核心算法的负载情况。图4 5l d o t i o n - J P E G 核心算法的负载信息我们对运动J P E G 解码应用进行任务自动并行化，其性能结果如下所示。图4 6 是在仿真不同硬件体系结构的情况下，采用1 0 帧Q V G AM o t i o n - J P E G 解码测试序列，经过任务并行化后的执行时间，可以看出，3 X T e n s a 处理器架构是所有架构中性能最好的。4 5浙江火学硕士学位论文第4 章实现与结果分析I 塔。，、I 要器。i 会1 5 0。、卜I 瑚1 0 0i 一7 5 5 0一n絮u皿妊1 A R M3 A R M2 X T1 A R M3 X T霜1 A R M2 X T硬件体系结构图4 6 不同体系结构的性能结果为了说明本文方案中提出的任务划分和软硬件任务映射及调度策略的有效性，我们设计- j * N 关实验来显示并行化的性能结果。图4 7 4 1 l 显示了经过本文的任务并行化方案处理后，应用在不同处理器类型和不同通信机制的M P S O C 体系架构中执行性能的分析，其中C o m p 表示计算量，C o m m 表示通信量，I d l e 表示处理器闲置时间。在J P E GG F I F O3 A R M 架构中，每个处理器的计算操作占了三种操作中较大比重，处理器间负载相对较平衡，其中图4 7 ( a ) 所示为手工原始方案的性能结果，图4 7 ( b ) 是本文自动并行化方案的性能结果。图4 7J P E G _ G F I F 0 3 A R M 架构的性能分析( a ) 手工方案，( b ) 自动并行方案在J P E GG F I F O2 X T l A R M 和J P E GG F I F O1 A R M 2 X T 两种架构中，采用手工方案的性能结果如图4 8 ( a ) 和4 9 ( a ) 所示，A R M 处理器计算负载较高，两个浙江大学硕= I ：学位论文第4 章实现与结果分析X T e n s a 处理器则花费大量时间在同步等待上，处理器间负载不均衡；而采用自动并行化方案的性能结果如图4 8 ( b ) 和4 9 ( b ) 所示，两个X T e n s a 处理器资源可以较好被利用，处理器间负载相对均衡。图4 8J P E G _ G F I F O _ 2 X T l A R M 架构的性能分析( a ) 手工方案，( b ) 自动并行方案图4 9J P E G _ G F I F O _ I A R M 2 X T 架构的性能分析( a ) 手工方案，( b ) 自动并行方案图4 1 0 和图4 1 1 分别显示了J P E G G F I F O _ 3 X T 架构和J P E G _ D M S 一3 X T 架构下自动并行化方案的性能结果，可以看出处理器间负载相对平衡。这两种架构的处理器子系统均采用三个X T e n s a 处理器，但分别采用G F I F O 和D M S 两种不同的通信机制。从性能结果分析可看出，D M S 机制的通信负载比G F I F O 机制的通信负载4 7浙江人学硕上学位论文第4 章实现1 j 结果分析降低很多，整体性能有所提高。图4 10J P E G _ G F I F O _ 3 X T 架构的性能分析图4 11J P E G _ D M S 一3 X T 架构的性能分析图4 1 2 显示了在三种不同处理器类型的M P S O C 架构下，本文研究的基于改进的层次任务图进行任务划分、采用两阶段任务映射和兼容条件任务的调度策略进行的任务自动并行化方案，与基于计算负载进行流水划分、映射和调度的手工方案相比，所获得的性能加速。浙江大学硕上学位论文第4 章实现j 结果分析图4 。1 2 任务自动并行化方案与手工方法相比获得的性能提高实验结果表明，本文的研究方案可有效地引导任务的划分、软硬件映射和任务调度，有助于实现体系结构设计空间的自动探索工作，达到M P S O C 体系结构的性能需求。4 3 本章小结本章介绍了多核系统芯片任务自动并行化系统的实现，然后介绍了仿真和实验的体系结构环境，接着针对M o t i o n J P E G 应用，给出了本文任务自动并行化方案的实验结果与性能分析。4 9浙江大学硕十学位论文第5 章总结和展望第5 章总结和展望5 1 本文主要工作概述本文是基于M P S O C 流程设计平台，对S i m u l i n kC A A M 建模的应用进行任务自动并行化的研究，包括对提出一种扩展的任务图模型进行并行化方案的前期建模，研究基于该新图模型的任务划分方法，并针对迭代计算和运行不确定任务提出两阶段任务映射方案，在求得映射初解的基础上，依据开销函数公式，使用智能算法不断对结果进行调整，来求得映射结果近似最优解，最后在映射结果信息的基础上，采用兼容条件任务和通用任务的调度方法，得到了任务节点在时序上的先后执行信息，从而完成整个任务自动并行化过程。本文研究并实现了任务自动并行化系统，并通过仿真环境和实验结果，表明本文的研究方案可有效地引导任务的划分、软硬件映射和任务调度，尽可能地挖掘任务级并行性，满足性能需求，以此对整个M P S O C 软硬件体系架构的实现产生积极，从而提供M P S O C 设计的整体性能。本文第一章介绍了课题的研究背景，及国内外任务并行化的研究。第二章对多核系统芯片软件设计流程进行了简单介绍，并着重对设计流程中用来建模应用的S i m u l i n kC A A M 模型和通用映射调度方法所需使用的中间表达式程序图模型进行了相关介绍和分析。第三章重点阐述本文对多核系统芯片任务级并行化的研究方案，介绍了应用程序模型以及对任务映射调度的建模，然后重点讲述了针对已建模的应用，进行任务自动并行化的方案，包括基于改进的带注释的层次任务图的任务划分，两阶段任务映射方案以及兼容条件任务和普通任务的调度方法。第四章介绍了本文研究方案的系统实现，并介绍了仿真和实验的体系结构环境，针对运动J P E G 应用，给出了本文任务自动并行化方案的实验结果与性能分析。5 0浙江大学硕士学位论文第5 章总结和展望5 2 未来工作展望本文研究的多核系统芯片任务级并行化方案及实现的系统虽然在多媒体编解码应用领域的性能提高方面达到了一定的效果，但仍然存在着一些需要改进的地方，主要有以下几个方面：1 任务并行化中映射问题求解时，本文使用智能算法进行探求近似最优解，未来工作中可将整数线性编程I P 和约束式编程C P 结合进来，可以更有效地对映射调度中的约束条件进行建模和描述，从而找到合适的方法获得性能上更大的提高。2 本文的任务调度方案中，出于实现复杂度的考虑，对于普通任务的调度，采取较为简单的列表启发式调度方法，今后可探索遗传算法、模拟退火等智能算法来进行调度工作。3 对于应用领域，本文的研究方案主要针对多媒体编解码应用，今后需要在更广阔通用的领域进行任务并行化的探索。浙江大学硕士学位论文参考文献参考文献 1 】A A J e r r a y a , e ta 1 S p e c i a lI s s u eo nM P S o C J I E E EC o m p m e r ，2 0 0 5 ，3 8 ( 7 ) ：3 6 4 0 【2 】C a s p iP ，e ta 1 L U S T R E ：ad e c l a r a t i v el a n g u a g ef o rr e a l - t i m ep r o g r a m m i n g C P r o c e e d i n g so ft h e14 t hA C MS I G A C T - S I G P L A NS y m p o s i u mo nP r i n c i p l e so fP r o g r a m m i n gL a n g u a g e s ( P O P L ) ，19 8 7 ：17 8 18 8 3 】G K A H Na n dD M A C Q U E E N C o r o u t i n e sa n dn e t w o r k so f p a r a l l e lp r o c e s s e s C P r o c e e d i n g so ft h eI n f o r m a t i o nP r o c e s s i n g ，19 7 7 ：9 9 3 9 9 8 4 G a r e yMR ，J o h n s o nDS C o m p u t e r sa n dI n t r a c t a b i l i t y ：AG u i d et ot h eT h e o r yo fN P C o m p l e t e n e s s M N e wY o r k - 19 7 9 【5 】王涛实时系统任务调度若干关键技术的研究博士学位论文，哈尔滨工程大学。2 0 0 6 【6 】吴彤，张冬松，金士尧基于简单反馈的混合静态动态节能弱硬实时调度算法计算机学报，2 0 0 9 ，3 2 ( 6 ) ：114 0 11 4 6 7 】陈德来，焦进等基于状态方程组并行任务划分的策略计算机学报，1 9 9 6 ，19 ( 5 ) ：2 8 2 2 8 7 【8 】P u m aK M GD B h a t i a T e m p o r a lp a r t i t i o n i n ga n ds c h e d u l i n gd a t af l o wg r a p h sf o rr e c o n f i g u r a b l ec o m p u t e r s J I E E ET r a n s a c t i o n so nC o m p u t e r s ，19 9 9 ，4 8 ( 6 ) ：5 7 9 5 9 0 【9 】周博，邱卫东，谌勇辉等基于簇的层次敏感的可重构系统任务划分算法计算机辅助设计与图形学学报，2 0 0 6 ，18 ( 5 ) ：6 6 7 6 7 3 1O 】陈伟男，周博，彭澄廉概率构造算法与遗传算法融合的可重构计算系统硬件任务划分计算机辅助设计与图形学学报，2 0 0 7 ，1 9 ( 8 ) ：9 6 0 9 6 5 1 1 】周一萍，郑守淇函数型程序的并行计算模型及任务划分软件学报，1 9 9 8 ，9 ( 1 2 ) ：9 3 2 9 3 6 1 2 】黄凯面向特定应用的M P S o C 设计流程平台研究博士学位论文，浙江大5 2浙江大学硕士学位论文参考文献学2 0 0 8 1 3 】陈晓红关于计算网格调度模型的研究博士学位论文，电子科技大学，2 0 0 4 1 4 】陈锋基于P 2 P 的网格调度算法研究硕士学位论文，浙江大学，2 0 0 4 【1 5 】苏培一种基于分类的网格调度模型G S M C 硕士学位论文，南京航空航天大学，2 0 0 6 【1 6 】雷迎春，张松等W 曲集群服务器的分离式调度策略计算机研究与发展，2 0 0 2 ，3 9 ( 9 ) ：10 9 3 - 10 9 8 【1 7 】赵明宇，张田文一种分布式计算环境下并行应用的调度算法计算机研究与发展，2 0 0 8 ，4 5 ( 4 ) ：6 9 5 - 7 0 5 18 】黄金贵，陈建二，陈松乔网络集群计算系统中的并行任务调度计算机学报，2 0 0 4 ，2 7 ( 6 ) ：7 6 5 7 7 1 1 9 钟一文，杨建刚基于混合遗传算法的并行多处理器系统的任务调度复旦学报：自然科学版，2 0 0 4 ，4 3 ( 5 ) ：9 18 9 2 2 【2 0 】韩建军，甘露等多处理器环境中基于节能及容错的实时动态调度算法计算机研究与发展，2 0 0 8 ，5 ( 4 ) ：7 0 6 7 1 5 2 1 】苗蕾，齐勇等基于多目标粒子群优化的片上多处理器节能调度研究电子学报，2 0 0 7 ，3 5 ( B 1 2 ) ：1 1 3 1 1 7 2 2 】兰舟，孙世新基于动态关键任务的多处理器任务分配算法计算机学报，2 0 0 7 ，3 0 ( 3 ) ：4 5 4 - 4 6 2 【2 3 】宾雪莲，杨玉海，金士尧一种基于分组与适当选取策略的实时多处理器系统的动态调度算法计算机学报，2 0 0 6 ，2 9 ( 1 ) ：8 1 9 1 【2 4 杨根科，吴智铭周期实时任务在多处理器下的可调度条件上海交通大学学报，2 0 0 4 ，3 8 ( 9 ) ：1 5 9 7 1 6 0 0 【2 5 】乔颖，王宏安等实时异构系统的动态调度算法研究计算机研究与发展，2 0 0 2 ，3 9 ( 6 ) ：7 2 5 - 7 3 2 【2 6 刘勇嵌入式可重构计算系统及其任务调度机制的研究博士学位论文，中国科学院研究生院( 上海微系统与信息技术研究所) ，2 0 0 6 浙江人学硕士学位论文参考文献 2 7 】K r z y s z t o fR z a d c a ，F r a n c i s z e kS e r e d y n s k i H e t e r o g e n e o u sm u l t i p r o c e s s o rs c h e d u l i n g 、硝md i f f e r e n t i a le v o l u t i o n C P r o c e e d i n g so ft h eI E E EC o n g r e s so nE v o l u t i o n a r yC o m p u t a t i o n ，2 0 0 5 ：2 8 4 0 2 8 4 7 2 8 】A n n aS w i e c i c k a , F r a n c i s z e kS e r e d y n s k i ，A l b e r tYZ o m a y a M u l t i p r o c e s s o rs c h e d u l i n ga n dr e s c h e d u l i n gw i thu s eo fc e l l u l a ra u t o m a t aa n da r t i f i c i a li n 2 m u n es y s t e ms u p p o r t J I E E ET r a n so nP a r a l l e la n dD i s t r i b u t e dS y s t e m s ，2 0 0 6 ，17 ( 3 ) ：2 5 3 2 6 2 2 9 】M o kAK ，C h e nD Am u l t i f r a m em o d e lf o rr e a l - t i m et a s k s J I E E ET r a n so nS o f t w a r eE n g i n e e r i n g ，19 9 7 ，2 3 ( 1 0 ) ：6 3 5 - 6 4 5 【3 0 B a r u a hS D y n a m i c a n ds t a t i c - p r i o r i t ys c h e d u l i n go fr e c u r r i n gr e a l t i m et a s k s J 】R e a l - T i m eS y s t e m ，2 0 0 3 ，2 4 ( 1 ) ：9 9 12 8 【31 】C h a k r a b o r t yS ，T h i e l eL An e wt a s km o d e lf o rs t r e a m i n ga p p l i c a t i o n sa n di t ss c h e d u l a b i l i t ya n a l y s i s C P r o c e e d i n g so ft h eC o n fo nD e s i g n ，A u t o m a t i o na n dT e s ti nE u r o p e ，2 0 0 5 ：4 8 6 - 4 9 1 【3 2 】E r b a sC ，P i m e n t e lA D M u l t i o b j e c t i v eo p t i m i z a t i o na n de v o l u t i o n a r ya l g o r i t h m sf o rt h ea p p l i c a t i o nm a p p i n gp r o b l e mi nm u l t i p r o c e s s o rs y s t e m - o n c h i pd e s i g n J I E E ET r a n so nE v o l m i o n a r yC o m p u t a t i o n ，2 0 0 6 ，1 0 ( 3 ) ：3 5 8 3 7 4 【33 F a b i oW r o n s k i ，E d u a r d oW e n z e lB r i a o ，F l a v i oR e c hW a g n e r E v a l u a t i n ge n e r g y - a w a r et a s ka l l o c a t i o ns t r a t e g i e sf o rM P S O C s C P r o co fI n tF e d e r a t i o nf o rI n f o r m a t i o nP r o c e s s i n g ，2 0 0 6 ：215 2 2 4 【3 4 】P e n gY a n g ，C h u n gW o n ge ta 1 E n e r g y - a w a r er u n f i m es c h e d u l i n gf o re m b e d d e d m u l t i p r o c e s s o rS O C s J 】I E E ED e s i g n & T e s to fC o m p u t e r s ，2 0 01 ，18 ( 5 ) ：4 6 5 8 【35 】R u g g i e r oM a r t i n oe ta 1 C o m m u n i c a t i o n - a w a r ea l l o c a t i o na n ds c h e d u l i n gf r a m e w o r kf o rs t r e a m o r i e n t e dm u l t i p r o c e s s o rs y s t e m s o n c h i p C P r o c e e d i n g so f t h eC o n f o nD e s i g n ，A u t o m a t i o na n dT e s ti nE u r o p e ，2 0 0 6 ：3 - 8 【36 】C h oYe ta 1 S c h e d u l e ri m p l e m e n t a t i o ni nM P S o Cd e s i g n C P r o co ft h eC o n fo nA s i aS o u t hP a c i f i cD e s i g nA u t o m a t i o n , 2 0 0 5 ：151 15 6 【37 】X u eL i p i n g ，O z t u r kO z c a n ，L iF e i h u ie ta 1 D y n a m i cp a r t i t i o n i n go fp r o c e s s i n ga n dm e m o r yr e s o u r c e si ne m b e d d e dM P S o Ca c h i t e c t u r e C P r o co ft h eC o n fo n浙江大学硕上学位论文参考文献D e s i g n ，A u t o m a t i o na n dT e s ti nE u r o p e ，2 0 0 6 ：6 9 0 6 9 5 【3 8 K H u a n g ，S I H a ne ta 1 S i m u l i n k - b a s e dM P S o Cd e s i g nf l o w ：c a s es t u d yo fM o t i o n - J P E Ga n dH 2 6 4 C P r o c e e d i n g so ft h e4 4 t hD e s i g nA u t o m a t i o nC o n f e r e n c e 2 0 0 7 ：3 9 4 2 【3 9 】W a n d e rO e ta 1 C o l i f ：AD e s i g nR e p r e s e n t a t i o nf o rA p p l i c a t i o n S p e c i f i cM u l t i p r o c e s s o rS O C s J I E E ED e s i g n & T e s t ，2 0 0 1 ，1 8 ( 5 ) ：8 - 2 0 4 0 E l l s b e r g e r , J ，H o g r e f e ，D ，S a r m a , A S D L ，F o r m a lO b j e c t - o r i e n t e dl a n g u a g ef o rc o m m u n i c a t i n gs y s t e m s M P r e n t i c e H a l l ，1 9 9 7 【41 M a t h w o r k s C P O L h t t p ：w w w m a t h w o r k s c o m 【4 2 】O B J E C TMAN A G E M E N TG R O U P ( O M G ) U n i f i e dM o d e l i n gL a n g u a g ev e r s i o n2 O S 】2 0 0 4 4 3 L B B r i s o l a r a , e ta 1 U s i n gU M La saf r o n t - e n df o ra ne f f i c i e n tS i m u l i n k - b a s e dm u l t i t h r e a dc o d eg e n e r a t i o nt a r g e t i n gM P S o C s C D e s i g nA u t o m a t i o na n dT e s ti nE u r o p e ，2 0 0 8 ：5 0 4 5 0 9 【4 4 】GK a r y p i s ，VK u m a r A n a l y s i so fM u l t i l e v e lG r a p hP a r t i t i o n i n g C P r o c e e d i n g so ft h eI E E E A C MC o n f e r e n c eS u p e r c o m p u t i n g ，19 9 5 ：2 9 - 2 9 【4 5 】B r u c eH e n d r i c k s o na n dR o b e r tL e l a n d Am u l t i l e v e la l g o r i t h mf o rp a r t i t i o n i n gg r a p h s R T e c h n i c a lR e p o r tS A N D 9 3 13 0 1 ，S a n d i aN a t i o n a lL a b o r a t o r i e s ，1 9 9 3 【4 6 】GK a r y p i sa n dVK u m a r Af a s ta n dh i g h l yq u a l i t ym u l t i l e v e ls c h e m ef o rp a r t i t i o n i n gi r r e g u l a rg r a p h s J S I A MJ o u r n a lo nS c i e n t i f i cC o m p u t i n g ，19 9 9 ，2 0 ( 1 ) ：3 5 9 3 9 2 4 7 】K w o k ，Ye ta 1 As e m i - s t a t i ca p p r o a c ht om a p p i n gd y n a m i ci t e r m i v et a s k so n t oh e t e r o g e n e o u sc o m p u t i n gs y s t e m s J J o u r n a lo fP a r a l l e la n dD i s t r i b u t e dC o m p u t i n g ，2 0 0 6 ，6 6 ( 1 ) ：7 7 9 8 4 8 】S a r k a r , VP a r t i t i o n i n ga n dS c h e d u l i n gP a r a l l e lP r o g r a m sf o rE x e c u t i o no nM u l t i p r o c e s s o r s D S t a n f o r dU n i v e r s i t y ，G A X 8 7 2 3 0 8 0 ，19 8 7 4 9 】S i n n e n , O a n dS o u s a ，L 2 0 01 E x p l o i t i n gU n u s e dT i m eS l o t si nL i s tS c h e d u l i n gC o n s i d e r i n gC o m m u n i c a t i o nC o n t e n t i o n C P r o c e e d i n g so ft h e7 t hi n t e r n a t i o n a lE u r o P a rC o n f e r e n c eo nP a r a l l e lP r o c e s s i n g 2 0 01 ：16 6 17 0 5 5浙江大学硕1 ：学位论文参考文献 5 0 】Q W a n ga n dK H C h e n g Ah e u r i s t i co fs c h e d u l i n gp a r a l l e lt a s k sa n di t sa n a l y s i s J S I A MJ o u r n a lo nC o m p u t i n g ，19 9 2 ，2 1 ( 2 ) ：2 8 1 - 2 9 4 51 W u , M Ya n dG a j s k i ，D D H y p e r t o o l ：AP r o g r a m m i n gA i df o rM e s s a g e P a s s i n gS y s t e m s J I E E ET r a n s a c t i o n so nP a r a l l e la n dD i s t r i b u t e dS y s t e m s ，19 9 0 ，1 ( 3 ) ：3 3 0 3 4 3 【5 2 R u s s e l lS ，N o r v i gP A r t i f i c i a li n t e l l i g e n c e ，am o d e ma p p r o a c h M P e a r s o nE d u c a t i o n ，2 0 0 3 ：13 9 - 17 2 【5 3 K h a n ，A A ，M c C r e a r y , e ta 1 AN u m e r i c a lC o m p a r a t i v eA n a l y s i so fP a r t i t i o n i n gH e u r i s t i c sf o rS c h e d u l i n gT a s kG r a p h so nM u l t i p r o c e s s o r s R T e c h n i c a lR e p o r tC S E 9 3 12 ，A u b u r nU n i v e r s i t y , 19 9 3 【5 4 】M L o m b a r d i ，M M i l a n o S c h e d u l i n gC o n d i t i o n a lT a s kG r a p h s C I n t e r n a t i o n a lC o n f e r e n c eo nP r i n c i p l e sa n dP r a c t i c eo fC o n s t r a i n tP r o g r a m m i n g ，2 0 0 7 ：4 6 8 4 8 2 【5 5 I n c C S K Y C K C O R E E B O L h t t p ：w w w c s k y c o m 5 6 】G K W a l l a c e T h eJ P E GS t i l lP i c t u r eC o m p r e s s i o nS t a n d a r d J C o m m u n i c a t i o n so f t h eA C M ，19 9 1 ，3 4 ( 4 ) ：3 0 4 4 浙江大学硕j ：学位论文攻读硕士学位期间主要的研究成果攻读硕士学位期间主要的研究成果【1 】李莹，孙煦雪，袁新宇基于交互信息的投机并行化方法计算机应用研究，己录用，待2 0 1 0 年7 期发表 2 孙煦雪，李莹，袁新宇Z I P S 交互式并行化系统计算机工程，已录用，待2 0 1 0年2 0 期发表 3 】孙煦雪，李莹，袁新字一种交互式并行化编译系统及其编译方法，申请专利( 已受理) 浙江人学硕士学位论文致谢致谢时间飞逝，岁月流年，转眼已在浙江大学的校园里度过了三年美好的时光。在这段时间里庆幸能有各位老师的悉心教导以及实验室里各位师兄师姐师弟师妹的热情帮助，让我最后的学业生涯在快乐和感动中度过，仅借此机会向大家一一表示感谢。本论文能够如期顺利完成首先要感谢我的导师李莹副教授。李老师严谨的治学态度，渊博的学识、新颖独到的见解无不让人钦佩。生活上的朴素作风，工作上的勤奋努力以及对学生的关心备至，让他无愧于为人师表这个称谓。由于李老师的言传身教，让我不论在为人处事，生活学习还是科研工作方面都有了长足的提高和进步，在这里深深地向他致敬。衷心感谢吴健老师和尹建伟老师。吴健老师十分平易近人，待人和蔼，在工作上积极的作风给人以深刻的印象。尹建伟老师扎实的理论功底，分析问题的思维方法，总能够使各种难题迎刃而解。感谢我的师兄袁新宇博士，感谢他三年多以来的指导和帮助。他在工程技术和科学研究方面的能力和广博的专业知识让我受益匪浅。感谢我的师弟徐印成硕士和闰卫斌硕士，谢谢他们在各方面的帮助和共同的进步。感谢丁小明硕士、来瑾颖硕士、吕春旭硕士、杨显发硕士、叶斌硕士、赵琳硕士、张凌硕士，很高兴能和他们一起度过这三年的学习生涯。深深感谢我的家人，正是他们无私的爱和默默的奉献以及对我精神上的支持给了我不断前进的动力。再次感谢所有曾经关心和帮助过我的老师、朋友。最后，谨向百忙之中抽出宝贵时间评审本论文的专家、学者致以最诚挚的谢意!孙煦雪2 0 1 0 年1 月2 7 日于求是园5 8面向多媒体编解码应用的多处理器系统芯片任务并行化方法面向多媒体编解码应用的多处理器系统芯片任务并行化方法的研究与实现的研究与实现作者：孙煦雪学位授予单位：浙江大学计算机科学与技术学院 本文读者也读过(2条)本文读者也读过(2条)1. 王志涛 片上多处理器系统的存储子系统设计学位论文20072. 胡威 基于ScratchPad Memory的嵌入式系统优化研究学位论文2008 本文链接：http:/d.g.wanfangdata.com.cn/Thesis_Y1640087.aspx