（计算机软件与理论专业论文）soc系统级设计中并行划分方法的研究.pdf

j ：海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 摘要 过去的几十年中，摩尔定理一直是计算机和电子工业发展的推动力。 它不断地促进计算机和电子领域的创新变革，使得我们可以将一个大的系 统集成到一个芯片上，即所谓的片上系统s o c ( s y s t e m0 1 1c h i p ) 。现在， s o c 正以高集成、多功能的趋势在发展，系统的复杂度越来越高、设计周 期越来越长，相对应地如何缩短设计周期、降低设计成本的问题也日益受 到关注。 对系统并行划分是在进行大规模系统设计时常采用的手段，它具有将 大系统划分为一系列子系统，然后并行设计的能力。同时，对于一个系统 工程在并行划分前，必须为之构建一个系统模型，这样才有利于将并行划 分技术运用到系统设计中去。 本文根据s o c 发展的趋势，提出了将并行划分技术运用到s o c 设计过 程中的方法。引入带有信号激活率和输入输出延时的过程模型图，并结合 系统级计算方法快速地为模型计算并行参数；设计了一种s o c 系统级的并 行划分算法对s o c 系统模型进行划分，将划分结果分配到并行机系统运行。 该算法建立在贪心算法的基础上，并改进了贪心算法的负载不平衡现象， 另外该算法能对有环图进行划分。实验证明，该并行划分方法可行的，并 对s o c 系统运用并行技术能有效地缩短执行时间。 关键词：片上系统系统级并行划分系统模型负载平衡 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y a b s t i 认c t f o rm o r et h a n3 0y e a r s ，m o o r e sl a wh a sb e e nc o n s t a n t l yf o r c i n gc h a n g e sa n d d r i v i n gi n n o v a t i o ni nt h ec o m p u t i n ga n de l e c t r o n i c si n d u s t r i e s i ti st h ed r i v e rb e h i n d t h es y s t e m o n c h i p ( s o c ) p a r a d i g mt h a tu s e st h ev a s t l yi n c r e a s e dt r a n s i s t o rd e n s i t y t oi n t e g r a t ee v e r - l a r g e rs y s t e mc o m p o n e n t so n t oas i n g l ec h i p n o w , t h ed e v e l o p m e n t c u r r e n to fs o ci sh i g h - i n t e g r a t i o na n dm u l t i f u n c t i o n s ot h ed e s i g no fs o cw i l lb e m o r ec o m p l e xa n dd e s i g nc y c l ew i l lb el o n g e r a c c o r d i n g l yi ti st h ep r o g r a m st h a t a t t r a c to u ra t t e n t i o nt or e d u c et h ed e s i g nc y c l ea n dt i m e p a r a l l e lp a r t i t i o n i n gi st h em e t h o dw h i c hi su s e di nt h el a r g e - s c a l es y s t e m d e s i g nf r e q u e n t l y i th a st h ea b i l i t yt op a r t i t i o nt h es y s t e mf r o mt h es i n g l es y s t e mt o m a n ys u b s y s t e m s m e a n w h i l eap a r a l l e lm o d e li s e s s e n t i a lf o ra n ye n g i n e e r i n g s y s t e mb e f o r et h ed i v i s i o n ，w h i c hc a nt r a n s f o r mt h ee n g i n e e r i n gp r o b l e m st ot h e p a r a l l e lc o m p u t i n gp r o b l e m ss ot h a tt h ec o m p l e x i t ya b o u tt h ew h o l ep r o b l e m sc a l l d e c l i n et ot h er e a s o n a b l ed e g r e ea n dt h eb a s i so ft h es t u d ya b o u tp a r t i t i o n i n gw i l lb e e s t a b l i s h e d a c c o r d i n gt h ed e v e l o p m e n t t r e n do fs o ca n dt h ee f f e c to fp a r a l l e lp a r t i t i o n i n g ， am e t h o do fs o cp a r a l l e ld e s i g na tt h es y s t e m l e v e li sp r e s e n t e di n t h i sp a p e r a p r o c e s sm o d e lg r a p ha p p e n d e dr a t ee s t i m a t i o na n di 0d e l a yi si n t r o d u c e dt om o d e l o fs o cs y s t e m ，a n dt h ec o m p u t i n gs p e e do fp a r a l l e lp a r a m e t e r sb e c o m e sf a s t e r a t t h es a m et i m e ，an e wa l g o r i t h mi s p r o p o s e dt op a r t i t i o nt h es o cm o d e l t h e a l g o r i t h mb a s e do ng r e e d yr u l ec a na l s op a r t i t i o nt h ec y c l i cg r a p h s ，w h i c hd e a l sw i t h t h ep r o b l e mo fl o a db a l a n c i n g t h ee x p e r i m e n tr e s u l t ss h o w st h a tt h ep a r t i t i o n i n ga t s y s t e m l e v e lo fs o ci sg o o da ti m p r o v i n gt h et i m e c o n s u m i n ga n dl o w e f f i c i e n c y q u e s t i o n si ns o cs y s t e m k e y w o r d s ：s o c ，s y s t e m l e v e l ，p a r a l l e lp a r t i t i o n i n g ，s y s t e mm o d e l ，l o a db a l a n c i n g i i 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：主全窒：主日期：至! ! 墨! 至占 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：蛆导师签名：妲吼出h 址箩 e 海大学硕七学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 1 1s o c 发展的趋势 第一章前言 s o c 设计技术始于2 0 世纪9 0 年代中期，当时集成电路i c ( i n t e g r a t e dc i r c u i t ) 设计者已经将愈来愈复杂的功能集成到单硅片上，s o c 正是在i c 向集成系统转 变的大方向下产生的1 1 。目前，s o c 正朝着高度集成的方向发展【2 1 。在众多的 s o c 产品中，设计者努力将系统所有的重要数字功能网络开关、打印机、 蜂窝式电话或者数字电视做在一个芯片上，这造成了s o c 的设计过程越发的复 杂。 从简单i c 到复杂s o c 这一发展历程充分验证了由i n t e l 联合创办人g o r d o n m o o r e 在1 9 6 5 年总结存储器芯片增长规律时，提出的“微芯片上集成的晶体管 数目将以每1 8 个月翻一番的速度增长”的科学论断 3 1 ，后人们把此发现称之为 摩尔定律。从i c 工业半个多世纪以来的发展历史不难看出，摩尔定律一直较为 准确地描述着i c 技术的发展方向。根据美国、欧洲、韩国以及中国台湾等地区 的半导体协会于2 0 0 5 年共同撰写的国际半导体技术蓝图报告中的预测，在未来 1 0 年左右，虽然面临着接近物理极限的网难与挑战，i c 及s o c 制造技术仍将 沿着摩尔定律的方向继续前进。 现在，如何完美地、快速地设计一个新的s o c 产品使它迅速地走上市场， 是许多设计厂商急需解决地问题。针对系统复杂性问题，s o c 设计迫切需要提 高设计抽象层次，加快设计进程，缩短研发周期，改进设计效率，以弥补设计 能力与制造能力之间的鸿沟【4 1 。 1 2s o c 设计中并行划分的意义 目前，在交通、材料、航空航天、电路模拟等大量的科学领域，常将大规 模、高复杂度的问题与并行计算结合起来，解决它们的设计中高开销、低效率 的现象。并行划分，简单的讲就是通过设计一个并行划分算法对问题进行划分， 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 达到一种分而治之的效果，从而缩短设计时间，改进设计的效率。传统的s o c 设计中常采用的方法是在早期设计过程中将系统划分为硬件和软件两部分，然 后反复精练，直到一个好的体系的产生，如遗传算法【5 】。但随着s o c 相关技术 的不断发展，s o c 复杂度日趋增大，它的问题规模亦不断扩大，这种方法在优 化效率和求解质量上都显得有些力不从心。 为了解决这个难题，提高设计速度，在s o c 设计中运用并行技术已经作 为一个新的研究领域开始受到重视，通过将复杂系统划分为简单子系统同时进 行来减少整体设计时间，被看作是解决s o c 复杂性，提高其设计速度的一种有 效途径。 1 3 国内外研究的现状 国内外提出了很多s o c 系统级的设计方法，大多数体现在软硬件的协同设 计上。它的目标是搜索任务分配到硬件模块，使设计不仅能满足系统时间限制， 而且使成本、功耗等最优。传统的设计方法有：模拟退火、禁忌搜索算法、演 化算法、迭代移动、迭代改进、动态粒度模拟退火、动态规划、构建性算法、 遗传算法、混合性规划、贪婪迭代改进算法等等。下面作一个简单的介绍。 n i e m a n n 和m a r w e d e l 针对广泛的目标体现结构中联合划分提出了整形线性 规划模型【6 】。整形线性规划是两阶段启发式最优化方案中的一部分，通过重复 调度阶段获得越来越好的时间估计，然后在划分阶段适用这些估计。jg r o d e 提 供了分配硬件资源的最优划分方法【7 1 。该算法本质上是一个贪心算法，通过对 每个元件的主意尝试，把当前元件的最关键的构成模块分配给硬件。pe l e s 和z p e n g 提供了启发式方法【8 】。成本函数的优化是一个复杂的、启发式的权和，要 考虑多个启发式算法。p e t e ra r a t o 给出了基于整形线性规划算法和遗传算法 g a 9 1 ，指出基于线性规划算法可以得到最优解，遗传算法只能找到近似最优解。 注意到线性规划仪适用于小规模的系统，对于大规模的系统，计算时间将 呈指数上升，而遗传算法适用于规模比较大的系统f l o 。1 3 】。但随着s o c 技术的不 断发展，遗传算法也存在一定缺陷，主要是因为问题规模的不断扩大，面对计 2 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 算复杂程度越来越高的搜索空间，遗传算法在优化效率和求解质量上都显得有 些力不从心，为了解决这个问题，有人提出了并行遗传算法”18 1 。它就是将遗 传算法与并行计算结合起来，解决大规模的优化问题。随之在s o c 中也设计了 一种s o c 协同设计的并行遗传算法【5 】，但是并行遗传算法同样也有其本身就无 法克服的缺陷。因为，虽然遗传算法无论是从直观上还是理论上都具备并行性， 遗传算法的并行化也是势在必行，但标准遗传算法在并行化过程中会遇到通信 量过大的网难【l5 1 。通信量越大大，彼此交互的时间也就越长，必然导致整个算 法的执行时间也相应增大。 从目前s o c 设计的现状不难看出，无论是遗传算法还是线性规划在处理大 规模的系统时都存在很多的问题。主要体现在它们都不能降低s o c 的系统规模， 而且随着系统规模的增大，这些算法的执行效果越差。因此，本文采用并行划 分的方法将s o c 系统划分为一系列的子系统，利用分治策略来设计s o c 。这在 其他领域都有类似的研究。例如，k l k a p p 1 9 提出了深度优先遍历划分算法， 是对图形进行深度优先遍历的顺序进行划分。s p o r r e r f 2 0 1 提出了一种启发式划分 方法，用来对大规模集成电路进行划分。在电路模拟中s m i t h 【2 i 】研发了一种由 初始输入结点出发进行划分的算法，该算法是基于结点的扇入扇出锥形的划分 方案，总的来说，目前国内外对s o c 系统的并行性仍然具有较大的研究空间。 通过研究一种新的高效的系统划分算法是缩小问题规模，降低复杂度，节省开 发时间的一个重要途径。 1 4 论文的主要研究内容 本文研究的课题来源于上海一应用材料研究与发展基金项目( 美国a m 基 金) 资助的( ( s o c 并行软硬件划分与协同模拟验证技术研究中的子课题 s o c 系统级设计中并行划分方法的研究。该基金项目的研究重点是研究与实现 一个在并行环境下运行的高性能软硬件划分与协同模拟系统及验证平台，能将 输入的系统说明，经过一种良好的软硬件划分算法与自动划分方法，划分为比 较合理且符合需求的软件与硬件部分，并根据划分结果建立软硬件各部分的多 层次模拟模型，然后，对所建模型在事务级验证平台上进行快速验证与测试。 3 一 ：海大学硕：十：学位论文 t h e p o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 本文主要研究内容是如何利用并行划分来减少s o c 设计的时间，提高设计 效率。研究对s o c 系统进行并行划分的有效方法，找到系统中各个功能模块的 并行性，使整个系统能够进行并行设计，从而达到预期目标。还研究s o c 系统 的并行建模技术，为并行参数设计系统级的计算方法，并使之能够应用于并行 计算中，这为s o c 系统并行问题的解决建立很好的理论基础。 本文将按如下章节进行探讨： 第一章介绍课题的研究背景及国内外研究现状，并对本文的主要工作进行 概括。 第二章介绍s o c 系统并行划分的基本概念和构架，分析其影响因素，对已 有的s o c 系统模型进行分析和研究。 第三章介绍s o c 系统模型的整体结构，分析模型中并行性。研究系统模型 的并行参数，设计参数的计算方式。 第四章设计s o c 系统的并行划分算法，并且验证算法的有效性，同时也对 并行算法的负载平衡做出改进。 第五章通过实验验证划分算法的有效性。 第六章对本文工作做总结，并对下一步工作做介绍。 4 上海大学硕- l 二学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 第二章相关知识的介绍 2 1s o c 系统级设计理论 一般而言，s o c 系统都具备强大的数据处理和存储能力，能适应于一类典 型的应用功能和性能要求。在s o c 设计中，整个过程是一个软、硬件协同设计 的过程，它从整个系统的角度出发，把处理机制、模拟算法、芯片结构、各层 次电路直至器件的设计紧密的结合起来，在单个芯片上完成整个系统的功能。 系统级设计一般在产品开发的初期进行，其目标是寻找适合s o c 的算法和结构， 从而满足所需功能下实现最小的成本。整个s o c 系统的开发流程可见图2 1 。 图2 1s o ( 3 系统开发流程图 l 海大学硕士学位论文 t h e p o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y s o c 系统级设计的相关技术主要包括了软硬件协同设计技术、设计重用技 术、超深亚微米集成电路设计技术【2 2 1 。软硬件协同设计理论起源于2 0 世纪9 0 年代初，最初丰要面向嵌入式系统设计领域。在经历了l o 多年的发展之后，现 己逐渐形成其理论体系框架。一般来说，面向s o c 的软硬件协同设计理论是从 一个给定的系统描述着手，通过有效地分析系统任务和所需的资源，采用一系 列变换方法并遵循特定的准则自动生成符合系统功能要求、符合系统约束的硬 件和软件架构。在经历长期的理论探索后，s o c 的软硬件协同设计将迎来高速 发展的时期。目前，在软硬件设计中最为活跃的研究工作包括系统描述、模型 形式化规范、细化与变换技术，软硬件划分、软硬件协同综合以及软硬件协同 模拟与验证【2 3 1 。 ( 1 ) 系统描述 系统描述的目的是在最高抽象层次上利用某种高级语言，如c c + + 、s y s t e m c 或统一建模语言等。描述整个系统行为，获取用户功能需求和约束要求，以 便在详细设计开始之前，验证需求分析的正确性；同时进行必要的性能分析， 作为后续设计的基础。系统描述独立于后续的实现过程，可以仿真运行。系统 描述的研究内容主要包括描述模型与描述方法。描述模型主要研究适合描述系 统行为与功能的抽象模型。常用的系统描述模型有离散事件模型、有限状态机 模型、通信进程网络模型、p e t r i 网模型、任务流图模型、控制数据流图模型等 几大类，每一大类中还包括若干针对需求的变种。描述方法是指在描述模型基 础上具体的描述手段，通常使用系统级描述语言并辅以一定的图形输入支持。 系统级描述语言的选择需要考虑语言的描述能力、配套的验证手段( 编译和仿 真运行环境) 以及与后续设计阶段的衔接等问题。 ( 2 ) 模型形式化规范、细化与变换技术 一般而言，一个复杂系统具备三个特性：a 并发性。系统功能可以很容易 地被描述为并发行为的集合；b 层次性。层次化的模型适用于描述较大系统， 便于模块功能的管理与设计，大大地简化系统的开发；c 时序与通信。时序信 息能有效地说明系统功能之间的偏序关系，而通信则描述了系统间的相互协作 6 一卜海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 与行为功能。 为了能更好地反映系统特性，系统模型通常需要采用形式化规范，应用逐 步细化求精的思想，实现可变粒度的层次化任务描述能力，并通过控制机指导 控制相关性，捕获其并发性、时序与通信关系；同时将系统模型与底层实现相 关联，通过一系列的细化与变换规则，完成功能任务到实现的映射，支持快速 生成系统原型，有利于在系统级进行功能验证与性能评价。 ( 3 ) 软硬件划分 软硬件划分是在系统描述与建模层次的分析结果上，将系统功能合理地划 分为软件和硬件实现部分，使系统性能与成本最优，它是软硬件协同设计中的 一个重要课题。划分结果力求提高速度、缩小面积、降低成本、减少功耗。但 软硬件划分是一个传统难题，由于划分问题本身是具有n p 难度的问题，加上 s o c 带来的巨大搜索空间，使情况更为严峻。 ( 4 ) 软硬件协同综合 软硬件协同综合的任务是把高层次的描述自动转化为低层次的实现。软件 综合又称为代码生成，硬件综合通常分为高层次综合和逻辑综合两种层次。目 前，硬件的逻辑综合已经发展的比较成熟，但是软件综合以及硬件的高层次综 合都还没有进入使用阶段。因此，现在还难以从软硬件划分所得的高层描述自 动综合出在功能和性能上满足要求的软硬件。 ( 5 ) 协同模拟与验证 软硬件协同模拟的目的是在硬件生产出来之前，通过模拟的手段验证软硬 件集成方面的问题。软件模拟和硬件模拟都存在着不同的抽象层次：抽象层次 越高，模拟速度越快，但是，反映的细节也越少。 协同验证的目的和协同模拟的一样，都是希望在设计的早期验证系统软硬 件的正确性，特别是功能的正确性和性能的满足性。然而，验证基本是通过形 式化的方法，如数学方法、布尔逻辑理论来推理其系统的正确性。目前，对软 硬件协同验证的研究还处在一个初级阶段，还有很多问题等待研究人员去探索。 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 在s o c 设计越来越复杂的驱动下，人们对s o c 系统级的研究需要重新审视已 经熟知的设计方法，必须提出一套符合新的设计思路、新的工艺环境、严格的时 序要求以及高的性能标准的设计方法。探索s o c 设计方法进程中首当其冲的是系 统级设计方法学的研究，其中包括对复杂系统并行性和相关划分方法的研究，它 直接影响到了后续开发工作的展开。因此它获得了来自学术界、工业界以及不同 行业的重视，是未来芯片设计中的重要砝码。当s o c 系统越发的复杂时，它也是 极具挑战性的内容。 2 2 系统并行划分的概念 2 2 1 系统并行划分的定义 所谓的划分就是将一原始问题分成若干个部分，然后各部分由相应的处理 器同时执行，它是并行算法中最基本的部分。用划分法求解问题可分为两步： 将给定的问题劈成p 个独立的几乎等尺寸的子问题；用p 台处理器并行求解诸 子问题。划分的关键在于如何将问题进行分组，使得子问题较容易并行求解， 或者子问题的解较容易被组合成原问题的解【2 5 1 。 s o c 系统并行划分指的是遵循子系统间相关性最小和子系统内并行性最小 的原则对s o c 系统进行划分。系统划分大都采用基于图论的方法，所以本文将 采用模块化技术，为s o c 系统构建模型图。 2 2 2 系统并行划分的分类 系统并行划分方案通常分为两类，一种是静态划分，一种是动态划分【2 6 】。 区别某种划分方案是静态划分还是动态划分的主要依据是该划分算法在什么时 候被执行调用。 静态划分是在对s o c 系统实现之前被执行调用的，并且静态划分产生的结 果在整个模拟过程中间是固定不变的。不过有的时候，静态划分也利用过去模 拟过程中积累的一些历史信息来帮助对s o c 模型进行划分，但是其在模拟过程 之前调用的特性不会改变。 ：海大学硕f ：学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 与静态划分截然相反，动态划分算法首先进行一个初始化划分，然后在实 现的过程中根据实际的情况对s o c 系统进行再划分。 本论文主要是从系统级的层次去划分s o c 系统模型，以便找到各功能模块 之间的并行性，所以主要对静态划分算法进行相关的研究和实现。 2 3 影响系统并行划分的关键因素 s o c 的系统并行划分中有很多因素会对划分的结果产生影响。由于静态划 分是先于模拟验证过程之前进行的，确定和预测这些相关的因素对划分结果的 并行验证十分重要。 2 3 1 模块间并行性 并行性由s o c 系统中每个功能模块对象的活动决定。假如在划分后，对系 统中验证的任何时刻，每个划分块中间有相同数量的模块在活动，那就到达了 验证性能的最大化并行性。 2 3 2 模块间通信量 并行划分后在不同的划分块中有各种消息进行传递，包括数据信号，驱动 信号等，这些信号存在增加了处理器之间的通信开销，使得并行模拟的性能降 低。一个好的并行划分算法应该是能够尽量的将通信量降到一个较低的值。 2 3 3 其他相关因素 除了上面一些因素还有别的因素对划分的性能产生影响，如处理器的负载、 处理器的数量、划分块的数量、划分所花费的时间等。 9 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 2 4s o c 系统模型 并行划分需要一个系统模型，也称计算模型。对于一个特殊领域的并行划 分更是如此。要对s o c 进行并行划分，必须首先为s o c 系统构建一个系统模型。 在s o c 设计中常用到带有同步数据流图有限状态机h f s m s d f 、有向无环图 d g a ( d i r e c t e d a c y c l i cg r a p h ) 、数据流副2 7 1 ，控制数据网络副2 8 1 等系统模型， 它们适用于不同的研究领域。下面对部分系统模型作个简单介绍。 h f s m s d f ( h i e r a r c h i a lf i n i t es t a t em o t i t i o n s y n c h r o n o u sd a t af l o w ) l 拘模型【2 9 】 由圆圈、方框和弧来表示，见图2 2 。圆圈和方框分别代表状态和s d f 的行为。 状态之间的弧代表一个状态的转移。状态转移弧用保护动作标记。s d f 行为之 间的弧输入用消费的令牌数标记，输出用生产的令牌数标记。缺省的弧表示没 有一个牛产消费令牌。这样，为了平衡生产令牌数和消费令牌数，s d f 图有一 个行为激发调度。h f s m s d f 模型对控制复杂和数据流计算复杂的设计都适用。 它们在形式化分析如：状态可达性测试和死锁分析等中也有用。因此可以把 h f s m s d f 模型用于可重配置s o c 设计中。 图2 2h f s m s d f 的模型 有向无环图d a g 也称任务流图( t a s kg r a p h ) ，它在并行计算中常作为系统 1 0 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 模型来使用，时常用于研究任务调度、系统并行性分析等问题。d a g 有一个起 始结点和一个终止结点，两个结点之间最多只有一条边。图中每个结点表示系 统一个任务( 或功能模块) ，边表示任务之间的控制关系或数据流向，每条边的 终点必须在此边的始点任务完成之后才可以开始进行，图2 3 给出一个简单的 d a g 图，其中子任务2 、3 、4 、5 、6 的持续时间和资源消耗量用二维数组( 2 ， 3 ) 、( 4 ，2 ) 、( 2 ，4 ) 、( 3 ，2 ) 、( 4 ，3 ) 来表示。在s o c 软硬件划分中，每个 结点包含其软件、硬件成本信息，边的权重代表两个结点之间的通信开销。任 务流图是系统的行为级描述，主要描述系统中任务间的控制、数据关系及每个 任务的成本信息，而与系统实现采用什么样的体系结构无关。本文是对系统进 行并行划分，而不是进行软硬件的设计。所以尽管所需构建的模型与d a g 基 本相似，但是结点和边所代表的信息有所不同，所以需要重新定义d a g 的结 点和边的信息，以便使其能够完整的描述一个系统，符合系统划分的要求。 图2 3 一个简单的d a g 图 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 2 5 小结 并行划分存在于很多领域，比如电路模拟、大规模机群系统、网格计算、 材料设计等。本文主要针对大规模s o c 系统进行并行划分，其划分的对象、影 响划分的因素、划分的结果、相关的系统模型都与其他领域有所不同。本章首 先介绍了s o c 系统级设计理论，讨论了目前系统级设计中的主要研究内容。随 后介绍系统并行划分的定义及影响并行划分的一些因素，指出了本文并行划分 属于静态划分。最后探讨了s o c 的系统模型，主要介绍了其中的h f s m s d f 模型和d a g 模型，指出了它们在系统并行性研究中存在的缺陷。这为接下来 s o c 的系统模型中并行性的研究和并行划分算法的设计奠定了很好的理论基 础。 1 2 卜海大学硕十学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a i u n i v e r s i t y 第三章s o c 系统模型一过程模型图中的并行性研究 s o c 系统模型中的并行性是系统并行划分前必须考虑的重要内容。本文采 用了过程模型图p m g ( p r o c e s sm o d e lg r a p h ) 3 0 】，其特点是易于表示s o c 各个 层次，易于表示大规模系统，另外该模型图是粗粒度的模型图，容易从系统的 高层描述中抽象获得。本章重点分析了p m g 中并行性及与其相关的并行参数， 并为参数设计了系统级的计算方法。首先介绍过程模型图。 3 1 过程模型图的定义 过程是任何工程学理论体系的基础都是过程( p r o c e s s ) 3 1 】。i e e e 将过程定 义为：为实现给定目标所执行的一系列操作步骤。一个过程里的活动是顺序执 行的，但不同的过程操作是同时进行的。可以利用硬件描述语言如v h d l 中的 p r o c e s s e s 3 2 1 ，s y s t e mc 中的线程t h r e a d s 和方法m e t h o d s 来描述过程。一个完整 的系统可以认为是由一个或多个由信号和线连接的过程。 过程模型图是一个有向图g ( v e ) 。由结点v 和弧e 构成。其中结点表示过 程，弧表示信号。结点有端口，弧通过端口把结点连接起来，端口可以是输出， 输入或双向，图3 1 给出了一个简单的过程模型图。利用这个过程模型图，该图 可以为系统的并行性进行建模。同样，也很容易利用s y s t e mc 对图进行描述。 下面给出过程模型图的定义 过程模型图是一个图d = n ，s ) ，其中： ( 1 ) n 是图的结点( 过程) 集，s 是弧( 信号) 集。 ( 2 ) n = p u i u o p 是n 个过程结点集，i 是源结点集，0 是漏结点集合。这样每个过程 鼻( f = 1 , 2 ，3 ，刀) 是一个定点，代表一个过程；每个，( = 1 , 2 ，) 代表一个源结点， 其入度为0 ；每个q ( 七= 1 , 2 ，) 代表一个漏结点，其出度为o 。s ，s ( i = 1 , 2 ，g ) 是 上海大学硕七学位论文 t h e p o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 一个弧，表示一个信号。 图3 1 一个简单的过程模型图 过程模型图通过上面的描述抽象出来，但仅此还不能用于划分。过程和信号 的特性是划分中重要的数据。一个带有特征数据的过程模型图，我们称之为一个 带参数过程模型图。下面给出一些主要的参数。 ( 1 ) 激活率：它是一个信号触发一个过程的比率，是信号的属性。 ( 2 ) 输入输出延迟：延迟是过程的属性，被标注到过程模型图的结点中。他 描述输入信号和输出信号之间的延迟时间。因此，如果一个结点有刀个输入，研 个输出，这个结点有，z 聊的延迟时间。 ( 3 ) 缓冲区大小：缓冲区的尺寸是一个过程的输入输出缓冲需要的存储器的 数值。这个值属于结点的特性。 ( 4 ) 线宽：这里指输入输出信号的宽度，属于弧的特性。 ( 5 ) 功耗需求：每个过程的功耗被标注到结点上。这个信息对涉及低功耗设 计的划分算法有用。 本文在对模型进行并行划分时，主要考虑的特性是激活率和延迟。 1 4 一卜海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 3 2 过程模型图的特点 3 2 1 易于表示各个层次的s o c 根据粒度的不同，p m g 可以表示不同层次的s o c 系统。例如，较高层的 系统模型可以表示多路复用器部件，较低层的可以表示复用器中触发器的结构。 这个层次问题也常称为粒度。粒度越低，结点数越多，p m g 越发的复杂，也意 味着在设计中付出的努力越多：但是从另一个方面，越详尽的p m g 图在处理 过程中能得到更优的解。所以要综合考虑这两个方面，结合设计需求采用一个 适合的粒度。 3 2 2 易于表示大规模系统 大的系统常由几个子系统构成，而子系统由多个过程构成。过程模型图可将 子系统先用一个结点表示，在这个结点内部又可以形成一个过程模型图。一个过 程模型图由项层结点构成，这些结点又可以表示低一层的子图，称该过程模型图 为分层次的过程模型图。注意到这里的“分层”与上面提到的“不同层次”是不 同，“分层”是为了简化某个层次上的大规模系统，也可以称“分等级”。为了 说明的方便，后面均称“分等级 。图3 2 给出了一个分等级的图，它是一个顶 层的p m g 图，其中c 是分等级的结点，图3 3 是结点c 的下一级子图，图3 4 是再 下一级的子图，这样就可以将一个复杂系统简化。 图3 2 带有分级结点c 的项层p m g j ：海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 图3 3 表示结点c 的子p m g 图 图3 4 表示结点c ：d 的子p m g 图 一般来说，一个s o c 的设计的是巨大而且复杂的工程，相应地，划分它的 p m g 图有时因过于复杂也很难完成。因此，我们可以考虑将系统分解为一个分 等级的结构。一种划分方法可以首先应用在项层( 如系统层) ，接下来在低等级 的结点中接着使用。为了方便做到这一点，这些带有子结点的结点和信号值是 从它的低一级的图中计算而来。 3 3 过程模型图与并行划分相关的参数 从过程模型图的定义和特点可以看出，过程模型图是非常适合表示复杂 s o c 系统的，但是在对s o c 系统进行并行划分前，必须首先知道模型图中的 并行性因素。因此在本节重点分析过程模型图中与并行相关的参数，找到各个 参数在并行划分中所起到的作用。 3 3 1 激活率 激活率不同于其他参数，它是s o c 设计中独特的参数。在计算激活率时可以 根据软硬件描述语言中事件与信号之间的关系来考虑信号激活率的值。 在软硬件描述语言中事件的发生当且仅当信号的值发生了变化，所以有： 乞r e ，其中：信号的激活率，乞：事件的发生率。 1 6 上海大学硕十学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 其中事件发生率是信号激活率最坏值，即为它的上界。 在系统级设计时，我们采用的是静态的分析方法，结合上面的激活率的计 算方法，可以作一个推断：若激活率越大，信号值变化的频率越高，需要通信 传输量也越大。所以以激活率为弧的权值的p m g 适合系统的并行性分析。 3 3 2 输入输出延时 在划分系统时，不得不考虑划分后对系统的影响。有时候系统被划分会导 致在后面的设计中出现差错，所以本文希望通过一种方法来保证系统在划分前后 的稳定性，这里涉及到了输入和输出延时及与其相关的复杂度。 一般s o c 系统的设计中，常需考虑系统各个部分实现的工艺，即硬件或者软 件实现，这部分工作称为软硬件划分。所以在设计初期就存在模块的软硬件实现 问题，对应的延时也有软件延时和硬件延时。 延迟值是与每个输入输出端口联系在一起的，端口用数值来表示。如果两 个端口之间的延迟没有指定，假设延迟为0 。但是如果给一个不知的端口指定延 迟值，则会出错。延迟的单位可以是m s 、n s 币i p s 。延迟无论对与软件或者硬件 都是可以获得的，也即可以确定的。图3 5 给出了一个具有两个输入和两个输出 端口的结点上的延迟表示。 在实时系统中，信号路径有严格的限制。在p m g 中的一些路径的延迟可能 被限定到一定的值。比如在控制系统中，从温度传感器的输出到温度控制器的输 入的延时对一个部件的操作是关键的，因此被限定为很小的值。所以在设计一个 结点时，要考虑关键路径必须符合时间要求。 如果两个彼此通信的过程被实现为不同的实体( 软件或硬件) ，那么在它们 之间的信号必须通过一个接口交互机制。最通常的接口机制是总线接口，例如 p c i 。 同时，在s o c 设计中存在信号并发可用数目的限制，即所谓的带宽。如果 带宽不够，亦会影响到结点间路径的延迟。 1 7 ：海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 图3 v 具有两个输入和两个输出端口的结点上的延迟 本章第4 节将介绍如何利用已有的工具在系统级下计算延迟值。 3 3 3 时间复杂度劢、过程复杂度印和过程平均复杂度印 一个p m g 的结点可能被一个或多个信号激活。结点的活动始于一个信号激 活它并延迟到这个结点执行时间的完成。如果一个信号的激活率很高且激活后结 点的执行时间较长，则认为在该信号激活下结点代表的过程的时间复杂度较高。 根据上面的描述，用，表示信号的激活率，d 表示过程某个输入信号到 输出信号的延迟。 时间复杂度：印= ，d 。在嵌入式处理器中，执行时间往往只能被分配到 几个过程中，所以只有将那些时间复杂度高的过程映射到处理器，才能符合整个 系统的要求。因此可以将尽可能多的结点用软件来实现，而对一个较高时间复杂 卜海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 度结点可考虑用硬件来实现。 过程复杂度：c p = xd “，栉是结点激活信号的个数且认为某个结点 i = lj = l 所有的输入信号都是激活信号，l 是结点输出信号的个数，：过程第f 个信号的 激活率，d u ：表示第f 个激活信号和第个输出信号之间的延迟。 过程平均复杂度：历：垒，g 表示结点的度数，其值为结点的入度( i n j e g r e e ) g 和出度( o u t _ d e g r e e ) 之和。 在s o c 设计过程中，软件实现相对于硬件实现更加有效，这是因为在设计 到综合过程中，软件需要的工作少于硬件。一般的体系结构( 例如d s p 或者 r i s c 处理器) 可用便宜的价格作为一个i p 核来实现，但有些部分则必须用软 件来实现。找到那些既能用软件实现又不违反设计限制的节点，是s o c 设计中 一个重要的工作。本文将过程平均复杂度作为一个软硬件衡量的简单标准，使 那些具有较高复杂度的结点作为硬件来实现。目的是为了在对系统划分前，保 留它们初始特征，防止因划分影响系统的后期设计，当然它们也是后期软硬件 设计中一个很好的参考值。 3 4 过程模型图中参数的计算 3 4 1 激活率的计算 事件激活率一般通过事件的方法和事件跟踪方法。通过事件方法是对整个系 统进行模拟，产生相当标准的结果。输入信号有触发输入( 如时钟信号，某些数 据信号) 和数据输入。但是考虑到构建系统模型需要耗费大量的时间，而且构建 的模型时必须结合软硬件划分结果来进行，在不知道各个模块软硬件实现情况来 建模是不合理的。所以本文采用事件跟踪方法。事件跟踪方法是对系统的一个小 的统计模型进行模拟，同时，高层模拟工具提供了跟踪信号事务和事件的方法。 在这个动态方法中，给系统模型一个有