（计算机应用技术专业论文）vlsi布图规划布局若干算法研究.pdf

摘要 布图规划是超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t ， v l s i ) 物理设计中一个重要的阶段。它主要是规划模块在芯片上的形状和位置。 随着集成电路设计的发展，越来越多的问题需要被考虑，特别是操作频率的逐 渐增加和芯片的更高的集成度，使得芯片上的面积、延迟、温度等成为集成电路 设计中严重的问题。 本文对大规模集成电路物理设计中的布图布局算法进行了研究，包括模拟 退火算法，禁忌搜索等方法，并对布图中的一些目标，如：面积、线长、拥塞 等进行了考虑，提出了一些解决方法。论文的主要贡献如下： 在模拟退火算法和禁忌搜索的基础上提出了一种混合算法用于在有限的解 空间中搜索最优解，利用模拟退火来产生邻域解，同时利用b * - t r e e 表示法 来表示布图，以b 木一t r e e 的前序和中序序列作为禁忌对象。实验结果表明我 们的方法能够在更短的时间内获得较高的面积的利用率。 在处理多目标最优化问题时，用传统的线性加权函数方法平衡不同的目标很 困难。为了克服这个问题，模糊准则和隶属函数被引入用来结合不同的目标。 它是一个很方便的方法用于结合冲突的目标并且能够利用专家知识。实验结 果表明，这个方法稳定有效，能在更短的时间内得到令人满意的解。通过实 验结果，我们能够对参数设置的变化有一个直观的理解。这个方法也能够被 延伸去解决其它大规模多目标最优化问题。 为了避免耗时的拆线重布，提出了一个新的二阶段布图规划方法用于拥塞最 优化。我们采用了概率估计模型去评估线网的拥塞程度，同时利用单元的扰 动策略去消除布线拥塞。在拥塞指导下，利用我们的算法，对拥塞进行进一 步的减小。实验结果表明我们的算法是有效的，稳定的并且能够非常大的减 小拥塞。对比传统的拥塞性能的布图规划，我们的二阶段方法能够在更短的 时间内有效地减小拥塞。 关键词：v l s i ：布图规划：多目标：随机算法：b * - t r e e a b s t r a c t o o r p l a n n n i n gi sav e r yi m p o r t a n ts t e pi nv e r yl a r g es c a l ei n t e g r a t e dc i r c u i t s ( v l s op h y s i c a ld e s i g n i tm a i n l yp l a n st h es h a p e sa n dl o c a t i o n so ft h em o d u l e s o na c h i p w i t ht h ed e v e l o p m e n to f i c ( i n t e g r a t e dc i r c u i od e s i g n s ，m o r ea n dm o r e 1 s s u e sn e e dt ob ec o n s i d e r e d e s p e c i a l l yw i t ht h ei n c r e a s i n go ft h e o p e r a t ef r e q u e n c y a n dh i g hi n t e g r a t i o no ft h ec h i p ，a r e a ，d e l a y , a n dt e m p e r a t u r ea r e b e e t m ev e r yt o u g h i s s u e si nv l s i d e s i g n t h l st h e s i sh a sd o n es o m er e s e a r c ho nt h ef l o o r p l a n n i n g p l a c e m e n t a l g o r i t h m s u s e di nv l s l p h y s i c a ld e s i g n ，i n c l u d i n gs i m u l a t e d a n n e a l i n g ( s a ) ，t a b us e a r c h ( t s ) e t c a n di ta l s o p r o p o s e da p p r o a c h e st os o l v es o m ep r o b l e m s ，s u c ha s a r e a 0 p t i m i z a t i o n ，w i r e l e n g t h o p t i m i z a t i o n ，c o n g e s t i o no p t i m i z a t i o n t h em a i n c o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w i n g s ： w e p r o p o s e dah y b r i da l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h ma n d t a b us e a r c ha l g o r i t h mt os e a r c ht h eo p t i m a ls o l u t i o ni nf i n i t es o l u t i o ns p a c e t h e s l m u l a t e da n n e a l i n gw a sa p p l i e dt o g e n e r a t en e i g h b o r h o o ds o l u t i o n sa n dt h e b 宰- t r e ew a se m b e d d e dt o r e p r e s e n taf l o o r p l a n t h ep r e o r d e ra n di n o r d e r 8 e q u e n c e so fb * - t r e ea r ea c t e da sat a b uo b j e c t e x p e r i m e n t a lr e s u l t ss h o w e dt h a t o u ra p p r o a c hc a ni m p r o v ea r e au t i l i z a t i o ni ns h o r t e r t i m e a sa m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ( m o p ) ，i ti sd i f f i c u l tf o rf l o o r p l a n n i n g t ob a l a n c ev a r i o u so b j e c t i v e s s i m u l t a n e o u s l yu s i n gt r a d i t i o n a ll i n e a rw e i g h t e d s u ma p p r o a c h t oo v e r c o m et h i sp r o b l e m ，f u z z yr u l e sa n d m e m b e r s h i pf u n c t i o n w e r ee m p l o y e dt oc o m b i n ed i f f e r e n to b j e c t i v e s i t i sac o n v e n i e n tm e t h o dt o c o m b i n ec o n f l i c t i n go b j e c t i v e sa n di ta l s oc a nu s et h ee x p e r th u m a n k n o w l e d g e e x p e r i m e n t a lr e s u l t ss h o w e dt h a tt h i sa p p r o a c hw a ss t a b l ea n de f f i c i e n tw h i c h c o u l do b t a i ne n c o u r a g i n gr e s u l t si n s h o r t e rt i m e t h r o u g ht h ee x p e r i m e n t a l r e s u l t s ，w ec o u l dh a v ea ni n t u i t i v e u n d e r s t a n d i n go fo b j e c t i v e sw i t hv a r i o u s c h a n g e smp a r a m e t e rs e t t i n g s t h i sa p p r o a c hw o u l da l s ob ee x t e n d e dt oh a n d l e o t h e rl a r g es c a l em o p p r o b l e m s 萝i no r d e rt oa v o i dt h er i p 。u pa n d r e r o u t ew h i c hi sat i m i n g c o n s u m i n gp r o c e s s ，w e p r o p o s e dan e wt w o 。s t a g ec o n g e s t i o nr e d u c t i o na p p r o a c hf o rf l o o r p l a n n i n g w e a p p l i e dt h em e t h o do fp r o b a b i l i t y - e s t i m a t i o nt oe v a l u a t et h er o u t i n go fn e t s w e i l a l s om a d eu s eo ft h es t r a t e g yo fc e l l p e r t u r b i n gt oe l i m i n a t et h er o u t i n g c o n g e s t i o n f u r t h e rc o n g e s t i o nr e d u c t i o nw a so b t a i n e db yu s i n go u ra l g o r i t h m ， g u i d e db yc o n g e s t i o n t h ee x p e r i m e n t sr e s u l t ss h o w e dt h a to u ra l g o r i t h mi s e f f i c i e n t ，s t a b l ea n dc a nr e d u c ec o n g e s t i o nl a r g e l y c o m p a r e dw i t ht h et r a d i t i o n a l c o n g e s t i o n d r i v e nf l o o r p l a n n i n g , o u rt w o s t a g ea p p r o a c hc a na l l e v i a t et h e c o n g e s i t o ne f f i c i e n t l yi nm u c hs h o r t e rt i m e k e y w o r d s ：v l s i ；f l o o r p l a n n i n g ；m u l t i o b j e c t i v e ；s t o c h a s t i ca l g o r i t h m ；b * - t r e e i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：矽嘞 e l 期! 竺兰：型 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：黾伏专 导师( 签名) ：尉 日期2 。o t 上石2 ， 武汉理1 二大学硕士学位论文 第一章引言 目前，以集成电路为核心的电子信息产业超过了以汽车、石油、钢铁为代表 的传统工业成为第一大产业，成为改造和拉动传统产业迈向数字时代的强大引 擎和雄厚基石。1 9 9 9 年全球集成电路的销售额为1 2 5 0 亿美元，而以集成电路为 核心的电子信息产业的世界贸易总额约占世界g n p 的3 ，现代经济发展的数据表 明，每1 2 元的集成电路产值，带动了1 0 元左右电子工业产值的形成，进而带动 了1 0 0 元g d p 的增长。目前，发达国家国民经济总产值增长部分的6 5 与集成电 路相关；美国国防预算中的电子含量已占据了半壁江山( 2 0 0 1 年为4 3 6 ) 。预 计未来1 0 年内，世界集成电路销售额将以年平均1 5 的速度增长，2 0 1 0 年将达到 6 0 0 0 8 0 0 0 亿美元。作为当今世界经济竞争的焦点，拥有自主版权的集成电路已 日益成为经济发展的命脉、社会进步的基础、国际竞争的筹码和国家安全的保 障。 1 1 集成电路技术的发展 1 9 5 8 年，t i 开发出全球第一个i c ，意味着i c 时代的正式开始，这给电子 工业界尤其是计算机业带来了巨大变革。集成电路从诞生到现在经历了小规模 集成( s s i ) ，中等规模集成( m s i ) ，大规模集成( l s i ) 三个阶段。现在已进入 超大规模集成( v l s i ) 和特大规模集成( u l s i ) 阶段。1 9 6 5 年，i n t e l 公司的 g o r d o nm o o r e 博士提出了著名的m o o r e sl a w s ( 摩尔定律) ，即集成电路上可 容纳的晶体管数目，约每隔1 8 个月便会增加一倍，性能也将提升一倍，当价格 不变时；或者说，每一美元所能买到的电脑性能，将每隔1 8 个月翻两倍以上。 这些年来，i c 产品集成度不断提升正是遵循着这个规律。 从2 0 0 8 年国际半导体技术发展路线图可以知道，几十年来，半导体工业最 明显的特征是它的产品的更新换代速度非常迅速。大部分的改进和提高都用一 个重要的特征来体现，即：集成电路的最小尺寸不断地呈指数性的迅速缩小。 重要的几种改进趋势的典型范例如表1 1 所示： 武汉理工大学硕士学位论文 表i i 特征尺寸缩小带来的i c 改进趋势 趋势范例 集成度 元件数府片，摩尔定律 成本单位功能的成本 速度微处理器吞吐率 功耗笔记本电脑或手机电池寿命 小巧紧凑 小型和轻型产品 功能 非易失性存储器，图像处理器 传统上看，国际半导体技术发展线路图主要专注于c m o s 技术的按比例缩小。 从2 0 0 1 年开始，对c m o s 工艺按比例缩小的最乐观估计也有很大困难，如m o s 管的沟道长度能否小于9 n m 的水平? 如摩尔定律所述，微处理器和逻辑器需要 基于硅的c m o s 技术。最小尺寸的按比例缩小，使得越来越多的晶体管可以集成 到一个芯片上。这样的系统级芯片( s o c ) 的基本功能是数据存储和数字信号处 理。但是，有许多的功能性需求，例如由传感器实现的功能都无法实现摩尔定律 那样的按比例缩小，在很多情况下，需要使用非c m o s 的解决方案。在未来 s o c ( s y s t e mo nc h i p ) 和s i p ( s y s t e mi np a c k a g e ) 都可以实现互补共存。这些发 展趋势如图l 所示。从图l ：l 【1 1 可以看出，在工业界的发展过程中，在摩尔定律 以外的其它发展的相对比重将随时间越来越大，从而导致了科学领域的多样化 发展。 图l - l 摩尔定律发展方向 2 武汉理1 二大学硕士学位论文 集成电路的设计能力远远跟不上集成电路的增长。图1 2 是硬件和软件设 计随着时间产生的差距图【1 1 。增加计算机辅助设计工具的功能，提高工具的效 率是解决这个矛盾的一种方法。因此集成电路的高速发展对“设计自动化” ( d e s i g na u t o m a t i o n ，d a ) 技术提出了巨大挑战。尤其是i p 模块重用技术， s o c 设计以及超深亚微米工艺为设计自动化技术提出了崭新的研究领域。 1 2v l si 设计流程 图1 2 硬件和软件设计差距图 大规模集成电路( v e r yl a r g es c a l ei n t e g r a t i o n ，v l s i ) 设计周期一般可 以分为以下几个步骤：系统规范说明，功能设计，逻辑设计，电路设计，物理 设计，设计验证，制造，封装和测试【2 _ j 。v l s i 设计可能会在一个步骤中，或在 几个步骤之间反复交替进行。v l s i 电路的设计流程如图1 3 所示。 3 武汉理t 大学硕士学位论文 图1 3v l s i 设计流程 v l s i 物理设计( p h y s i c a ld e s i g n ) 也称为布图设计( l a y o u td e s i g n ) 。 其输入是电路的元件的说明和网表，输出是设计好的版图。即根据电路和 工艺要求完成芯片上单元或功能块的安置，实现它们之间所需要的互连。 由于布图设计的复杂性，它又分为以下几个步骤：划分、布图规划、布局、 总体布线、详细布线和压缩。布图设计流程如图1 4 所示。 物理设计 1剐什 0 布囝规划和布局 i 电路设计10i 芯片制造 l 总体布线 0 详细布 主 l 图1 4 物理设计过程 1 3 布图规划问题面临的挑战 布图规划( f l o o r p l a n n i n g ) 技术主要是由于b b l 模式( b u i l d i n gb l o c k l a y o u t ) 分级设计的需要而产生的。根据自顶向下的设计思想，在结群完成 之后，布图规划根据高一层的设计目标，确定模块的最佳形状和引线端位 4 武汉理丁大学硕+ 学位论文 置。布图规划和布局是布图设计流程中较早的阶段，它们完成的质量对布 线工作的顺利完成乃至最终芯片的面积和性能都有很大影响，尤其在深亚 微米工艺下，早期的布图规划对设计出满足工艺和性能要求的芯片有着极 为重要的意义。 1 3 1 深亚微米工艺下布图规划面临的挑战 问题的规模和复杂性 随着集成电路技术的不断发展，芯片的集成度逐渐增高，布图规划中 的模块数量以及种类也日益增长。布图规划问题已经被证明是一个 n p h a r d 问题，随着问题规模的逐渐增加，布图规划的解空间却急剧增加， 这使耗费的搜索时间增加很多，并且更容易陷入局部极小解。传统的布局 方法已经不能与当前技术工艺下布图规划问题的需要相适应，布图规划算 法在问题规模上提出了更高的要求，算法本身搜索的收敛性也成为布图规 划算法中很重要的因素。因此布图表示方法和解空间的搜索方式也逐步成 为布图规划算法中最根本和最迫切需要解决的问题。 互连和拥塞等性能优化 芯片的设计目标已经从以往单纯地追求芯片面积最小，连线总长度最 短等转向同时要求芯片具有更高性能( 时延小、拥塞小、功耗省) 。性能 已经成为芯片设计者考虑的首要因素，随着特征尺寸的逐渐减小，连线上 的延迟已经大大超过了门延迟，连线上的寄生电容和电阻已经不再是可以 忽略不计的部分了。这样一个趋势使得性能驱动( p e r f o r m a n c ed r i v e n ) 或互 连驱动( i n t e r c o n n e c td r i v e n ) 等算法成为布图设计的热门研究课题。但是， 由于约束条件和限制条件的增加，设计过程中需要考虑的因素也大大的增 加了，因此它的复杂程度变得空前大。更有效的时延驱动性能的算法和时 延性能的估计模型还需要更进一步的深入研究。 在布图布局阶段可布性也是一个需要考虑的问题。虽然在现在的集成 电路工艺中，布线的层数逐渐增加，但是电路设计的高复杂性及其对性能 的高要求使得走线的局部拥挤现象仍不能避免。如果布图布局的结果不能 成功地完成布线，就必须返回到前面的设计步骤，调整参数，重新进行设 计。这样就会推迟产品进入市场的时间或者增加了产品成本，并且如果不 及早考虑，返回修改也有可能不能得到满意的结果。所以，为了提高布线 的布通率，布图规划布局算法必须考虑布局结果的可布性。 5 武汉理工大学硕士学位论文 优化目标离散性 性能驱动的优化问题和几何约束问题具有许多子问题，各个子问题的 优化目标都相对独立，在很多情况下，它们会出现各自优化目标不一致或 相互抵触的情况。因此考虑几何约束和性能驱动的布图规划问题的解空间 非常复杂，它的优化过程也容易陷入局部极小。因此，随机优化过程中好 的搜索策略和设计流程对于求解质量起到了非常关键的作用。 对布图表示方法的依赖性 由于几何约束和性能驱动优化问题一般都是采用随机优化的方法，各 个问题比较依赖于布图表示的性质，从而来设计不同的算法。不同的布图 表示方法不仅影响各个问题的实现方法而且很大程度上影响算法的复杂 度。合理选择有效的布图表示，可以有效地解决布图规划中的几何约束和 性能驱动的优化问题。 1 4 论文主要工作与组织结构 正如前面所述，随着深亚微米工艺的发展，v l s i 设计方法发展的主 要趋势在于不断的进行改变以适应超深亚微米技术带来的各种挑战。在布 图设计的最初阶段，布图规划和布局的质量对于芯片的性能有着显著的影 响。高效的布图规划和布局算法对于布图设计的许多方面都有着非常重要 的作用。针对这个有意义的课题，本文探索超深亚微米工艺条件下，v l s i 布图规划的一些新方法，并且考虑了一些性能驱动的优化方法。具体论文 的组织结构下： 第二章主要介绍超大规模集成电路物理布图布局。 第三章主要介绍混合算法用于布图规划。 第四章介绍了基于模糊逻辑的多目标布图规划。 第五章介绍了基于两阶段最优化的考虑拥塞性能的布图规划。 第六章是总结和展望。 6 武汉理j r 大学硕七学位论文 第二章超大规模集成电路物理布图布局 本章对布图规划布局问题和相关典型的布图布局算法进行了介绍， 首先对布图规划布局给出了问题的描述，然后介绍了布图规划中各种不同 的布图结构及相关的表示方法，最后介绍了布图规划布局中的常用的随机 优化算法。 2 1 布图规划问题的描述 布图规划布局是超大规模集成电路物理设计中的最重要的步骤之一， 布图和布局质量的好坏将直接影响芯片的性能。b b l ( b u i l d i n gb l o c k l a y o u t ) 布图布局的过程就是将一组模块或单元安置在芯片合适的位置上 使得由芯片的面积、线长、拥塞等目标组成的目标函数值达到最优。 随着工艺技术的发展，布图规划布局问题已经从只考虑面积和线长优 化逐渐发展成为多目标多约束同时考虑的问题。其优化目标是多种多样 的，可以是芯片线长，面积，拥塞，时延性能等的组合目标， 其输入一般包括： ( 1 ) 一个由单元或模块组成的集合m = m 1 ，m 2 ，m 。) ，其中每个 模块是有固定边长的矩形或其它形状的硬模块，或是面积固定而长宽比例 可以变动的矩形软模块。每一个布局的模块m i 均含有引线端的集合 p i = p i l ，p i 2 ，】，其中每个引线端p i i 都位于模块的边界上，每个软模 块的宽高比的上界和下界分别为r w i 和r h i ，布图规划算法确定的模块m i 的宽度w i 和高度h i 必须满足r w i sw i h i j 如司记- - - - 知 - ，1知 -：毒j l v o ”o 。v 。一毒4 - - 4 - 4 - -0 点 ：- - 二- - ：i - - f ： 司- - 0 翼 l 、- 对 r q 知- 1- i 知- - ， - -4 - 4 - 一4 - 。 r 知- 。l -i ：_ j l - i - - - - i - - - 图5 2 布线路径模型 3 2 g p 武汉理。r 大学硕七学位论文 5 3 我们的拥塞减小方法 5 3 1 两阶段的最优化方法 传统的拥塞性能的布图规划器般都是基于模拟退火算法。拥塞估计 是一个耗时的的过程，并且同进平衡多个目标比较困难。拥塞受线网的位 置约束比较大。由于早期的随机最优化过程不稳定并且早期的中间结果和 最终结果有很大的差距，因此在早期的随机最优化过程中考虑拥塞将影响 收敛。不同于以前的方法，我们提出了一个新的基于模拟退火的两阶段最 优化方法去解决上面的问题。 在第一个阶段，我们主要是优化面积和线长以便得到一个紧凑的布 局。用于这个阶段的代价函数不包括拥塞代价。因此，为了评估模拟退火 中得到的解，下面的代价函数被用。 c o s t = qa + 1 3w ( 1 ) a 是布图规划后的芯片面积，w 是所估计的总的线长，b 是权重 表示各个目标的重要性。在这个阶段，我们运行文献【5 】中的程序。 在第二阶段，我们主要减小和消除拥塞，使面积和线长增加量尽可能 的小，基于第一阶段得到的布图。这个阶段所用的代价函数包含拥塞。c 是布图中最大的拥塞值，y 是权重。 c o s t - - aa + 1 3w + y c 在第二阶段，当进行布图时，我们的算法保持检查拥塞并消除拥塞。 为了检查布线拥塞，我们用资源估计的方法，以便拥塞结果能够更一般和 通用，不依赖于布线器。为了减小和消除拥塞，我们用拥塞作为机制去指 导布图规划，我们扰动与最拥塞的网格有直接的联系的模块。在我们的方 法中，我们用b 宰t r e e 表示法去表示布图并且用模拟退火去最优化相关目 标。详细的拥塞减小在下面一节介绍 5 3 2 有指导性的拥塞减小 在第一阶段，我们得到一个具有较好的面积和线长的布图。接下来， 我们基于这些结果考虑拥塞，但是在模拟退火中的代价函数中包含拥塞代 价去减小拥塞的随机性比较大，并且这个方法不能很好的去得到最优拥塞 值的布图。因此，我们用拥塞作为一个机制去指导布图规划，这样做更有 效。 3 3 武汉理：i ：人学硕士学位论文 下面是在第二阶段用于拥塞减小的伪代码。 i n p u t ：af l o o r p l a n o u t p u t ：ac o n g e s t i o n d r i v e nb e t t e rf l o o r p l a nw i t hm i n i m a li n c r e a s ei na r e aa n dw i r e l e n g t h ( 1 ) d e t e r m i n et h es i z eo ft h em e s h ( 2 ) c o m p u t e rt h ec a p a c i t yo ft h eg r i d s ( 3 ) f o re a c hn e t ( 4 ) m i n i m u ms p a n n i n gt r e e ( m s t ) ( n e t ) f 5 ) f o re a c ht w o p i ns e c t i o no ft h em s t ( 6 ) c o m p u t e rt h ec o n g e s t i o n o ft h eh o r i z o n t a l e d g ea n d v e r t i c a l e d g e i ng r g c o r r e s p o n d i n gt ot h eb o u n d i n gb o x ( 7 ) f o r e a c h g i r d ( 8 ) c o m p u t et h ec o n g e s t i o no ft h eg a d ( 9 ) i d e n t i f yt h em a xc o n g e s t i o ng r i d ( 1 0 ) f i n dt h en e t sw h i c hp a m i n gt h em a xc o n g e s t i o n 班d ( 1 1 ) f i n dt h em o d u l e sw h i c hh a v i n gt h en e t s ( 1 2 ) p e r f o r ml o c a lc o n g e s t i o nt u n e 在模拟退火中，我们仅扰动那些与最大拥塞网格相关的线网所连接的 模块的邻域模块。终止条件是最大拥塞值小于预先指定的拥塞值或迭代次 数达到预先指定的迭代次数。 lcl _i in i f ia 喘 i i 。一 l 二一r l刿 一r 拦一i 一， 一 一 n e tk 以图5 3 为例，黑色格子是当前最大拥塞的格子。网k 经过格子，因此 我们找到经过网k 的模块a 和b 。困此我们得到两个邻域模块集合 c ，d ， e ) 和 f g h 。我们能够扰动 c ，d ，e ) 和 f ，g ，h 去减小最大的拥塞。 5 4 实验结果 我们在同样的平台上执行了所有的实验：在一个s u nv 8 8 0 工作站上。 两个测试都是基于b 木t r e e 表示法和模拟退火算法【5 1 。五个基准电路被用于 实验来表明我们方法的性能。详细的数据描述如表5 1 所示。用于下面的 实验的代价函数如公式1 所示。权重值d ，1 3 ，y 是我们设置的，对于一般 的例子也是可以用的。为了保证准确性，我们用拥塞1 0 0 1 0 0 的网格模型。 武汉理t 大学硕十学位论文 表5 1 电路参数 c i r c u i t# m o d u l e s# n e t s # p a d s a p t e 99 77 3 x e r o x1 02 0 3 2 h p 1 18 34 5 a m i 3 33 31 2 34 3 a r n i 4 94 94 0 82 2 表5 2 比较运用三种不同方法得到的实验结果( s a c o n g e s t + s a t w os t a g e ) d a t as a c o n g e s t i o n + s a t w os t a g e a r e a w i r e l e n g t m a xr u n t i l l l ea r e aw i r e l e n g tm a xr u n t i m ea r e sw i r e l e n g tm a xr u n t i ( pmh ( 1 1m )c o n g e s t s ( - i m2 )h ( i tm )c o n g e s t s ( 工i m2 )h ( 1 1 玎1 )c o n g e s tm e s z ) ( s )( s )( s ) a p t c 4 9 9 4 6 3 35 4 0 0 5 9o 7 8 92 1 34 8 7 9 9 4 05 2 0 1 6 9o 2 41 4 1 5 9 74 8 4 5 6 9 95 0 7 8 鹤0 2 31 4 0 5 5 06 x c m x2 1 7 3 5 6 l5 1 4 5 2 02 0 1 94 2 72 1 2 0 9 3 05 0 8 6 2 70 4 71 8 2 2 4 32 1 5 6 0 9 85 5 3 8 6 8o 5 12 9 7 8 1 670 h p l 1 0 3 2 0 52 3 3 3 3 61 6 7 41 1 81 2 1 1 8 6 81 9 3 3 3 60 4 59 7 5 1 81 1 2 1 6 6 81 9 8 8 7 60 4 71 5 4 5 6 6o8 a m i 3 31 3 0 9 4 7 66 3 7 0 4 2 6 5 1 2 0 5 31 “9 4 2 07 4 7 1 8 1 3 7 8 7 4 0 21 3 2 9 4 6 86 5 5 7 2 1 2 7 0 8 4 6 a m i 4 94 1 3 0 8 1 71 1 3 9 6 5 21 1 4 88 1 3 64 6 7 8 8 3 3 1 3 6 3 4 4 4o 41 0 0 0 3 84 3 5 3 9 4 41 1 4 8 1 3 60 5 56 8 6 1 660 a v g ll l1 1 0 5 81 0 2 9 90 3 2 2 99 9 8 4 81 0 0 9 60 9 8 1 2o 3 5 16 1 9 3 实验结果如表5 2 所示。表5 2 中列出了最优的面积，线长，运行时 间和最大的拥塞值，这些值都是用拥塞模型得到的。在表5 2 中，我们比 较了相关结果，这些结果是用我们的方法( t w os t a g e ) 和模拟退火( s a ) 得 到的，它的代价函数中不包含拥塞并且结果( c o n g e s t i o n + s a ) 用模拟退火得 到的，代价函数中包括拥塞。 在s a 中，目标仅有面积和线长。不失一般性，我们设置q = 0 5 ，b = o 5 。 这些解是我们第二阶段算法的输入。 在c o n g e s t i o n + s a 中，得到的解所用的代价函数中包含了拥塞代价。 在代价函数中，我们设置q = 0 3 5 ，t 3 = 0 3 5 ，y = 0 3 。在不同的随机数种子下， 基准电路 a p t e ，x e r o x ，h p 被执行1 0 次，并且最好的结果被列出在表5 2 。 由于执行基准电路 a m i 3 3 ，a m i 4 9 的运行时间很长，我们对这两个电路仅 运行了一次。 在t w os t a g e 中，我们用与c o n g e s t i o n + s a 中一样的代价函数，设置a = o 3 5 ，1 3 = 0 3 5 ，y ：0 3 。每一个测试例子被执行1 0 次，用不同的随机数种 子。表i i 列出了不同方法所得到的运得时间和拥塞减小的直接比较，结果 如图5 4 ，图5 5 所示。从实验结果中，我们能够看到我们的方法能够在更 短的时间内，有效地减小拥塞。 3 5 武投理j ：人学顶十学位论文 拥塞减小的有效性：如表所示，撮大捌塞值的减小表明我们的算法能 使屉大的捌塞减小至少5 20 9 1 。减小值是用公式( a b ) b 计算得到的， 其中a 是两阶段的拥塞结果，b 是用s a 得到的拥塞结果。从图54 我们 可以看出，两阶段的方法对比不考虑拥塞的方法能够很大程度上减小拥 塞，并且我们的方法的结果与传统的考虑拥塞的布图规划的结果具有可比 性。 效率：正如表52 所示我们算法能够减小至少8 36 5 9 的运行时间。 减小值也是同样用上面的公式计算出来的。从图5 4 中，我们可以看出， 两阶段的方；去对比传统的考虑拥塞性能的巾图规划具有可比性。从表52 和图5 5 ，我们能够看到两阶段的方法同样比传统的考虑拥塞性能的布图 规划速度更快。 稳定性：正如表52 所示，最后行( a v 9 1 比较了对应于各自目标的平 均增加值。最大拥塞值的减小表明我们的算法能够很大程度上减小拥塞但 是面积和线长增加很小。它们也表明我们得到了较好的结果，只是在运行 时间上有恶化。 上面的实验结果的分析表明我们的算法是有效的，稳定的，并且能够 很大程度上减小拥塞。对比传统的拥塞性能的布图规划，我们的二阶段的 方法能够在更短的时间内，有效的减小拥塞。 i 缸c o n g e s t i o n 熊。，。卜一p ：黑。r 一 = = = = = = = 2 = = ! + 。一 爿 1 引h际 即“姗l岫 钔i 3 3a n l 4 9 图5 4 比较最大拥塞值 ( s a c o n g e s t + s mt w os t a g e ) 口“ ic e 口t s h r u n t l _ 1 1 e ( s 盎；“琶建行黼“4 9 武汉理工人学硕：学位论文 5 5 小结 在这篇文章中，我们提出了一个新的两阶段最优化布图规划方法。我们 利用了单元扰动的策略去消除布线拥塞。更进一步的拥塞减小是用我们的算 法得到的，它用拥塞作为一个度量去指导布图规划。我们的两阶段算法能够 有效的地减小拥塞并且较好地保持解中面积和线长的质量。这个方法不仅能 够减小布图规划中的最大拥塞值同时也能够进行布图规划。实验结果表明我 们的方法在更短的时间内，能够较大程度上减小拥塞值并且保留初始布图的 性能。实验结果同时也表明我们的方法是稳定的。 3 7 武汉理t 人学硕l ：学位论文 6 1 总结 第六章总结和展望 本文研究的课题是国家自然科学基金，清华信息国家实验室( 筹) 学科 交叉基金项目中的一部分。 鉴于当前国际上布图规划和布局的发展趋势，我们针对超深亚微米工艺 下布图规划设计面临性能和约束方面的挑战提出了一些解决方案。我们对大 规模集成电路物理设计中的布图布局算法进行了研究，包括模拟退火算法， 禁忌搜索等方法，并对布图中的一些目标，如：面积、线长、拥塞等进行了 考虑，提出了一些解决方法。 本文的贡献主要有： 在模拟退火算法和禁忌搜索的基础上提出了一种混合算法用于在有 限的解空间中搜索最优解，利用模拟退火来产生邻域解，同时利用 b 一t r e e 表示法来表示布图，利用b 幸t r e e 的前序和中序序列作为禁忌 对象。实验结果表明我们的方法能够在更短的时间内改进面积的利用 率。 在处理多目标最优化问题时，用传统的线性加权函数去同时平衡不同 的目标很困难。为了克服这个问题，模糊准则和隶属函数被引入去结 合不同的目标。它是一个很方便的方法去结合冲突的目标并且能够利 用专家知识。实验结果表明，这个方法稳定，有效，能在更短的时间 内得到令人满意的解。通过实验结果，我们能够对参数设置的变化有 一个直观的理解。这个方法也能够被延伸去解决其它大规模多目标最 优化问题。 为了避免耗时的拆线重布，提出了一个新的二阶段布图规划方法用于 拥塞最优化。我们采用了概率估计模型去评估线网的拥塞程度，同时 利用单元的扰动策略去消除布线拥塞。在拥塞指导下，利用我们的算 法，对拥塞进行进一步的减小。实验结果表明我们的算法是有效的， 稳定的并且能够非常大的减小拥塞。对比传统的拥塞性能的布图规 武汉理工大学硕： ：学 7 = 论文 划，我们的二阶段方法能够在更短的时间内有效地减轻拥塞。 随着系统芯片设计方法和知识产权( i p ) 模块技术在集成电路设计中的 不断发展和应用，布图规划日渐成为超大规模集成电路( v l s i ) 物理设计的 关键环节，其完成的质量对后续设计工作的顺利完成乃至最终芯片的面积和 性能的影响非常之大。 6 2 进一步的工作展望 在布图规划阶段考虑时延和拥塞变得十分重要。因为这一阶段的结果决 定了与电路的结构，时延和布通率性能有关的问题，而且随着集成电路设计 的发展，越来越多的问题需要去被考虑并且大多数与找最优的布图规划相关 的问题是n p 难问题。在布图规划阶段，对于具有多目标的最优化问题，用 传统的线性加权和方法去平衡不同的目标比较困难。因此，我们可以在布图 阶段考虑时延和拥塞。我们也可以基于模糊逻辑提出新的代价函数去解决多 目标最优化问题并且基于智能算法和模糊逻辑去提出混合方法。我们期望可 以在设计的前期考虑一些性能约束目标并且尽可能的减小时间和资源。 在本文中，我们在评价拥塞时，是用的概率估计模型计算的拥塞值并且 我们仅能在详细布线之后才能得到准确的拥塞值。因此，我们期待能设计出 更准确的拥塞模型，并运用它来进行拥塞评估。提出的混合算法虽然可以得 到较满意的结果，但是其中还有许多需迸一步研究的地方如：禁忌对象的选 取，候选长度的选取等。在计算时延时，基于路径的方法，准确但是计算代 价大。基于线网的方法，速度快但是准确性比较低。所以，我们也可以试着 基于这两种方法去提出一个混合模型，用来计算时延，这可能会得到比单独 用某一种方法得到的时延值更准确。 武汉理工大学硕士学位论文 参考文献 【1 】s e m i c o n d u c t o ri n d u s t r ya s s o c i a t i o n ，“i n t e r n a t i o n a lt e c h n o l o g yr o a d m a pf o rs e m i c o n d u c o t r s ， 2 0 0 7 - 2 0 0 9 ，【o n l i n e ：h t t p ：p u b l i c i t r s n e t e 2 洪先龙，严晓浪，乔长阁超大规模集成电路布图理论与算法 m 北京：科学出版社， 1 9 9 8 ：2 4 【3 】s h e