《面向多媒体编解码应用的多处理器系统芯片任务并行化方.pdf》由会员分享，可在线阅读，更多相关《面向多媒体编解码应用的多处理器系统芯片任务并行化方.pdf（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浙江大学计算机科学与技术学院硕士学位论文面向多媒体编解码应用的多处理器系统芯片任务并行化方法的研究与实现姓名：孙煦雪申请学位级别：硕士专业：计算机科学与技术指导教师：李莹20100101浙江大学硕I：学位论文摘要摘要具有高性能、并行处理和灵活的编程性等优点的多核系统芯片M P S O C 已经成为超大规模集成电路研究领域的全球前沿和热点，它的研究和发展给软硬件设计者和系统开发者带来了巨大的机遇和挑战。任务的划分、映射和调度影响多核系统芯片软硬件体系架构的实现，对整体性能有着巨大影响，是多核系统芯片设计待解决的一个关键问题。本文的研究课题针对目前多核系统芯片流程设计中任务并行化的局限性而提出的，
2、解决如何通过有效的算法引导任务划分、软硬件映射和任务调度，实现体系结构设计空间的自动探索工作这一具有研究价值和意义的问题。本文的主要贡献在于提出了多核系统芯片任务级自动并行化的研究方案和系统实现。本文的研究方案对S i m u l i r t kC A A M 计算模型建模的应用进行任务自动并行化，首先提出了改进的带注释的层次任务图模型对任务并行化进行建模，研究基于该新图模型的任务划分方法，然后针对迭代计算和运行不确定任务提出了两阶段任务映射方案，在求得映射初解的基础上，依据开销函数公式，使用智能算法不断对结果进行调整，来求得映射结果近似最优解，接着在映射结果信息的基础上，采用兼容条件任务和通
3、用任务的调度方法，得到了任务节点在时序上的先后执行信息，最终生成了包含任务并行化信息的多线程代码，从而完成了整个任务自动并行化过程。在阐述研究方案后，本文介绍了任务自动并行化方案的系统实现，并通过仿真环境和实验结果，表明本文的研究方案可有效地引导任务的划分、软硬件映射和任务调度，实现体系结构设计空间的自动探索工作。关键词：任务图模型，任务划分，映射调度，并行化，系统芯片浙江人学硕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
4、 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
5、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
6、 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
7、 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
8、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
9、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
10、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
11、 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
12、 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
13、 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
14、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
15、 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
16、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
17、 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)自动并
18、行方案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
19、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)口
20、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 软硬件体系架构的实现，对整
21、体性能有着巨大影响，是M P S O C 系统设计待解决的一个关键问题。把复杂任务进行分解，将其映射到异构多处理器上，也就是说，将划分后的并行任务合理有效得分配给各个硬件资源以满足实时性、功耗与成本等条件的约束，从而获得最佳软硬件协同效果，有效地挖掘任务级并行性，是值得研究和探索的课题，同时也具有很大挑战性。任务划分和软硬件架构映射是一个相互制约、相辅相成的共同体，最优的软件划分通常是在给定的硬件架构基础上来确定，而最优的软硬件架构映射也是浙江大学硕1：学位论文第1 章绪论基于某种软件任务划分结果来评估。随着体系结构设计空间的扩展，任务划分和软硬件架构映射的难度系数也显著增大。因此，最佳的任务
22、划分和软硬件架构映射事实上是一个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)和
23、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)式并行划分的策略，随着划分步数的增加，各个子系统任务的粒度也越来越细，设计的灵活度和难度也相应增大。任务调度的研究
24、很多都是基于抽象模型给出任务的形式化定义，然后进行调度策略与算法的设计。不同体系结构上的任务调度算法已有不少相关研究。对于网格计算环境，陈晓红【l3】提出了计算网格环境下一种基于代理的面向服务、多级个性化的调度模型；陈锋的论文【1 4】中，结合对等计算的优势，提出了一种基于P 2 P 的网格调度模型，包括作业运行时、资源选择、数据管理、对等点管理、网格信息等模块，并在此基础上探讨了网格资源发现、网格任务分解及调度算法；苏培【15】分析认为影响网格调度系统效率的瓶颈主要集中在对任务需求的理2浙江大学硕士学位论文第l 章绪论解方式和对资源信息的组织方式上，为此提出了一种基于分类的调度模型，通过对用
25、户任务和网格资源进行统一分类，用分类号来表征资源的计算力特征，为调度器提供资源匹配参考，同时采用周期性的动态分类策略，该文用实验证明新模型提高了网络资源信息的可管理性和系统执行效率。对于分布式集群计算环境，雷迎春等人【l6】用排队论方法讨论了W e b 集群整体性能与请求调度策略之间的关系，得出在W e b 集群不过载情况下，分离式调度策略比所有后端服务器既处理静态请求又处理动态请求的混合式调度策略更有性能优势的结论；赵明宇等人【1 7】提出了可防止同步通信引起死锁的调度算法，降低了同步通信的时延影响；黄金贵等人【】嚣】基于多处理机并行任务调度模型，探讨网络集群计算系统中的并行任务调度问题，分
26、析了最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法这三种不同的启发式算法，并用实验对文中提出的启发式算法和文献中的算法进行了性能比较。对于多处理器系统，钟一文等人【l9】针对并行多处理器系统的任务调度问题，提出一个新的混合遗传算法，使用拓扑排序表的交叉来保证下代的合法性和搜索空间的全局性；韩建军等人【2 0】提出了针对实时多处理器计算环境的调度算法，以执行时间最短的任务优先调度为基础，结合共享空闲时间回收技术及检查点技术等，可动态降低整个系统的能量消耗及动态容错，同时满足节能性和容错性；苗蕾的论文【2 1】中，认为片上多核处理器系统的功耗主要受任务的执行时间及系统的能耗这两个
27、因素影响，文中通过对片上多核系统任务调度和能量消耗的分析建立了新颖的编码策略，使用随机权重适应度以及精华解保留策略对粒子群优化算法进行改进，提出了多目标粒子群算法，并通过仿真实验表明新算法可提高系统任务调度的效率，降低任务运行时间和能耗：兰舟的论文1 2 2】分析了几个典型的基于任务复制的调度算法，提出了基于动态关键任务的多处理器任务分配算法，调度过程中动态计算任务时间参数来确定处理器的关键任务，以关键任务为核心优化调度；宾雪莲等人【2 3 1 提出了一种新的实时多处理器系统的动态调度算法分组适度算法，包括分组策略和适当选取策略，以期提高资源利用率和处理器的利用率；杨根科等人【2 4】研究硬实
28、时周期任务在并行等同多处理器下的可调度问题，在浙江大学硕1：学位论文第 章绪论任务处理器静态绑定和周期任务静态优先权配置策略下，依据单处理器情形下的最优配置实时策略，给出了以实时任务集合的任务数、利用率作为可调度依据，并通过实例分析说明其有效性；乔颖等人f 2 5】提出了一种新的实时异构系统的动态调度算法，采用集中式调度方案，并引入一个新的任务分配策略，通过提高任务可行性增大了调度成功率；鉴于任务调度策略是决定可重构计算系统性能的关键，刘勇【2 6】对实时并行系统的多任务调度理论进行了深入的讨论，分析了表调度算法、任务复制调度算法、任务集群调度算法和随机搜索调度算法的优缺点及适用范围，使用评价
29、参数对调度算法进行了性能分析，同时，文中重新定义了任务粒度，分析了任务划分和任务调度间的关系，提出了一种基于相关任务优化的任务调度算法，在调度长度、处理机数目和算法复杂度方面有一定的结果性能优势。近年来，基于不同任务模型的多处理器片上系统调度算法的研究主要分为三类：周期模型类相关算法、D A G 模型类相关算法及其他扩展模型算法。对于周期模型类相关算法，由于嵌入式计算系统始终关注可靠性与功耗，因此，利用任务冗余提高系统的可靠性和调度成功率是近年来多处理器任务调度研究的一个方向。基于D A G 图模型的任务调度问题可以描述为将任务分配到处理器并协调执行，使得在满足实时性约束条件下，任务的整体执行
30、时间、功耗或其他指标最优【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】等等。近年来有不少在任务调度实现框
31、架上的研究进展。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
32、 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 体系结构的任务调度算法的研究仍然停留在调度分析和算法效率改进上，无论是
33、离线调度还是在线实时调度都与实际应用还有不小的距离，还需要结合新的任务模型进一步改进算法效率与实现机制，并在具体的实际应用平台上实现。本文的研究课题就是针对目前M P S O C流程设计中任务调度的局限性而提出的，通过使用合适的任务模型及研究合适的算法，完成了任务调度在实际应用平台上的有效实现。下一节将进一步阐述本文的研究内容和研究目标。l-3 本文研究内容和目标任务划分，软硬件映射及任务调度是M P S O C 流程平台中的关键步骤，是实现体系结构探索的重要部分。本文的研究是基于论文【1 2】中提出的M P S O C 流程平台展开的。该流程平台工具未能实现完全自动化，而是依靠人为经验或简单
34、的基于计算负载划分策略来完成任务划分，导致最后的结果和设计的效率都不令人满意。任务划分，软硬件映射和任务调度是一个与性能评估相结合的反复迭代的优化过程，经过任务划分和软硬件映射后得到的软硬件体系架构需要在随后的各层次软硬件仿真中予以性能评估和验证。如何通过有效的算法引导任务划分，软硬件映射和任务调度，实现体系结构设计空间的自动探索工作，是本文研究课题需要解决的问题。本文主要工作是基于M P S O C 流程设计平台【1 2】，研究对S i m u l i n kC A A M 建模浙江大学硕1：学位论文第1 章绪论的应用进行任务自动并行化，包括对提出一种扩展的任务图模型进行并行化方案的前期建模
35、，研究基于该新图模型的任务划分方法，并针对迭代计算和运行不确定任务提出两阶段任务映射方案，在求得映射初解的基础上，依据开销函数公式，使用智能算法不断对结果进行调整，来求得映射结果近似最优解，最后在映射结果信息的基础上，采用兼容条件任务和通用任务的调度方法，得到了任务节点在时序上的先后执行信息，从而完成整个任务自动并行化过程。本文研究并实现了任务自动并行化系统，并通过仿真环境和实验结果，表明本文的研究方案可有效地引导任务的划分、软硬件映射和任务调度，实现体系结构设计空间的自动探索工作。本课题的主要目的是研究和实现面向多媒体编解码应用的多核系统芯片任务自动并行化方案，有效地实现任务的划分、映射和调
36、度，尽可能挖掘任务级并行性，满足性能需求，以此对整个M P S O C 软硬件体系架构的实现产生积极，从而提高M P S O C 设计的整体性能。1 4 论文结构第一章主要介绍了课题的研究背景，对国内外任务并行化的研究，特别是任务调度的研究及发展进行了简单介绍和分析。最后对本文的主要研究工作和目标作了简单描述。第二章对多核系统芯片软件设计流程进行了简单介绍，并着重对设计流程中用来建模应用的S i m u l i n kC A A M 模型和通用映射调度方法所需使用的中间表达式程序图模型进行了相关介绍和分析。第三章主要阐述本文对多核系统芯片任务级并行化的研究方案。章节开始部分对本文研究的问题进行
37、了建模，介绍了应用程序模型以及对任务映射调度的建模，然后重点讲述了针对已建模的应用，改进的带注释的层次任务图的任务划分，和普通任务的调度方法。进行任务自动并行化的方案，包括基于两阶段任务映射方案以及兼容条件任务第四章介绍了本文研究方案的系统实现，并介绍了仿真和实验的体系结构环6浙江火学硕十学位论文第l 章绪论境，针对运动J P E G 应用，给出了本文任务自动并行化方案的实验结果与性能分析。论文最后对本文的工作进行了总结，并指出了目前存在的不足之处及提出了今后工作的目标。7浙江大学硕+学位论文第2 章多核系统芯片软件设计流程及模型第2 章多核系统芯片软件设计流程及模型2 1 术语与缩写任务(t
38、 a s k)：一个任务可以是一条原子指令或操作，也可以是一个线程或一段组合语句，例如循环块，基本块等等。任务的粒度可以从粗到细，可以有很大变化。并行计算粒度：计算的顺序单元的平均大小，可分为粗粒度，中粒度和细粒度。粗粒度表示计算由相对长的顺序片段或线程，循环块、函数、过程调用等组合语句组成。中粒度表示计算由基本块、循环主体、小的函数或过程组成，最多到上百条指令。细粒度表示计算由一条或几条指令组成。迭代计算：在串行编程语言中，迭代计算指代循环或递归函数。迭代计算的每次迭代由一个或多个任务组成，这些任务在同一个迭代中执行。任务处理器映射(m a p p i n g)：确定一个任务会在哪个处理器上
39、执行，也就是将任务分配到特定对应的处理器上。调度(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 建模
40、，即分析给定的目标应用，提取其算法，然后使用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
41、 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 层四种不同层次的硬件体系结构和多线程代码。这两步同
42、时生成不同层次的软硬件仿真平台，用于软硬件系统架构的性能评估，并反馈给第二步的任务划分和体系优化，在这样的循环迭代中，软硬件系统架构逐步优化，性能逐渐提高。流程的第五步和第六步属于物理实现阶段，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 _
43、一(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
44、姗删佃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)非时
45、序(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
46、 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 模型中，一个计算进程在输入端口上得到足够的数据后开始工作。在进程工作的过程中，它将消耗每个输入端口上固定数量的数据，然后产生固定数量的数据到每个输出端口上。同步数据流模型在每个单位时间内数据接收、处理和生产数目都是
47、固定的。S D F 模型适用于信号处理应用的建模，但是它不能表示含条件选择分支的应用。K a h n 进程网络是一种异步非时序的计算模型，它静态连接各计算进程。各进程间的通信是通过未限制容量的单向通道实现。当通道中有足够的数据时，它的终端进程将接收这些数据，进程的写操作可立即将数据送到通道中。K a h n 进程网络模型的通道可以显性揭示各线程之间的通信及其通信量。当应用粒度变细，线程和通道逐渐变多时，进程阻塞问题将会加剧。如何平衡各进程执行速度，避免通道中数据累积，是K P N 调度的主要问题。K a h n 进程网络模型适用于粗粒度的应用算法建模。系统建模描述语言主要有系统设计语言(S y
48、 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
49、 能够提供方便有效的算法浙江大学硕士学位论文第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 设计工具主要侧重于在给定硬件
50、架构条件下生成多线程软件，或在给定多线程应用下生成硬件架构。与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