（电路与系统专业论文）vlsi物理设计中布局及有约束的布局优化.pdf

p l a c e m e n t c o n s t r a i n e d p l a c e m e n t o p t i m i z a t i o ni nv l s i p h y s i c a ld e s i g n m a j o r ：i 坠i ! 垒娶堕苎y 鲤望l 一 a d v i s o r ：q l ；至垒坠坠垒坠g 一 a u t h o r ： 坠i k 垒坠2 一 独创性声明 l | i i i i i i ! y 1 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 ，签名：b 期：勿厶年厂月p 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：掉导师签名： 耄獬 日期：纱户年厂月召日 摘要 摘要 随着微电子技术的高速发展，v l s i 的集成度急剧增加，特征尺寸迅速下降至 深亚微米甚至纳米级，导致v l s i 物理设计阶段的任务更重，难度更大。布图规划 和布局是v l s i 物理设计中的早期阶段，其结果不但直接影响v l s i 的整体设计质 量，而且会对后续的布线设计产生决定性的影响。因而，布图规划和布局已成为 、，】l s i 设计的关键问题之一。 本文在分析影响v l s i 布图规划和布局相关因素的基础上，从布图规划及布 局的表示法、布局算法中所采用的数据结构、布图规划的结构分析以及模块放置 的优化方法等方面，对布局算法的优化、有约束的布图规划和布局、布线优化和 标准单元模式布局等问题作了一些探索性研究，主要工作和取得的成果概括如下： 1 在布局算法上，详细研究了布局算法中所采用的辅助数据结构和模块放置 方法对算法运行效率的影响，提出了角轮廓结构( c o m e r - c o n t o u r ) 数据结构，证 明其从左至右阶梯下降的重要特性，并结合0 唿和s i n g l e - s e q u e n c e ( 简称s s ) 表示法编码各自的特性，简化并优化了基于这两种表示法的布局算法；提出凹轮 廓( c o n c a v e c o n t o u r ) 数据结构，并用其实现有固定外框约束的布局；在布局算 法中考虑矩形外框对布局的影响，以矩形外框对角线为准线引导模块放置，加快 了布局算法的收敛；利用边界约束条件，在不执行模块放置程序的条件下快速评 价布局编码，以缩小搜索范围，加快布局算法的收敛。 2 在有约束的布局方面，详细研究了s s 表示法的编码特性，提出并证明了 基于该表示法的边界约束的充要条件，给出了边界约束条件的数字串表达式并用 算法实现。对s s 表示法边界约束条件的研究迸一步完善了这种新式表示法。 3 在布线优化方面，详细研究了s s 表示法与对应布图规划之间的关系，提 出基于该表示法的边界约束对布图规划进行分层结构分析、通过引导模块放置以 优化布线结构的方法，不但使s s 编码对应的布图规划图形结构更加清晰，而且实 现了布局对布线的指导作用和基于布线优化的布局；基于b 宰t r e e 编码，用插入虚 拟模块的方法实现了紧致型布局中任意模块对的连通，解决了布线中局部模块布 通性的问题。 4 在标准单元布局方面，从全新的角度考虑标准单元布局的优化问题，提出 摘要 元方式下的布局表示法- o r d e r e ds i n g l ec h a i nt r e e ( 简称o s c t ) 。o s c t 码以数字串编码形式表示标准单元布局的拓扑结构，易于实现标准单元 界约束和布线优化，并能够借助现代随机优化算法对标准单元布局进行 的、更加精确的优化计算。 v l s i 物理设计，布图规划，布局，布线，单序列表示法，标准单元布局 a b s t r a c t a b s t r a c t a sr n i c r o e l e c t r o n i ct e c h n o l o g ya d v a n c e s ，i n t e g r a t i o ns c a l ei n c r e a s e sd r a m a t i c a l l y w h i l ef e a t u r es i z eo fv l s ii ss h r i n k i n gt od e 印- s u b m i c r o no re v t on a n o m e t e r i t m a k e sv l s ip h y s i c a ld e s i g nm o r ec o m p l i c a t ea n dc r i t i c a lt h a ne v e rb e f o r e a st h ee a r l y s t a g eo fv l s ip h y s i c a ld e s i g n ，f l o o r p l a n p l a c e m e n tn o to n l yd e t e r m i n e sp e r f o r m a n c eo f ac i r c u i td i r e c t l y , b u ta l s oi n f l u e n c e st h ef o l l o w i n gr o u t i n gs t a g eg r e a t l y t h e r e f o r e ， f l o o r p l a n p l a e e m e n tb e c o m e st h ec r i t i c a ls t a g ei nv l s id e s i g n i nt h i st h e s i s ，b a s e do no v e r a l l a n a l y s i so fi n f l u e n t i a lf a c t o r si nf l o o r p l a na n d p l a c e m e n t , s o m ef r o n t i e rf i e l d so ff l o o r p l a n p l a c e m e n t , i n c l u d i n gp l a c e m e n ta l g o r i t h m o p t i m i z a t i o n , c o n d i t i o n s o fc o n s t r a i n t e d p l a c e m e n t s ，p l a c e m e n t - b a s e dr o u t i n g o p t i m i z a t i o na n ds t a n d a r dc e l lp l a c e m e n te t c ，a r ee x p l o r e da n di n v e s t i g a t e d s o m e u s e f u lc h a r a c t e r i s t i c so ff l o o r p l a n p l a c e m e n ta r ed i s c o v e r e da n daf e wn o v e li d e a sa r e p r o p o s e d t h em a i nr e s u l t sa r ea sf o f l o w s ： 1 i nt h ep l a c e m e n ta l g o r i t h mf e l d ，e f f e c t so fe m p l o y e dd a t as t r u c t u r e sa n dm o d u l e p l a c e m e n tm e t h o d so ne f f i c i e n c yo fm o d u l ep l a c e m e n ta l g o r i t h m sa r ei n v e s t i g a t e di n d e t a i l an e wd a t as t r u c t u r e ，w h i c hi sn a m e dc o m e r - c o n t o u r , i sp r o p o s e da n di t sp r o p e r t y o fs t a i r w a yd e s c e n d i n gi nl e f t f i g h td i r e c t i o ni sp r o v e d c o m b i n i n gi tw i t hc o d i n g s c h e m eo fs i n g l e s e q u e n c e ( s s ) a n d0 一t r e er e p r e s e n t a t i o n s ，t h ei n d u c e da l g o r i t h m sc a n i m p r o v ec o r r e s p o n d i n gm o d u l ep l a c e m e n tl a r g e l y a n o t h e rd a t as t r u c t u r e ，w h i c hi s n a m e dc o n c a v e c o n t o u r , i sa l s op r e s e n t e dt os o l v et h ef i x e d o u t l i n ep a c k i n gp r o b l e m s ， w h i c ha r ea r i s i n gi nm o d e r nv l s ip h y s i c a l d e s i g nr e c e n t l y g u i d i n gp r o p e r t i e so f b o u n d i n gr e c t a n g l ea n di t sd i a g o n a ll i n eo nt h ep l a c e m e n ta l g o r i t h ma r ea l s os t u d i e da n d u t i l i z e dt oa c c e l e r a t em o d u l ep l a c e m e n tp r o c e s s f u r t h e r m o r e ，b a s e do nb o u n d a r y c o n s t r a i n t so fs s ，f a s te v a l u a t i o no fac a n d i d a t ec o d ei sr e a l i z e dw i t h o u tp e r f o r m i n g w h o l ep l a c e m e n tp r o c e s s i tc a l lr e d u c et h ee x p l o r i n gs c o p ea n db o o s tc o n v e r g e n c eo f t h ep l a c e m e n ta l g o r i t h ml a r g e l y 2 i nt h ec o n s t r a i n e dp l a c e m e n tf i e l d ，a c c o r d i n gt ot h ed e t a i la n a l y s i so ft h ec o d i n g s c h e m eo fs s r e p r e s e n t a t i o n ， s u f f i c i e n ta n d n e c e s s a r yc o n d i t i o n s o fb o u n d a r y i i i a b s t r a c t c o n s t r a i n t so fs sa r ep r o p o s e da n dp r o v e d t h e i re x p l i c i te x p r e s s i o n si nn u m e r i cs t r i n g m o d e sa l ea l s ob e e nd e r i v e d b e c a u s es si san o v e lf l o o r p l a n p l a c e m e n tr e p r e s e n t a t i o n , t h i sr e s u l tw i l lf u r t h e rc o m p l e t ei tt h e o r e t i c a l l y 3 i nt h er o u t i n gf e l d ，t h ec o r r e s p o n d e n c eb e t w e e na ns sc o d ea n dt h ei n d u c e d f l o o r p l a ni se x p l o r e di nd e t a i l b a s e do nb o u n d a r yc o n s t r a i n t so fs sr e p r e s e n t a t i o n , a f l o o r p l a ni ss t r u c t u r a l l yp e e l e d a n ds t r u c t u r eo ft h ec o r r e s p o n d i n g f l o o r p l a n c o n f i g u r a t i o ni su n c o v e r e d t h i ss t r u a m a la n a l y s i so faf l o o r p l a nc 觚n o to n l yf a c i l i t a t e t h em o d u l ep l a c e m e n t , b u ta l s og u i d et h em o d u l ep l a c e m e n tt oo p t i m i z et h ef o l l o w i n g r o u t i n gp u r p o s e f u l l y t h i sm a yl e a daw a yt o s o l v er o u t i n g - r e l a t e dp r o b l e m sf r o m f l o o r p l a n p l a c e m e n tp e r s p e c t i v e b e s i d e s ，b a s e do nc h a r a c t e r i s t i c s o fb * - t r e e ，t h e r o u t a b i l i t yb e t w e e na n ym o d u l ep a i ri ss o l v e ds m o o t h l yb yi n s e r t i n gd u m m ym o d u l e s i n t ot h ec o r r e s p o n d i n gc o d e i t 锄s o l v et h em o d u l e - p a i ri n t e r e o r m e c t i o np r o b l e ma n d r e l i e v el o c a lr o u t i n gc o n g e s t i o na tt h ea f t e r - p l a c e m e n td e s i g ns t a g e 4 i nt h es t a n d a r dc e l lp l a c e m e n ta r e a , an o v dc o d i n gs c h e m eo fs t a n d a r dc e l l p l a c e m e n t , w h i c hi sn a m e do r d e r e ds i n g l ec h a i nt r e e ( o s c t ) ，i sp r o p o s e d t h e n u m e r i cs t r i n gm o d em a k e si tf a c i l i t a t i v et or e a l i z eb o u n d a r yc o n s t r a i n t sa n dr o u t i n g o p t i m i z a t i o n b a s e do nt h eo s c tc o d i n gs c h e m e ，m o r ew i d e l ya n da c c u r a t e l yo p t i m a l s e a r c h i n gc a n b ei m p l e m e n t e db yu t i l i z i n ga n yh e u r i s t i c si nt h es t a n d a r dc e l lp l a c e m e n t f i e l d k e y w o r d s ：v l s ip h y s i c a ld e s i g n ，f l o o r p l a n ，p l a c e m e n t ，r o u t i n g ，s i n g l e s e q u e n c e ， s t a n d a r dc e l lp l a c e m e n t 1 1 1 集成电路的发展历史与现状2 1 1 2 集成电路设计流程3 1 2v l s i 物理设计中的设计方式。7 1 2 1 全定制设计方式8 1 2 2 标准单元设计方式9 1 2 3 门阵列设计方式1 0 1 2 4 逻辑可编程门阵列设计方式1 l 1 3 布图规划布局表示法1 2 1 3 1b o u n d e ds l i c e - l i n eg r i d 表示法1 4 1 3 2s e q u e n c e p a i r 表示法15 1 3 3c o m e rb l o c kl i s t 表示法l6 1 3 4o t r e e 表示法17 1 3 5b 宰t r e e 表示法18 1 3 6t r a n s i t i v ec l o s u r eg r a p h 表示法l9 1 3 7s i n g l es e q u e n c e 表示法2 l 1 4 布图规划布局中的约束条件2 2 1 4 1 边界约束2 2 1 4 2 对称约束2 3 1 4 3b u s 总线约束2 5 1 4 4 其它约束2 6 1 5 布图规划布局中常用的随机优化算法2 7 v 目录 1 5 1 模拟退火算法2 7 1 5 2 遗传算法。2 8 1 6 本论文的选题和研究内容3 l 第二章布局算法及其优化3 4 2 1 引言3 4 2 2 布局算法中的数据结构角轮廓3 5 2 2 1 问题描述与预备知识3 6 2 2 2 用角轮廓结构实现基于s s 表示法的快速模块放置算法。4 l 2 2 3 用角轮廓结构实现基于o - t r e e 表示法的模块快速放置算法4 5 2 2 4 用h v c 数据结构实现基于s s 表示法的布局和布图规划4 8 2 3 布局算法中的数据结构凹轮廓5 l 2 4 基于矩形外框对角线对称性模块放置算法5 6 2 5 基于边界约束条件和布局半程判断的模块放置算法6 l 2 6 本章小结6 5 第三章有约束的布局6 6 3 1 引言6 6 3 2 基于s s 表示法的边界约束布局6 7 3 3 本章小结7 5 第四章布线及其优化7 6 4 1 引言7 6 4 2 基于布局结构分析的布线优化7 7 4 3 基于b 幸t r e e 表示法的任意模块对的连通一8 3 4 4 本章小结8 8 第五章标准单元布局8 9 5 1 引言8 9 5 2 标准单元布局表示法o s c t 9 3 5 3 本章小结9 8 v i 第六章全文总结及进一步的工作9 9 6 1 全文总结9 9 6 2 进一步的工作1 0 2 致谢1 0 4 参考文献1 0 5 攻读博士学位期间取得的研究成果1 18 第一章绪论 第一章绪论 1 1v l s i 物理设计自动化及其发展 随着人类迈入2 l 世纪，微电子技术领域不断进步与发展，使得电子产品的性 能进一步提高，产品更新换代的节奏变得越来越快。集成电路( i n t e g r a t e dc i r c u i t ， 简称i c ) 正在不断地向超大规模、极低功耗和超高速的方向发展【l 。1 6 1 。微电子技术 的进步主要表现在大规模集成电路加工技术即半导体工艺技术的发展上，表征半 导体工艺水平的线宽已经达到了4 5 纳米【她1 1 】，并且还在不断缩小。芯片特征尺寸 的下降使集成电路中的各种寄生效应越来越多且越来越大；器件间连线拥挤度增 大，而且连线延迟超过门延迟，使连线更加困难【怍1 6 】；同时，在硅片单位面积上 集成了更多的晶体管( 例如，目前主流c p u 芯片上集成有5 8 1 0 8 个晶体管【1 0 。1 1 】) 。 集成度的增加使得v l s i ( 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 ) 设计中广泛采 用了i p ( i n t e l l e c t u a lp r o p e r t y ) 核重用和分层设计( h i e r a r c h i c a ld e s i g n ) 的方法来 提高设计效率。然而这些方法在处理平面模块的放置和连线问题时功能和效果有 限，而且其自身也带来了新的设计难题，因而使得v l s i 物理设计中处理模块放置 的布局和布图规划成为v l s i 设计的关键【”1 2 - 1 6 。 与此同时，电子设计自动化技术( e l e c t r o n i cd e s i g n a u t o m a t i o n ，简称e d a ) 也获得了飞速的发展。在目前这种海量集成度、高复杂性的条件下，现代电子设 计技术的核心日趋转向基于计算机的电子设计自动化技术。它依靠功能强大的计 算机，在e d a 工具软件平台上基于用硬件描述语言表达的系统逻辑设计文件，自 动地完成逻辑编译、逻辑化简、逻辑分割、逻辑综合、结构综合( 布局布线) 、逻 辑优化和仿真测试等工作，直至实现既定的电子线路系统功能。 在现代高新电子产品的设计和生产中，微电子技术和现代电子设计技术是相 互促进、相互推动又相互制约的两个环节；前者代表了硬件电路实现的发展，后 者则反映了现代先进的电子理论、电子技术、仿真技术、设计工艺和设计技术与 最新的计算机软件技术有机的结合和升华。e d a 技术在硬件实现方面结合了大规 模集成电路制造技术、i c 版图设计技术、a s i c 测试和封装技术、f p g a j c p l d 编 程技术、自动测试技术等；在计算机辅助工程方面融合了计算机辅助设计( c a d ) 、 电子科技大学博士学位论文 计算机辅助制造( c a m ) 、计算机辅助测试( c a t ) 、计算机辅助工程( c a e ) 技 术以及多种计算机语言的设计概念；而在现代电子学方面则容纳了更多的内容， 如电子线路设计理论、数字信号处理技术、数字系统建模和优化技术理论等。因 此，e d a 技术是微电子技术和现代电子设计技术的结合，是这两个领域共同发展 的结果。在其推动下，现代电子产品几乎渗透到社会的各个领域，有力地推动了 社会生产力的发展和社会信息化程度的提高【3 。7 1 。 随着微电子技术进入深亚微米和纳米领域，高集成度和小特征尺寸给集成电 路的设计和生产带来了巨大的挑战。器件特征尺寸的不断缩小，已经逐步进入深 亚微米以及纳米尺度的范围，微电子技术的发展模式也已经逼近了材料、技术、 器件，以及其他宏观物理规律的适用极限，使v l s i 的制造和设计遇到了很多难题， 诸如光刻、功耗、散热、芯片在片参数波动、器件连通性等，而目前工业界广泛 流行的设计技术仍落后工艺的发展【1 乏，8 - 9 , 1 纠6 1 。这种挑战尤其体现在v l s i 的物理 设计阶段，因为高集成度和小特征尺寸的影响在前序阶段的结构、功能和逻辑设 计中并不具体体现或影响不大。而在物理设计阶段，主要任务是基于前序设计阶 段的结果，在芯片上实现实体电路元器件的布局和布线，高集成度和小特征尺寸 的影响就完全显现出来，尤其是布线问题已经成为v l s i 的物理设计发展的瓶颈， 并且布局和布线的问题模型都是属于n p c 难题，更增加了v l s i 物理设计的复杂 性。 1 1 1 集成电路的发展历史与现状 自从晶体管( b j t ) 与场效应晶体管( f e t ) 在1 9 4 7 年被相继发明后，就开始了新 的电子革命。原来由真空管所组成的电子仪器设备和产品，被速度更快、功率更 低、体积更小和价格更低的晶体管所取代，使得晶体管在电子工业中担任了承先 启后的主导角色。1 9 5 8 年，德州仪器公司( t i ) 首先结合了数十个分离式的组件而开 发出第一批单晶集成电路( m o n o l i t h i ci n t e g r a t e dc i r c u i t ) ，接着仙童( f a i r c h i l d ) 等 公司相继开发出电阻式逻辑晶体管( r t l ) 、二极管式逻辑晶体管( d t l ) 、晶体管式 逻辑晶体管( t t l ) 及射极耦合逻辑晶体管( e c l ) 等集成电路。 1 9 6 0 年，金属氧化半导体晶体管( m e t a lo x i d es e m i c o n d u c t o r ，简称m o s ) 出现后，r c a 公司率先于1 9 6 2 年开发出m o s 集成电路，并于次年研发出一系列 的互补式m o s ( 即c m o s ) 集成电路。这种c m o s 组件比双极性晶体管及场效应 晶体管具有更高的制造密度与更低的功耗等优点，但速度低是其主要缺点。1 9 6 4 2 第一章绪论 一 年，仙童公司首先研发出线性i c ，使l c 应用范围更广。1 9 6 8 年，i n t e l 公司开发 出m o s 内存芯片，使得数据能够储存于集成电路中。1 9 7 1 年，m o s t e k 研发出 m o s 计算器芯片，使得掌上型计算器得以实现。同年，i n t e l 公司首先研发出第一 片4 位微处理器( m i c r o p r o c e s s o r ) ，更是激起了后来数十年的微型计算机革命，而 后各家厂商相继研发出更多位的微处理器与微型计算机。目前，具有6 4 位处理芯 片的微型计算机正是市场的主流【1 。 如果以集成电路内部所集成的器件数量为标准来划分集成电路的发展历史， 则1 9 5 1 年为单一组件或晶体管；1 9 6 0 年开始有小型集成电路( s m a l ls c a l e i n t e g r a t i o n ，简称s s i ) ，其集成度小于1 0 0 ；1 9 6 6 年开发出中型集成电路( m o d e r a t e s c a l ei n t e g r a t i o n ，简称m s i ) ，其集成度大于1 0 0 ，但小于1 0 0 0 ；1 9 6 9 年生产大规 模集成电路( l a r g es c a l ei n t e g r a t i o n ，简称l s i ) ，其集成度大于1 0 0 0 ，但小于1 0 0 0 0 1 1 9 7 5 年研发出超大规模集成电路( 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 ) ，其内 部组件高达1 0 6 。如i n t e l 公司在1 9 8 5 年生产的3 2 位微处理器8 0 3 8 6 ，内部就包含 有2 7 万5 千个晶体管。集成度超过一百万门的电路，被称为甚大规模集成电路 ( u l t r al a r g es c a l ei n t e g r a t i o n ，简称u l s i ) ，如i n t e l 公司结合了双极性与金属半 氧化晶体管( b i c m o s ) 设计的p t i u m 芯片，以o 8 微米工艺流程制造，内部集 成了3 x 1 0 6 个晶体管；p e i l t i u mp r o 芯片则高达5 5 x 1 0 6 个晶体管【j 。 在目前流行的c p u 中，典型代表如i n t e l 公司2 0 0 7 年上市的c o r c 丌2 芯片， 采用四核构架和6 5 r i m 技术制造，时钟频率达2 6 6 g h z ，片上集成了5 8 2 x 1 0 8 个晶 体管；同年上市的另一款x e o n e ( p c n r y n ) 处理器，采用四核构架和4 5 r i m 技术制 造，时钟频率高达3 g h z ，片上集成了8 2 x 1 0 8 个晶体管【j u j 。 目前，集成电路被广泛应用于生产和生活中的各个领域，如c p u 、d s p 和各 种控制设备中：应用于存储芯片中，如r a m 、r o m 和e e p r o m 等；应用于各种 模拟电路中，如移动通讯、视频和音频处理设备；应用于各种逻辑可编程器件中， 如p l a ，f p g a 等；应用于各种嵌入式系统中，如车辆、工厂中的各种导航、生 产和控制仪器中。随着集成电路应用范围的不断扩大，重要性不断增加，其设计、 制造也随之更加关键。 1 1 2 集成电路设计流程 二十世纪6 0 年代，大规模集成电路( l s i ) f 丌始发展之际，计算机辅助设 计( c o m p u t e ra i d e dd e s i g n ，简称c a d ) 工具应用在集成电路j 。丌始萌芽。随着 电子科技大学博士学位论文 集成电路制造技术的进步与器件特称尺寸的下降，集成电路的复杂度也相对地增 加。因此，集成电路的设计工作也就变得相当庞大而昂贵，而且极费时又易出错。 为了简化设计流程和降低设计难度，一般将其分成几个设计阶段，每一个设计阶 段可单独作业，再相互衔接而成。其中的每个设计阶段都使用计算机辅助设计工 具，极大地减少了所需的电路开发人员，降低了设计成本，同时也缩短了设计时 间、避免设计错误。 图1 1 为一个典型的集成电路设计流程。按照设计流程，首先需要对电路进行 系统描述，紧接着的结构化设计( a r c l l i t c c t u r a ld e s i g n ) 是根据电路的系统描述以 硬件描述语言来进行电路行为描述与验证。例如，电路中电路模块的组成与连结、 每个电路模块的子模块组成与相互连接等。依此类推，这个电路即由结构式或分 层式的子模块所形成。接着以硬件描述语言( h a r d w a r ed e s c r i p t i o nl a n g u a g e ，简 称h d l ) 来描述此结构化设计，并经过仿真验证其功能。如果功能不符合原有设 计要求，经修正后再做模拟，直至正确为止。 图1 - 1 集成电路设计流程图 逻辑设计( l 0 西cd e s i g n ) 是将上述j 下确的结构化设计经过寄存器转移逻辑 ( r e g i s t e rt r a n s f e rl o g i c ，简称r t l ) 设计步骤而实现成为具体的电路，即对每个 分层式的模块完成其电路设计。当然，如果在单元库中已有该电路模块，可直接 转移使用。但每个新设计的电路模块仍可以用硬件描述语言作逻辑最佳化、功能 仿真及时序验证等以确保电路的正确性。 4 苛 苛 热正豁案 图1 - 2v l s i 物理设计流程图 物理设计非常费时，它是整个集成电路设计过程中与产品研制和生产直接相 关的关键过程，直接关系到芯片的设计周期、生产成本和产品质量等。这一步骤 也是以往人工设计中耗时最多和差错率最高的设计过程之一。如早期的1 6 位微处 理器z 8 0 0 0 的v l s i 芯片，在使用较少c a d 工具的情况下，完成此芯片花费了大 约1 3 0 0 0 人工小时，而物理设计部份就占了约5 0 的时间。正因为如此，v l s i 物 理设计自动化成为近年来在设计自动化方面发展最快的领域之一。随着集成电路 制造技术的不断发展，芯片的集成度急剧增加( 单片集成度可达几千万几亿 f - i ) 胁i i 】，物理设计中面对问题的规模越来越大，复杂度与日俱增，分层设计和i p 核重用技术被广泛应用来应对r 益复杂的v l s i 设计；同时，特征尺寸的迅速下降 ( 目前业界主流为6 5 和4 5 纳米，甚至更小) 导致电路中的电阻、电容等寄生效 应迅速增加，连线延迟越加严重，成为影响整个电路功效的关键因素。连线优化 和布线连通性问题也同益突出，已经成为v l s i 设计的瓶颈问题。面对高集成度和 小特征尺寸发展趋势以及由此带来的连线高度复杂性和电路参数的畸变性，v l s i 的物理设计将变得更加复杂，更加关键，并成为v l s i 设计的关键阶段。 物理设计后的阶段是电路设计和验证、生产制造阶段。该阶段经过光刻、抛 光、沉积和散射等工艺过程，将电路版图制成相应的芯片。 集成电路设计的最后阶段是芯片的封装即将所有的芯片放置在一块p c b 板 电子科技大学博士学位论文 上或组成m c m 的形式，制成客户需要的产品。 在v l s i 物理设计中，布图规划和布局设计是早期阶段。它们的任务是将电路 元器件简化和抽象成矩形模块，在满足各模块间不重叠的基本约束条件下，根据 电路功能和工艺技术的要求实现芯片上单元或功能模块的放置和互连，并对矩形 模块施行二维紧致放置。其基本优化目标是使芯片面积最小以及连线最短。因为 布图规划和布局阶段的结果对后续的布线以及芯片的整体结构有着决定性的影 响，所以它们成为v l s i 物理设计中的关键步骤。在v l s i 高速发展的今天，布图 规划和布局无疑将面对更大的挑战，并成为关注和研究的焦点【l q 6 1 。 在现代v l s i 物理设计中，布图规划和布局的基本解决方法是利用某种表示法 对模块间的拓扑结构进行有效描述，并由此表示法导出布图规划或布局的解空间， 然后以某种随机优化算法( 如模拟退火或遗传算法等【1 7 - m s ) 作为搜索引擎，对解 空间进行优化解的搜索。此外，基于表示法与布图规划或布局的对应性，通过对 模块放置位置的设置，可以实现有各种约束条件的布图规划或布局以及布线的优 化。所以，布图规划或布局的基本问题在于找到一种精确描述模块间几何位置关 系的、高效而灵活的表示法或编码，以便于布局的实现以及有效地处理各种有约 束的布局问题。布图规划或布局问题从根本上属于传统2 d p a c k i n g 的n p c 优化难 题1 2 1 - 2 s 1 ，即矩形模块的紧致放置问题，它类似于优化问题中的“背包问题或“旅 行商问题”。这类问题的优化涉及到解空间的表示、所采用的随机优化算法框架( 算 法中各参数的设置) 、算法中所使用的数据结构、矩形模块的放置方法和编码的快 速估算等方面。 布局或布图规划表示法韵研究从上世纪8 0 年代开始，到9 0 年代中后期至今 经历了很大的发展，出现了很多表示各种拓扑类型的表示法或编码【2 9 ”】，并有相 应的模块放置算法【饰b 4 1 ，但这些算法不一定是最优化的。随着研究的不断深入， 不少文献提出了很多优秀的模块放置算法和辅助数据结构【1 3 1 4 5 1 ，以改进和提高基 于相应表示法的模块放置算法。 此外，在实际设计中，基于某种优化目标或技术上的特殊需求，要求某个或 某些模块放置在芯片的特定位置，即实现有约束的布图规划或布局。随着对集成 电路性能要求的提高，有约束的布图规划或布局也成为目前v l s i 物理设计中研究 的热点领域 s 4 - 1 4 0 。例如，在v l s i 物理设计中，分层设计、i p 核重用以及连线优 化都要求将某些与外界有紧密关系的模块放置在布局的边界，以利于整体布局的 优化，这使得边界约束布局显得尤其重要【搏9 3 】；模块对称分布的布局有利于降低 芯片上模块分布的密集度以及由此引起的寄生问题，某些元器件的特殊组成、预 6 第一章绪论 先定义的外形要求和外形轮廓匹配要求等也对模块提出了对称放置的约束等 【蚪1 0 1 1 。除了上述布局约束条件，还有很多约束条件在v l s i 设计时应加以考虑 1 0 2 - 1 4 0 1 ，以提高芯片的性能。 现代v l s i 物理设计中，按照对布局布线位置和布局模块类型的限制，可以将 版图设计方法分成全定制( f u l l c t l s t o m ) 和半定制( s e m i - c u s t o m ) 设计方式两大 类【l ，9 1 0 】。全定制方式对单元外型和布局位置没有限制，单元或模块可以有任意的 形状和尺寸，可以安放在芯片的任意位置上且没有固定的布线区域。全定制设计 方式是最灵活，但又最困难的一种设计方法，这种布图方式接近人工的设计方法， 因此可以得到比其它设计方式更高的布图密度。目前，有三种c a d 工具服务于全 定制设计模式：基于几何图形的交互图形编辑( i n t e r a c t i v eg r a p h i ce d i t o r ) 、符号 法版图设计( s y m b o l i cl a y o u t a p p r o a c h ) 和积木块式布图( b u i l d i n gb l o c kl a y o u t ) 。 半定制设计方式对单元的高度，电源线位置和单元引线端的引出方向都有一定的 限制，它又可分为：标准单元( s t a n d a r dc e l l ) 、门阵列( g a t e a r r a y ) 和f p g a ( f i e l d p r o g r a m m a b l eg a t ea r r a y ，简称f p g a ) 等设计方式，其中门阵列和标准单元方式 又常被称为基于行排列( r o wb a s e d ) 的方式。在这两种布图方式中，电路的基本 单元有规则地成行排列，单元行之间的区域作为布线通道( c h a n n e l ) 。由于单元行 排列比较规则，问题相对比较简单，所以布图设计的技术首先在门阵列和标准单 元方式上得到了充分的发展，而且其中一些主要算法已经发展得比较成熟。但随 着单片集成度的增加，优化问题的规模越来越大，出现了一些新的布局难题，如 局部过密，布线连通性等问题，这些也是本