（电磁场与微波技术专业论文）超大规模集成电路布局算法研究.pdf

占誊銮望盔主兰圭兰垡丝苎 超大规模集成电路布局算法研究 摘要 当今信息时代，作为电子信息技术发展的核心和基础，集成电路得到了迅猛的发 展，这除了由于半导体工艺技术、设备、原材料等方面的不断改进之外，计算机辅助 设计技术的采用也是一个重要原因。然而，随着半导体制造工艺的特征尺寸越来越小， 芯片的集成度越来越大，电路的工作频率越来越高，布图工艺越来越复杂，这些发展 都对集成电路计算机辅助设计技术提出了新的要求。布局作为集成电路版图设计中一 个基本而且非常重要的环节，也面临着严峻的挑战，在大规模( 上百万门的单元需要 布局) 和复杂的设计约束( 时延、噪声、功耗、拥挤度等) 条件下。如何获得高质量 的布局结果同时花费较少的布局时间非常关键。本文正是围绕这些问题展开计算机辅 助设计领域内的超大规模集成电路布局算法研究工作的，通过改进现有的方法以及提 出新的布局算法，尝试更好地解决当前和未来集成电路设计中的些问题。 首先介绍了本文的研究对象标准单元设计模式和基本的布局理论，然后对传 每5 以线网总长为优化目标的基本布局算法进行了分类分析。在此基础上，提出了一 个基于改进等分节点法的启发式迭代优化布局算法，该算法对原有的等分节点法进行 了改进，使得单元的目标位置在更广的范围内得到搜寻，从而提高了迭代法的优亿质 量，而且通过使用启发式策略使迭代优化跳出局部最优，设定合理的局部寻优次数来 有效地终止布局优化，并采用记忆装置记录最优布局结果，使整个优化布局过程在没 有花费过多时间的情况下，得到了较充分的迭代优化。实验表明，与接近全局壤优的 7 抽v o l f 7 0 布局算法相比，该算法能够获得更好的布局质量。 针对超大规模集成电路线长优化布局中布局质量和花费时间的严峻挑战，讨论了 面向高复杂度、大规模问题的有效解决策略分级设计方法，分析了基于分级设计 的各种超大规模集成电路线长优化布局算法。在此基础上，提出了一个基于划分的迭 代优化布局算法，该算法采用分级设计将大规模的布局问题分拆，借鉴好的递归划分 上噼交通大掌博士学位论文 方法将电路分解，采用和改进结群、终端传递等技术提高了划分质量，并且结合本文 提出的启发式迭代优化方法在划分所得的各个子电路内进行并行布局优化，在保证布 局质量的同时提高了布局速度。实验表明，与当前流行的f e n gs h u i 布局工具相比， 该算法在花费稍长一点的时间内获得了更好的布局质量。 时序约束作为保证电路正常工作性能的一个重要因素，本文讨论了以路径时延为 优化目标的布局算法。曹先介绍了有关时序问题的基本知识，分析了互连线时延的估 算模型，并对当前的各种时延驱动布局算法进行了分类分析。在此基础上，提出了一 个时延驱动布局算法，该算法基于对电路时延图的拓扑结构分析，将优化路径时延的 问题转换成优化路径上单元位置的问题，通过建立优化单元位鹭的队列链表，采用一 种新的等分节点法寻找路径上单元的目标位置，使得关键路径的时延得到了有效地减 小，路径时延的分布更加合理。在优化路径时延的同时还结合了优化线长的布局算法， 在获得好的路径时延优化效果的同时，能够尽量保留原有已取得的好的线长优化效 果，使两种布局优化目标能够有机地结合。 在深亚微米及更先进的工艺条件下，芯片的设计密度问题变得严峻起来，它会导 致对布线资源需求的大幅度增加，当芯片某些区域内的布线资源无法满足实际的走线 需要时，就会迫使线网绕道而行从而恶化设计性能，甚至无法实现1 0 0 布通率，造 成布线拥挤，因此本文对以布线密度为优化目标的拥挤度驱动布局算法进行了研究。 首先介绍了布局阶段使用的布线密度分析方法和常见的布线密度估计模型，在对现有 的各种拥挤度驱动布局算法分析的基础上，提出了一个用于布局后处理的拥挤度驱动 布局算法，该算法对原有的线网边框布线估计模型进行了改进，在保留估算速度| 陕， 易于编程实现等优点的同时，提高了分析布线密度的精度：在优化布线拥挤度时，提 出以线网为中心，通过逐步扩大或者缩小布线拥挤区域内线网边框尺寸的方法，最终 达到降低布线拥挤度的目的。实验结果显示，电路的布线溢出总量和布线溢出峰值都 明显减小，电路的布线拥挤情况得到了明显的缓解。 最后，将本文布局算法的研究成果进行了软件实现，开发了具有自主知识产权的 布局自动设计工具。论文首先介绍了布局程序系统的结构框架，然后针对系统中各个 软件模块分别进行了解释和说明，并给出了用户界面和实际电路布局结果的显示。该 布局工具既可以与工业界其它布图工具进行无障碍衔接，实现混合运用，也可以用于 。，! 苎竺竺! 竺! ! ! 笪墼篓鐾篓鐾鐾婆。，。，：。一 学术研究，具有很好的可扩展性。 关键词：计算机辅助设计，超大规模集成电路，布局算法，划分，时延驱动布局， 互连线，拥挤度驱动布局 ! 竺苎! 竺! ! 曼! ! ! 三鐾型鳖墼生箜鍪垒，：，。：一 s t u d yo np l a c e 嗄e n ta l g o r 【t h m0 fv e r yl a r g e s c a l ei n t e g ra t e dc i r c u i t s a b s t r a c t a tt h ea g eo fi n f o r m a t i o n ，a st h ec o r ea n df o u n d a t i o no fe l e c t r o n i ca n di n f o r m a t i o n t e c h n o l o g y , i n t e g r a t e dc i r c u i t sh a v eb e e nr a p i d l yd e v e l o p e d i ti sn o to n l yo w i n gt ot h e c o n t i n u o u si m p r o v e m e n ti ns e m i c o n d u c t o rf a b r i c a t i o nt e c h n i q u e ，e q u i p m e n t s ，m a t e r i a l s ， e t c ，b u ta l s oo w i n gt ot h eg e n e r a la d o p t i o no fc o m p u t e ra i d e dd e s i g n ( c a d ) h o w e v e r , 奶t ht h em i n i m u mf e a t u r es i z es c a l i n gd o w n ，t h ec h i pi sm o r ec o m p l e x ，t h ew o r k f r e q u e n c yo fc i r c u i ti sm u c hh i g h o ra n dt h ep h y s i c a ld e s i g ni sm o r ed i f f i c u l t a l lo f t h e s e c a l lf o rt e c h n i c a li n n o v a t i o ni nc a dt ow e l ls a t i s f yt h er e q u i r e m e n to fi n t e g r a t e dc i r c u i t d e s i g n p l a c e m e n ti sa ni m p o r t a n ts t e po fp h y s i c a ld e s i g n i t i sa l s of a c i n gs e v e r e c h a l l e n g e s i ti sv e r yc r i t i c a lh o wt oo b t a i nah i g hq u a l i t yp l a c e m e n tr e s u l t 、v i t l ll i t t l e m n n i n gt i m eu n d e rt h ec o n d i t i o n so fl a r g es c a l e ( m o r et h a nam i l l i o nc e l l sn e e dt ob e p l a c e d ) a n dc o m p l e xd e s i g nc o n s t r a i n t s ( o fd e l a y , n o i s e ，p o w e rc o n s u m p t i o n ，c o n g e s t i o n ， e t c ) i nt h i st h e s i s ，w es t u d yo ns e v e r a lp r o b l e m si na u t o m a t i cp l a c e m e n t s t a n d a r dc e l ld e s i g nm o d e la n de s s e n t i a lp l a c e m e n tt h e o r ya r ef i r s ti n t r o d u c e d t h e n t h et r a d i t i o n a lw i r e l e n g t hd r i v e np l a c e m e n ta l g o r i t h m sa r ec l a s s i f i e da n da n a l y z e d b a s e d o nw h i c h ，ah e u r i s t i ci t e r a t i v ep l a c e m e n tb a s e do ni m p r o v e dt w oe q u a lt e r m i n a lp a r t i t i o n ( t e t p ) m e t h o di sp r o p o s e d ，w h i c hp r o v i d e sam o r ef l e x i b l ea n de f f i c i e n tc e l l l o c a t i o n a d j u s t m e n ts c h e m ea n dm o r ee x t e n s i v es e a r c h i n gs c a l ef o rb e t t e r i t e r a t i v ep l a c e m e n t o p t i m i z a t i o nt h a nt 1 1 e1 1 巳t pm e t h o d an e w h e u r i s t i ca l g o r i t h mb a s e do nl o c a lo p t i m i z a t i o n i sc o m b i n e dw i t ht h ei m p r o v e dt e t pm e t h o dt oi m p r o v et h ep l a c e m e n t t h r o u g hs e t t i n ga r e a s o n a b l el o c a lo p t i m i z a t i o nn u m b e rt ot e r m i n a t eo p t i m i z a t i o np r o c e s sa n dar e c o r d e rt o 上海交通大学博士学位论文 s t o r et h eb e s ti t e r a t i v eo p t i m i z a t i o nr e s u l t ，t h ep l a c e m e n ts t a t eh a sb e e n o p t i m i z e d s u f f i c i e n t l yw i mn o tal o n gt i m e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep l a c e m e n tq u a l i t yo f o u r si sm u c hb e t t e rt h a nt i m b e r w l o f 7 0w h i c hc a no b t a i nn e a rg l o b a l o p t i m i z a t i o n p l a c e m e n t f a c i n gt h es e v e r ec h a l l e n g e so f p l a c e m e n tq u a l i t ya n dr u n n i n gt i m ei nv e r yl a r g es c a l e i n t e g r a t e dc i r c u i t s ，h i e r a r c h i c a lm e t h o d o l o g yi sag o o ds o l u t i o n s e v e r a lw i m l e n g t hd r i v e n p l a c e m e n ta l g o r i t h m s b a s e do nh i e r a r c h i c a lm e t h o da r e a n a l y z e da n da ni t e r a t i v e o p t i m i z a t i o np l a c e m e n ta l g o r i t h mb a s e do np a r t i t i o n i n gi sp r e s e n t e df o rv e r yl a r g es c a l e c i r c u i t s i nt h i sa p p r o a c h ，ah i e r a r c h i c a lp a r t i t i o n i n gb a s e do nan e wp a r a l l e lc l u s t e r i n g t e c h n i q u ei sa d o p t e dt od e c o m p o s ec i r c u i t si n t o s e v e r a ll e v e ls u b c i r c u i t s d u r i n gt h e p a r t i t i o n i n gp h a s e ，as i m i l a rt e c h n i q u et o t e r m i n a lp r o p a g a t i o n i sp r e s e n t e dt oi m p r o v e t h eq u a l i t yo fp a r t i t i o n i n g i ne a c hl e v e ls u b - c i r c u i t s ，o u rh e u r i s t i ci t e r a t i v eo p t i m i z a t i o n m e t h o di su s e dt op e r f o r mp a r a l l e lp l a c e m e n to p t i m i z a t i o n ，s ot h a tr u n n i n gt i m ec a nb e s a v e dw h i l eg u a r a n t e e i n gp l a c e m e n tq u a l i t y e x p e r i m e n t a r e s u l t ss h o wt h a to u rp l a c e m e n t a l g o r i t h mp r o d u c e sab e a e rt o t a lw i r el e n g t ht h a nt h a to ff e n gs h u iw i t hal i t t l el o n g e r c p ut i m e b e c a u s et i m i n gc o n s t r a i n to nc r i t i c a lp a t h sh a sb e c o m eac r i t i c a lf a c t o ri nd e t e r m i n i n g c i r c u i tp e r f o r m a n c ea n dr e l i a b i l i t y , t i m i n gd r i v e np l a c e m e n th a sb e e na ni m p o r t a n ts t e pi n p h y s i c a ld e s i g no fc i r c u i t s f i r s t ，p r i m a r yk n o w l e d g ea b o u tt i m i n gp r o b l e ma n ds e v e r a l t r a n s m i s s i o nd e l a ym o d e l sa r ei n t r o d u c e d t h e nv a r i o u st i m i n gd r i v e np l a c e m e n tm e t h o d s a r ec l a s s i f i e da n da n a l y z e d b a s e do nw h i c h ，an o v e lt i m i n gd r i v e np l a c e m e n ta l g o r i t h mi s p r o p o s e d i nt h i sa l g o r i t h m ，t h eo p t i m i z a t i o nf o rp a t hd e l a yi st r a n s f o r m e di n t o c e l l l o c a t i o no p t i m i z a t i o n p a t ht o p o l o g i e sa r ep a i dm u c ha t t e n t i o na n da ne f f e c t i v et e t p m e t h o di sa p p l i e dt of i n dc e l lt a r g e tl o c a t i o n s d u r i n gt h eo p t i m i z a t i o nf o rc r i t i c a lp a t h d e l a y ，w i r e l e n g t hd r i v e no b j e c t i v ei sa l s oi n t r o d u c e di nt h ep l a c e m e n t ，s ot h a tag o o dr e s u l t o ft o t a lw i r e l e n g t h c a l lb er e s e r v e dw h i l eo b t a i n i n ga no p t i m a lc r i t i c a l p a t hd e l a y e x p e r i m e n t a lr e s u l t ss h o w t h a tt h el o n g e s tp a t hd e l a yh a sb e e nd e c r e a s e de f f i c i e n t l ya n d t h ed i s t r i b u t i o no f a l lp a t hd e l a y si sm o r er e a s o n a b l ea f t e rt i m i n go p t i m i z a t i o np l a c e m e n t 上海变通大学博士学位论文 a st e c h n o l o g ya d v a n c e sa n dc o m p l e x i t yo fs y s t e mi n c r e a s e s ，r o u t i n gc o n g e s t i o n p r o b l e mh a sb e c o m em o r ea n dm o r ei m p o r t a n t ap l a c e m e n tw i t hw i r e l e n g t ho p t i m i z a t i o n w i l lo f t e nl e a dt oal a r g en u m b e ro fn e t se x i s t i n gi ns o m el o c a lr e g i o n s ，w h i c hc a nc a u s e t h ed i f f i c u l t yo f1 0 0 r o u t a b i l i t y t h e r e f o r e i ti sv a l u a b l et oc o n s i d e rr o u t a b i l i t ya n d r e d u c t i o no fc o n g e s t e dr e g i o n si nt h ep l a c e m e n ts t a g e c o n g e s t i o na n a l y s i sa n dr o u t i n g e s t i m a t i o nm o d e l su s e di np l a c e m e n tp h a s ea r ef i r s ti n t r o d u c e d t h e nb a s e do nt h ea n a l y s i s o fv a r i o u s c o n g e s t i o n d r i v e n p l a c e m e n ta l g o r i t h m s ，ap o s t l i l a c e m e u tc o n g e s t i o n o p t i m i z a t i o nm e t h o di sp r o p o s e d i te s t i m a t e sr o u t i n gc o n g e s t i o nw i t han e wi m p r o v e d b o u n d i n gb o xm o d e lw h i c hc o r r e l a t e sw i t ht h ea c t u a lr o u t i n gm o r er e a s o n a b l et h a nt h e t r a d i t i o n a lb o u n d i n gb o xm o d e l i nt h ep r o c e d u r eo fc o n g e s t i o nr e d u c t i o n ，an e t c e n t r i c t e c h n i q u ei s u s e dt og u i d en e tm o v i n g b yf lp r o c e s so fe x p a n d i n ga n ds h r i n k i n g e x p e r i m e n t a lr e s u l t ss h o wt h a tt h er o u t i n gc o n g e s t i o n si nc i r c u i t sh a v eb e e nd e c r e a s e d d r a m a t i c a l l y , w h i c hd e m o n s t r a t e st h ee f f e c t i v e n e s so f o u ra p p r o a c h t h ea b o v ep l a c e m e n ta l g o r i t h m sa r ei m p l e m e n t e du s i n gs o f t w a r ep r o g r a ma n d a u t o m a t i cp l a c e m e n tt o o li sd e v e l o p e d t h et o o lh a sf r i e n d l yi n t e r f a c ew i t ho t h e ri n d u s t r i a l p h y s i c a ld e s i g nt o o l s ，s ot h a tt h e yc a l lc o m b i n ew i t he a c ho t h e r i na d d i t i o n ，i tc a nb eu s e d i na c a d e m i cr e s e a r c hw i t hag o o de x p a n s i b i l i t y k e yw o r d s ：c o m p u t e ra i d e dd e s i g n ，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 ，p l a c e m e n t a l g o r i t h m ，p a r t i t i o n i n g ，t i m i n g d r i v e n p l a c e m e n t ，i n t e r c o n n e c t ，c o n g e s t i o n d r i v e n p l a c e m e n t 上海交通大学学位论文答辩决议书 申请者程锋 j l 所在学科( 专业) 电磁场与微波技术 i 论文题目超大规模集成电路布局算法研究 i 答辩日期 2 0 0 5 - 0 4 - ii 9 答辩地点 l 上海交通奄掌条鍪袁主楼，三楼f 答辩委员会成员 担任职务0 姓名 职称所在工作单位备注 签名i 主席 i | 李英教授上海大学通信工程系无 。兹嚣 i 委员i l 安同一教授华东师范大学无 移一i 锚一i 委员 | f 沈秀英 教授上海微系统所无 沼程兰i 委员 l i 金荣洪 教授上海交通大学无 扩韧气i 委员 l l 周希朗l教授 上海交通大学无 彳协朋 评语和决议： f 程锋同学的博士论文涉及超大规模集成电路布局算法研究。版图设计中的布局阶段是 集成电路设计中的一个重要环节，随着集成电路规模的增大，电路工作频率的提高，布局 算法也需要更新。程锋同学的主要创新性工作：1 针对传统的以线网总长为目标的布 局，提出了一个基于改进等分节点法的启发式迭代优化布局算法，提高了优化质量。2 针对超大规模集成电路线长优化布局，提出了一个基于划分的迭代优化布局算法，与当前 的f e n gs h u i 算法相比，花费稍长时间，获得了更好的布局质量。3 针对电路设计中的 时序约束问题，提出了个时延驱动布局算法，使关键路径时延减小，路径时延分布更合 理。4 针对布线拥挤问题，提出了一个布局后处理的拥挤度优化布局算法，使电路的布 线拥挤情况得到明显改善，提高了走线布通率。另外，根据以上成果，开发出具有自主知 识产权的布局自动设计工具软件，可与工业界其它布图工具进行无障碍衔接，具有很好的 可扩展性。博士论文反映了程锋同学具有扎实的基础和专业知识，具有较好的外语和计算 机应用能力，具备独立从事研究工作的能力。论文条理清楚，数据完整，在答辩中能正确 回答问题，答辩委员会通过无记名投票，一致通过答辩，并建议校学位委员会授予工学博 士学位。 揪躲： 一臌席旗徽， 如。舞“月，日 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：程肆 日期：弘够年4 月i 中日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密d 。 ( 请在以上方框内打“4 ”) 学位论文作者签名： 径锋 日期：；。哕年* 月i q 臼 坛 相么溯 名 年 獬 洱 教 誊 期 占鎏塞望查芏堡主兰堡婆兰 1 1 研究背景 第一章绪论 当今信息时代，电子信息技术作为强大的社会生产力，在推动经济发展、社会产 业结构和生活方式的变革中的作用日益增大。其中，集成电路( i n t e g r a t e dc i r c u i t 。i c ) 起着十分重要的作用，它是电子信息技术发展的核心和基础。集成电路的迅速发展已 经改变了电子技术的面貌，并且对一系列科学技术，甚至人们的同常生活都产生了强 烈的影响“j 。 集成电路从6 0 年代开始，经历了小规模集成( s s i ) 、中规模集成( m s i ) 、大规 模集成( l s i ) 的发展阶段，目前已经进入超大规模集成( v l s i ) 和甚大规模集成( u l s i ) 阶段。传统上，一般把含有1 0 4 至1 0 6 个甚至更多晶体管或3 0 0 0 以上个门单元的i c 称为v l s i 2 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 ，s i a ) 从1 9 9 2 年 开始研究并发布国家半导体技术发展路线报告( n a t i o n a lt e c h n o l o g yr o a d m a pf o r s e m i c o n d u c t o r ，n t r s ) ，揭示半导体工业在今后1 5 年的发展趋势和技术路线，该协会 于1 9 9 7 年4 月扩展到包括欧洲、日本、韩国和台湾在内的世界范围，从此每年给出 国际半导体技术发展路线报告( 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 t o r ， i t r s ) 。表1 1 列出了2 0 0 3 年i t r s 中的部分数据【3 】，从表中可以看出，半导体的最 小加工工艺线宽已经进入纳米级( 1 0 0 纳米以下) ，并且继续以大约每三年为原有0 7 倍的速度减小，例如2 0 0 3 年的最小工艺线宽为l o o n m ，到2 0 0 6 年时为7 0 n m ( 1 0 0 n m x 0 7 ) 。同时，芯片的集成度不断提高，以微处理单元( m i c r op r o c e s s o ru n i t ， m p u ) 为例，它从最初1 9 7 0 年4 位m p u 包含2 0 0 0 个晶体管的规模【4 1 发展到当前 6 4 位m p u 可包含大约5 5 3 百万个晶体管的规模。另外，芯片内部的工作速度已经进 入g h z 时代，布线层数也在不断地增加。 ! 竺竺，。，。皇。：童墼鐾蛰堡篓丝些童，：。，。，。一 表1 - 12 0 0 3 年i t r s 部分数据 t a b l e1 - 1p a r to f d a t ai ni t r so f 2 0 0 3 年份 2 0 0 32 0 0 42 0 0 52 0 0 62 0 0 72 0 0 82 0 0 9 最d , i 艺线宽( r 蚰) 1 0 09 08 07 06 55 75 0 微处理单元集成度 4 3 95 5 36 9 78 7 8 1 ，1 0 61 ，3 9 31 ，7 5 6 ( 百万晶体管) 工作频率( m h z ) 2 ，9 7 6 4 1 7 1 5 , 2 0 46 ，7 8 3 9 2 8 5 1 0 ，9 7 2 1 2 3 6 9 布线层数 9 1 3 1 0 1 4 1 1 1 51 1 1 51 1 1 51 2 1 61 2 1 6 年份2 0 1 0 2 0 1 2 2 0 1 32 0 1 52 0 1 62 0 1 8 最d , i 艺线宽( n m ) 4 53 53 22 52 21 8 微处理单元集成度 2 ，2 1 2 3 , 5 1 1 4 4 2 4 7 0 2 2 8 ，8 4 8 1 4 0 4 5 ( 百万晶体管) 工作频率( m h z ) 1 5 0 7 92 0 0 6 5 2 2 9 8 03 3 ，4 0 3 3 9 ，6 8 35 3 。2 0 7 布线层数1 2 。1 6 1 2 一1 6 1 2 1 6 1 3 1 7 1 4 1 81 4 一1 8 集成电路之所以得到如此迅速的发展，除了半导体工艺技术、设备、原材料等方 面的不断改进之外，设计技术的革新也是重要原因之一。这一革新技术主要表现在全 面采用了计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) 技术。因为事实上，集成 电路发展到现在已经十分复杂，要在几十平方毫米硅片上完成线条只有零点几个微米 的上百万门器件的整个电子系统设计，只依靠手工设计是完全不可能的，必须借助计 算机辅助技术和工具诤j 。 集成电路的发展对c a d 技术不断提出新的要求，以满足日益提高的设计需求； 相应地，c a d 技术的发展又使得集成电路设计向着更广( 产品种类越来越多) 、更快 ( 设计周期越来越短) 、更准( 一次成功率越来越高) 、更精( 设计尺寸越来越小) 、 更强( 9 - 艺适应性和设计自动化程度越来越强) 的方向发展【6 】【。 图1 - 1 是一个典型的集成电路设计流程，几乎在其中的每个设计环节和整个设计 过程都普遍用到c a d 技术和工具。其中， l a y o u t ) 阶段是一个极其重要的设计环节， 版图设计即物理设计( p h y s i c a ld e s i g n ，o r 也是最费时的。该阶段的设计任务是根据 ! ：烹，。皇竺! 些窖坠箜坠篓坠鳖：，：，。：一 逻辑和电路功能要求以及工艺制造的约束条件( 如线宽、线间距等) ，完成电路中单 元的摆放和互连，最终形成设计的掩膜图。版图设计的输入是电路的元件说明和网表， 输出是设计好的版图。 规范说明 行为描述 结构表示 结构表示 版图表示 集成电路 图1 - 1 集成电路设计流程【9 】 f i g 1 - 1f l o wc h a r to fi cd e s i g n 对于规模较小的集成电路来说，由于集成度低，版图可以人工完成：但是随着集 成电路规模的不断扩大，连线众多，版面图形极其复杂，如果完全由人工设计不仅需 要花费大量的时间，而且不可避免存在人为的差错失误，以至无法完成设计，因此版 上海交通大学博士学位论文 图设计无疑要借助c a d 工具。由于版图设计的复杂性，通常又将其分为若干个子过 程，图1 2 是版图设计流程。 图1 - 2 版图设计流程【9 】 f i g 1 - 2f l o wc h a r to f p h y s i e a ld e s i g n 表1 1 数据显示，半导体制造工艺的最小线宽越来越小，芯片的集成度越来越大， 电路的工作频率越来越高，布图工艺越来越复杂，这些发展对c a d 技术都提出了新 的要求和挑战。例如，在高时钟频率下如何保证电路满足时延约束要求，在高集成度 的电路中如何满足设计的低功耗要求，在离密度芯片内如何保证1 0 0 的布通率等等。 这些不断出现在c a d 领域的新问题都是值得认真深入研究的，从而更好地指导和辅 助集成电路设计。本文研究的内容是c a d 领域内的超大规模集成电路布局算法，研 究的目的是通过改进现有的方法以及提出新的布局算法，尝试更好地解决当前和未来 集成电路设计中的一些问题。 上海交通大学博士学位论文 1 2 研究现状 1 2 1 引言 布局算法完成的任务是在满足各项电学和工艺要求的条件下，在给定区域内( 或 尽可能小的区域内) 互不重叠地安置电路中的所有单元，并且尽可能好地满足单元互 连的要求。电路的布局是版图设计中一个基本而且非常重要的环节，因为它直接影响 着电路的设计目标，如芯片面积、布通率( r o u t a b i l i t y ) 以及时序( t i m i n g ) 等。 在过去二十多年的时间里，布局算法得到了广泛的关注和研究，并且产生了大量 的科技文献和有效的布局工具【1 0 】【l l 】。i e e e 有专门的刊物讨论包括布局在内的集成电 路设计自动化问题，如i e e et r a n s a c t i o n so nc o m p u t e ra i d e dd e s i g no fi n t e g r a t e d c i r c u i t sa n ds y s t e m s ，c i r c u i t sa n ds y s t e m s 等。国际上每年就此专题要举行多个研讨会， 如i e e ep r o c e e d i n gd e s i g na u t o m a t i o nc o n f e r e n c e ，i n t e r n a t i o n a lc o n f e r e n c e c o m p u t e r - a i d e dd e s i g n ，a s i aa n d s o u t hp a c i f i c d e s i g na u t o m a t i o nc o n f e r e n c e ， i n t e r n a t i o n a ls y m p o s i u mo np h y s i c a ld e s i g n 等。国外许多大学的电子工程系和计算机 科学系都有这一研究领域的研究小组，如u n i v e r s i t yo fc a l i f o r n i aa tl o sa n g e l e sa n d s a nd i e g o l l 孙，u n i v e r s i t yo f b i n g h a m t o n l l3 1 ，n o r t h w e s t e r nu n i v e r s i t y t l 4 】等。国内的清华大 学、复旦大学、上海交通大学、浙江大学等高校也都设有专门的教研室一直从事该领 域的研究和教学工作。 虽然许多文献提出的布局算法都相当成功地应用于当时的实际电路设计，但是随 着集成电路规模的扩大，深皿微米( d e e ps u b - m i c r o n ，d s m ) 工艺成为主流，这些布 局算法和布局工具已经不再那么高效，有的甚至完全不能适用，因此需要研究和开发 新的布局方法和工具，从而解决版图设计中出现的新问剐”1 1 1 6 】。 当前布局方法面临两大严峻的挑战：大规模的设计尺寸( 上百万门的单元需要布 局) 和复杂的设计约束( 时延、噪声、功耗、拥挤度等) 。研究布局方法的目的主要 集中在两个方面：针对各种优化目标，提高布局的质量和减少布局的花费时间1 1 7 】。 本文正是围绕这些问题展开布局算法研究工作的。 占鎏塞鎏盔兰兰主兰丝鲨苎 1 2 2 研究方法概述 本文涉及的布局算法研究主要集中在三个方面的优化目标( o p t i m i z a t i o n o b j e c t i v e ) 上：线网总长、路径时延以及布线密度。它们都是当前正在研究和急待解 决的热点问题，相应地出现了许多新的布局技术和方法，下面将对这些布局算法分别 进行介绍。 1 以线网总长为优化目标的布局算法 线网总长是一个传统的布局优化目标，也是最早展开研究的【1 8 1 。通过经验总结和 分析，多数人认为带权线网总长( w e i g h t e dt o t a lw i r el e n g t h ) 最短化能较好地综合 反映“使芯片面积最小化”、“1 0 0 布通率”、“减少寄生干扰和连线产生的延时”等 目标。较早期的各种线长优化布局算法大致可以分为三大类【2 0 】：迭代法( i t e r a t i v e m e t h o d ) 【2 1 1 f 3 0 1 、数学规划法( m a t h e m a t i cp r o g r a m m i n gm e t h o d ) 3 1 1 。【3 6 j 和划分法 ( p a r t i t i o n i n gm e t h o d ) 3 7 】。【4 5 1 。这三类方法是分别独立应用的，在优化质量和花费时 间上各有所长。 迭代法是从一个已有布局状态出发，通过反复调整一个或者多个单元的位置，从 而不断地修改布局状态，最终获得一个比原布局状态质量好得多的布局结果。与其它 两类布局方法相比，迭代法通常可以获得更好的布局质量，只是需要花赞更多的运行 时间。典型的迭代优化方法有模拟退火( s i m u l a t e da n n e a l i n g ) 法、力矢量 ( f o r c e 。d i r e c t e d ) 法和遗传( g e n e t i c ) 算法等。 数学规划法是将布局问题抽象成为一个数学规划问题，如二次规划( q u a d r a t i c p r o g r a m m i n g ) 问题，然后对该模型进行数学求