（精密仪器及机械专业论文）基于平台的SoC系统综合技术研究(精密仪器及机械专业优秀论文).pdf

摘要随着v l s i 技术的进步和电路复杂度的不断提高，基于平台的设计技术逐渐成为国际学术界的研究热点之一。在传统的基于平台的s o c 设计中，设计师首先要根据经验选择合适的平台，然后在选定的平台上增加或者删减功能模块，从而实现一个新的设计。这种设计方法过多地依靠人的设计经验，并不适合于设计实现的自动化。本文以系统综合自动化为目标，展开研究基于平台的s o c系统综合技术。并把研究的重点放在系统综合的规范和系统综合的优化技术上。在基于平台的s o c 系统综合技术研究中，本文采用遗传算法作为优化系统综合过程的数学工具，并在以下几个方面为基于平台的s o c 系统综合自动化及其优化技术做了一些基础性研究工作。1 ) 为了克服基本遗传算法局部搜索能力不足的缺点，提出了基于两级记忆模型的混合遗传算法，然后在此基础上做了进一步改进，提出了基于两级记忆模型的爬山混合遗传算法；2 ) 为了克服基本遗传算法容易早熟的缺点，提出了使用复合排序选择算子( 包括线性的和指数的) 的方法。这种方法通过考量个体相似度来降低相似个体被同时选中并参与遗传操作的概率。根据选择算子中的参数是否与时间相关，我们将之分为静态复合排序和动态复合排序两种选择算子。本文分析了采用静态复合排序选择算子时遗传算法的收敛性，也论证了采用动态复合排序选择算子时遗传算法的弱遍历性；3 ) 在基于平台的s o c 设计方法中，本文研究了系统综合技术的规范问题。在通用问题规范的基础上，提出了基于平台的s o c 设计的系统综合规范；4 ) 合理的库结构是系统综合技术自动化的基础。本文以尽量摆脱人力介入，更多实现综合自动化为目的，提出了一种新的库结构：平台i p 混合库；5 ) 减少无效编码的数量是所有自动综合技术必须考虑的重要问题。本文针对平台i p 混合库的特点，为系统综合提出了一个两级映射过程模型，以尽量减少综合自动化过程中无效码的数量：6 ) 将上述各种经过改造的遗传算法引入系统综台的优化过程，并通过实验比较了各种遗传算法在基于平台的系统综合中对优化的贡献。关键词；系统综合，遗传算法，两级记忆模型，复合排序选择算子，两级映射模型，分配，绑定t h er e s e a r c ho np l a t f o r m - b a s e ds o cs y s t e ms y n t h e s i sa b s t r a c ti no r d e rt oc o p ew i t ht h ei n c r e a s i n gc o m p l e x i t yo fi n t e g r a t ec i r c u i t sa n dt h ep r e s s u r eo ft i m e - t o m a r k e t ，t h ep l a t f o r m b a s e dd e s i g nm e t h o d o l o g yw h i c he m p h a s i z e sp l a t f o r ml e v e lr e u s eb e c o m e sam a j o rf o c u s b u tt h et r a d i t i o n a lp l a t f o r m b a s e ds o cd e s i g nf l o wi st o oe x p e r i m e n t a lt oa d o p te n o u g ha u t o m a t i ct e c h n i q u e s ，i nt r a d i t i o n a ld e s i g nf l o w ，d e s i g n e rc h o o s e sp l a t f o r mb ye x p e r i e n c ef i r s t l y ，t h e na d d so rr e m o v e si p st og e tn e ws o ci m p l e m e n t a t i o nf i n a l l y ，t h et w os t a g e sc a nn o tb ef u l f i l l e da u t o m a t i c a l l y t h er e s e a r c hi nt h i sd i s s e r t a t i o nf o c u s e so nt h ea u t o m a t i cp s s s ( p l a t f o r m - b a s e ds o cs y s t e ms y n t h e s i s ) t e c h n i q u e si n c l u d i n gs p e c i f i c a t i o na n do p t i m i z a t i o na l g o r i t h m t h em a i no r i g i n a lw o r k si nt h i st h e s i sa r ef o l l o w i n g 1 t h ep r o p o s e dp s s st e c h n i q u e si nt h i st h e s i sc a nb ei m p l e m e n t e da u t o m a t i c a l l y 2 t h et w o - s t a g em a p p i n gm o d e lc a na v o i dal o to fi n v a l i dc o d e sd u r i n gt h es y s t e ms y n t h e s i s 3 t os p e e du pt h ec o n v e r g e n c eo ft h eg a ，i ti sp r e s e n t e du s i n gt w o - s t a g em e m o r ym o d e lt om o d i f yt h em u t a t i o no p e r a t o r ，a n dat w o - s t a g em e m o r ym o d e lb a s e dh i i ic l i m b i n gg e n e t i ca l g o r i t h mi sp r o p o s e d t h et w om e t h o d sa r ep r o v e dv a l i dd u r i n gt h ee x p e r i e n c e 4 t h ep l a g u i n gp r e m a t u r ec o n v e r g e n c ep r o b l e mh a sa l w a y sb e e nt h eh i n d r a n c ef o rg a st ob ea p p l i e di nw i d eo p t i m i z a t i o np r o b l e m s t h ep a s tr e s e a r c hw o r k sf o c u so nt h ec r o s s o v e ro p e r a t o ra n dt h em u t a t i o no p e r a t o ro ft h eg a sa n di g n o r et h ei n f l u e n c eo ft h es e l e c t i o no p e r a t o r t h i st h e s i sp r o p o s e san o v e ls e l e c t i o no p e r a t o r ，m o d i f i e dr a n k i n gs e l e c t i o no p e r a t o r ( m r s ) m r si n c l u d e st h es t a t i cl i n e a rr a n k i n gs e l e c t i o no p e r a t o r ( s - m r s ( l ) ) ，t h ed y n a m i cl i n e a rr a n k i n gs e l e c t i o no p e r a t o r ( d - m r s ( l ) ) ，t h es t a t i ce x p o n e n t i a lr a n k i n gs e l e c t i o no p e r a t o r ( s m r s ( e ) )a n dt h ed y n a m i ce x p o n e n t i a lr a n k i n gs e l e c t i o no p e r a t o r ( d - m r s ( e ) ) a tl a s t ，t h ep r o p o s e dp s s sa r ep r o v e dt ob ev a l i dt h r o u g ha ne x a m p l e t h ep r o p o s e dp s s st e c h n i q u ei st h ef i r s ta u t o m a t i ct e c h n i q u es u p p o r t i n gt h ep l a t f o r m - b a s e ds o cd e s i g n k e y w o r d s ：p s s s ，g a ，t w o s t a g em e m o r ym o d e l ，m o d i f i e dr a n k i n gs e l e c t i o no p e r a t o r ，t w o s t a g em a p p i n gm o d e l ，a l l o c a t i o n ，b i n d i n g图2 ，i图2 2图2 3图2 4图2 5图2 6图2 7图3 1图3 2图3 3图3 4图3 5图3 6图3 7图3 8图3 9图3 1 0图3 1 1圈3 1 2图3 1 3图3 1 4图3 1 5图4 1图4 2图4 3图4 4图4 5图4 6图4 7图4 ，8图4 9图4 1 0图4 1 i图4 1 2论文图清单f c 设计方法学的演化图硬件部分结构示意图一软件部分示意图普林斯顿提出的基于平台的设计流程侧重电路重用基于平台的设计流程一基于平台设计流程遗传算法流程图遗忘曲线1 6 2 l 多存储模型示意图1 62 l 两级记忆模型两级记忆模型伪码实现t m h 的流程图t h m 与s g a 运行结果对比t m h h 流程图t m h h 、t m h 及基本遗传算法运行结果对比图比例选择伪码联赛选择伪码槛式选择伪码线性排序选择伪码m r s ( l ) 伪码重新排序算法采用不同选择算子执行结果直方图对比简单问题图规范示意简单结构图示意简单层次化示意图简单层次化结构图示意基于平台的结构图示意系统综合流程分配映射边示意单级映射模型两个基于m + c o l t e 的平台及【p 库单元示意图一p s s s 过程模型基于t m h h 算法的p s s s 整体优化结构图j-墙口=砚鸵m巧勰如儿靳”朋m岗mm用川曩_ _ 7_ 棚黑懑薹叠蔫撼菘燕麓爱一p s s s 整体伪码需修正分配修正分配编码伪码可行绑定伪码绑定生成伪码分配更新伪码一一多解决方案判定一交叉伪码实现一变异伪码实现一寻找需变异基因位伪码实现变异基因位对应任务节点，一寻找替代节点变异的伪码实现两种爬山关系舀一爬山法伪码一调度伪码一虚拟任务图一采用不同策略的系统综合结果直方图对比( 5 0 0 周期)采用不同策略的系统综合结果直方图对比( 8 0 0 周期)羔冀黑焉黑篇黑基黑m盯博旧加弛幻“幻舶刀m埘珈乱乱乱ttt 乱t乱乱玑4444444图图图图图图图图图图图图图图图图图图表3 1表3 2表3 3表3 4表3 5表3 6表4 l表4 2表4 3论文表清单搜索尺寸为3 的重新排序过程搜索尺寸为2 的重新排序过程多组相似个体重新排序( 搜索尺寸为3 )多组相似个体重新排序( 搜索尺寸为2 )插入式重新排序不同选择算子搜索到最优解次数虚拟库单元成本、功耗指标采用不同策略的系统综合结果执行8 0 0 个周期的效果对比拍钉 蛇卯鲫独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得盒起王些盍堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文储龆枷皓签字吼细辞纱月加日学位论文版权使用授权书本学位论文作者完全了解盒壁王些太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒壁王些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位论文作者签名拗弘签字日期：砌务驴月如日学位论文作者毕业去向工作单位通讯地址导师签名：知沙签字日期j 一。侔0 月。日电话邮编致谢首先，我要衷心地感谢我的导师高明伦教授，在我六年半的硕士博士求学期间，高老师给了我极大的支持和帮助。高老师渊博的知识、严谨的治学态度激励着我不断的探索：高老师宽广坦荡的胸怀、高风亮节的人格、亦师亦友的长者风范感染着我。其次，感谢高老师的夫人潘建宏教授，正是由于高老师与潘老师在生活上的关怀与呵护才使得我能心无旁骛地完成学习研究。感谢合肥工业大学微电子设计研究所的张多利老师、王锐老师、尹勇生、宋宇鲲、杜高明、胡德俊、张俊、杨明、许海辉、沈健生以及已经毕业的张珍硕士在研究中的帮助与建议。感谢邓红辉老师、贾靖华老师、林微老师、胡永华老师、张溯老师、刘聪老师在日常生活中的帮助。感谢南京大学微电子设计研究所的李丽老师、何书专老师的支持与帮助。感谢合肥工业大学与南京大学微电子设计研究所所有同事们的帮助。感谢我的父母与岳父母在我生活中无微不至的照顾。尤其感谢我的爱人时娜娜女士的理解、关心与支持。谨以此文献给所有关心、支持与帮助过我的人。程作仁2 0 0 6 年2 月1 0 日1 1序言第一章概述由于基于平台的设计技术采用了比i p ( i n t e l l e c t u a lp r o p e r t y ) 更大的重用单元一一平台( p l a t f o r m ) ，使设计效率的提高取得了更显著的效果，受到了众多研究机构和企业的关注。基于平台的设计方法的基础重用单元是平台，因而针对平台的系统综合技术就显得非常必要。本文以基于平台的s o c 的系统综合( p l a t f o r m b a s e ds o cs y s t e m 1 e v e ls y n t h e s i s ，p s s s ) 为切入点，着重研究了p s s s 的优化问题。在科学研究和工程实践中，许多问题最终都可以归结为求最优解的问题，特别是复杂优化问题求解方法的研究，已经成为众多学科共同关注的对象。优化问题受到广泛重视的原因不仅在于其内在的复杂性有着重要的理论价值，还在于它在现实生活中有着广泛的应用。在优化问题研究中，本文以遗传算法为主要数学工具和研究对象，针对遗传算法易“早熟”和“局部搜索能力不足”的缺陷提出了两种解决方案：复合线性排序选择算子和基于两级记忆模型的混合遗传算法，并将这两种方案应用到p s s s 中。本文提出的两种解决方案并不仅仅适用于p s s s 。同时由于他们是对遗传算法自身的改进，也可以在不同的优化领域中得到应用。1 2论文结构本文的研究内容包括两个部分：遗传算法研究和p s s s 研究。遗传算法的研究成果是解决p s s s 优化问题的数学基础。第二章是论文的相关技术背景介绍，分为平台技术介绍和遗传算法介绍两部分。前者介绍了基于平台设计的相关概念及基于平台的集成电路设计流程，部分修改了传统流程，并提出了更适合予设计自动化的基于平台的设计流程。后者介绍了遗传算法的基本概念、流程、优点啦及研究现状。第三章研究遗传算法，针对基本遗传算法局部搜索能力不足和易“早熟”两个问题改进遗传算法。针对基本遗传算法局部搜索能力不足的缺点，提出了基于两级记忆模型的混合遗传算法( t w o - s t a g em e m o r y m o d e l b a s e dh y b r i d g e n e t i c a l g o r i t h m 。t m h ) 。该算法能有效她从执行过的种群中提取信息以加速遗传算法的收敛速2合肥工业大学博士学位论文度。同时，针对t m h 只对变异算子起作用的特点，还实现了基于两级记忆模型的爬山混合遗传算法( t w o s t a g em e m o r y m o d e l b a s e dh i l l c l i m b i n gh y b r i d g e n e t i c a l g o r i t h m ，t m h h ) ，并通过试验对这两种算法的效果进行了验证。试验结果显示，t m h h 的收敛效果优于t m h ，而后者的效果又优于基本遗传算法。针对基本遗传算法易“早熟”的缺点，提出了复合排序选择算子( m o d i f i e dr a n k i n gs e l e c t i o no p e r a t o r , m r s ) ，其中包括线性m r s ( m r s ( l i n e a r ) ，m r s ( l ) )和指数m r s ( m r s ( e x p o n e n t i a l ) ，m r s ( e ) ) 。分析了该算子对“早熟”现象的影响，并通过实验证明了该算子的有效性。同时分析证明了采用该算子的遗传算法的收敛性与基本遗传算法相似，即非最优保留地采用静态m r s ( s t a t i c m r s ，s - m r s ) 的遗传算法在最低选中概率大于零的情况下也是不收敛的，而采用最优保留的算法在最低选中概率大于零的情况下( 采用s - m r s ( e ) 没有该条件限制) 是收敛的。同时还证明了采用动态m r s ( d y n a m i c m r s ，d m r s ) 遗传算法在最低选中概率大于零的情况下( 采用d m r s ( e ) 没有该条件限制) 的弱遍历性。第四章是对p s s s 的研究。本章将遗传算法的上述研究成果引入多目标优化的p s s s 研究中，并在新算法的基础上研究设计实现方法。第四章还详细定义了系统综合实现过程并提出了两级映射的p s s s 过程模型。第四章的开始部分介绍了系统综合的研究现状和主要研究内容，并为p s s s提出了一种以通用问题规范( g e n e r a lp r o b l e ms p e c i f i c a t i o n ，g p s ) 为基础的p s s s 问题规范。第五章总结了论文的研究内容并展望了未来的研究方向。1 3论文创新点本文所取得的创新点包括：提出了基于两级记忆模型的混合遗传算法( t m h ) ；提出了基于两级记忆模型的爬山混合遗传算法( t m h h ) ；提出了动静态复合线性( 指数) 排序选择算子( s - m r s ( l ) ，s - m r s ( e )d - m r s ( l ) ，d - m r s ( e ) ) ，并对采用m r s 算子的遗传算法的收敛性进行了分析：本文以尽量摆脱人力介入，更多实现综合自动化为目的，提出了一种新的库结构：平台i p 混合库：在通用问题规范的基础上提出了p s s s 的问题规范；提出了p s s s 的两级映射模型；第一章概述实现了p s s s 算法并给出了实验。1 4课题来源本论文的研究内容来源于：国家自然科学基金资助项目“基于平台的s o c 设计方法及其关键技术研究”( 项目编号：6 0 3 7 3 0 7 6 )国家教育部项目“s o c 软硬件集成协同设计和验证优化理论和方法研究，( 项目编号：教技司【2 0 0 1 】2 1 5 )第二章相关技术背景摘要：本章介绍基于平台的s o c 设计技术和遗传算法的相关技术背号，包括现代设计方法学的演变、基于平台设计技术的相关概念和设计流程；修改传统设计流程，以期达到更高效率的设计自动化的目的；介绍遗传算法的基本概念、流程，遗传算法的优点以及研究现状。2 1 基于平台设计( p l a t f o r m - b a s e dd e s i g n ，p b d )2 1 。1现代设计方法学演变随着电路复杂度的不断提高，电路设计工作越来越依赖于设计方法学的进步。进入s o c 时代以后，设计方法学对设计效率的影响更发展到空前的程度。为满足不同时期的设计复杂度的需求，先后产生了三种主要的设计方法：时序驱动设计、基于模块的设计和基于平台的设计。图2 1 是设计方法学的演化图。图2 1i c 设计方法学的演化圈2 1 1 1 时序驱动的设计方法( t d d ，t i m e d r i v e n d e s i g n )早期的设计是面积驱动的设计，其优化目标是逻辑( 面积) 最小化。由于!合肥工业大学博士学位论文面积驱动的设计方法使用统计平均的线负载模型，导致深亚微米设计中的时序设计不收敛，从而推动了时序驱动设计方法的诞生。时序驱动的核心是版图规划和互连线延迟模型，关键的设计工具是版图规划工具和时序分析工具。2 1 1 2 基于功能块的设计方法( b b d ，b l o c k - b a s e d d e s i g n )随着制造技术的进一步提高，系统的设计规模越来越大，t t m( t i m e t o m a r k e t ) 压力也随之增加。重用技术、基于模块的设计方法就成为必然。现在，重用技术和基于模块的设计方法更进一步发展成为专业化分工的产业格局。i p ( i n t e l l e c t u a lp r o p e r t y ) 设计业与系统集成业已经发展成为两个基本独立的产业。制造技术的提高一方面造就了新一轮的产业分工，另一方面削弱了前端和后端的差别。在深亚微米技术中，连线延迟在系统总延迟中所占的比例越来越大。由于连线产生于布局布线之后，因此延迟信息的不可预知性制约着前端设计的各个环节。早期的前端一后端不断循环的设计方法常常遇到不收敛的问题。c a d e n c e 公司为此提出了物理综合的概念，从而打破了传统的前端、后端之间的界限。门级综合将带有连线延迟信息，而连线延迟信息是在前端的“预布局”中获得的。物理因素考虑的提前对工具软件提出了新的要求。在“前端”的各个设计环节中都需要“预布局”功能，以尽早得到连线延迟信息。2 1 1 3 基于平台设计方法为了应对电路复杂度逐步提高的趋势，b b d 开始主动地采用基于功能模块的重用技术，但是其重用单元通常是未标准化的，为了能更好的发挥重用技术的优点，出现了采用平台重用和i p 重用技术的p b d 技术f 2 】【”。平台是比i p 规模更大的重用单元。2 。1 1 3 1平台的定义在很多领域都有关于平台的定义，文献【2 儿5 总结了基于平台设计的平台定义，其采用的平台的定义起源于计算机平台，包括硬件和软件两个部分，是一个可重用、可扩展的基本系统。平台有以下几个方面的属性：( 1 )平台是一个基本系统( s y s t e mc o r e ) ：它是比嵌入式c p uc o r e高一个层次的可重用结构，是系统库的基本元件。( 2 )可重用性：这是平台的基本属性。只有可重用，才能提高开发系列产品的效率；同时，只有可重用，才能降低每个产品的开发成第二章相关技术背景!本。( 3 )可扩展性：软件和硬件的可扩展功能。可扩展功能是系统平台的基本属性，也是产业界为什么需要平台的根本原因。产业界只需在系统平台上做简单的软硬件扩充就可以设计出新产品，既节省了经费，又缩短了产品的面市时间。基于平台设计的目标是通过平台重用，并在平台的基础上增加或删减部分模块就设计出一个新的产品，以降低整体的设计周期，从而达到降低设计成本的目的。在基于平台的设计中，大规模地采用了层次化的技术。这一技术虽然会在面积和性能上产生一定的影响，但它可以大大地提高平台的使用便捷程度。2 1 1 3 2平台的结构从平台组成结构来看，平台可以分为硬件部分和软件部分。下图就是一个简单平台的硬件部分结构示意图：图2 2硬件部分结构示意图从上图可以看出，硬件部分就是满足一定约束的硬件集合。硬件电路的控制寄存器由软件操作，而应用软件直接操作硬件控制寄存器的可能性非常小，所以应用软件与硬件部分之问需要一个接口，这就是软件部分。软件部分通常由三部分组成：实时操作系统( r t o s ，r e a l t i m e o p e r a t i n g s y s t e m ) ，驱动程序( d e v i c e d r i v e r ) ，和网络间通讯子系统( n e t w o r kc o m m u n i c a t i o ns u b s y s t e m ) 。其中实时操作系统用来控制可编程的核与存储器子系统；驱动程序用来控制i o端口子系统；网络间通讯子系统用来控制网络互联。图2 3 是软件部分的结构示意图。合肥工业大学博士学位论文图23软件部分示意图基于平台的设计流程就是一个不断向下层映射的过程。而所谓映射就是依据设计约束在下一层的库中选择合适的库元件的过程。从理论上说，映射过程需要在e d a 工具软件的支持下进行，甚至可以完全由e d a 完成。2 1 1 3 3基于平台的设计流程基于平台的设计是基于更大规模重用单元的设计。目前比较典型的基于平台的设计流程是普林斯顿大学2 0 0 2 年提出的设计流程 6 1 与文献f 5 1 所提出的设计流程。图2 4 所示的普林斯顿模型采用了三个关键步骤取代了传统设计流程中的软，硬件划分环节，郎行为模型、结构模型和映射。行为模型( b e h a v i o r m o d e l i n g )是设计的关键环节，它根据设计任务书描述系统的功能及约束。行为模型的描述语言有多种，包括c c + + 、s d l 等。结构模型( a r c h i t e c l u r e m o d e l i n g ) 是选择i p 核和专用模块并将它们集成在一起的过程。在功能模型和结构模型两个环节中设计经验都被作为一种重要的设计输入来加以考虑。映射( m a p p i n g ) 则是将功能模型映射到结构模型之上，也就是把功能模型中描述的系统功能划分到结构模型的硬件和软件两部分中。映射的结果需要接受性能分析( p e r f o r m a n c ea n a l y s i s ) ，并决定是否有必要调整映射过程。接口细化环节( i n t e r f a c er e f i n e m e n t ) 为硬件和软件的所有组件选择出适当的通讯机制，这样接下来可分别进行软件、硬件细化以及协同验证( c o v e r i f i c a t i o n ) ，最后将两部分细化的结果集成在一起，布局布线后完成整个设计流程。攫誊蘩囊i 器慧基二蒸l畏l 豳第二章相关技术背景甲i 传巍设计试翟1 e 著、靶! 生盥5 基于平台的设计注靼9图2 4普林斯顿提出的基于平台的设计流程普林斯顿模型存在的不足是，它在本质上还是基于i p 重用的设计。如果将平台看作是一个系统，那么普林斯顿模型更像是平台的设计流程，而不是基于平台的设计流程。它总结了基于i p 设计的相关流程，却没有研究平台重用，并不能体现出平台重用的优势。为了弥补以上不足，文献【5 】提出一种新的基于平台的设计流程，增加了平台库的映射，通过更高层次的库的建立与映射扩充基于平台设计流程，其模型如图2 5 所示。图中的三个虚框分别界定了系统级设计的三个组成部分：设计、验证和支持( 建库) 。其中，椭圆形表示“设计环节”；梯形框表示“库”：方框表示“仿真环节”。这个模型与普林斯顿模型的核心不同点是平台映射与i p 映射的分离。旦合肥工业大学博士学位论文s p c m c 曲“t a p e - c a a tl麓缄设计圈2 5侧重电路重用基于平台的设计流程文献 5 】提出的基于平台的设计流程的最大贡献在于提出了平台是比i p 规模更大的重用单元的思想，并将平台映射与l p 映射分离。虽然该流程与产业应用有许多相似之处，但是其系统设计阶段的选择过多地掺入了人为因素，首先需要依据经验选定合适的平台，然后在选定平台的基础上增加删减模块以实现设计。该模型不适合设计自动化的实现。在文献【5 1 提出的基于平台的设计流程的基础上，本文将平台库与i p 库放在同一个层次，这样在选择库单元时可以直接得到解决方案。通过比较解决方案的优劣，得到满足需求的设计实现。本文提出的更符合设计自动化要求的基于平台的设计流程如图2 6 所示。第二章相关技术背景s p | 姐c “匝爿 釜嚣一向曩麓曩设计i 碡b 州l图2 6基于平台设计流程可以看出与普林斯顿设计流程相比，图2 6 流程中的库包括了平台库与l p库；与文献 5 】的设计流程相比，图2 6 流程中的平台库与i p 库并没有分层的概念。这种不分层的库单元映射，可以将系统功能映射成一系列潜在解的集合，通过在潜在解中寻找最优解，就可以实现满足功能要求和约束的准系统。如果将最优化算法引入这种寻找最优解的过程，则更易于实现设计自动化。从设计流程中可以看出，系统自动映射，即基于s o c 平台开展系统综合工作，是基于平台设计技术的主要研究内容之一。2 2遗传算法2 2 1 全局优化问题最优化( o p t i m i z a t i o n ) 一般指在某种情况下做出的最好决策，或者是从几个候选解中选出最优解【”。最优化问题可以描述为：“在给定的约束条件( c o n s t r a i n t ) 下，找出一个变量( v a r i a b l e ) ，使得目标函数( o b j e c t i v cf u n c t i o n )的值最优( 最大或者最小) 。”最优化问题可以用如下数学公式表述( 本文所有问题的描述与推导都以求最小值为例，最大值函数取反即为求最小值) ：m i n ( f ( x ) )r ，1 、r s”坚合肥工业大学博士学位论文其中m i n ( 厂( 工) ) 表示对目标函数，( 工) 求晟小值，x s 是必须满足的约束条件。所有满足约束条件的解称为可行解( f e a s i b l es o l u t i o n ) 。如果在所有解空间内，满足：f ( x ) s 厂( x ) ( x s ) ，则x 称为该问题的全局最优解。如果在一定的区间q 内，满足：f ( x ) ，( z ) ( x q ，q s ) ，则称x 为该问题的局部最优解。在科学研究和工程实践中，许多命题最终都可以归结为求最优解的问题特别是复杂优化问题求解方法的研究已经成为众多学科所共同关注的问题。传统的优化方法通常基于精确的数学模型进行计算，称为基于精确模型的方法或者确定方法( e x a c tm e t h o d ) 1 7 1 1 3 】 9 。】i l ”，其中应用广泛的是基于梯度的数值解法。这种方法可以求得问题的精确解，但是这种方法对问题的要求较高，如要求问题连续、可导等。当目标函数的维数较高时，优化的效果与实现的难度都很大。在工程实践中，很多问题都十分复杂，比如一般都有复杂的约束条件、高度非线性、多极值等，不适合采用传统的基于精确模型求解的方法。为了避免传统优化算法的缺点，各种启发性方法相继被提出。启发性方法通常是针对某一类问题自身可获得的知识( k n o w l e d g e ) 构建的方法。启发性方法的缺点是无法确保求得最优解，但在工程实践中，许多问题如果难以得到最优解，相对优的解( 可接受解) 也是符合要求的。因而，启发性方法在工程实践中得到了广泛的应用。常用的启发性算法包括：蒙特卡罗算法、爬山法、模拟退火算法、遗传算法、遗传编程、进化策略、进化编程和禁忌搜索算法等。蒙特卡罗算法 12 】1 1 3 】【14 】是简单的单点到单点的搜索，与爬山法【15 】【1 6 】十分相似，但不同之处在于蒙特卡罗算法新解的生成需要解分布函数的辅助，而爬山法需要邻域函数的辅助。这两种方法都不具有以往解的保留功能，因而都不容易跳出局部最优鳃。模拟退火算法【”】f 18 1 1 1 9 】【2 0 1 f 2 1 】是从物理退火过程中提取的一种全局优化算法，具有质量高、初值鲁棒性强、易实现等优点，但是该算法通常需要较高的初温，较低的降温速率，较低的中止温度以及在各温度下足够多的采样才能保证解的质量，因而算法优化往往需要很长的时间。禁忌搜索算法是对局部邻域搜索的扩展i 18 1 2 0 】【2 ”，通过设黄禁忌准则和赦免准则来避免迂回搜索。虽然这种算法能有效地避免局部最优解的生成，但是对邻域函数的设置有较高要求，并且禁忌列表的长度也常常成为解决问题时需要不断考虑的问题，因而其易用性受到一定的限制。遗传算法、遗传编程、进化策略及进化编程的思想都是源于生物进化，被统称为进化算法或者进化计算 18 】【2 0 】f 2 ”。遗传算法、进化策略和进化编程是独第二章相关技术背景堡立发展起来的；遗传编程是在遗传算法的基础上发展起来的，可以看作是遗传算法的一个特殊应用。现在研究人员已经开始将这四种方法融合起来，相互之问的界限已不十分明显。2 2 2 遗传算法简介二十世纪六十年代初，美国m i c h i g a n 大学的j h h o l l a n d 教授意识到生物进化过程中蕴含着朴素的优化思想。他借鉴达尔文的生物进化论和孟德尔的遗传定律的基本思想，在对它们进行提取、简化与抽象的基础上提出了第一个进化计算算法，即遗传算法 4 2 】。遗传算法也是进化算法中应用最为广泛的算法。达尔文认为生物的进化是适应环境的选择结果。生物的基本特征会遗传到后代，在自然的不断发展变化中，只有适应环境的生物才能生存。孟德尔提出了基因遗传的观点，认为在进化过程中，决定一种生物是否能适应环境，关键要看生物中是否存在适应环境的基因。基因本身具有遗传、变异等特点，而生物遗佳的是其父代个体的特征，经过环境的选择适应环境的基因得以保存。只有具有适应环境的基因的个体才能生存。由于遗传算法是一种参照进化遗传理论而建立起来的随机优化算法，因而其术语也采用与遗传进化理论相同的术语。表2 1 是生物学术语在遗传算法中的含义说明表：表2 1生物学术语在遗传算法中的含义i 生物学术语遗传算法f 个体对应问题的潜在解基因字符串的位基因型字符串的结构表现型字符串的含义种群由若干个体组成的解的集合选择在潜在解中选择参与遗传操作的个体 交叉字符串片断的交换i 变异字符位的改变1 4合肥工业大学博士学位论文2 2 2 1 遗传算法的基本流程遗传算法把问题的解表示成个体，通常用二进制编码的数据串来表示。首先给出一群个体，也就是假设解。个体可以是随机生成的，也可以是按照某种规则预先设置的。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异产生更适应环境的新一代“染色体”群。遗传算法的基本流程如图2 7 所示。从图2 7 可以看出，遗传算法实质上是一个“生成+ 检测”的迭代计算过程，通过引入适当的全局正反馈机制实现种群进化。遗传算法的种群进化特征是遗传算法与其它启发性算法( 如爬山法、蒙特卡罗算法、模拟退火算法等) 的标志性区别。幽2 7遗传算法流程图遗传算法的主要步骤包括：编码、种群初始化、适应度计算、选择、交叉、变异和终止判定六步。( 1 ) 编码个体编码的主要任务是建立解空间点与染色体空间点的一对应关系。遗传算法通常在染色体空间中进行操作。不同的编码方式决定了不同的遗传操作方式。通常编码需要满足完备性、健全性和非冗余性：完备性是指解空间中的第二章相关技术背景堕所有点都能表示为染色体空间中的点；健全性是指染色体空间中的所有点都能表示解空问中的点；非冗余性是指满足解空间到染色体空间的一一对应关系。根据编码方式的不同，遗传算法主要可分为二迸制型、序列型和浮点型三种，分别适用于不同类型的工程优化问题。( 2 ) 种群初始化与传统优化方法相比，遗传算法的个显著特点就是对种群的操作，所以在进化的开始必须进行种群初始化，以产生进化的初始种群。通常是随机构造初始种群，也可以在初始种群中放入一些具有特殊特征的个体，以加速算法向全局最优解的收敛。种群中个体的数目n 称为种群规模。( 3 ) 适应度计算计算个体的适应度值。计算适应度函数的值是为了评估个体优劣，遗传算法也正是因为有了量化的评估方式才实现了随机的有向搜索，而不再是简单无序的随机搜索。( 4 ) 选择遗传算法的选择操作与生物的自然选择机制相类似，体现了“适者生存”的生物进化机理，也就是说优良个体拥有较多机会被选中产生后代。选择操作也被称为再生( r e p r o d u c t j o n ) 。选择是在对个体的适应度函数的量化的基础上实现的。最常用的选择方式有赌轮选择、联赛选择、线性排序选择、指数排序选择、比例选择等。它们的基本原则都是高适应度的个体有较高的几率参与繁殖，而在适应度值对选择几率的影响上则各自有所不同。选择压( s e l e c t i v ep r e s s u r e ) 描述了选择机制挑选种群中不同个体做母体的概率大小的差异。选择压过大，会造成几个较好可行解( 不一定是近似全局最优解)迅速抢占了整个种群；选择压过小，则会使算法呈现出纯粹的随机徘徊行为。( 5 ) 交叉交叉模拟了自然界生物的交配，目的在于不同个体之间的基因交换。其实现方式是在选中的用于繁殖下一代的个体中，对两个不同个体相同位置的基因进行交换，从而产生新的个体。交叉算子通过实现遗传算法基因池中基因的重组，从而发现高阶、长距、高适应度的更加优良的模式，并增加、扩展算法的搜索空间，使算法搜索到全局最优值。常用的交叉算子包括单点交叉( s i n g l ep o i n tc r o s s o v e r ) 、多点交叉( m u l t i p l ep o i n tc r o s s o v e r ) 、均匀交叉( u n i f o r mc r o s s o v e r ) 、洗牌交叉( s h u f f l ec r o s s o v e r ) 及缩小代理交叉( c r o s s o v e rw i t hr e d u c e ds u r r o g a t e ) 等。单点交叉算子交叉前个体示意如下所示：工】2 o ，1 ，o ，o ，1 ) ；2 0 ，o ，1 ，1 ，1 )如果交叉点在第三点，则其交叉后新个体为：台肥工业大学博士学位论文五= c o ，1 ，1 ，1 ，1 )如= 0 ，o ，o ，o ，1 ) ；( 6 ) 变异变异模仿自然界生物进化过程中的基因变异，在选中的个体中对其基因按变异概率p m 执行取反操作。其目的是生成新的个体，增加种群的多样性。它对克服算法“早熟”、跳出局部最优点、提高全局收敛性能都有重要作用。( 6 ) 终止判定终止判定提供遗传算法的结束条件，通常在满足约束后或在一定的代数后结束当前程序。2 2 2 2 遗传算法的特点遗传算法的特点主要体现1 3 9 1 4 0 3 1 为智能性和本质并行性。智能性指遗传算法本身具有自组织、自适应和自学习的能力。在应用遗传算法求解问题时，确定了编码方案、适应度函数及遗传操作之后，遗传算法可以根据进化过程中逐步获得的信息自组织搜索，适应度较高的个体得到较高的生存机会。遗传算法的本质并行性表现在两个方面：一是遗传算法的内在并行性( i n h e r e n tp a r a l l e l i s m ) ，即遗传算法本身非常适合大规模并行化：二是遗传算法的内含并行性( i m p l i c i tp a r a l l e l i s m ) 。由于遗传算法采用种群的方式进行搜索，因而可以同时搜索多个解空间，并能相互交流信息，这种搜索方式使得它虽然每次执行的是与种群规模成比例的计算，而实质上已经进行了大约o ( n ) 次的有效搜索。2 2 2 3 遗传算法的优点与其它优化算法相比，遗传算法主要有以下几个优点：( 1 ) 搜索过程不直接作用在变量上而是在搜索集合上对编码的个体进行操作；( 2 ) 传统优化算法采用点到点的搜索方式，而遗传算法则采用种群到种群的搜索方式，因而较易于达到全局最优；( 3 ) 搜索不依赖于目标函数的梯度信息，只需提供能够评价个体相对优劣的量化指标( 适应度) 即可。因此，遗传算法的适用面更广，尤其适合于处理复杂的非线性问题，包括目标函数为高维、不可导、不连续或带有噪声的优化问题。第二章相关技术背景旦而传统优化方法则无法或至少难以解决这类问题；( 4 ) 进化过程具有有向随机性，这是遗传算法与穷举法的本质区别。同时，遗传算法的搜索结果具有非稳定性。与传统优化方法相比，优化效率也相对较低；( 5 ) 对给定问题可以产生许多潜在解，最终选择可以由使用者确定( 在某些特殊情况下，如多目标优化问题不止存在一个最优解，存在一组p a r e t o 最优解，这种遗传算法对于确认可接受解集而言是非常合适的) ：( 6 ) 简单通用，鲁棒性强。2 2 2 4 遗传算法的研究现状遗传算法由于其简单通用的特点，在很多问题上得到了很好的应用，但是在具体的应用中，其收敛性、收敛速度及“早熟”现象却一直困扰着研究人员。为了解决这些问题，研究人员从理论分析、算子选择、混合思想等多个方面对遗传算法进行了分析、研究和改进。( 1 ) 理论分析j h o l l a n d 在1 9 7 5 年”驯提出了关于s g a ( s i m p l eg e n e t i ca l g o r i t h m ) 的模式定理和内含并行性定理，它将遗传算法的运算过程理解为模式操作过程，并从模式运算的角度解释遗传算法的性能特点。模式定理揭示了具有低阶、短定义矩、平均适应度高于种群平均适应度的模式子代以指数级增长的规律。由于重组变异的作用并非低阶、优于平均的模式都是有效模式，但在一个规模为n 的种群中有o ( n 3 ) 个模式是有效的即每一代遗传算法处理n 个个体的同时却获得了对个模式的并行处理，并且无需额外的存储量，这一性质就被称之为内含并行性。从另一个角度来看，遗传算法在种群中搜索的过程可看作是隐含的对模式的抽样过程，然后通过遗传算子的作用将短的、低阶模式的信息