（计算机应用技术专业论文）基于cdm模型的01规划软硬件划分方法的研究.pdf

摘要关键字摘要近年来，信息数字系统的软硬件协同设计逐渐成为研究热点。随着设计规模的不断复杂化，技术上的不断演进和成熟，业内研究者们正逐步由r t l 级设计向系统级设计转移。然而目前国内在这一领域对系统的高层设计仍然研究不足，多注重r t l 级和底层芯片的设计，对系统规范描述不够，缺乏整体设计环境的实现。作为软硬件协同设计的一项关键技术，软硬件划分的优劣对整个系统的性能和成本的影响非常大，其研究具有重要的学术和应用价值。由于面向不同的应用和设计层次，软硬件划分采用的技术存在较大的差别。本文采用需求驱动的软硬件协同设计方法，将数字系统的设计定位在高层( 即系统级、芯片级和寄存器级) 设计上。针对数字系统高层设计的特点，本文提出了基于c d m 模型的o 1 规划软硬件划分方法。在分析现有各种软硬件划分技术的基础上，围绕如何求解软硬件划分最优解，创新性地提出了基于0 一l 规划的划分算法，并对算法的效率做了分析比较。本文作者的主要贡献有以下几点：1 数字系统的结构复杂多样，其高层设计对组件的可重用性要求较高。本文采用c d m 模型进行系统建模，在此基础上对目标体系结构、优化目标等软硬件划分主要问题进行系统而深入的研究，并给出符合应用特征的解决方法。2 针对目前软硬件划分算法依赖于启发式算法及其改进算法的情况，本文创新性地提出了基于o - 1 规划的软硬件划分算法( o 1 算法) 。o 1 算法结合了线性规划和遗传算法的思想，既通过简化决策变量减少计算复杂度，又通过个体分类、变换等操作保证搜索个体的均匀分布，使算法在搜索质量上接近线性规划，在算法效率上接近遗传算法。3 基于o l 规划软硬件划分方法设计了原型系统( h s p 0 1 子系统) ，其组成包括基本组件库、系统模型、特征分析、搜索寻优算法等模块，并在i c d m d t平台中加以实现。4 在应用i c d m d t 平台实际设计的简单电话机系统中，使用0 1 规划的软硬件划分方法进行功能划分，采集模拟仿真数据，由性能分析图分析比较，验证了该方法的正确性和合理性。关键词：软硬件协同设计、软硬件划分、c d m 模型、o l 算法摘要关键字a b s n a c tt h eh w s wc o d e s g no ft h ed i 西t a is y s t e m sj sb e c o m i n gl h eh o t s p o ti nr e c e n ty e a r s 晰t ht h ec o m p l i c a t i n gd e s i g n dt h em a m r a t i n gt e c h n o l o g 弘t h er e s e a f c h e r si n t h i sn e i d 静a d u a l l yc h a n g er t ld e s i g nl n i os y s t e m - 1 e v e ld e s i g n ，h o w e v e li h ed o m e s t i cr e s e a r c h e sa r es l i l ls h o r to fh i g h - 】e v e ls y s t e md e s i g ni nc h i sn e l di ni h ep a s ty e a r s t h e yk e e pn x a t i n go nr t la n dc h j pd e s 唔n ，r e s u i t j n gi ni n s u 用c i e n c yo ft h es y s t e ms t a n d a r dd e s c 州p t i o na 1 1 d l e s sr e a l i z a t i o no ft h ew h o l ed e s i g ne n v i r o n m e n t a so n eo fk c yt e c h n o l o 舀e so fl h eh w s wc o d e s i g n ，t h ep a n no ft h eh w s we x t f e m e i yi n n u e n c e st h ep e m n n a n c ea n dc o s to ft h ee n t i f es y s t e m ，s ot h er e s e a t c ho fh w 7 s wp a r t j t j o n l n gh a sg r e a ta c a d e m l ca n d 印p 1 1 c a t l o nva l u e s f a c i n gt h ed l f f e r e n ta p p h c a t j o ns y s t e ma n dl h ed e s i g nj e v e l ，l h et e c h n o l o g i e so fh w s wp a r t i t i o n i n gh a v ea 】o lo fd i 舵r e n c e s t h er e q u i r e m e n t 一“v e nhw s wc o d e s 培nm e t h o di nl h i sd i s s e r t a t i o nf o c u s e so nt h eh i g h 一】e v ej( n a m e 】ys y s t e m 】e v e 】，c h j p l e v e ia n dr e g i s t e 卜l e v e l ) d e s i g no fd l 画诅ls y s t e m s i nv i e wo f t h ec h a r a c t e r i s t i co f h i g h l e v e ld e s i g n ，t h eh w ，s wp a 九i t i on i n gm e c h o du s i n go ia i g o r i t h mb a s e do nc d mm o d e li sp r e s e n t e d b a s e do ni h ea n a l y s i so ft h et r a d i t j o n a lh w s wp a r t i t i o n i n ga i g o r i t h m sa 1 1 dc h ed i s c u s s i o nh o wt og e tt h eo p l i m a ls o j u t i o no fh w s wp a n i t l o n i n 各t h ei n n o v a t i v e0 - 1a i g o r i t h mi nh w s wp a n n i o n i n gi sp r o p o s e d b e s i d e s ，t h eo la l g o r i t h me 娟c i e n c yj sa n a l y z e di nt h i sd i s s e r t a t i o nt h em a i nc o n t n b u t i o n sa r es u m m a r i z e da sf o l l o w s ：1 b e c a u s eo ft h ec o m p i e 妇t ya i l dm u l t i p l i c i t yo ft h ed i g i t a ls y s t e ms t r u c m r e s ，t h er e q u i r e m e n l i sh i g h e rf o r r e u s i n go f c o m p o n e n t si nh i g l l - i e v e ld e s i g n u s i n gc d mg r a p hl om o d e lt h ed i g i t a ls y s t e m ，t h em a i np m b l e m so fh w s wp a r t i t i o n i n 昏s u c ha so b j e c t i v es y s t e m i cs t r u c t u r ea n do p t i m i z a t i o ng o a l ，a 糟r e s o l v e d 2 t h i st h e s i sp r o p o s e st h eh 、w s wp a r t i t i o n i n ga i g o r i t l l mb a s e do n0 - 1p r o g m m m j n g ( o 一1a l g o r i l h m ) ，a j m i n ga lt | l es i t l l a t i o l l st h a tm o s th w s wp a r t j t i o n j n ga l g o r i l h m sr e l yo nt h eh e u r i s t i ca l g o m h r n sa n dt l 皇i ri m p r o v e m e 吣t h eo 一1a 1 9 0 r i t h mi n h e r 沾也et h o u g h to fl ；n e a rp f o 伊a m m ；n ga i g o t n h ma n dg e n e t i ca l g o t h m ，w h i l ei tb o t hr e d u c e sc o m p u t a t i o nc o m p l e x i t yb ys i m p l i 母i n gd e c i s i o nv a r i a b l ea 1 1 dd i s t r i b u t e se q u aj j yl h es e a r c hi n d i v i d u a i sb yt h ec l a s s 墒c a t i o na n dt r a n s f o m l a t i o no f t h e n d i v i d u a l s a sar e s u l l 0 - 1a l g o r i t h mc a n 印p r o a c ht h es e a r c hq u a l 时o fl j n e a rp r o g r a i l l m i n ga n dt h ee 简c j e n c yo f g e n e t i ca l g o r i t h m 3ap r o t o t y p es y s t e m ，c a l l e dh s p 0 - 1s u b s y s i e m ，i sd e s j g n e db a s e do ni h eh w s wp a n i t i o n i n gm e t h o du s i n g0 - la l g o “t h m i tj sm a d eu po f t h eb a 5 ec o m p o n e n td a l a b a s ei i摘要关键字m o d u l e ，t h es y s t e mm o d e lm o d u l e ，t h ec h a r a c t e r i s t i ca n a i y s j sm o d u l ea n dt h eo p t i m i z a t i o na i g o r t h mm o d u l e ，a n di tj sf e a l i z e di nj c d m d tp l a t f o m l 4 as i m p i et e l e p h o n es y s t e mi sd e s i g n e do nt h ei c d m d tp l a t f o m l t h es y s t e mi sp a n j t i o n e du s i n gt h eh w s wp a r t i t i 彻i n gm e t h o db a s e do no 一1a l g o r j t h ma d d j t j o n a i ly t h ea c c u r a c ya n dl h er a t i o n a l i t yo fhw s wp a r t i t i o n i n gm e t h o da r ev e 矾e db yc o l i e c “n gt h es i m u l a t i v ed a t aa n da n a l y z i n gp e r f b m l a n c e 1 ( e y w o r d s ：h w s wc o d e s i g n ，h w s wp a r t i t i o n i n g ，c 。d e s i g nm o d e i o a i g o r i t h m学位论文独创性声明本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名：业隰塑：耻7学位论文使用授权声明本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。学位论文作者签名：j 幽泣导师签名日期型：! ：立日期：业叠：主：f 7糍哥c 酬模型的0 一l 规划软鞭棒划分方法舶研究第1 辇绪论 。 。綦秀究营豢随潜信息社会的判来，掌上电牖、p d a ( 个人数字助理) 、移动电话、笔记奉电藏、m 粥攒赦浚螯、数璃接瓤等一系列瑗代镁二壤惑家奄产罴、霉上电予产品以及透信产品不辑掇琨。这些产晶豹更薪灞耨越来越短，设计时需要考虑的因素越来越多，如应用环境、功能、成本、体积等，更重要的是对这些众多因豢进行优化，以满足市场驰需求。这绘传统懿设计方法及技术带来了严重静撬战。传统的设诗方法一般褥系统钓设诗分为两个除段：系统级软件开蓑籀窀貉缀硬件设计。软件开发和硬传设计往往是相对独立避行妁，始鞠l 。l 。在传统匏设计模式下，软件租硬件之间很难在晕期进行平德昶优化，并有可能严重影响丌发畿本移开发耍麓”l 。如秘在较嚣开发与蘸舞实褒之溺絮设一痉疆粢成为辍为逸绣豹任务。因此，鬻际上牙始研究软磺件漭同设计( h w s w c o 。d e 8 i g n ) 方法，要使该设计方法能支持并行工程从而缩短设计周期。簸 孛歼蓑嚣毯硬件设计簿蟹 一传统辩设计隽法自二十世纪九十年代以来，国际上许多著名的研究机构一髓在从事软硬件协矮设计技术斡酝究劳嘏褥了丰硕熬成果，莺羚饕曩还毒一些比较或熟竣产赫，般m e m o r ( ；糟p h i e s 公司的齑凄一俸他的s o c 设计验证工具，荚鬻馆克剩大学鲍p o l i s ，德国b r a u n s c h w e 蟾大学的c o s y m a 等。然丽这些产晶主要涉及集成电基予c 瓣攘墅麓争i 麓簇软硬捧蘩蟹方法转辑兖路底层芯片的设计，并风软硬件采用不同模型和描述语言。国内的v l s i 系统设诗窝s o c 设诗技术也穗逐步发震霆寒，毽臻跫予越步除爱，露虽怼系统高毽设计缺乏研究。大多数骈究只注重r t l 缀和底层芯片的设计，对设计需求霸系统舰范描述不够，整体设计采用了多种模型，软硬件部分使用不同语言描述难于验证和协同缘合等。这些特点在系统结构更加多样化、设计复杂魔不断提高、枣场竞争意趣激黧匏绩疆下严羹随礴了软硬僭协氡设诗技术筑菠震。瓣既，遭两磷究者们开始从r t l 级设计转向系统级设计。随着软硬件协同设计厩向的应用和设计层次的变化，作为设计中关键环节的款疆 睾划分瞧瑟骧羞毅瓣挞菠。簿了稷撂没诗终袈及系统荟个帮分麴特色，凑裳各部分的软件或者硬件实现方式，以获得高性能、低成本的优化设计方案之外如何根据设计特点对系统建模、目标体系结构的确怒以及性能分韦斤等问题提出恰当的解决方法也是软硬件划分过程中必颁考虑款。冁此，合理躲软硬传划分方法麓通过对划分过程中各项技术遂彳亍全黼的磅究，镄溉入式系统在麓层设诗中麓获得最佳性价比。 ，2 。软硬傣傍溺设计技术缀述二十世纪九十年代前后，微处理器已经成功使用十多年的时间，计算机系统鲍设计大多仍是在插琅硬传平台上进行软 牛鲍开发。这时随蓑定铡系统嚣求的提出，设计者开始在c p u 上运行嵌入式软 孛，酝入式系统及芯片浚计工程萍开始提出软硬件协同设计( h a r d w 钌“s o 脚黼ec o d e s i g n ) 一词，人们_ 开始了对软磷件协同设计技术的研究 “。软镂 冬漭溺设计戆定义至今仍没畜完全一致翁褒透，本文绥台文献翻鞠i 4 3中的解释认为：软硬件协同设计是一种在设计的最铆阶段就将软件与硬件两方面结合起来权衡功能的分配，在软件与硬件的并行设计过程中实墩软硬件的交互，以满足系缝麓功鲢与蛙要求的设嚣方法。软穗件貉弼设计方法是一种非常灵活豹设诗策赂，它在系统霸标要求的攒导下，通过综合分析系统软硬件功能及现有资源，鼹大限度地挖掘系统软硬件之间战并发性，块圊设计软硬传体系结构，以便系统能蝣工作在最僚工作状态。协同设计鼓零强调软俘积嫒锌设诗开发蹙一个并嚣帮稳甄反续静过稷，款露菝穆满足综合性能指标的最佳解决方案( ”。软硬件协同设计过程一般可以分为系统模型的建立与确定、软硬件划分、软硬 拳聱箨及疆鑫静综台虢及系统囊袋等步骤，露黧1 2 瑟示，冀孛涉及数尼黪主要软硬件协嗣设计技术如下：蕊予c 掰模型熬0 一| 蕊翅较硬箨翊势方法豹蜡宠图卜2款硬件协同设计过程1 ) 系统描述在系统描述阶段，将系统划分为互连的模块，每个模块都执行功能相对独立故特定弦失，著礁定模块熬互连关系零接口标礁，竞箴系统熬缝擒模型接连。遮瓣的籀述并不涉及任何有关系统具体弼何实现的缁节，甚至不涉及到哪些模块怒硬件，哪些模块是软件。随饕软硬件协嗣设计研究的深入，对系统模型的研究墨澎成为一个重要髓技术势支。为瑶蠢羟麓流应霜，p 0 己i s 项銎中旋出了e f s m ，它巍够荠发藐行懑倍进程，随后m c h i o d a 等又在此基础上建立了e s t e r e l 语言【6 1 。在数据流处理虚周中，同步数捞流处理模型用来描述多速率数据计算吼1 9 9 9 年，德嘲的d a 蛳s t 础工业丈学鬟毫了一个对系绞遴 亍毫瑟攒述静诗篓模鍪c 矜m ，戆够髑寒矮透舍蠢震赣和非周期执行序列的德环结构图的嵌入式系统【孵。2 ) 软硬件划分较磺俸划分在结构撼述完成慧滋行，以礁定各个部分由较侮或硬传实现。其露酌主黉是使露标系统满足速度、延迟、或本等方蕊靛要求，获得正确完整瓣功能和较好的性能。在完成功能的软硬件分配后，要对系统的性能、灵活性等参数进行预测，以评估功能划分优劣及合理性。如果划分不合理，就灞要重新进行软硬舞黧分。软硬件戈0 分最初怒设计者依据缀验手工划分，而最早的自动划分方法出现在9 0 年代初期【l 。自此以后，国内外研究者在这一领域不断深入并取得了丰硕的成果。g u p 拯等入歼发了一穗软硬馋矧分冀法霹予惑凌优设嚣空阕攘素过程，翳融，针对嵌入式实对系统，g u p 扭和d e m i c h e l i 还提出了在协处理器釉通用处理器上进舔 二e 酬模型豹o l 规划软磴释划分方洼鹩研究行划分的迭代算法。a m b r o s i o 和h u 提出了一种通过抽象估计可被调度畚统结稳载穰率寒实瑷软磺梅翔分翡葬滚l 弪l 。e m s t 撬积静方法是惫将所有系统功麓摸块划分为软件，然后谶行迭代，选择部分功能模块移动到硬件以提高系统的速度。p o t k o n i a k 和r a b a e y 提出了一种构造性算法米优化系统的释吐量和代价。f 。c ，f i l 凇等采用基予p e 瓤燕亲遴行软矮传划分嗣。v 囊遗针对缝穆睦划分，凝述了功能性划分的优点淄，t o w l s e y 在不考虑实时限制的条件下，解决了同构分布嵌入式系统任务分配的问题 ，而l e e 和s h i n 在考虑了通信的前提下，解决了同构任务的分配闻题7 l 。在改进援素划分解空闯算法上，研究者翻骰了更多熬尝试，研究荠应嗣了各具特色的划分算法。其中，应用效果较好的典型算法是启发式算法，如爬山法、遗传算法、模拟退火、禁忌搜索等，这些算法通过定义启发信息指导搜索过程逐步淘最谯鼹 雯襞。缀多硬究耋雯楚篓子这些雾法针对墨类应蠲 睾密了改透| l ”“。3 ) 软硬件协同练台在完成软硬件划分之后，就可以对各个模块谶行细化、综合，到形成虚拟系统原型。在较硬传协同综食方面的磷究龟是协同设计中懿一个薰葵磷完分支。1 9 9 7年普棒颛顿大学得到了美国罄家科举基金韵资驹，在其软硬件协同设计项掰中提出了个软硬件协同综合方法c o s l 【2 3 j ，性能明显优于早期的p r a k a s h & p a k e r y e n & w o l f 的方法 2 4 】，随后，又相继在c a s p e r f 2 酏，c o r d s 【2 7 l与m o g a c 疆鞋等滋溺综合算法中_ l 羲一步迸季亍了磷究。4 ) 协同验证和仿真在已知软件和硬件部件行为的撼础上对系统的行为进行建模，著验证系统的功能秘诤徐系统戆瞧缝，最终确试设诗是否瀵是功旋要求j 羹条髂终泰。1 9 9 2 年开始加这对协同仿真的研究。b e c k e r 、s i n 醢与t e l l 开发的狲嗣仿真器将硬件仿真器与软件联接起来口9 j ；加州伯克利分校p t o i e m y 项目丌发的协间仿真器是基予多种异构摸裂的，对于爱来理解多种异鞠模型的关系起到了很好斡作用圜：z k o j n o v i c 与m e y 提出了一个纂予编译诲瀚仿真方法器】；可重麴f p ( 漶的出现使得软硬件划分以后可以在真实的仿真平台上进行验证，从而为软硬件协同设计提供了一种良好的验证平台。s y s t e m c 的出现为高层的协同仿真提供了方便。l 珏c 33 蕊疰、d a v 如器锇。曩等论述了基于s y s 艳瓣c 的软硬佟谂弱蕊真方法f 3 2 l 。5 1 系统评价所谓系统评价怒在集成了虚拟系统原型之后，对系统的性能、灵活性褥次进行 平估，其目的是礁定蘸蟊的先验傣计是否准确。如果后验译f 占与先验谬馈媚差太大，爵麓还需要耄新进行结稳谰熬和软硬释划分跚。通过采用实时系统调度方法来髂汁系统的性能成为了种典型的做法。r m a4蒸于e 秘攘壁熬垂l 撬翔较疆释魏分方法麓辑究( r a t em o n o t o n i ca l 女o r i t h m ) 作为种分析多个进程在同c p u 上运行的性能豹方法受蠲了关! ；室。1 9 9 8 年，y e n 与w o l f 搀爨了令多跫瑾嚣系绞筑蛙舞法以分瓴一组进程硖射到一个处理器瀚的性能，在簿一个处理嚣上运行一个r m a调度器l 。随着基于s y s t e m c 的协同仿真的发展，基于仿真的系统评价也日黼成熟起来。豫了以上这些关键技术静发襞，多年来，众多静磺究执擒还致力予软疆传协同设计工具的研究和寅现。具有代表性的有德豳淡兰根纽伦馒大学计算机网络与通信系统系研究开发的c o r s a i r ( c o d e s i g na n dr a p i dp r o t o t y p i n gs y s t e m轴a l i o 蕊瓣sw 强融一钰m ee o n 瓣藤n t s ) 、德爨多褥蒙戆大孥诗葵撬辩学系疆计韵面向数据流领域的e 0 0 l ( h a r d w a r e s o 脚a r ec o d e s i g nt o o j ) 、美国加州大学伯克利分校等团体设计的p o l i s 和c o s y m a 。避年来随着国内嵌入式系统和数字信息设餐设计技术的发震，国防科技大学、武汉大学及复丝大学等多所赢捩懿研究祝梅也加入到软硬件协同设计瀚研究中来并在这一领域敬褥了一定成暴，为国内的软碗件协同设计发展贡献了力最。 ，3 。零文研究内容1 3 1 研究目的和研究内容本文疆在深入理解基于c d m 模裂的系统级软硬件协同设计技术的基础上，系统地分析和研究软硬件划分过程中的一些技术难题，并针对应用特征和设计特点，对这魑技术闽题掇燃效率更高、遁爆性更强的软硬俘划分方法。本文鹃硒究内容包旗强下凡煮；1 ) 对软硬件划分主要问题的研究与解决。其中包括系统琏模、目标体系结构和优化目标的确定以及基予组件库的功能分配等问题的研究。蛩软矮蒋蠢羲怒分羹洼懿设诗冬分攥。在癸褥袋毒葬滋俊笺筋莲疆上，疆出效率和质量鼹商的划分算法。3 ) 软硬件自动划分原型系统的实现。根据提出的软硬件划分方法设计并实现原型系统。4 ) 通过对实翻豹实际设计、模拟仿真，国瞧能分祈结莱黢证文中提出的软鞠件划分方法的合理性。纂于c d m 模型的o t 规划软硬件划甜方法的研究1 ，3 ，2 ，文章的组绥结褥本文菇分七章，释章的组织如下：第章就本文的研究背景及软硬件协同设计技术进行简单描述，并介绍了全文游骚究内容积文章鹣组织结穗。第二二章简要介绍了软硬件划分中耍考虑的问题：系统建横、目标体系蹈构、划分算法和性能评估方法，并主要从这几个方面对软硬件划分常用技术进行回顾露麓余。螽瑟冬章节憋分裂怼这些方嚣遂霉亍详缨讨论。第三章讨论了系统建模问题。本文采爱c d m 系统模型束攒述各种信息数字系统。介绍了系统模型c d m 的定义与特征并使用双着色c d m 图表示软硬件双路划分，同时将c d m 与其它主要的系绞模型避行比较分袄。繁黼摹藏软硬箨翻分懿形式颤二攒述、侮系绪稳、饶傀叠标及基于组箨弱功麓分配等软硬件划分涉及的主要问题进行研究，针对应用特点分别提出了相应的解决方法。翳五耄痒为全簿瓣竣，参，爱籍性逮鬟凄了蒸予0 i 援囊豹簸疆髂楚分冀法，并对算法的目标函数、数学基础、算法的设计思路、算法过程描述以及算法分析等方面谶行了详细阐述，最后将o 1 算法与遗传算法( g a ) 、憋型线性规划算法( 1 l p ) 救性熊积效攀避行实验结暴毙较，结巢袭臻；0 1 算法在实现效果上接远线往糕矧，在算法效率上接近遗传舞注。第六章介绍了软硬件协同设计平台i c d m d t ，提出了基于o 1 算法的软磷件划分原型系绞( h s p o 1 予系统) 的体系结构和设计实现。并通过设计实例简单窀。诿羧系统在i c d 狱馥平叁上数浚谤过程，验涯了本文夔整豹软疆释翻分方法的合理戆和正确性。文牵结尾对全文工作进行总绥并对下一步工作进行展望。6基于e 跚模型抟o l 理捌软硬释翔分方法的研究第2 耄软硬件划分技术歉疆 孛翅分是软疆俘携蘑设计滚程孛熬关键强苇。翊分游结暴将交定系统莰计的方向。性能优良的划分算法能够在充分考虑系统设计需求的前提下，给设计者提供性能优良的划分方案，为下一步详细设计打下良好的基础。而性能较麓的划分算法垮会导致设诗周赣跌富，扶嚣影嗡整个设计诗划，惩长设诗周鬻，莲至导致整个设计的失效。因此，随着软硬件协同设汁技术的不断发展，软硬件划分问题也成为众多研究机构的研究热点，并提出和发展了多种软硬件划分方法。本章从软硬件划分涉及的几个主要方蕊分别分析了软硬件划分鲍各项技术。2 ，1 软硬件划分涉及的主臻方面由予数字产晶或设备鳇结孛毒多元纯，设诗终窳差异穰大，对软硬俘划分获疆究往往爱依据具体静应用背景避行。但是无论采用哪种方法，面向何种应用在研究软硬件划分方法时一般都涉及列以下几个主瑟问题。2 。 ， 系统建模建立系统描述是软硬件划分过程中重要的步。面向不同的应用特征，往往采用不弼躲系统模登，瑟不圈斡系统模型畜时瞧会遣戒划分敕度静区裂。溺筵，系统建横成为软硬件划分其它问题的基础。2 ， 。2 。目标体系缩构目标体系结构是精系统中各个模块以及各个模块之间的通信在硬件层次上的实现方式。软硬件划分算法只有在明确了系缆的目标结构的前提下，才能将系统模型缀攥该傣系结构划分藏软馋秘分强硬謦部分。逶霉将嚣器薄系缝擒分为多处理器结构和单处理器结构两类。2 3 优化目标优化目标即软磺件划分算法使系统设计达列的最佳状态，同时也是系统需箍千蕊模型翁0 一l 撬麓较疆转鞠努方法秘臻竞求的体现。对于不同的鹿用背景，划分冀法的优化目标也不尽相同。选择恰当的捷讫嚣椽缝更好教髂瑷没诗蠹数设谤霭求帮牲筑终索。2 1 4 软硬件划分算法软骥传巅分葬法辩确定采熏嚣释算法方链在怒努方案窆阉中逡取合适鹃麓分方案，取得较好的划分效果。软硬件划分算法的优劣直接影响最终的划分效果，因此算法的设计成为划分的关键，也是人们研究的重点。目前赎型的软硬件划分冀法毒毽逡性算法、送 弋冀法、改遴迭伐算法、綮瑟援索算法、攥聿娃退炎冀法良及遗传算法等。2 1 。5 性缝分析性熊分析问题是软硬件划分的个扩展问题，阕为软硬件划分的性能好坏是通过对设计系统性能进行分析评价柬体现的。如聚系统性能无法满足约束要求，鹫表餐瑕蹇可爱存奁越分主兹不舍遐，羲嚣要重瑟遽 亍软硬件嘲分。嚣笾，蓉绕的性能分析成为判断划分优劣的有力方式。2 2 软硬 牛划分技术分析对软硬件划分技术的广泛研究使这一领域的备项技术迅速发展，研究翥提出了众多相关理论和技术，这里主蒙从系统建模工县、划分算法和性能评价几个方瑟对各秘莛墅菝拳避 亍奔绥。2 2 1 ，典型系统建模工具嚣弱，在较矮 孛麓分中逶常采弼数撵流延邂鞠或数据瀛瀚、p e 订i 两、强务图、协同设计模型c d m 来对系统进行建模，它们的定义和特征分别如下。2 2 ，1 。 ，数据渡处蘧甄数据流处理网( d a t a n o w p m c e s s n e t w o r k ) 用个有向图来描述系统。艇顶点表示计箨，有向弧表示数据顺序( 弥为流) 。系统的行为用顶点的激活序列表示，在镶一个顼点激溪辩，蒋撬雩亍定季亍为，产生薪懿数据浚舞。冀通蔼掇潮是无底f i f o 队列( u n b o t t o m e df i f oq u e u e ) ，采用的是阻塞读的方式，即每个顶纂予e 隧穰垂翡0 一l 艘菇较硬辞翻转方法羲骚究点激活前所有必需的数据都应就绪。数据流处理网中并没有携带显式的时间信塞，奁弧褥一令数据浚处理鼹聪鼹瀵麸豹只是数攥产生聂游麓熬先磊关系。在数掘流处理网中，每一个顶点按激滔规则决定在接收到哪些输入的情况下进行激活以及采用何种操作，但数据流处理网不能描述在某个状态下，不同的输，久与输出的对应关系( 3 4 f 3 郁。2 2 1 2 p e t r i n e tp e 撕n o t 可势为经壤憝p e 壤n 姓与p e 瓤n e t 懿交释。经典懿p e t r in e t 由疑静基本要索组成：库所( p j a c e ) ，变迂( f m s 砸o n ) 、输入函数( i n p u tm n c t i o n 、输出函数( o u t d u t 向n c t i o n ) 。输入函数、输出函数将变迁映射到库所。用p e t “n e t可以非常炎活方便地攒述系统的并发、异步特征。其并发性表现在变迁可以独立鲢发，只器萁输入痒疆褥到激活；辩步往表囊在蚤个变迁豹簸发并没有内在豹霸于钟同步机制。p e 砸n e t 的变种有着色p e t “n e t 、定时p e 埘n e c 、谓词p e t r in e t 、p r e n 、h p n 等 3 7 】 3 8 】，其中h p n 具有层次化的特点。2 2 3 袁限状态税有限状态机( f i n i t es t a t em a c h i n e ，f s m ) 办可分为经典的f s m 和变种f s m 。经葵熬f s 麓由获态爨、输入集、羧窭集、输窭骚数、获态转移涵鼗等五个熬分组成。奠中输出函数将输入集与状态集映射到输出集，状态转移函数将输入熊与状态集映射到下一个状态，因此，有限状态机是熊够描述条件输入输出关系的。南睦惑瓤豹优点是状态弱要、可决定蠖篦较妊，薅要多少内移、嚣么嚣候谬壤、性能酶渤态特征理论上都可以得到证实。僵状态机也有一个致命的缺点欹态爆炸问题；即状态组合随系统的复杂性增加呈指数增长。对于复杂的嵌入式系统尤其是彀古有著发行为与内存系统的嵌入式系统，要把每一个状态都清楚地撼述篷来不避 孛容易的攀。在p t o l e m y 中采用层次化的f s m 与其它模型如数据流圈、离散事件模型等嵌套在起。在p o l i s 中则采用了抽象化的全局异步局部同步( g a l s ：g l o b a la s y 珏e 糖o n o u s o c a ls 辨e h 羚n o u s ) 戆熬象蛰嗣设诗蠢疆获态撬( a c 碣m ：硒s r a c tc o d e s i g nf i n i t e s t 砒em a c h i n e ) ，其中采用了f l f o 通信通道将释个有限状态机连接起来，通过对有限状态机及f i f o 通信通道的细化完成系统的设计【3 4 】。9基予c 蕊模型鹣铲l 撬翅软硬搏到分方法豹研究2 2 1 4 1 壬务图任务图( 蕊kg r a p h ) 是一种以缩点代表任务，以边代表任务闽数据通信的有向图。任务图已用于c a s p e r 、c o s y n 等著名的软硬件协同综合系统俐【2 3 j 。任努图具有层次傀的特点，可以鼹于屡次他的设诗。可以将一个任务分瓣戏多令 壬务来完成。在文献【4 锈中，s 艳曲a n 疆a 垃s e 在任务强中臻艇了南戎、如溆、n o n n “三种情况，增强了任务图的描述能力，但怒没有状态的定义，不具备条件输入输出的描述能力。22 1 s + c d m 模型德豳d a r r n s t a d t 工业大学v l s l 与系统实验爨提出了系统建模工具c d m( c o d e s i 勰麓o d e l ) 翻，荠盈已经应麓予祝器久、m p 3 撂旅器警多令系统敬设许；c d m 支持循环操作结构的描述，能用于复杂的数字系统建模，它采用了内核与外壳相分离的处理结构，能较好地支持部件的可藏用化设计。它通过定义条件输入输出关系，怼系绫懿有效捩态遵露 鑫诗。莫遭僖数箨隧令矮袭示热薅煮笺溪台复杂系统润高层设计。2 2 2 典型软硬件划分算法软硬件划分所要解决的问题是找出一种绍点的分配方式使系统在满足约束的条件下性能最优。这是一个n p - h a r d 问题。而如何在大量划分方案中快速和有效连攫索戮溺霆翳全麓疆德簿或遥织矮钱簿是装诗鲻分算法敬瓣麓，邀是宅必须考虑的问题。自1 9 9 3 年e m s t 等人把模拟退火辣法用于硬软件划分1 1 4 】并用于c o s y m a 系统以来，人们在这个阍熬上已经散了大量涎工 乍，取愿了许多成粱。基蘸，在划分润题上采用的方法鹅缡起来主要有：( 1 ) 整黧线性藏翊l l p ( i n t e g e rl i n e a rp r o g r a n u n i n g ) 混合熬型线性规划m i l p ( m i x e di n t e g e rl i n e a rp r o g r 黜i n g ) 方法【4 1 1 ；( 2 ) 启发式算法，如模拟退火簿法1 4 2 j 、遗传簿法 6 0 】、禁戆搜索 6 l 】；( 3 )其毽一骛方法，餐魏，基予簇夔算浚嘲、动态鬣翻法f 4 “、& e m i i 篷h a l i n 算法、g c l m b s i q 创算法等。下面就几种典型软硬件划分算法避行逐一分析比较，其中线性规划和遗传算法擦是本文提出的软襞传划分算法戆基整思怒，壤越对这薅耪舞法送行详述。1 0基于c 删模型的0 1 规划软硬件划分方法的研究2 2 2 1 线性规划在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的个重要分支数学规划，而线性规划( l i n e a rp r o 盯a m m i n g 简记l p ) 则是数学规划的一个重要分支。自从1 9 4 7年g b d a n 乜i g 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一| 5 。线性规划所能解决的问题通常包含下列特性：1 ) 其目的为将某个相关变量( d e p e n d e n tv a r i a b l e ) 极大化或极小化，该相关变量可以由线性的目标函数( o b i e c t i v e 缸1 c t i o n ) 所定义。2 ) 目标函数中含有许多变量，这些变量的数值描述不同的决策可能性，通常代表达到目标所必须使用的项目。3 ) 有许多条件的限制，其限制内容可以用线性的等式或不等式来描述。线性规划是数学规划方法中发展的非常完整、使用非常广泛的一种方法。使用线性规划可以保证在固定的步骤之内，获得所有可能解中的最佳解。如果用图形来分析适合线性规划分析的系统，则将定义一个凸空间( c o n v c xs p a c e ) ，在凸空间内部的任两点连线，必仍属于该凸空间的内部范围。细节说明如下：系统中n 个变量定义了一个n 维向量空间，成为问题空间。每一个约束条件是一个n - l 维的次空间，将问题空间分割为两半，一半包含所有符合该条件的解，另一半为不符合该条件的解。不论约束与变量的数目为多少，符合所有约束的解所形成的集合必然是一个凸空间。图2 1 为二维空幅3 中的情况。、图2 1线性规划问题圈解豢予c 掰攘囊酶8 一l 瓣鑫| 软硬辟糍势方法静鹾窕图2 1 中每一条实心直线将平面分割为两侧，其中一侧为符台约束的部分，勇弱慰不簿含终寒。每逢麴一拿终寒疑筹毙在联蠢懿空藤孬魏一刀，薏不餐含条件豹部分丢弃，所剩余的部分必定仍然是凸空间。虚线代表蹦标多项式，可以看作是一条方向固定但位霞可以平行移动的直线，若移到a 位鬻，则与凸多边形耀交于a 点，a 点就是浚线性翘划系绞中艇有符台条传斡鼹中，其嚣标多项式的对应静檄大值，丽b 煮刘是极小值。褥变量的数秘增秘至三个躐更多个，其掰定义的空间为一个三维或多维空间，但蕻关系不变，仍是试图寻找个方向固定但可平行移动的次空间与一个定义的所有可能解的凸空间的交叉点，试隰找出极小篷或掇大镶。整数线性规划( i n t e g c r1 i n e a rp r 0 舒a 1 1 1 m i n g ，i l p ) 通常简称整数规划，它比普通的线性规划( 即无熬数约束的线性规划) 无论在理论上还怒实践中都要难得多。挺对予整数残鲻，蘩述线瞧线鲻可拣炎蛰逶线选规划( 艇巍蕊科l n e a fp r o g r a m m i n g ) ，整数舰鲻是组合问题( c o m b i n a t o r i 越p r o b i e m s ) ，两者都属予所谓n p h a r d 问题，即未找到多项式时间算法的问题，并且人们相信对此类问题根本不存在多项式时间算法，计算量将随问题规模( 变量数、约震数等) 按指数增长，整数线淫趣麓豹滋雉在予当同熬豹维数( 交豢与约束静个数) 增热 雪，计算量将爆炸性( 即按指数规律) 增加。对于i l p 问题常用求解方法有：穷举法、舍入凑整法、分支定界法、割平面法簿。软磺侮分趣题翁褥短与线穗篾戴瘊2 睡凌戆凌蔻嚣骜毽援为稳囊薹，嚣鼗裁用线性规划来实现软硬件划分是合联的，但是单纯利用线性规划来寻优时，随着系统规模的增大，算法的爆炸式耗时是不能接受的。2 2 。2 。2 禁惹算法禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 的思想最早由g l o v e r ( 1 9 8 6 )提出，它怒对届部邻域搜索鹣一耱扩袋，是一毒孛垒鼹逐步寻爨冀法，是对人类智力过程的一车中模拟，蔑人工智自在缀合优化算法中的一个成功应用。禁忌搜索算法的特点怒采用了禁总技术，所谓禁忌就是禁止薰复前面的工作。它通过引入一个灵活驰存储结构和襁成的禁忌准则来避免迂回搜索，并通过藐视准则来赦兔一些疆禁慧瓣饶襄获态，避蕊保证多群镬：懿有效穆索叛最终实魂全两饶纯。简单t s 算法的基本思想是：给窳一个当前解( 初始解) 和一种邻域，然后在当前的邻域中确定若干候选解；若最佳候选解辩应的目标值优于“b e s ts o 妇”状态，戴忽凌葵禁忌黪魏，羁萁替代警藩瑟瑟e 鞋s o 纽”状态，莠海据应麓对象加入禁忌表，同时修淑禁忌表中备对象的任期；藩不存在上述候选解，则选择旗于e 蹦穰垒静静一l 撬凳j 软硬箨划分方法韵研究在候选解神选择非禁憨的最佳状态为新的当前解，而无视它与当前解的优苎；，同霹褥稳应熬对象怒入蘩忌袁，劳修浚蘩瑟表中套对象兹 王麓；弼瓮重复上述迭代搜索过稳，直至满足停止准则。很鼹然，邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。2 2 2 3 遗传算法遗传算法是根据达尔文的生物进化原理，对生物界的自然选择和自然遗传机制豹援羧簿法，基 ；孑愁成为一静羹簧戆饶纯诗嚣方法。它与终绞蕊隧梯度为蒺醚的优化算法相比，不需要往用梯发，计算过程对函数性态的依赖性较小，熟有适应范围，“、鲁棒性好、适合于并行计算等优点。把计算机科学与进化论撮合到一块的最初尝试是在弱年代末6 0 年代甥。但由于过分依赖变异( m u t 越i o n ) 旋不是配对( m 雒i n g ) 来产生额的基因，所以收效甚徽。这种摸孝l i 自然选择和遗传祝瓤的寻优技术，它是6 0 年代中期美国密执安大学j h o l l a n d 教授首先提出并随后主要出他和他的一批学生靛展起来的1 4 ”。他的主要功续在子开发了一种既可描述交换又霹掇述变吴赘鳊璃技拳，这是簸晕懿邃传算法，文献中嚣在怒宅豫失繁攀邃铸算法( s i m p l eg e n e t i ca l g o r i t h m s ，s g a ) 。简单遗传算法大体上是在遗传算法的三个基本操作机制的日l 导下进行的。要褥到闫瑟盼舞，黄先遴嚣初戆佬操 乍，露逶过陵糖编码捉裁产生一令秘器或葶枣族，其中每个染色体代袭一个可行解。在每一代进化过程中，道过复翩操作，代表较好的可行解的染色体将被挑选出来，重新组合以产生性能不断提高的后代。种群的自然进化持续到预先殴定的进化代数达到了，或者一个代淡问题最优或接近交往释麴合逶染色体羧蜀了，对算法结束。遗诧过程中揉终帮参数选取不洽滏会导致遗传算法产生早熟收敛现象。近几年