（计算机科学与技术专业论文）面向多媒体编解码应用的多处理器系统芯片任务并行化方法的研究与实现.pdf

浙江大学硕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 t a b s t r a c t m 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 n v 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 f h 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 g a n df l e x i b l e p r o g r a m m a b i l i t y t h e d 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 d o 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 n t 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 c h 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 o b 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 m a 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 d s c h e d u l i n g ，a n dt o a 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 n s 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 l p 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 y s i m u l i n kc a a mt o e 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 e 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 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 sa t 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 h t 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 m a 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 n a 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 m c 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 d f 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 d m 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 e p 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 t g 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 n s 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 k p 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 9 l 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 s n 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 e m 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 l f!i!；|i；il!i；iilii；!ii：-一-t a h b 曲s l a 1 c 掣l i o 。n 1 l 丽蒜i - 宴z 9 ：f 一蕊蛐酬c 施锄 m o d e l s y s t e m c v i r t u a la t c h i t e c t u r em o d e l t 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 l p 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 n s 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 d a 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 s c 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 一