（计算机应用技术专业论文）带约束的vlsi布图规划算法的研究.pdf

中文摘要 随着片上系统( s o c ) 设计的不断发展，在现阶段层次化设计中，许多学 者根据片上系统的性能和可靠性的需求，在布图优化问题中增加了一些与实际 需求相关的约束，其中包括模块问的位置约束，比如固定边框约束，边缘约束， 对齐约束和邻接约束等；还有电性能约束，比如电压降约束，电子迁移约束以 及最小电源线宽约束。现代布图规划问题已经从传统的、简单的布图规划问题 向具有各种约束的，复杂的布图规划问题转变。 在解决带约束的布图规划问题时，奉文采用的是一种有效且非常灵活的布 图表示法胪t r e e 表示法。 本文提出了一种新颖的位置约束问题，即边界聚集约束。该约束是针对宏 模块而言的，它要求所有的宏模块都必须放置在或者聚集的放置在版图的边缘。 该约束有利于减小互连线长和布线时空问的不连续性。在解决基于该约束的布 图规划问题时，本文对扩t r e e 表示法进行了深入的研究，并在满足一定限制 条件的前提下提出了四个充分条件。本文提出的优化算法可以动态的将随机产 生的非法解有效、快速的转化为合法解，从而大大提高了搜索效率，而不是采 用惩罚函数法。本文提出的优化算法通过了基于m c n c 和g s r c 标准电路中五 个基本电路的测试和验证。实验结果表明，本文提出的解决带有边界聚集约束 的布图规划算法是非常有效的。 同时，基于电性能约束的布图规划问题已经成为一个研究热点。本文也对 电源地线网络和布图规划的协同设计进行了深入研究。电源地线网络和布图 规划协同设计的主要目标是获得一个比较优秀的布图结果并且同时产生一个相 对应的电源地线网络使其在满足所有相关电性能约束的前提下绕线资源最少。 本文提出了一种模式选择机制，它有效的提高了整个优化流程的效率。本文同 时也提出了一个基于电源地线网络的增量式布图方法，它可以有效的修复优化 流程中产生的非法解。考虑到电源地线网络资源的优化，本文提出了合理分配 电源地线引脚和改变电源线线宽的方法，并把它们嵌入到整个优化过程中。实 验结果证明了本文采用的方法不仅提高了优化流程的效率，也在保证版图解的 质量的同时，优化了电源地线网络的绕线资源。 关键字：布图规划，边界聚集约束，舻t r e e ，模拟退火算法，电源地线网络 a b s t r a c t w i t ht h ed e v e l o p m e n to f s o cd e s i g n s ，i nm o d e r nh i e r a r c h i c a ld e s i g n s ，m a n y r e s e a r c h e r sa d ds o m ee x t r ac o n s t r a i n t si n t ot h ef l o o r p l a n n i n go p t i m i z a t i o np r o c e s st o m e e tt h ed i f f e r e n tp e r f o r m a n c ea n dr e l i a b i l i t yr e q u i r e m e n t s ，s u c ha sf e d o u t l i n e c o n s t r a i n t , b o u n d a r yc o n s t r a i n t , a l i g n m e n tc o n s t r a i n t , a b u t m e n tc o n s t r a i n ta n ds oo n s o m ep o w e ri n t e g r i t yc o n s t r a i n t sa l ea l s oc o n s i d e r e di nt h ef l o o r p l a nd e s i g np r o c e s s ， s u c h 舔i r - d m pc o n s t r a i n t s m i ni m u mw i d t hc o n s t r a i n t sa n de l e c t r om i g r a t i o n c o n s t r a i n t s ac r i t i c a lp r o b l e mo ff l o o r p l a n n i n gi st h e r e p r e s e n t a t i o no fg e o m e t r i c r e l a t i o n s h i pa m o n gm o d u l e s i nt h i st h e s i s , t h eb * - t r e er e p r e s e n t a t i o ni sa p p l i e df o r i t ss i m pl e ，y e tef f e c t i v ebi n a r yt r e es t r u c t u r e t h i st h e s i sf o c u s e so nt h eb o u n d a r yc l u s t e r i n gc o n s t r a i n tw h i c ho u rp r o p o s e d i t h a n d l e sw i t ht h em a r c om o d u l e sw h i c hr e q u i r e dc o n s t r a i n e dm o d u l e sb e i n go nt h e b o u n d a r i e so rcl u s t e r i n gt ot h eb o u n d a r i e s t h eb o u n d a r yc l u s t e r i n gc o n s t r a i n tc a n h e l pt om i n i m i z et h ew i r el e n g t ha n dr o u t i n gs p a c ef r a g m e n t a t i o n i no r d e rt o e f f e c t i v e l ys e a r c ht h ef e a s i b l es o l u t i o n s ，t h ef e a s i b l ec o n d i t i o n sb a s e do nb * - t r e e r e p r e s e n t a t i o nw i t hb o u n d a r yc l u s t e r i n gc o n s l r a i n ta r ei n v e s t i g a t e d t h ep r o p e r t i e s ， c o u p l e dw i t ha ne f f i c i e n ts i m u l a t e da n n e a l i n ga l g o r i t h m , p r o v i d et h ew a y t op r o d u c e f e a s 曲l ef l o o r p l a nb yd y n a m i cr e p a i r i n g , w h i c hc a nt r a n s f o r ma ni n f e a s i b l es o l u t i o n i n t oaf e a s i b l eo n ei f t h ec o n s t r a i n ti sv i o l a t e d t h ep r o p o s e da l g o r i t h mi sv e r i f i e db y u s i n gt h em c n ca n dg s r cb e n c h m a r k s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a to u r a l g o r i t h mw h i c hs o l v e st h ef l o o r p l a n n i n gw i t hb o u n d a r yc l u s t e r i n gc o n s t r a i n tc a n o b t a i np r o m i s i n gs o l u t i o n si na c c e p t a b l et i m e a st h ed e s i g nc o m p l e x i t yi n c r e a s e sd r a m a t i c a l l y , i ti sn e c e s s a r yt oh a n d l et h e p o w e rc o n s t r a i n t se a r l i e ri nt h ed e s i g nc y c l ef o rb e t t e rd e s i g nc o n v e r g e n c e i nt h i s t h e s i s ，w ed os o m ed e e p l yr e s e a r c ho nt h ep o w e r g r o u n dn e t w o r ka n df i o o r p h n c o d e s i g n t h eo b j e c t i v eo fc o - d e s i g n i st oo b t a i naf e a s i b l ef l o o r p l a na n d s i m u l t a n e o u s l yg e n e r a t eac o r r e s p o n d i n gp gn e t w o r kw i t hm i n i m a lw i r i n gr e s o u r c e w h i l et h ep o w e rc o n s t r a i n t sa r es a t i s f i e d i nt h i st h e s i s ，w es e tu pap a t t e r ns e l e c t i o n s c h e m ef o rf a s ts i g n a l - i n t e g r i t ye s t i m a t i o n u s i n gp a t t e r ns e l e c t i o nm e t h o dc a n n s i g n i f i c a n t l ys p e e d u p t h e o p t i m i z a t i o np r o c e s s w e a l s o p r o p o s eag u i d e d i n c 佗m e n t a lf l o o r p l a n n i n ga p p r o a c ht oa m e n dt h ev i o l a t i o n si n t e l l i g e n t l yd u r i n gt h e f l o o r pl a n n i n gp r o c e s s a tt h es a m et i m e ，t o m i n i m i z et h ea r e ao fp gn e t w o r k ，t h e p gp i na s s i g n m e n ta n dw i r es i z i n gm e t h o da r ea l s oe m b e d d e di nt h ef l o o r p l a n n i n g o p t i m i z a t i o np r o c e s s e x p e r i m e n t a l r e s u l t ss h o wt h a to u rd e s i g n n o t o n l y s i g n i f i c a n t l ys p e e d su pt h eo p t i m i z a t i o np r o c e s s ，b u ta l s oo p t i m i z e t h ep o w e rr o u t i n g r e s o u l ew i t hm a i n t a i n i n gt h eq u a l i t yo f t h ef l o o r p l a n k e yw o r d s ：f l o o r p l a n n i n g , b o u n d a r yc l u s t e r i n gc o n s t r a i n t , b * - t r e e ，s i m u l a t e d a n n e a l i n g ，p o w e r g r o u n dn e t w o r k 1 i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：奎建e l 期：建堕： ： 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：鸯馨 导师( 签名) ：徐雪日期町p 孓 武汉理丁大学硕士学位论文 第1 章绪论 1 1 研究背景 随着设计复杂性和电路规模的日益增长，层次化设计和i p 模型都得到了广 泛的应用。在这种发展趋势之下，版图设计对v l s i 设计的质量起到了至关重 要的作用。而布图规划又是版图设计中一个很重要的步骤，所以布图规划的优 化问题也成为了一个重要的研究热点。传统布图规划问题的目标是粗略的放置 一组给定的模块，使它们相互之间不能重叠，而且达到面积和互连线长最小。 随着s o c 设计的不断发展，许多研究者们根据性能和可靠性的特殊需求， 在布图规划设计时增加了一些模块间的位置约束。比如，两个模块之间有很强 的互联关系，这就产生了邻接约束；在基于b u s 的布线过程中有些模块需要垂 直对齐的放置在芯片的中央，这就产生了对齐约束；还有一个很常见的约束就 是整个芯片的每一个模块都必须放置在一个给定的边框内，这就是固定边框约 束；有些具有一定功能的模块需要与i o 连接或者发热量比较大，这就产生了 边缘约束。还有对称约束在模拟器的设计中也常常被提及，这些约束在布图规 划设计中占有很重要的地位。由此可见，现代布图规划问题已经慢慢从传统的 布图规划问题向具有各种约束的布图规划问题转变。通过火量文献的阅读，本 文提出了一种新颖的位置约束一边界聚集约束。这种约束有利于减小互连线 长和布线时空问的不连续性。它要求所有的宏模块都必须放置在或者聚集的放 置在版图的边缘。边界聚集约束包含了边缘约束，它比边缘约束更具有实际意 义。本文对基于该约束的布图规划问题进行了深入的研究。 在s o c 设计过程中，我们也发现电性能约束也越来越多的在布图规划的早 期阶段被考虑。电源地线网络是为整个版图中的每个模块分配供电电压的。如 果在后续的版图验证过程中发现某个模块的供电电压低于其最小需求电压，则 整个：签片必须重新设计。这种时间花费是完全不可取的，所以电性能的相关约 束越早考虑越好。本文对电源地线网络与布图规划协同设计做了深入的研究。 在布图规划阶段，本文充分考虑到电源地线网络的设计需求及其需要满足的电 性能相关约束，并且在满足所有约束的前提下优化电源地线网络的绕线资源。 在协同设计的研究中，我们提出了很多有效的方法，将在后续章节中详细介绍， 同时实验数据也证明了本文提出的方法的有效性。 武汉理丁大学硕士学位论文 l2 相关研究 目前，在集成电路物理设计中有一些比较优秀的布局表示方法，例如：序 列对( s p ) 表示法泖，b t r e e 表示法q ，o - h e e 表示法一形网格( b s g ) 表示法 啊角模块序列( c b l ) 表示往m 和t c g 表示法唧。每一种表示方法都有它们 各自的特点。基于不同的表示方法在相关文献中研究者们已经提出了处理相 应约束的有效方法，例如在文章【1 5 】和f 1 9 】中，作者在处理布圈规划设计时增加 了固定边框约束。它是根据所有模块的大小粗略估计了一个可行的固定边框的 大小。在整个设计过程中，设计者们都要保证所有的模块必须放置在这个固定 边框的区域内。在文章1 1 0 中，研究者利用序列对表示法培出水平和垂直约 束图根据该约束图对边界约束进行有效的处理。在文章 1 4 】中，它是利用c b l 表示法处理边界约束。但是由于c b l 表示法的局限性，所以其应用范围不是很 广泛。在文章 1 1 】中，它是利用b t r e e 表示方法解决边界约束问题。它将受约 柬的每个模块都严格的放置在最终版图的边缘。而没有考虑到本文所提出的聚 集的情况。这种做法是有一定的局限性的。 图1 宏模块的版图布局 正如杂志文章【1 2 和【j3 】中所说，当今s o c 设计中宏模块的设计是至关重 要的。由于大量混合模块的存在，版图设计方法将起到决定性的作用。由于一 蝗相同或者相似性能的模块放置在起能更好的实现芯片的功能，所以本文提 出了一种新颖的约束，也就是边界聚集约束。边界聚集约束不同于边界约柬， 因为受约束的模块可以不放置在版图的边缘，而是聚集的放置在边缘。边界聚 集约束的一种特殊情况就是边界约束。就像图l 所示一些小的宏模块并没有 茎婆型王查堂堡主堂焦笙塞 放置在版图的边缘，而是聚集的与放置在边缘上的大宏模块相邻。特别是在层 次化设计中，边界聚集约束是很有意义的。t c c h e n 等在【1 1 】中提出了m p t r e e 表示法来解决宏模块的布局问题。它在处理标准单元和宏模块时采用两阶段法。 首先将宏模块放置在版图中由四个角延伸出来的边缘上，再将剩下的中间的区 域放置数量众多的标准单元。尽管这种两阶段法确保了标准单元之间最大的连 通性，但是没有考虑到两种模块之间的互联性，很有可能导致互连线长的恶化。 因此，为了获得全局最优解，设计者有必要将宏模块和标准单元同时处理。在 高层次设计阶段，标准单元可以以一定的形式和数量聚集成虚拟的大模块，同 时将这种大模块看作是宏模块来处理。这样就可以看作是由宏模块组成的布图 规划设计。这种做法有利于层次化设计。所以，研究带有边界聚集约束的布图 规划方法是很有必要的。 基于电性能约束的布图规划问题也有很多学者正在不断的研究中，而且现 在这个领域中的研究热点也在不断的出现。电源地线网络与布图规划的协同设 计已经成为提高电性能的一个重要途径【4 硒6 1 。通过阅读大量相关文献，我们发 现解决电源地线网络与布图规划协同设计的方法主要有i 种：1 ) 对电源地线 网络进行优化，也就是选取合适的电源地线网格的大小和假定供电电源的位置 和个数h 6 - 5 2 1 ；2 ) 调整电源线的宽度【5 3 巧4 】；3 ) 插入去耦电容【5 5 - 5 6 1 。后面两种方 法是建立在已经固定好电源地线网络的基础上的。所以，如何设计一个优秀的 电源地线网络来满足布图规划中产生的多种多样的版图是一个讨论很广泛的 问题。文章 4 6 5 q 】提出了三种电源地线网络的拓扑结构，它们分别为树形，均 匀网格和不均匀网格。均匀网格【4 6 】是现今广泛采用的一种拓扑结构，也是本文 采用的拓扑结构。它容易实现而且分析起来比较简单，也符合供电网络的真实 性。树状拓扑结构f 4 7 f i r , 够最小化电源地线网络的绕线资源，但是其稳定性比较 差，会出现因为一处电子迁移的发生使得整个供电系统瘫痪的情况。而不均匀 网格【5 0 】的实现比较复杂，且为后续的绕线过程增加了难度，所以现在还没有被 广泛使用。在文章【4 6 】中，设计者们提出了一个同时考虑布图规划和电源地线 网络的协同设计方法，并且将一些对电压要求比较高的模块强制的放置在边界 上，这样虽然能够在一定程度上提高搜索的效率，但是它缩小了解空间。在文 章【5 4 】中，设计者提出了一种改变电源线线宽的方法来优化电源地线网络的绕 线资源，但是它是在布图规划完成之后进行的。而布局的结果对电压降的影响 是很大的，所以我们有必要将改变线宽的操作嵌入到布图规划过程中，这样得 到的效果往往会更好。 武汉理丁大学硕士学位论文 1 3 研究意义 1 3 1 理论意义 通过阅读大量相关文献，我们发现布图规划问题越来越成为研究者们的热 点。基于约束的布图规划问题也逐渐取代了传统布图规划问题。而在现代s o c 设计需求分析中，我们发现很多宏模块都聚集的放置在版图的边缘，这样有利 于散热，同时也方便与l o 进行连接。所以本文提出了边界聚集约束。在处理 布图规划问题时，首先要选择适当的版图表示法。不同的表示方法对解决不同 的约束问题在时间复杂度和空间复杂度这两方面都是不同的。本文采用灵活有 效的胪t r e e 表示法。其次就是要选择高效的布图规划算法。本文对b 幸t r e e 的 构造方法进行深入的研究，并且找到满足边界聚集约束的几个充分条件。在搜 索最优解的过程中，通过对边界聚集约束的充分条件进行判断，动态的将非法 解修正为合法解，从而大大提高了算法的效率。本文依据一定的规则改进了基 本模拟退火算法的扰动机制，这样从过程上控制了非法解的产生。 同时本文也对基于电性能约束的布图规划问题进行了深入研究，将电源， 地线嘲络与布图规划进行协同设计。在协同设计过程中，本文提出了很多新颖 有效的方法，首先构建了一个模式选择机制，它有效的提高了整个优化流程的 效率。同时也提出了一个基于电源地线劂络的增量式布图方法，它可以有效的 修复优化流程中产生的非法解。考虑到电源地线网络资源的优化，本文提出了 一个合理分配电源地线引脚和改变线宽的方法，把它们嵌入到整个优化过程 中。实验结果证明了本文的方法不仅提高了优化流程的效率，也在保证版图解 的质量的前提下，优化了电源地线网络的绕线资源。 1 3 2 现实意义 随着s o c 设计的发展，层次化设计和i p 模型都得到了广泛的应用。在层 次化s o c 设计中，许多研究者根据其性能和可靠性的特殊需求，在布图规划阶 段增加了一些特定的约束使得整个设计更加符合实际的要求。本文提出的边界 聚集约束就是一种很重要的约束。在布图规划阶段，通常都是将宏模块先放置 在或者聚集的放置在版图的边缘，它有利于大模块的散热和与i 0 的连接；而 大量标准单元则放置在中间剩余的连续空间，这样有利于减小互连线长和碎片 的不连续性。所以解决基于边界聚集约束的布图规划问题是很有现实意义的。 解决基于电性能约束的布图规划问题也是很有实际意义的。在芯片设计过 4 茎鲨些三奎堂堡主堂堡迨奎 程巾，供电电压的作用是非常巨大的。如果一4 个模块的供电电压没有达到它的 最低需求值，则整个：笆；片必须重新设计，这样从时间代价方面考虑是完全不可 取的。所以，在现代v l s l 设计中，电性能约束在布图设计的早期就开始考虑 了。考虑得越早，在后期出错的几率就越小。电源地线网络的设计在布图规划 阶段进行是很有现实意义的。所以，本文对电源地线网络与布图规划设计协同 设计进行了深入的研究。 1 4 创新点 在基于边界聚集约束的布图规划问题的研究中，本文有两个创新点。 i ) 本文提出了个重要的在布图规划设计中应该考虑的约束边界聚集 约束，它具有很强的现实意义。 2 ) 针对边界聚集约束的定义，本文结合b 木t r e e 的构造法提出了四个满足 边界聚集约束的充分条件。根据这些充分条件，本文提出的算法对不合法的解 动态修正，使其转变成合法解，在扰动机制上采用适当的约束来保证合法性。 通过这些操作，我们可以使随机搜索的解的质量得到很大的改善，同时也提高 了整个优化流程的效率。 在电源地线网络和布图规划协同设计的研究中，本文有三个创新点。 1 ) 本文采用了模式选择的方法提高了优化流程的效率。 2 ) 为了更进步的提高搜索效率，本文提出了种基于电源地线网络的增 量式布图方法。它能够在保证搜索空间的同时，有效的修复违反约束的节点。 3 ) 考虑到电源地线网络的协同优化，在满足所有电性能约束的前提下，本 文也提出了电源地线引脚的分配方法和改变电源线线宽的方法优化电源地线 网络的绕线资源。 1 5 本文的组织结构 本文共分为六个章节。第一章是绪论，介绍相关背景知识和研究意义及其 创新点；第二章介绍了v l s i 设计的基础知识以及布图设计相关内容：第三章 介绍了布图规划表示方法及其相关算法：第四章详细介绍了基于边界聚集约束 的布图规划问题的研究；第五章详细介绍了电源地线网络和布图规划的协同设 计的研究；第六章是对全文进行总结以及对未来的展望。 武汉理工大学硕士学位论文 第2 章v ls i 布图设计 自晶体管于上世纪4 0 年代后期发明以来，集成电路经历了小规模集成电路、 中规模集成电路、大规模集成电路、超大规模集成电路和特大规模集成电路等 五个阶段。目前已经进入片上系统( s o t ) 时代。在集成电路的工艺水平已经进入 深亚微米以后，集成电路设计面临着四个方面的挑战，即：缩小尺寸，增加集 成度，提高系统性能和降低功耗。这四个因素之问是相互制约的。本章主要介 绍v l s l 设计流程和其巾布图规划设计的基本内容。 2 1v l s i 设计流程 v l s i ( 超大规模集成电路) 设计是一个 分复杂的过程。它涵盖了计算机 科学与技术，电路与系统和微电子学等多个电子相关专业。由于v l s i 设计的 复杂性和设计对正确性的要求，这就决定了v l s i 设计必须借助c a d 等工具进 行。如下图2 1 所示，v l s i 设计一般分为系统规范说明，寄存器传输级设计， 逻辑设计，电路设计、物理设计和设计验证六个步骤。以下分别介绍每个步骤 的相关内容和主要功能。 l 多笔摆翌望塑l 匝垒堕麴圃 一i 7 前端设计副墒砹计 后端设计 图2 iv l s i 设计流程 6 茎鲨型三奎堂堕主堂堡垒壅 2 1 1 系统规范说明 v l s i 设计一般要从需求分析开始。e d a 工具需要将用户的需求转化为功 能描述和技术指标表示的系统规范化说明。它一般包括系统的功能、物理尺寸 和系统的性能。此外，系统规范说明还需要考虑设计模式、制造工艺、制造周 期和设计费用等等【16 1 。 2 1 2 寄存器传输级设计 在寄存器传输级设计过程中，设计者在这一阶段主要完成系统功能的实现 方案。它考虑的是系统的行为特性，即给出系统的时序图及各子模块之间的数 据流图。设计者们利用这些信息可以采用仿真模拟的方法来改进整个设计过程 或简化后续的设计步骤，并达到最优状态【1 6 1 。 2 1 3 逻辑设计 在逻辑设计过程中，我们可以得到一个表示系统功能的逻辑结构并反复测 试其正确性。这一过程是将系统功能结构化。它将各个子系统模块加以结构化， 实体化，选择合适的逻辑部件来实现系统的功能。设计者们通常采用文本、原 理图或者逻辑图来表示设计方案，有时也可以用布尔方程表示设计f 1 6 1 。 2 1 4 电路设计 在电路设计过程中，我们要将逻辑设计过程中设计的电路方案具体实现。 在进行电路设计时，我们要考虑的因素很多，包括速度、功耗和噪声等实际需 求。此外，设计者们还要注意各种元器件的屯性能指标。在此设计阶段中，设 计者们通常是采用详细的电路图表示相关的电路结构。 2 1 5 物理设计 物理设计也就是版图设计，是v l s i 设计中最费时的一步。物理设计时， 设计者们要把每个元件的电路表示转化为几何表示。同时，所有元件间连接的 线网也被转换成几何连线图形。电路的几何表示称为版图。这些版图信息是用 带有层次的几何图形表示的。版图设计要符合与制造工艺相关的设计规则要求。 由于版图设计的复杂性，往往把版图设计分成若干子步骤进行。在下面的2 2 节中，我们将对物理设计过程做详细的介绍。 2 1 6 设计验证 7 墓鲨些三盔堂堕主兰堡笙茎 设计验证也称版图验证。这是版图设计后一个很重要的步骤。它是为了确 保版图设计完成后，所得到的几何图形满足制造工艺要求，并且符合系统的设 计规范。在设计验证过程中，设计者们的主要任务包括设计规则检查，版图的 电路提取，电学规则检查和寄生参数的提取等。 经过上述几个步骤，我们可以将验证合格的版图提交给厂家进行制造和生 产。 2 2 布图设计 版图是墨i 物理设计阶段的结果，同时它也是集成电路设计与制造之间 的惟一的联系。在现阶段超大规模、甚大规模集成电路设计中，布图设计的结 果将直接影响整个版图的设计。布图设计也就是上述2 1 5 节中提到的物理设 计。布图设计这一步骤也是人工设计中最耗费时间、错误率最高的设计过程之 一。布图设计的过程可分为划分，布图规划，布局，布线和压缩五个阶段，如 图2 2 所示。以下各节将分别介绍布图设计过程中的各个阶段。 物理设计 划分 i 布图规划和布 i 电路设计i 。 i 芯片伟f i 诰 总体布线 j 详细布线 图2 2 布图设计过程 2 2 1 版图的划分 随着电路元器件尺寸的不断减小，现代芯片中可能包含了上亿个晶体管。 由于计算机的存储空间和计算能力是有一定限制的，我们在处理物理设计问题 时，通常把整个芯片划分为若干个子系统，这样可以缩小问题规模。根据经验 值，一般5 2 5 个模块划分在一起组成一个虚拟模块。在划分时，我们要考虑到 8 茎鲨堡三奎堂堡主堂堡堡奎 模块的大小，数日以及模块之间的互连线数等多个因素。 2 2 2 布图规划 布图规划主要是为整个芯片选择一个比较好的布图方案。在经过划分之后， 我们一般根据每个划分后形成的虚拟模块中包含的元器件的个数和每个元器件 的宽、高来估计它们各自的形状、面积和相应的p i n 脚的位置分布【1 1 。在布图规 划阶段，我们总体的设计目标一般是优化：卷片的互连线长和面积。在一些特殊 的情况下，我们还要考虑其它实际约束和时延效果。在布图规划设计过程中考 虑的因素越多，那么在后续设计中遇到的阻碍就越少。因此，布图规划阶段也 是学者们研究的热点之一。 2 2 3 布局 布局是电子设计自动化中一个很重要的步骤。布局阶段的主要任务是在芯 片的核心区域确定各个电路元件的位置信息。一个比较差的布局器不仅会影响 整个芯片的性能，也会由于互连线长超过布线资源而使其不能被制造。因此， 一个好的布局器在确定每个元器件位置的同时也必须满足电路的性能需要来优 化多个目标。典型的布局优化目标包括以下几项： 1 ) 互连线总长：2 ) 时序性；3 ) 拥塞区域；4 ) 功耗；5 ) 布局时间。 2 2 4 布线 布线是根据电路网表信息，在指定的区域中完成百分之百连线的过程【3 6 1 。 布线阶段的主要目标是要实现所有模块之间的互连，其次是在达到布通率的前 提下对布线结果进行优化，例如如何提高电性能，如何减少通孔数量等等。通 常，我们把布线分成两步：第一步是总体布线，然后进行详细布线【3 6 1 。在总体 布线阶段，我们要完成线网的合理分配，但它仅仅是将线网分配在合适的布线 区域内以便确保得到的尽 - y m 匕高的布通率，而不去关心实际的走线情况【翊。详 细布线则是最终确定连线的具体位置和具体走向。采用这种两阶段布线方法， 我们可以在总体上分析线网连接的要求和布线区域资源，做到合理分配线网以 避免局部拥塞。 2 2 。5 压缩 压缩是一个在布线完成后，对整个版图进行优化处理的个过程。压缩的 效果是进一步缩小芯片的总面积，它将所有的模块均同时向下和向左移动。目 9 武汉理工大学硕士学位论文 前，常用的压缩技术有一维压缩和- 维压缩，其巾较为成熟的是一维压缩技术。 2 3 本章小结 本章主要介绍了v l s i 设计的流程。在v l s i 设计过程中，设计者们首先要 完成系统规范说明，按照系统规范说明，再进行相关的寄存器传输级设计和逻 辑设计。在逻辑设计完成的基础上进行电路设计，之后进行物理设计。当整个 设计完成之后，设计者们要验证设计的可行性。如果通过验证则开始制造和封 装，否则重新进行设计。如果以一卜步骤都顺利完成，那么最后一步就是要进行 单元测试和功能测试。由于本文主要解决的是布图规划阶段的优化问题，所以 本文也详细介绍了物理设计( 布图设计) 的几个重要步骤，如版图的划分、布 图规划、布局、布线和压缩五个阶段。 1 0 武汉理工大学硕士学位论文 第3 章布图规划表示方法及其相关算法 本章主要介绍在布图规划阶段应用比较“泛和有效的算法以及在此阶段常 用的版图表示方法。 3 1 布图规划常见算法 由于布图规划问题是一个n p h a r d 问题，即它不能在多项式时问内找到问 题的最优解。所以，我们一般采用启发式的算法来寻找较优的可行解。在近几 年的研究过程中，研究者们为了解决布图规划相关问题，已经提出了很多行之 有效的方法，这些方法总体可以分为三类：1 ) 构造式的方法，常用的构造式方 法包括二划分法和数学规划方法；2 ) 迭代式的方法，典型的迭代算法有模拟退 火算法，力矢量互换松弛算法和遗传算法；3 ) 基于知识获取的方法。 在下述的两个小节中，本文将对模拟退火算法和线性规划算法进行详细的 讲解。 3 1 1 模拟退火算法 3 1 1 1 模拟退火算法简介 模拟退火( s a ) 算法是一种通用的概率演算法。它的主要应用是在个复杂 而庞大的搜索空问中寻找最优解或者准最优解。它能在搜索过程中自动获取和 积累相关信息，并且自适应的快速完成搜索的全过程。 模拟退火算法来源于固体退火的原理。它是将热力学的原理用到了统计学 上。它将搜索空间里的每一个解都想象成为固体中所含有的原子。而搜索空间 内的每一解，也像固体内的原子一样，它们都带有“能量”，用来表示此解对所 求问题的适应度【2 1 。模拟退火算法是先以搜索空间中的任意一个合法解当作初 始解。在每一次的迭代过程中，通过扰动机制产生一个邻居”，即邻域解，然 后计算从现有的位置到“邻居”的概率是否被接型2 1 。如果被接受，那么该领域 解将代替当前的解，进行下一次的迭代。反之，如果不被接受，则当前解不改 变，继续进行下次迭代操作。直到满足预先设定的终止条件，整个迭代过程结 束。下表3 1 所示的是模拟退火算法和物理退火过程之间的相关性。 武汉理工大学硕士学位论文 表3 1 模拟退火算法与物理退火的对比 模拟遗火物理退火 解粒子状态 最优解禽皂量最低状态 设定韧温熔解过程 m e t r o p o l i s 采样过程 等温过程 控制参数的下降 冷却 目标函数 能量 3 1 1 2 模拟退火算法基本思想 模拟退火算法是基于m e t r o p o l i s 准则迭代求解法的一种启发式随机搜索算 法圆。m e t r o p o l i s 准则可以用以下形式描述： 假设在状态日时，系统受到了某种扰动而使其状态变为x n e w 。与此相对应， 系统的能量也从e ( x o 力变成e ( x 疗- - ) ，系统由状态h 转变为状态x 疗例的接受概率 p 通过公式( 3 1 ) 求得。 i f e ( 州) 硫。 1 ) f o r j = l k 2 ) 对当前最优解b 。，按照某一领域溺数，产生一新的锯h 。 3 ) 计算新的 标函数加。，并计算f 标豳数值的增量么= 纯。_ 矗划 4 ) 如果4e o ，则p = e x p 一4 ； 1 ) 如粜c = r a n d o m 0 ，i j 印，戈触瓢。州；否受4 ，w 细 6 ) e n d f o r 4 ) i = f l ： 5 ) e n dd o 6 ) 输出当时最优点，计算结束 3 1 1 3 模拟退火算法的要素 根据模拟退火算法的基本流程，下文对模拟退火算法中的几个要素做了详 细的介绍。 1 ) 搜索空间与邻域函数 在智能优化算法中，搜索空间又称为解空间，它是由所有可行解组成的集 合。而邻域函数则应该尽可能的保证其产生的候选解均匀的分布在整个搜索空 问里。 2 ) 接受概率p 接受概率是指接受一个新解作为当前解的概率。它一般采用m e t r o p o l i s 准 则进行优化迭代，具体的计算方法请参见公式3 1 。 3 ) 温度变换函数刑 温度变换函数是指温度从某高温状态瓦向低温状态冷却时的转换函数。模 拟退火算法的全局搜索性能与退火的速度是密切相关的。假设，当时间为t 时， 温度用刑来表示。则传统的模拟退火算法的温度变换函数为： m 。薪 ( 3 2 ) 而快速模拟退火算法的温度变换函数为： 墓鲨些三奎堂堡主堂垡堡茎 w ) 一鲁 ( 3 - 3 ) 这两种方式都能够使模拟退火算法收敛于全局最小点。 4 ) 初始温度乃 初始温度乃的设置是影响模拟退火算法搜索性能的重要因素之一。通过大 量实验表明，如果初始温度高，则搜索到全局最优解的可能性比较大，但是也 要花费大量的时间；反之，则可节约时间花费，但全局搜索性能可能受到影响。 因此，初始温度的确定应该折衷考虑优化质量和优化的效率。 5 ) 内循环终止准则 内循环终止准则用于决定各温度下产生候选解的个数。常用的内循环终止 准则包括：检验目标函数的均值是否稳定；连续若干次迭代的目标函数值变化 较小；按一定的迭代次数抽样。 6 ) 外循环终止准则 外循环终止准则即算法终止准则。常用的算法终止准则包括：设置终止温 度的阈值；设置外循环迭代次数：算法搜索到的最优值连续若干次都保持不变。 3 1 2 线性规划算法 线性规划( l i n e a r p r o g r a m m i n g ) 算法一种很常见的带约束的优化算法。带 约束的优化算法比不带约束的优化算法要复杂很多。因为在找到一个最优解时 还必须考虑到相关变量的约束条件是否满足。例如：当你取得一个最优解时， 其中一些带约束的变量不满足相关约束，而另一个次优解的所有变量都满足相 关的约束，此时我们将选择这个次优解，而放弃最优解。 任何带约束的优化问题都包括以下几个重要的因素： 1 ) 变量。通常情况下，在开始解决此类问题时变量的值是未知的。这些变 量通常本身都是有实际意义的。整个问题的求解目标是要找到一个合理的变量 值使得目标函数具有最优值。 2 ) 目标函数。就是用一些变量通过一个数学表达式来表示要求问题的目标 值。例如，如果要求的是利益，则我们将需要最大化这个目标函数的值。 3 ) 约束。在很多情况下，涉及到实际问题时，目标函数中变量的实际意义 使得它的取值受到了一定的限制。比如，操作一台特定机器的工人数量是有限 的，或者是每天的用电量是一定的。 1 4 武汉理f t 大学侦士学位论文 4 ) 变量边界值。在优化问题巾很少有变量的取值可以是任意实数的。相反， 通常情况下很多变量的取值都在一定的范围内的。 在线性规划问题中，所有的目标函数的数学表达式和约束都是线性的。所 以，我们可以看出线性规划问题是对线性模型的规划和设计。在现实生活中， 很多问题都可以看成是一个线性模型，从飞机调度问题到最小耗油量问题，线 性规划算法都得到了广泛的应用。i b m 在1 9 7 0 年的调查中得出2 5 的科学计 算问题都可以归结为线性规划问题。 线性规划是至今应用最为广泛的解决带约束的优化问题的算法。使用线性 规划算法解决了世界上最大规模的优化问题，其中变量数达到了上百万个，约 束条件也有上千个。现在随着算法和计算能力的加强，这些大规模的问题都可 以在有限的时间内解决。 下面，本文将介绍一下标准的线性规划算法。线性规划算法中的目标函数 可能是将其最大化或者最小化，这是由具体问题所决定的。约束通常是用大于， 等于或者小于这三种符号表示的，并且变量的值也是有上限和下限的。一个标 准的线性规划形式是一种最简单的线性规划算法。它具有以下一些特点： 1 ) 对目标函数进行最大化求解； 2 ) 所有的约束都是小于( ) ； 3 ) 所有的变量都为非负值。 标准的线性规划算法一般有如下图所示的可行解的范围。 图3 1 标准线性规划的可行解范围 在一个线性表达式中，标准线性规划形式通常含有m 个有影响的约束和刀 个变量。 1 5 武汉理工大学硕士学位论文 目标函数： m a x z = c i x i + c 2 x 2 + c s x s + c , 嗣c n 其中目标函数中的q 系数表示的是x ，在z 中的增长或者下降。 m 个有影响的约束通常表示成以下形式： a l l x i + a 1 2 x 2 + + a l n x n = b l a 2 l x l + a 2 2 x 2 + + 鼢 = b 2 a m l x i + a m 2 x 2 + + a 盯m x n = o ，x 3 却：o 一一删 3 2 布图规划的表示方法 布图规划的表示法是用字母或数字表示每一个模块，并将其用一定的数据 组织形式( 如序列、树、图等等) 组织起来从而表示模块之间的几何位置关系【l 】。 对应一个最终版图布局的序列、树或图称为编码。所有可能的编码形式称为这 个版图表示法的解空间。所以版图的表示形式明显的影响到对各个模块的操作 和这个版图设计过程的复杂性。不同的布图规划表示法有着不同的解空间和冗 余度，它们在解码操作和扰动操作一卜的效率也是不一样的，所以表示法就有了 优劣之分。衡量一个布图规划表示法的优劣可以从以下6 个方面考虑：( 1 ) 解 空间的有限性；( 2 ) 表示法的解空间存在最优解：( 3 ) 解码操作不能太复杂，最好 能在线性时间内完成；( 4 ) 对编码的扰动操作不能太复杂；( 5 ) 表示法的冗余度要 小；( 6 ) 存储