（微电子学与固体电子学专业论文）软硬件协同设计的划分方法及其模型优化研究.pdf

y 介 5 2 3 摘 要 信息技术日 新月异的发展和业界厂商的剧烈竞争对计算技术提出了越来越 高的 要求。 随着集成电 路设计、 s o c 技术的飞速发展以 及应用市场不断增长的需 求， 软硬件协同设计在全球范围内得到越来越多的研究， 而软硬件划分正是其中 的一项关键技术。 本文在前人工作的基础上， 提出了 增加功耗和 n r e等系统开销分量以使得 系统开销的量化模型更具实用意义的方法，采用遗传算法对软硬件划分加以实 现， 有效的节省了 优化时间。 在此基础上， 我们针对时间开销特性提出了 一种简 化运算复杂度的方法，进一步提高了算法的优化速度。 为了 克服线性规划模型在开销量化系数上的缺陷，本文提出了开销系数自 适应方法， 该方法通过迭代逼近的方式对开销系数本身进行了 优化， 提高了系统 开销量化结果的可信度。 借用经济学的边际成本原理，本文进一步改进不同系统元素量化中的系数 问 题， 放弃了常数形式的开销系数， 提出了以函数形式来作为系统开销系数的系 统开销量化模型， 然后在此基础上结合遗传算法实现了 基于边际成本的软硬件划 分算法m c h 5 p a 测试结果表明， m c f is p 方法在有效改善系统量化合理性之后并没 有显著影响算法的优化速度。 关键词:软硬件协同 设计，软硬件划分， 遗传算法， 开销系数，自 适应， 边际成本 ab s t r a c t t h e r a p i d d e v e l o p m e n t o f t h e in f o r m a t i o n t e c h n o l o g y a n d fi e r c e c o m p e t i t i o n a m o n g m a n u f a c t u r e r s i n t h i s i n d u s t r y h a s p u t f o r w a r d i n c r e a s i n g l y h i g h e r r e q u e s t t o t h e c o m p u t i n g t e c h n i q u e . d r i v e n b y t h e d e v e l o p m e n t o f i c d e s i g n a n d s o c t e c h n o lo g y a n d e v e r - e x p a n d i n g a p p l i c a t i o n f i e l d , h a r d w a r e - s o f t w a r e c o d e s i g n t e c h n o l o g y i s r e c e i v i n g m o re a n d m o r e r e s e a r c h w o r l d w i d e l y . i n w h i c h h a r d w a r e / s o ft w a r e p a rt i t i o n i n g i s e x a c t l y a k e y t e c h n o l o g y . a t th e b a s i s o f p r e v i o u s w o r k i n t h i s a r e a , w e p ro p o s e s a m e t h o d w h i c h m a k e s t h e s y s t e m q u a n t i z a t i o n m o d e l s m o re p r a c t i c a l b y a d d i n g p o w e r a n d n r e p a r a m e t e r s . w e i m p l e m e n t e d t h e h a r d w a re / s o ft w a r e p a r ti t i o n i n g w i t h g e n e t ic a l g o r i t h m a n d m a d e a n i m p r o v e m e n t t o r e d u c e c o m p u t a t i o n c o m p l e x i 你 a c o e f f i c i e n t s e l f - a d a p t i v e m e t h o d i s p r o p o s e d in o r d e r t o o v e r c o m e t h e d e f i c i e n c y o f c o s t m o d e l o f l i n e a r p r o g r a m m i n g . t h i s m e t h o d o p t i m i z e s s y s t e m c o s t c o e f f i c i e n t s i n a n i t e r a t i v e l y a p p r o a c h i n g s ty l e a n d e n h a n c e d t h e c re d i b i l i t y o f o p t i mi z a t i o n r e s u l t . e n l i g h t e n e d b y m a r g i n a l c o s t p r i n c i p l e i n e c o n o m i c s , w e f u r t h e r e x p l o r e d t h e s y s t e m c o s t m o d e l a n d r e p l a c e d t h e n u m e r i c a l c o e ff i c i e n t s i n t h e m o d e l w i t h m a r g i n a l c o s t fu n c t i o n s . a h a r d w a r e - s o f t w a r e p a r t i t i o n i n g a l g o r i t h m b a s e d o n t h i s m a r g i n a l c o s t m o d e l , n a m e ly m c h s p , i s d e v e lo p e d . t h i s a l g o r i t h m i m p r o v e s c r e d i b i l i t y o f q u a n t i f i e d s y s t e m c o s t w i t h o u t s l o w i n g d o w n t h e o p t i m i z a t i o n s p e e d . k e y w o r d s : h a r d w a r e - s o ft w a re c o d e s i g n , h a r d w a r e - s o ft w a r e p a r ti t i o n i n g , g e n e t i c a l g o r i t h m , c o s t c o e f f i c i e n t , s e l f - a d a p t i v e , ma r g i n a l c o s t mo d e l 软硬件协同设计的划分方法及其模型优化研究 第一章 绪论 虽 1 . 1研究背景及目的 互 1 . 1 . 1 协同设计系统 信息技术日 新月异的发展和业界厂商的剧烈竞争对计算技术提出了 越来越 高的要求。 尤其是系统的实时性更成为关注的焦点。目 前基于多处理机系统的超 级计算，一般最好情况可以达到毫秒级的响应速度，而现在，尤其是国防方面， 己提出了微秒级的要求，称为强实时( h a r d r e a l t i m e ) 。多采用专用的嵌入式计 算机系统( 多处理机加a s i c电路) 来解决。 美国国防部于1 9 9 4 年提出了“ 专用信 号处理机快速样机生成( r a s s p ) ” 计划， 德国自然科学基金会d f g 也于1 9 9 6 年提 出了“ 强实时嵌入式计算机快速样机生成” 计划。 这不仅是高性能计算的竞争， 也是快速抢占市场的竞争。软硬件协同设计即是其关键技术。 过去，器件/ 硬件/ 软件的分工设计流程，曾推动了v l s i ,整机和软件三大 产业和各自相应学科的高速发展。随着微电子技术的飞速发展使得 “ s y s t e m o n c h i p ” 己 成为可能， 在新的技术水平和系统复杂度下， 这种原有的传统设计方法 己日 益难以 适应系统设计者的要求。 近年来e d a 技术取得了长足的发展， 最新的 综合工具已经使利用行为级描述来进行芯片设计成为可能。 e d a 技术的一个新的 发展方向是将目 前可以 做到的高层综合提高到系统综合，以支持由 硬件( 专用集 成电路) 和软件( 处理器) 共同构成的系统。软硬件协同设计( h a r d w a r e / s o f t w a r e c o d e s i g n s y s t e m ) 就是将器件/ 整机/ 软件，甚至加上应用等几个领域的合作设 计。 其目 在于提高产品质量， 缩短研制周期， 降低研制成本; 其基础是发展了多 年的软件和硬件设计自 动化资源， 网络分布式协同设计环境， 可编程器件， 软件 重用与组件技术， 性能评测技术，以及系统集成技术等; 其研究内容包括: 系统 形式描述，概念级设计、验证、测评，软硬件划分，软硬件组件库( 包括替换与 接口 技术) ， 软硬件实现( 综合和编译) ， 基于多处理机与f p g a的样机平台， 样机 系统测评等。 1 . 1 . 2协同设计系统的现状 在电子系统的应用日渐广泛深入的同时，许多应用对电子系统的计算处理 能力要求也日渐上升。 尽管近年来微电子技术取得了非凡的进步， 但是不少系统 的运算单元仍然需要专用电路来执行以满足系统的时间要求。 与此同时， 为了在 不同环境下具有一定的适应性和通用性， 一些电子系统的控制功能通常由软件实 现。因而目 前许多应用系统需要混合应用硬件和软件来实现。 系统设计人员最初从设计经验出发将这些软硬件混合系统的各功能部分划 分为软件和硬件两大部分， 然后分别加以设计实现， 最后再联合为整个系统。 随 着需要面对的系统复杂程度的提高， 这种比较原始的协同设计方法遭遇到不少困 难。这些困难表现为: . 早期的划分不当在设计后期被迫进行调整造成的人力浪费和进度耽搁; . 不合理的软硬件划分未能合理地发挥软件和硬件的相对优势， 从而使系统成 本高昂却不能获得与之相应的性能: . 粗略的手工划分还可能造成不完善的接口定义以致设计末期的联合调试难 于进行等其它问题。 为避免或减轻这些问题对软硬件混合系统设计工作带来的影响，设计人员 不断致力于寻求更合适更有效的系统协同设计方法。 如果处理不同问题的协同设 计方法( 或者工具) 被整合在一起构成一个作业流程( 或者工具包) ， 那么可以称之 为协同设计系统。 从上面的描述可以得知，目 前协同设计( c o d e s i g n ) 的定义是比较模糊的， 它可以表示一种电子系统设计方法， 也可以表示一套在某种程度上整合于一起的 e d a 工 具的 集 合。 由 于目 1前 这一 领 域的 许多 问 题尚 未 获 得 妥善的 解决 方 案， 使 得 相当一部分协同设计系统或是主要适用于某些特殊系统， 或是在整个协同设计流 程中的不同阶段部分或全部的依赖遵照协同设计思想的人工干预， 或是两者兼而 有之。 尽管如此， 协同设计方法与协同设计系统还是具有明显区别。 协同设计系 统的目标是通过建立合理的系统模型， 选择合适的估算方法和优化算法， 在同等 z 软硬件协同设计的划分方法及其模型优化研究 的硬件和软件实现能力下， 获取一个以( 接近) 最小硬件和软件总成本实现所需功 能的系统构成方式。 严格意义上而言， 协同设计系统是一套e d a 软件的集合， 而 协同设计方法则是安排设计资源和流程的一套统筹方法。 本文所讨论的协同设计 系统，正是符合这种定义的 e d a 软件工具集。 互 1 . 1 . 3协同设计系统与既有 e d a软件 目 前已有许多成熟的 e d a工具在业界得到了成功的应用，这些工具涉及到 系统高层仿真、 逻辑综合、 布线、后仿真等硬件设计的诸多方面。 协同设计系统 面对的问题与这些e d a 工具有所不同， 它处理的对象并不完全是硬件， 而是一个 需要由 硬件和软件共同 构成的系统; 而它的目 标则是在整合现有设计方法的基础 之上获取一个以( 接近) 最小硬件和软件总成本实现所需功能的系统构成方式， 缩 短设计周期，提高设计可靠性。 1 . 1 . 4 一些定义和概念 系统描述( s y s t e m s p e c i f i c a t i o n ) 是协同设计系统的输入。针对不同 应用 场合的 系统， 有多种文字的 或图形的系统描述方法可供选择( 如s d l 语言 ， f s m , s y s t e m c 等) 。 系统模型( s y s t e m m o d e l ) 从系统描述中直接获取或间接生成。协同设计系 统首先需要可供其操作的系统模型， 系统模型必须具有这样的性质: 首先它必须 有效表达系统的数据流向 和控制依赖关系; 其次必须是可评估的， 因为它需要用 来比较不同实现方案之间的优劣。 有了这样的系统模型， 就可以 在此基础上产生 各种备选方案并对之进行比较甄选，这个过程的实质是对系统方案的优化。 系统开销( s y s t e m c o s t ) :要对系统实现方案进行优化， 就需要对不同的备 选方案进行比较取舍， 因而必须使用某种量化方式对系统方案进行评估。 我们把 这种量化的结果定义为系统开销。 而要获取一个( 接近) 最优的系统实现方案或软 硬件划分方案， 不仅需要在既定系统量化方式下选区合适的优化方法， 合适的系 统量化方法更具决定意义。 如果系统的量化方式不能有效的综合体现系统各方面 的成本，在这基础上的优化努力很可能是事倍功半甚至是事与愿违的。 系统映射( s y s t e m m a p p i n g ) :系统的备选方案表现为系统模型中的各模块 与它们的实现方式之间的映射关系的集合。 而获取这一映射集合的过程则表现为 将系统按照功能要求划分为以软件实现的部分和以硬件实现的部分， 换言之， 即 软硬件划分。 元件库( c o m p o n e n t l i b r a r y ) 是含有评估系统开销所必须的所有功能单元的 各项参数的集合。一般含有硬件面积( h a r d w a r e a r e a ) 、存储器开销( m e m o r y s i z e ) 、 执行时间( e x e c u t i o n t i m e ) 、功耗( p o w e r c o n s u m p t i o n ) 等参数。 约束条件( d e s i g n c o n s t r a i n t s ) 是一些目标系统需 要满足的性能或成本要求。通常 含有硬件面积( h a r d w a r e 存储器开销( m e m o r y c o s t ) a r e a ) 、 时间 ( e x e c u t i o n t i m e ) , 、执行 功耗 ( p o w e r c o n s u m p t i o n ) 等指标。 1 . 1 . 5协同设计系统的 主要内容 系统设计系统一般都具有这 样一些特征:从某种文字的或图 形的系统描述输入开始，获取系 统模型，尔后在系统模型基础上 产生系统的不同实现方案并进行 对之评估比较，选取合适的系统 实现方案，尔后对系统方案的实 现进行逐步细化以得到可直接进 行硬件综合和软件编译的硬件和 软件描述。在此基础上进行协同 仿真以验证系统方案是否可行。 e nd 夕 图 1 一1协同设计系统流程示意图 软硬件协同设计的划分方法及其模型优化研究 图1 -1 是该流程的一个示意图。不同协同设计系统针对的目 标系统类型的差异 往往导致流程上的某些差别。 l . l . 6软硬件划分 软硬件划分是协同设计系统中一个关键的构成部分。它在系统模型的基础 上利用元件库中所提供的参数通过应用合适的算法获得满足约束条件的系统的 优化实现方案。软硬件划分的目标结构可以为单处理机单芯片 s p s a ( s i n g l e - p r o c e s s o r - s i n g l e - a s i c，也可以为多处理机多芯片 m p m a ( m u f t i - p r o c e s s o r - m u f t i - a s i c ) 。 软硬件划分在获取系统映射时尚需兼顾硬件共用/ 接口 / 功能流水调度等问 题。 在某些模型下， 可以用解析方法求得最优的划分方案， 但是由于这类问题通 常是n p 完全问 题，所以常见的做法是使用近似算法，牺牲系统的划分结果与可 能最优划分方案的接近程度以使优化过程能够在可接受的时间内完成。 l . 2文章组织 本文在第二章继续对一些既有划分方法稍作回顾并对其系统开销的评估方 式加以比较分析。 本文第三章我们给出与软硬件划分密切相关的系统控制数据流图， 元件库， 系统映射和系统映射集， 设计约束和系统开销的量化模型的定义和介绍， 它们是 后面的章节中所进行的工作的基础。 在第三章中， 我们还提出了 增加功耗和设计 等系统开销分量以使得系统开销的量化模型更具实用意义的方法。 第四章在第三章所提出的系统开销量化模型基础上使用遗传算法来对软硬 件划分加以实现，并针对时间开销特性提出了一种简化运算复杂度的方法。 在第五章中，为了克服线性规划模型在开销量化系数上的缺陷，本文提出 了开销系数自 适应方法，该方法通过迭代逼近的方式对开销系数本身进行了优 化，提高了系统开销量化结果的可信度。 第六章中，本文进一步改进不同系统元素量化中的系数问题，借用经济学 原理中的边际成本原理， 放弃了常数形式的开销系数， 提出了以函数形式来作为 系统开销系数的系统开销量化模型， 然后在此基础上结合遗传算法实现了基于边 际成本的软硬件划分算法m c h s p d 文章结尾对本文所做的工作稍作总结并对今后的工作作一展望。 软 硬 件 协 同 设 计 的 划 分 方 法 琴 基 矍 型 丝 丝 竺吐一 第二章 协同设计系统回顾 协同设计系统常常针对某种类型的系统结构， 如c o o l 协同设计系统应用于 数据流支配系统的设计，c o s y m a协同设计系统和l y c o s 协同设计系统则应用于 单处理机单集成电路结构系统的设计， 而 p o l t s 协同设计系统应用于控制流支配 的实时响应系统的设计。 本章将介绍几个比较典型的协同设计系统的工作流程以 及其划分方法，此外也简单介绍其它几个对本文有参考价值的划分算法。 2 . 1 c o o l 协同设计系统 5三三a片一on 卜、 s w p a r t s f骂蕊parts c o o l系统主要针对数 据流支配系统的设计， c o o l 使用v h d l 来描述目 标系统， 它还提供了一套具有层次结 构化的图形描述输入方式。 与其它在软硬件划分中使用 估算方法的系统不一样， c o o l利用综合工具和编译 工具来计算系统元素的开 销，这些开销存贮于系统开 销库中，这种方法保证通过 上述方法获得的开销可以重 用，并且其精确性也是有保 障的。 c o o l 系统的划分结果 可直接利用商业逻辑t具进 行综合的 v h d l代码和相应 于处理器的汇编代码。 c o o l 协同设计系统的流程示意见 图 2 一工 。 之 劣 h w p a r t s i r e f 内 日 t 吧用 矛2 矍粼藻 了 了 一 1卿 一日|1尹 hw 匀e d r . t io n s h ws w i m p le r r 祀 吐 翻， 图 2 一i c o o l系统流程示意 2 . 1 . 2 c o o l 协同设计系统中的软硬件划分 在c o o l 协同设计系统中，设计者首先从a r c h i t e c t u r e l i b r a r y 中选取合 适的目 标结构，并在此基础上指定设计约束。鉴于c o o l 系统致力于处理强实时 的目 标系统，为了保证元素开销评估的精确，c o o l对利用综合工具和编译工具 获得的结果进行直接分析以评估系统元素开销， 这样做尽管比较耗费时间， 但是 可以在系统开销的精确度上有所补偿， 同时还可以减少优化过程中的逼近操作次 数。 c o o l系统采用混合整数规划( m i l p ) 方法来对划分进行优化，为了节省运算 时间， c o o l将划分过程分作两步， 先在对单元时序近似的条件下运用启发式算 法获得软件和硬件的映射结果，其后再根据时序条件通过混合整数规划( m i l p ) 方法确定系统的时间进度表。 . 2 c o s y m a 协同设计系统 c o s y 。 协同设计系统的优化目 标是充分利用处理机以尽可能提高系统速 c o s y m a以一种类似于c 语言 但是允许定义并发结构和时延约束的c x 语言作 q乙0 圣度 为系统的输入描述，然后编译为一个内定的系统图，c o s y m a系统的软硬件划分 是用模拟退火方法实现的。 c o s y m a系统的一个严重缺陷是其硬件和软件不能同 时运作。 2 . 2 . 1 c o s y m a 协同设计系统的流程 c x 在输入之后将被编译为一种扩展符号图( e x t e n d e d s y n t a x g r a p h ) ，尔后 将这些c x 进程在目 标处理器的r t 级模型进行模拟以获取这些进程的包括时延在 内的各方面参数。c o s y m a的软硬件划分以纯软件实现开始，不断选取合适的单 元替代为硬件，直至以最小硬件开销满足系统时延约束。 2 . 2 . 2 c o s y m a 协同设计系统中的软硬件划分 c o s y m a协同设计系统以基本功能单元对目 标系统进行划分，这些基本功能 软硬件协同设计的 划分方法及其模型优化研究 单元并不既可以由硬件实现， 也可以由软件实现， 因而需要比较不同实现方式的 时间开销和硬件开销， 在c o s y m a 协同 设计系统中， 一个功能单元由 软件实现变 更为硬件实现时，系统执行时间的变化量为: a t ( b ) = t w ( b ) 一 t ., ( b ) + t a m ( z ) 一 t _ ( z v b ) 式中t ( b ) 即为通过硬件替换所节省的时间值，t ( b ) 为硬件/ 软件实现的时间开 销，t -( , ) 为单元b 在c p u 与a s i c 之间需要的通讯时间，t , ,- ( z u b ) 为由于相邻 单元之间由于同样由软件/ 硬件实现而节省的通讯时间。 通过硬件替换方法，c o s y m a协同设计系统能够将系统执行速度在纯软件实 现的基础上提高2 . 7 至9 . 7 倍。 2 . 3其它软硬件划分方法 2 . 3 . 1 m o g a c算法中的软硬件划分 r o b e r t p . d i c k 和n i r a j k . j h a 在1 9 9 7 年提出了一种应用遗传算法进行多 目 标优化的方法， 该方法在估算系统开销时针对功能单元的时序使用调度算法进 行精确估算， 并在此基础上使用遗传算法，以较少的运算时间获得了优良的划分 质量。 2 . 3 . 2一些其它软硬件划分方法的情况 一些协同设计方面的研究团队己经开发出了支持协同设计的某些方面的工 具。在这些研究中，f r a n k v a h i d 和t h u y d m l e 将k e r n i g h a n - l i n 算法应用在 划分问 题中获得了比较好的表现; j . t e i c h , t . b l i c k l e 和l . t h i e l e 将遗传算法 应用在一个图像压缩系统的系统级综合中， 获得了满意的结果; m a r t i n g r a j c a r 用列表调度算法来计算遗传算法中每一个体的时间开销， 大幅提高了系统运行时 间的估算精度。 2 . 4小结 经过业界研究人员多年的努力，软硬件协同设计系统己经在不少场合得到 初步的应用， 但是不可否认的是， 其通用性还很成问题。同时由于一些关键问题 尚未得到解决， 或者与现有e d a 用具之间的衔接问题， 使得软硬件协同设计系统 在实际应用中常常需要大量的人工干预。 在软硬件划分领域，前人己经进行了许多有意义的探索，有些软硬件划分 方法己经在实用方面获得了一定的成功， 有效的改善了系统的结构合理性， 缩短 了设计周期。 划分问题， 究其本质即映射优化问题， 仍然由一些疑问有待阐明和 改进。 在后面的章节中， 我们将给出我们的实现方法， 该方法将克服现有的一些 方法中的缺陷。 软硬件协同设计的划分方法及其模型优化研究 第三章 软硬件划分模型 由于协同设计系统所处理的内容比较宽泛，本文将主要致力于软硬件划分 方面的研究， 而不打算在其它方面涉及太多。 在本章中， 我们给出与软硬件划分 密切相关的系统控制数据流图， 元件库， 系统映射和系统映射集， 设计约束和系 统开销的量化模型的定义和介绍， 它们是后面的章节中所进行的工作的基础。 本 章中， 我们还提出了 增加功耗和设计等系统开销分量以 使得系统开销的量化模型 更具实用意义的方法。 就本文所研究的软硬件划分而言， 其数据输入输出关系大致如图3 -1 所示， 其输入数据为系统控制数据流图( s y s t e m c d f g ) 。 作为进行划分的条件，还需要 元件库( c o m p o n e n t l i b r a r y ) 以 便划分算法在其中选择软件或硬件单元: 此外， 软硬件划分问题往往 会具有一些约束条件 ( d e s i g n c o n s t r a i n t s ) 。 而 划 分 结果， 则是确定的系统 控制数据流图中的功 能单元至元件库中元 件的对应关系。 s y s t e m cdf g w .甲wls 日 伪mp o n e n t l ib r a r y f 一 下一 如闷卜 p a r t i t io n in g d e s ig n co n s t r a i n t s 上 内r t ib o n in g re s u f 图 3 一i软硬件划分的数据输入输出 3 . 1软硬件划分的输入数据 . 系统控制数据流图( s y s t e m c d f g ) 是由协同系统的输入系统描述( s y s t e m s p e c i f i c a t i o 旧生 成的 一 个有向 无环图g = ( v , 习 ， 其中v = f v t , v 2 . . . . . . r n , e c v x v , e ;, 一 (v ,叻 作 为 协同 设 计 系 统 的 内 部 数 据 格 式， 其 作 用 主 要 是 将 系 统描述的逻辑结构( 定义语言输入) 或者拓扑结构( 图形输入) 转化为含有必 要信息的功能单元及其依赖关系，并以图的数据格式进行保存。由于木文仅 仅研究软硬件划分的方法， 因此所用系统控制数据流图并非按照上面的方法 生成，而是按照系统控制流图的一般特征用随机方法生成的测试输入。为了 计算关键路径， 这些作为测试用途的系统控制数据流图都具有一个起始单元 和结束单元，这两个单元可以具有实际功能，也可能仅仅是计算用而没有实 际软件或者硬件开销的虚单元。 . 元件库( c o s t l i b r a r y ) 用来提供评估系统开销( s y s t e m c o s t ) 所必须的参数。 系统开销是所有系统用户关注的系统参数的综合。 随着对电路系统的高计算 能力高移动性的不断追求，功耗因素在系统中日渐重要。电子系统的设计成 本和面市时间对其商业价值有很大影响， 元件的设计需要一定的开发成本和 时间，对某些元件而言， 利用商业渠道获得的 i p可以节省开发成本和开发 周期中的一个或者是全部。 为了真实反映系统的设计开销对系统总开销的影 响， c o p a r t 算法将系统的开发成本和开发周期综合为设计开销。 这样我们结 合现实设计要求，在面积( h a r d w a r e a r e a ) 、存储器( m e m o r y ) 、运行时间 ( e x e c u t i o n t i m e ) 等常见开销的基础上增加了功耗( p o w e r c o n s u m p t i o n ) 和 设计开销( d e s i g n c o s t ) 参数。 . 系统映 射m i. 。 表示顶点v ， 或者 边e l 由 元件c . 的 第n 个实 例l m ,。 实 现。 每个 功能单元f u k fu n c t io n u n i t , v 1 或者c r) 对应若干个具有相应功能的元件c m ， 每 个元件c ， 又 有若干 个实 现实 例i . n ， 如果不同的 功能 单元f u 对应 着同 一个实 现实例1 . ,n ， 那么这些功能单元f u 之间就存在着共享资源的 关系。 我们的 方 法中考虑的是单处理器和单 a s i c的系统结构，所以对系统控制数据流图中 的边作简化处理。 这里边的开销只有3 种情况: 处理器内部数据传递， a s i c 内 部 信号 传 递， 处理器 和a s i c 之间的 总 线连接。 一 条边e 。 的 这3 种情况可 以 由 顶点v ， 和v i 的 映 射m jm ， 和崎m ,n 判 定; 所以 本文的 系 统映 射中 不 含 有 边的信息。 . 设计约束( d e s i g n c o n s t r a i n t s ) 给出 系统各个开销分量的 取值范围。 系统的 设计目 标一般包含一些具体的约束条件， 对系统最终在某一方面所具有的最 低性能或者在某一方面所可以接受的最大开销作出限制。 3 . 2软硬件划分的输出 划分问题的任务就是寻找一个最佳的，或者说，最符合系统设计要求 软硬件协同设计的划分方法及其模型优化研究 ( s y s t e m r e q u i r e m e n t s ) 的系统实现方案( s y s t e m i m p l e m e n t a t i o n ) 。 系统实现方案是一个由系统功能单元 ( f u n c t i o n u n i t s ) 至元件库 ( c o m p o n e n t l i b r a r y ) 的系统映射( s y s t e m m a p p i n g ) 。 m a p p in g f u n c t i o n u n i t s 一 一 一 一 一 一 一 一 一 -c o m p o n e n t l i b r a r y 刃了厂1|111、esl、 今 .一一一一-一-一-一-一- 从而软硬件划分就是从一组系统映射 中 寻获最佳系统映射 o p t i m u m s y s t e m m a p p i n g ) 。 因此，欲进行软硬件划分，需要 两个条件: spe c . 一组可供选择比较的系统映射集 ( s y s t e m m a p p i n g s e t ) ; 以下g 图 3 -2软硬件划分示意图 . 一个可行的评估标准( e v a l u a t i o n ) 对不同系统映射进行优劣比较。 3 . 3系统映射集 由于利用解析方法直接求解最佳系统映射的方法在实际实现上存在困难， 另一种方法是在一个系统映射集之中对不同系统映射个体进行相互比 较， 以 求得 到最佳( 或者接近最佳) 系统映射。 这种做法要求所比较系统映射集能够覆盖绝大多数可能的系统映射以 保证 可以在其中寻获最佳系统映射。 问题是， 这种方法的计算量同样无法接受。 一种 理想的做法是缩小系统映射集的范围， 同时保障( 接近) 最佳的系统映射个体仍然 被包括于其中。 遗传算法可以获得这样的效果。尽管遗传算法在所有时刻只含有整个系统 映射可能集合的很小部分， 而且在遗传算法的进化过程之中遍历的系统映射总数 也很有限， 然而由于遗传算法的种群平均质量能够一直稳定的上升， 遗传算法的 基因变异和概率选择机制又保证了个体可以变异为任何可能的系统映射， 并且不 会陷入局部极小而无法自拔。 在本文中，我们用随机构造的方法生成初始系统映射，此后在其基础_l 利 用遗传算法( g e n e t i c a l g o r i t h m ) 的变异( m u t a t i o n ) 和杂交( c r o s s o v e r ) 方法生 成具有一定数量的系统映射集，然后在此基础上进行优化。 夸 3 . 4系统开销的量化 要对不同系统映射进行优劣比 较， 最直接的方法就是以 某种方式将系统映 射量化( q u a n t i f y i n g ) ， 然后简单的比 较量化结果即可。现有的软硬件划分方法 也都是这么做的。 这一量化的本质是将需要同时进行硬件和软件等多目 标优化的系统映射通 过规定不同优化目 标之间的相对关系将问题简化为单目 标的优化问题。 从系统映射可以得知系统功能单元的对应元件，因而可以用这些单元所对 应元件的参数的特定函数来对系统映射进行量化。考虑到对同一系统映射集而 系统功能单元及其之间的时间和逻辑依赖还有元件库的参数都可以视为常 因而可以用系统映射的函数f ( a h 来对系统映射进行量化。 言量 由于比较不同系统实现方案的标准是成本和性能，因而由元件库中的各参 数来获取系统映射量化是合理的做法。 对元件库中提供的不同量纲的系统元素开销，必须统一为同一量纲进行加 权刁获得可以 相互比较的量化结果。 常见的做法是对所有不同单位的参数加以不 同量纲系数处理， 使之成为无量纲的数值， 然后进行简单加权得量化结果。 加上 约束条件，这种量化结果即可化为线性规划的标准形式 m in s y s c o s t = 艺c o eff ic ie n t, * c o s t 菩 a y * c o st _ )c o n s c o s t ; _ 0 软硬件协同设计的划分方法及其模型优化研究 这些系数体现了不同系统元素之间的成本差异，使得不同系统元素之间的 权衡取舍得以在一个共同的基础上进行。 因此这些系数能否确凿的体现元素之间 的成本差异就成为关乎软硬件划分结果质量的关键因素。 3 . 5系统开销分量的增加 系统开销是所有系统使用者关注的系统成本的综合。这些开销既可以是重 复发生的生产成本，也可以是设计、测试等非重复发生费用( n o n - r e c u r r i n g e n g i n e e r i n g c o s t ) 。 随着对电路系统的高计算能力高移动性的不断追求，以及这些年来发展相 对滞后的电池容量， 功耗因素对系统综合性能的影响日 渐重要。 为了 合理反映这 一因素对系统带来的影响，本文结合现实设计要求，在硬件( h a r d w a r e a r e a ) , 软件( s o f t w a r e s i z e ) 、运行时间( e x e c u t i o n t i m e ) 等常见开销的基础上增加了 功耗( p o w e r c o n s u m p t i o n ) 参数。 电子系统的设计成本和面市时间对其商业价值有很大影响，元件的设计需 要一定的开发成本和时间，对某些元件而言，利用商业渠道获得的i p 可以节省 开发成本和开发周期中的一个或者是全部。 伴随着市场的细分， 小批量生产的电 子产品也日 渐增多， 这类产品的设计测试费用将占其商业成本的较大比例， 因而 在设计这类产品时， 对以设计成本为主的n r e费用有必要加以考虑， 本文添加了 一个设计开销( d e s i g n c o s t ) 参数来体现这类n r e费用对系统成本的影响。本文 后面所提及的设计开销，若无特殊说明，则表示所有n r e 开销。 第四章 遗传算法 作为n p 完全问题， 线性规划的解析求解在规模较大时的耗时是难于接受的， 在实际工作中， 研究者们常常使用各种近似方法来对该问 题进行求解。 在本章中， 我们在第三章所提出的系统开销量化模型基础上使用遗传算法来对软硬件划分 加以实现，并针对时间开销特性提出了一种简化运算复杂度的方法。 4 . 1遗传算法的基本原理 生物界中，物种在世代更替的过程中会由于各种扰动产生无定向的基因突 变， 而种群中的个体之间也通过交换混合基因的方式来产生后代。 经过“ 物竞天 择， 适者生存”的自 然选择机制，良 性的突变基因以更多的机会得到继承;表现 不佳的突变基因以很大的概率得到抑制( 而不是立即被消灭，这样如果一个 突变基因的优势暂时未能表现， 也有一定的机会得以保留以在适当时候体现其优 势) 。 经过世世代代的扰动突变选择继承这样反复的过程， 良 性的突 变基因将会得到积累，物种后代的质量得 到逐步的改善。 i n i g r o u p 遗传算法( g e n e t i c a l g o r i t h m ) 仿照 上述机制，将问题的不同实现方案编码为 相应的染色体( c h r o m o s o m e ) ，然后对由一 定数目的染色体组成的种群( g r o u p ) 中的 个体分别使用基因突变( g e n e m u t a t i o n ) 或者异体杂交( c r o s s o v e r / r e c o m b i n a t i o n ) 的方 式不断产 生随机 的个 体 繁衍 ( r e p r o d u c t i o n ) 。 尔 后 对繁 衍的 种 群 应 用 合适的选择机制( s e l e c t i o n m e c h a n i s m ) 以控制繁衍过程中种群的属性不断向控制 者所希望的方向发展。这样受控的繁衍方 r e p r o d u c t io n s e le c t io n e c o n n g r e p r o d u c t io n p a r a me t e r s / 纽 冬沐 _、 i- - -k in 已 遗传算法流程示意图 k一|一-1 0厂又纲 式称为进化( e v o 土 u t i o n ) 。常见的遗传算法流程参见图 d 一1 。 软硬件协同设计的划分方法及其模型优化研究 夸 4 . 2 遗传算法在软硬件划分中的应用 4 . 2 . 1等位基因与编码 g e n e a l l e l e 染色体的等位基因机制:染色体 ( c h r o m o s o m e ) 由等位基因( a l l e l e ) 序列构 成，每个等位基因含有一个基因( g e n e ) ( 参见图4 一2 基因，等位基因与染色体) 。 9 湘2 7 9 而砍 9 5厂丫汉 9 r 图4 一2 基因，等位基因与染色体 在遗传学上， 特定的基因位置( 即等位基因) 表达特定的生物功能， 基因只有处于 该等位基因处刁 能表达出它所携带的生物信息。 例如， 某个等位基因位置处含有 个体眼睛颜色的信息， 而位于该等位基因处的基因才真正决定眼睛的颜色， 如果 该等位基因位置处基因缺失则无法表达眼睛的颜色， 而该基因位于其它位置也无 法表达出眼睛颜色。 简单的说， 等位基因机制通过等位基因的位置决定该处的基 因将表达何种功能，而位于等位基因位置处的基因则最终确定该功能的表现形 式。 染色体的这一特性与作为软硬件划分输入数据的系统控制数据流图性质非 常相似: 特定位置具有特定功能， 而该功能可以受控为不同的表现形式。 因此我 们可以把系统控制数据流图编码为染色体， 尔后运用遗传算法来对系统控制数据 流图进行间接优化。 系统控制数据流图的编码结果需要包含系统的所有必须信息，以便从经过 一系列进化过程后的结果里还原出经过优化的系统。 在软硬件划分问题中， 需要 对系统c d f g 的顶点集 v 和边集f. 进行编码，染色体的等位基因机制在这里表现 为在染色体中某 一 确定位置的基因所代表的总是某一确定顶点和边的信息， 所以 这里我们只需要确定对顶点和边自 身的信息进行编码， 而不必理会系统控制数据 流图的拓扑结构。 遗传算法中常见的基因 编码方法主要有二进制编码 ( b i n a r y c o d i n g ) 和实数编码 ( r e a l n u m b e r c o d i n g ) 两种。 利用二进制编码时同样的染 色体长度所表达的模式相对 于其它编码方式最多， 而且在 进行变异、杂交操作时也很方 9 1 ,l 学 d 9 3 d少 d 9 5 cd f g4c h romo s o me 图4 一3 c d f g 编码为染色体示例 便; 但是二进制编码的精度缺乏伸缩性， 对算法的微调功能很有负面影响， 同时 在处理一些高维问 题时缺乏效率。 而实数编码在进行遗传操作时要较二进制编码 复杂， 而且并不适合在软硬件划分问 题中应用。 本文中使用了 类似于二进制编码 的整数编码方式， 这种方法既可以高效的表达所有系统信息， 而且有效的解决了 二进制编码的 染色体无效杂交位置的问 题。 还需注意的是， 本文中系统功能单元 之间的数据依赖关系被记录于功能单元之内，因而只需对功能单元进行编码即 可。图 1 一3 是一个简单的系统控制数据流图的编码示例 、夕之入犷了 /习/9 ;