（电路与系统专业论文）芯片级多层布线关键技术研究.pdf

浙江大学博上学位论文摘要 摘要 布线系统分成两步：总体布线和详细布线。为了降低问题复杂度，传统布线 通常采用基于均匀网格图的有网格布线。但本质上来讲，布线资源是一个连续区 域，布线应该是可采用变线宽、变线间距的无网格布线。因此，随着计算机硬件 计算能力的不断提高，国内外对无网格布线的研究越来越多。 本论文在对国内外有关无网格布线最新技术以及大规模布线问题中的各关 键布线技术进行深入研究和深刻总结的基础上，针对性能驱动的芯片级多层布线 流程，对总体布线、无网格详细布线等关键技术进行了深入研究，提出了时延和 可制造性等多方面性能优化的一系列有效的布线算法。同时我们也对作为总体布 线和详细布线桥梁的过点分配方法进行了初步研究。 针对现有无网格布线算法以布通率为主要目标，而很少考虑时延等性能优化 的现状，本论文提出了一个时延驱动的多层总体布线算法。算法采用一种多层次 的“v ”字形工作流程，分粗化和细化两步完成布线。粗化阶段，采用t o p d o w n 的方式逐级缩小问题规模，直到到达能够处理的层次；细化阶段，采用d o w n t o p 的方式逐渐细化布线解，当重新到达最顶层，总体布线解确定。在粗化阶段的最 粗层，针对大线网布线，专门提出了一个满足时延约束的多线网布线算法。该算 法通过引入软边和移动斯坦纳点概念，来推迟精确走线的确定时机，以避免过早 固定走线带来的盲目性，为布线提供更加全局化的考虑和极大的布线灵活性。 针对多层无网格区域布线的特性，需要一个新的过点分配算法c p a ，以满足 噪声约束，最小化通孔数。本论文对过点分配算法进行了初步研究：首先根据障 碍物信息将小方块边界分解成多个区段，再分两步解c p a 问题：粗略过点分配 c e p a 和精细过点分配r c p a 。在c c p a 阶段，根据噪声约束计算每个过点的安全线 间距并将其分配到一个区段。c c p a 算法采用有效的图布线算法，以最小化通孔 数并确保没有区段溢出为目标：在r c p a 阶段，为每个过点确定精确的位置，使 其满足噪声约束，并使同一线网的过点对对齐数最大化。 详细布线阶段，本论文提出了一神基于非均匀网格图的多层无网格区域布 线算法。算法首先通过一个考虑时延性能的最小化半径和费用的生成树算法 m c s t 躲将待布多端线网进行解耦，形成两端线网集合。然后通过一种自适应迭 代策略，将多层布线转化为h _ v 布线层对序列来处理。当处理单个h v 布线层对 时，根据当前处理的布线层对的障碍物集合，形成非均匀网格图，为迷宫布线建 立基础图模型。在非均匀网格图上，利用改进的迷宫布线算法顺序处理两端线网 集合，获得详细布线解。针对布线无网格特性，论文主要改进了迷宫算法的搜索 策略，并通过二维区间树这一特殊的数据结构来管理障碍物，以加速迷宫算法。 浙江大学博士学位论文摘要 同时在迷宫布线算法中考虑可制造性概念，提出了o p c 友好的迷宫布线算法，以 提高设计的可制造性。 以上主要算法已经用c c 十+ 实现并调试通过，实验结果表明了本论文所提 出的算法的可行性和有效性。 关键字：无网格布线、最大流、n o n h a n a n 点、软边、移动斯坦纳点、过点分配、 噪声约束、非均匀网格图、天线效应、二维区间树、0 p c i i 浙江大学溥上学位论文a b s 仃a c i a b s t r a c t n e f o u f j n gs y s l e mj sd j v j d e dj n t o 呐os t e p s ：掣o b a lr o u t j n ga 1 1 dd e t a j l e df o u t i n g i no t d e rt or e d u c et l l ec o m p l e x i t yo fp r o b l e m ，t h et i a d i t i o n a lm u t i n gg e n e r a l l yi sa k i l l do f 鲥dr o u t i n g ，w l l i c hb a s e so u n i f 0 珊- 伊i d - g r a p h e s s e n t i a l l ys p e a h n g ，r o u t i n g r e s o u r c ei sas u c c e s s i v ea r e a ，s ot h er o u t i n gs h o u l db ea1 【i n do f 鲥d 王e s sf o u t i n g ， w h i c hc a nb es a t i s f i e dw i mt l l er e q u i r e i e n to fv a r i a b l cw i f ew i d t ha l l dv a f i a b l ew i r e s p a c e s o ，w i t hr a p i dd e v e l o p m e n to ft h ec o m p u t e rh a f d w a f e ，t h er e s e a r c h e so n 鲥d l e s sr o u t i i l ga r em o r ea n dm o r cp o p u l 盯a m o n gd o m e s t i ca n df o r e i 弘r e s e a f c h e r s i nt h i sd i s s e n a t i o n ，b a s e do nt h ei n - d e p mi n v e s t i g a t i o na n dl h o r 曲s 呦a f yo f t l l el a t e s t 鲥d l e s sr o u 矗n gt e c h n 0 1 0 9 ya i l dt 置i ek e y c c h n 0 1 0 舀e su s e dj i im e1 a r g es c a l e r o u t i n gp r o b l e m ，t h ek e yr o u t i n gt c c h n o l o g i c sa f et h o r o u 曲l ys t u d i e d ，w h i c ha r eu s e d i ng l o b a lr o u t i n ga n d 伊i d l e s sd e t a i l e dm u t i n gu n d e rp e r f o 珊a n c e - d r i v e nc h i p l e v e l m u l t i l a y e r r o u t i n gn o w a n das e r 主e so fe 凰c t i v ea l g o r i t h m si sp f o p o s e d ，w h i c ha r e u s e dt oo p t i m i z et t l ep e r f b 珊a n c eo ft h et i l i l i n ga i l dm a n u f a c t l l r e t h em e m o do f c m s s p o i n ta s s i g n m e n tw h i c hc o n n e c t s 弭o b a lm u t i n ga n dd e t a i l e dr o u t i i i g ，i sa l s o p 血n a r i l ys t u d i e d n e p r e s c n tg r i d l e s sr o u t i n ga 1 9 0 r i t h m sm a i n l yt a k e t h er o u t i n gr a t i oa st h e e s s e n t i a lg o a l ，b u tv e r yl i t t l et a j 【e sa c c o u n to fp e r f o 加a i l c eo p t i m i z a t i o ns u c ha s t i m i n go p t i m i z a t i o n i nv i e wo ft h e s es i t u a t i o n s ，at i m i n g d r i v e nm u l t i l a y e r 舀o b a l r o u t i n ga l g o r i t h mi sp r 叩o s e d t h i sa l g o r i t h me m p l o y sam u l t i l a y c rw o r kn o w l i k e “v ”a n df i n i s h e sr o u t i n gb yc o a r s e nf o l l o w e db yu n c o a r s e n i nc o a r s e ns t e p ，t h e p m b l e ms c a l ei s 伊a d u a l l yr c d u c e di na1 b p - d o w nw a y u n t i lt h es c a l ei se n o u 曲s m a l l t ob ed e a lw i t h ；i nu n c o a r s e ns t e p ，t h er o u t i n gr e s u l t sa r eg r a d u a l l yr e f i n e di na d o w n t o pw a y w h e nt h em o s tt o pl e v e la f r i v e s ，t h e9 1 0 b a lr o u t i n gr e s u l t s a r e d e t e r n l i n e d i nc o a r s e s ti e v e l ，as p e c i a lm u i t in e t sm u 妇ga j g o r i t h mc o n s i d e r i n g t i m i n gc o n s t r a i l l ti sp m p o s e df o r 百o b a ln e t s t oa v o j dt h eb l i n d i l e s si n t m “c e db y p r e m a t u r e l yf i x e dr o u t i n ga n ds u p p l yo v e r a l lc o n s i d e r a t i o na l l dn e x i b i l i t yf o rr o u t i n 岛 t h i sa l g o r i t h mp o s t p o n e s 傲i n gc x a c tr o u t i n gb yt h es o re d g e 柚dm o b i l es t e i n e r n o d e 1 l lv i e wo ft h ef e a t u r eo fm u l t i l e v e l 卯m e s st 0 u t i n 岛an e wc r o s s p o j n t 够s i 掣1 m e n t ( c p a ) m e t h o di sr e q l l i r c dt om e e tn o i s ec o n s t m i i i l a n dv i am i l l i i i l u m h it h i s d i s s e n a t i o n ，t h ea l g o r i t h mo fc r o s s p o i n ta 豁i 印m e n t i s p 曲耐l y s l u d i e d ：t h i s a l g o r i t h mf i r s yd e c o m p o s e st h eb o u n d a r yo fat i l e t oas e to fi n t e m a l sb yb l o c k l 浙江人学博士学位论文 i n f b h i l a t i o n ， a n dt h e ns o l v ea a p m b l e mb y t 、 r o s t e p s ：c o a r s e n e dc r o s s p o i n t a s s i 印m e m ( c c p a ) a n df e f j n e dc r o s s p o i n ta s s i g n m e n t ( r c e a ) ht h ec c p a ，s a f e s p a c cf o re a c hc f o s s p o i n ti sc a l c l i l a t c db yn o i s ec 0 璐t r a i m 蛆de a c hc r o s s p o i n ti s a l l o c a t e dt o 姐i n t e m a l c c p ae m p l o y se 虢c t i v e 笋印h i cr o u t i n ga l g o r i t h mt o m 曲i m i z ev i aa m o u n ta n de n s u r en o n eo fi n t e m a l so v e l 口w 1 1 lt h er c p a ，t h ee x a c t p o s i t i o no fe a c hc r o s s p o i n ti sd e t e n i n e dt om c c tw j t hn o i s ec o n s 协l i n t 卸d6 n dt h e m a 】【i m u mn u m b c ro fa l i 即m e n t sb e t w e e nt h ec r o s s p o i n to nt h eb o u n d a f ya n dt h e i r c i 曲b o r i n gp i s ( o rc r o s s p o i n t ) o f t h cs a m en e t s i nd e t a j l e dt o u t i n g ，am u l t i l 酊e r 伊i d l e s sa r c ar o u t i n ga l g o f i t h mb a s e do n n o n u n i f o 栅- 簪i df a p hi sp r o p o s e d n i sa l g o r i t h mf i r s t l yd i s a s s e m b l e sn e t s w 主l h m u l t i p l et e 肌i n a l sb ym c s t m r ，w h i c hm i n i m i z e st h er a d i u sa l l d c o s to fs p a l t n i n g t r e ec o n s i d 甜n gt i m i n gp e r f o m a n c e ，孤dg e n e r a t e sas e t0 fn e t sw i t hm ot e 咖i n a l s t h e nam u l t i l a y e rr o u t i n gp r o b l e mi s n v e n e di m oas e q u e n c co ft w o - l a y e rm u t i n g p r o b l e mb ys e l f - a d 印t i v ei t e r a t i v es t f a t e g y w h e n an e tw i mt 、v ot e n n i n a l si s p r o c e s s e d ，an o n - u n i f o 珊- 鲥dg r a p hi sg e n e r a t e db yi n f o 衄a t i o no fb l o c ki n s i d et h e c u e n tr o u t i n gl a y e i p a i r w h j c hi st h eb a s i c 黟印hm o d e l f o rm a z em u t i n ga l g o r i t m o ni h en o n - u n i f o n n 一铲i d 掣a p h ，a l ln e t sw i t ht w ot e 啪i n a l sa r ef o u t e do n eb yo n eb y i m p r o v e dm a z er o u t i n ga l g o r i t l l i i l ，t h e nd e t a i l e dr o u t i n gr e s u l t sa r eg e n e r a t e d i nv i e w o ft h ef e a t u r eo f 舒i d l e s sr o u t i n g ，t h i sd i s s e r t a t i o ni m p r o v e st h es e a r c h i n gs t r a t e g yo f m a z er o u t i n g 姐dm a n a g e st h eb l o c l 【sb ya2 一dj n t e m a n r c et oa c c c l e r a t em a z er o u t i n g a tt h es a m et i m e ，ac o n c e p t i o no fd e s i g nf o rm a n u f a c t u r ei si n t r o d u c e di nam a z e m u t i n ga n da i l0 p c - f r i e n d l ym a z ef o u t i i l ga l g o r i t h mi sp r o p o s e dt oi m p f o v e 也e p r o b a b i l i t yo fm a u f a c t u r e t h em a i na i g o r j t h m sa b o v eh a v eb e e ni m p l e m e n t e di nc c + + a n ds u c c e s s f h l l y d e b u g g e d i ti s s h o w ne x p e r i m e m a lt h a tt h ea l g o r i t l l i i l sp r c s e m e da r ev a l i da n d e f n c i e n t k e y w o r d s ：野i d l c s sr o u t i n 岛m a x f l o w ，n o n h 柚a i ip o i n t ，s o f tc d g e ，m o b i l es t e i n e r p o i l l t 2 一di n t e m a lt r e c ，趾t 锄ae 脏c t ，n o i s ec o n s t r a i t n o n - u n 讧0 皿一鲥d g r 叩h ，m a z er o u t i n g ，o p c 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得迸姿盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位黻作者签名昂冯络签字日期- 知戽眵日 学位论文版权使用授权书 本学位论文作者完全了解澎鎏盘鲎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝江盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：廷寸? 犸很 导师签名： 签字日期：伽年净月7 日 签字日期勃一年? 月尹日 学位论文作者毕业后去向：予所7 工刀南灰谚 工作单位：两才记d 尚丸厚 电话：，弓- 勿牛纠口 通讯龇恻千呵压确删i 兔堆椭川卯衫 浙江人学博士学位论文 第一章绪论 1 1 研究意义 第一章绪论 当今信息时代，电子信息技术作为强大的社会生产力，在推动经济发展、社 会产业结构及生活方式的变革中的作用日益增大。在电子信息技术中，集成电路 ( i c ) 被称为现代工业的“粮食”，起着十分关键的作用，是电子信息技术发展的 核心和基础，因此集成电路的发展倍受瞩巨。 自从1 9 5 8 年集成电路诞生以来，已经历了小规模集成( s s i ) 、中规模集成 ( m s i ) 、大规模集成( l s i ) 的发展阶段，目前已进入超大规模集成( v l s i ) 和特大规 模集成( u l s i ) 阶段，是一个“s y s t e mo nc h i p ”的时代，其发展速度相当惊人。 伴随着的是集成电路工艺技术的不断发展，目前已进入超深亚微米工艺时代，加 工芯片的特征尺寸已达到o 13 一o 1 8 u m ，预计2 0 0 6 年将达到0 0 7 u m 。集成电路 各种技术的日趋成熟，使得集成电路不断地向着更高集成度、超小型化、高性能、 高可靠性的方向发展。在几十平方毫米硅片上完成线条只有零点几个微米的上百 万个器件的整个电子系统的设计，只靠手工设计是完全不可能的，必须借用电子 设计自动化( e l e c t r o n i cd e s i g na u t o m a t i o n ，e d a ) 或计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，c a d ) 技术和工具。因此，集成电路的发展，不仅在于工艺的发展， 而且在于多种有效的设计手段的出现和强有力的c a d 工具的不断完善。而先进的 半导体工艺对v l s i 设计自动化技术提出了许多新的要求，传统的方法遇到了难 以克服的困难，所以，新的解决方案的研究和提出成为举世瞩目的焦点。 计算机辅助设计( 简称c a d ) 或电子设计自动化( 简称e d a ) 技术在v l s i 技术中扮演着非常重要的角色。三十年前，一个典型的集成电路( 1 c ) 仅仅由几 百个晶体管组成，所以仅仅通过人工就可以完成设计。而到了九十年代，个 v l s i 芯片上有高达几百万甚至上千万个晶体管，完全依靠人工完成设计就变得 非常困难了。同时，v l s i 的设计要求芯片提供更好的性能，更低廉的设计成本 和更短的设计周期。于是，c a d 或e d a 工具不可替代地成为v l s i 设计的关键。 高效率的e d a 工具为设计满足一定性能要求的集成电路芯片提供了必要的自动 化途径和人机交互手段。目前，c a d 或e d a 技术已经覆盖了芯片设计的全过程， 从系统设计、综合及模拟、布图设计、测试到验证都有相应的c a d 或e d a 工具的 支持，且有开放的环境和标准化的接口。 v l s i 电路工艺的发展不断对e d a 工具提出新的要求，目前e d a 技术仍落后 于工艺的发展，现有的工具不能满足高性能、高集成度设计的要求。超深亚微米、 超高速( 数g h z ) 、超大规模的集成电路芯片制造对当前的集成电路设计思想、 浙江大学博上学位论文第一章绪论 设计工具和设计方法提出了极大的挑战，特别对物理版图设计方法和设计工具， 带来更为巨大的冲击。因此，以s ( ) c 设计为代表的超深亚微米超高速超大规模集 成电路版图设计方法，是目前国际电子设计自动化( e d a ) 学术领域尖端的研究 课题之一，并正成为国内外集成电路业界争相研发的热点。本文就是针对v l s i 版图设计中的自动布线方法展开研究。 1 2 研究背景 三十年前，一个典型的集成电路( i c ) 仅仅由几百个晶体管组成，所以仅仅 通过人工就可以完成设计。随着集成电路工艺的不断发展，一个v l s i 芯片上集 成的晶体管越来越多。于是，c a d 或即a 工具不可替代地成为v l s i 设计的关键。 版图设计是整个集成电路设计过程中与产品研制和生产直接相关的一个设计过 程，它直接关系到v l s i 的设计周期、成本、正确性和产品质量，而且也是人工 设计中费时最长和差错率最高的设计步骤之一。正因为如此，它也就成为了近年 来倍受瞩目的研究领域之一。受到许多学者和众多知名c a d 公司的高度关注。他 们已经对版图设计的各环节展开了深入研究，尤其是在布图规划和布局、布线方 面已经取得了巨大的成就，提出了许多有效算法，甚至有些算法的性能已经接近 理论最优。 1 2 1v l s i 版图设计流程 在集成电路设计的各过程中，版图设计( 布图设计) 是重要的环节之一，其 任务是在满足给定的设计要求和各项电性能的条件下，在一个芯片或基底上，根 据集成电路的工艺要求，完成各单元电路的安放和电学上的互连。版图设计是整 个集成电路设计过程中与产品研制和生产直接相关的一个设计过程，它直接关系 到v l s i 的设计周期、成本、正确性和产品质量，而且也是人工设计中费时最长 和差错率最高的设计步骤之一。正因为如此，它也就成为近年来在设计自动化方 面发展最快、自动化程度最高的领域之一。 版图设计本身非常复杂，所以通常将其细分为划分、布图规划和布局、布线 和压缩。下面对各子过程作简略介绍”“。 1 ) 划分：由于一个芯片可能包含上百万个晶体管，并且也由于存储空间和 计算能力的限制，通常把整个电路划分成若干个模块，缩小问题规模。划分时要 考虑的因素有模块数目、模块大小、模块之阆的连线数、散热及对关键路径时延 的影响等。 2 ) 稚图规划和布局：布图规划为每个模块和整个芯片选择一个好的布图方 案。布局是要确定模块在芯片上的精确位置，其目标是在保证( 布线) 布通率的 2 浙江大学博士学位论文 第一章绪论 情况下优化芯片面积，随着工艺技术的发展，在布图规划和布局过程中考虑性能 方面的优化也日益迫切。 3 ) 布线：布线是在布局完成后，实现模块间各个线网互连的一个步骤，它 的目标是完成l o o 的布通率并进一步优化布线结果，如满足关键路径延迟约束、 串扰最小、减少通孔数，噪声最小，考虑可制造性等。通常把布线分为两步完成： 总体布线和详细布线。总体布线把各线网合理分配到合适豹布线区域，它不关心 走线的具体位置；详细布线则最终确定线网的物理位置。 4 ) 压缩：压缩是布线后的一个后处理优化步骤。它在不违反设计规则的前 提下进一步减少芯片面积。目前常用的有一维压缩和二维压缩。 布图设计的各个过程既相互依赖，又具有一定的独立性。整个布图过程是一 个反复迭代求解的过程，前阶段的算法要尽可能考虑其对后续阶段的影响。 1 2 2 布图模式晦“ 在版图设计中，单元的形状、大小及在芯片上的安置方式等直接关系到以后 的布线方式，不同的单元形式和安置方式对应不同的设计模式。v l s i 版图设计 的主要模式有：门阵列、标准单元、任意元胞、门海和现场可编程门阵列f p g a 等，详细内容可参考文献 5 1 第一章。 1 ) 门阵列设计模式 门阵列( g a t ea r r a y ) 设计模式利用预先制造好的所谓“母片”来进行版图 设计。母片上通常以一定的间距成行成列地排列着形状和大小相同的基本单元电 路( 一般是多个规则排列的晶体管) ，将单元内部晶体管互连就构成一定形式的 门。在版图设计时，根据具体电路的要求，首先使电路的每个单元与母片的某个 单元建立对应关系( 通常母片上的单元数将大于电路实际需要的单元数，因此母 片上有些单元将是“冗余”的) ，然后将单元间的布线区域划分为通道区，并以 图1 1 门阵列 标准单元( 元| 电) 适当的原则将互连线分配到各个通道区。最后用通道区布线算法实现单元的互连 浙江大学博士学位论文 第一章绪论 构成具体电路。见图1 1 所示。 门阵列由于其设计自动化程度高、制造周期较短、价格较低，特别适用于批 量较小的a s i c 产品。该方法的缺点是单元和通道固定，芯片利用率低，电性能 差。 2 ) 标准单元设计模式 标准单元( s t a n d a r dc e l l ) 设计模式又称多元胞( p o l y c e l l ) 模式，是以 预先设计好的功能单元为基础的。这些单元可以是不同类型的门电路，也可以是 复杂的触发器、全加器等功能电路，一般为2 0 0 到4 0 0 种，以逻辑符号、逻辑功 能及相应物理版图的形式存放在单元库中。这些单元库中的标准单元( 库单元) 的版图应具有相同的高度，但宽度可以不同：电源线和地线的位置是规范化的， 其它引脚位置一般在单元的上下边界上。在标准单元模式下进行布图设计时，根 据电路的互连要求及版图面积最小化、时延优化等设计目标，将单元成行排列， 以此完成单元的布局设计。行与行之间是称为通道的布线区，同行或相邻两行的 单元互连可通过单元行的上或下通道或相邻两行之间的通道进行连线完成，隔行 单元之间的垂直方向互连则必须借用事先预留在标准单元之间的“走线道” ( f e e d t h r o u g h ) 或在专门的“走线道单元”( f e e d - t h r o u g hc e l l ) 或“空单 元”( e m p t yc e l l ) 来完成连线。通道区的高度和走线道的宽度可依据布线的要 求进行调整。图1 2 是一个典型的标准单元版图的示意图。 目前由于多层金属工艺和基于此之上的“单元上( o v e r t h e c e l l ) 布线” 及区域布线( a r e ar o u t i n g ) 技术的日渐常用，布线资源增加，可允许出现不等 高单元和位置任意的弓l 脚。 标准单元的设计模式具有设计周期短、成本低、成功率高及系统可发展性好 等优点，目前使用较多。 3 ) 任意元胞设计模式 以上所述的几种都属于半定制的设计模式，而任意元胞或称积木块 ( b u i l d i n 邙l o c kl a y o u t ) 模式b b l 是一种全定制的设计模式。b b l 的基本单元 布 线 区 域 4 浙江大学博上学位论文 第一章绪论 是任意大小的直角多边形( 一般为矩形) 功能块，或称模块。其中长宽固定不变 的称硬模块，长宽比例可调的称软模块。b b l 设计的任务是把所有给定的模块合 理地安排在整块芯片上，然后采用可行的布线策略实现电路所要求的互连，目标 是在满足设计规则的前提下优化芯片面积或时延。见图1 3 所示。 b b l 的主要特点如下： l 、模块生成几乎不受限制，给用户以极大的方便。 2 、设计自由度大。 3 、布图密度高，布图灵活，有利于层次式设计，不受电路规模影响。 4 、易于同工艺紧密结合，伸缩性大。 以上特点决定了b b l 可以作为设计大规模、高性能集成电路的有效方法。 1 2 3 布线技术 布线是版图设计的一个重要环节，因此很早就受到了研究者的关注。随着设 计技术的不断发展，新问题，新优化目标不断涌现。从双层到多层、从有网格到 无网格、从简单的均匀线网分配、最小化布线面积等传统优化目标到时延、噪声 等性能驱动，再到考虑可制造性的布线都推动着布线技术的飞速发展。 早期的布线主要是基于均匀网格的布线，连线被抽象成了宽度为o 的几何线 段，线间距均匀固定。这样，布线资源的表示相对简单，出现了许多较为成熟的 算法，典型的可以分为总体布线和详细布线两类。 总体布线算法有串行布线算法和并行布线算法两种。串行布线算法按某种顺 序对各线网依次布线，己布线网马上成为布线障碍。显然，后布线网受到的制约 更多，因此串行布线中线序的确定非常熏要。同时为了降低线序的影响，串行布 线算法中引入了拆线重布( r i p u pa n dr e r o u t e ) 技术。并行总体布线算法同时 处理所有的线网，这类算法通常都需要求解某种n p 问题，为了降低问题规模， 算法常常将总体布线问题进行分级处理。 根据布线区域和线网端点在区域边界分布情况的不同，详细布线可分为通道 布线、开关盒布线、l 型通道布线“及区域布线。前三种详细布线问题中，线网 引脚分布在布线区域边界，如通道布线的线网引脚分布在两个边界上，高度可调 节，两开关盒布线中线网引脚出现在矩形布线区域的四周，且面积固定。区域布 线问题和开关盒布线相似，即引脚可分布于四周边界、布线区域一般不能扩展， 但区域布线允许线网引脚位于布线区域内部，布线区域内允许有预布线网和障 碍，且布线区域的形状也可以是任意的直角多边形。区域布线由于其布线区域的 可扩展范围很小，甚至根本不能扩展，布线时其首要目标是提高布通率。 从本质上来讲，布线资源是一个连续区域，所以布线应该是可采用变线宽， 浙江大学博十学位论文 第一章绪论 对此环节进行了深入研究和实现，租黑框无阴影的矩形( 包括过点分配) 表示论 对此进行了初步研究，但是由于时间关系还没有实现。 l 布局 l l i 芯片级布线 l + i 版图压缩| 图1 4 芯片级多层布线流程 芯片级多层布线流程包括总体布线、详细布线、作为连接总体布线和详细布 线桥梁的过点分配等主要过程，其中总体布线和详细布线是布线流程的核心环 节。这些过程既相互依赖，又具有一定的独立性。整个布线过程是一个反复迭代 求解的过程，前阶段的算法要尽可能考虑其对后续阶段的影响。 本论文的总体向线算法采用先t o p d o w n ，再d o w n t o p 的“矿字形流程， 分粗化和细化两步完成布线。粗化阶段，采用从上到下的方式逐级缩小问题规模， 直到到达能够处理的层次。粗化过程中主要进行资源估计、资源预留和t i l e 合 并工作，为了满足变线宽、变线距的无网格布线要求，资源估计方法充分考虑了 障碍物的实际信息。在粗化过程的最粗层，对全局线网( 相对于局部线网而言， 指在最粗层可见的线网) 进行时延驱动的总体布线。细化阶段，采用从下到上的 方式逐渐细化布线解，当重新到达最顶层，总体布线解确定。芯片级多层布线流 程中的总体布线在论文的第四章进行了详细阐述。 时延驱动的单线网布线是一个相对独立的模块。在本论文的总体布线算法 中，当在最粗层对全局线网( 相对于局部线网而言，指在最粗层可见的线网) 进 行时延驱动的总体布线时，将调用该模块。为了论述的方便，论文将该模块独立 出来，由第三章进行系统描述。 总体布线器决定线网的大致走线，详细布线器决定线网的精确走线。为了建 立总体布线与详细布线的联系，需要确定线网穿过布线边界的位置，即过点 ( c r o s s p o i n t ) 位置。过点分配很大程度上确定了线序和线间距，所以经常用来控 制线长最小化、通孔最小化和噪声约束。在芯片级多层布线流程中，我们对考虑 噪声约束的过点分配方法进行了初步研究，但是由于时间和精力的限制，算法还 没有实现，第五章主要对此展开了论述。 在类“v ”字形布线流程中，经过“v ”字形的下降边和上升边的处理后，完 7 浙江大学博上学位论文 第一章绪论 成了总体布线，产生了总体布线解。再经过过点分配环节后，进入了布线系统的 详细布线环节。为了满足变线宽、变线距的要求，芯片级多层布线流程中的详细 布线是一种无网格布线。该无网格详细布线算法采用非均匀网格图，第六章对基 于非均匀网格图的多层无网格区域布线算法展开了详细论述。 本论文的主要贡献包括： ( 1 ) 针对使各个漏点满足指定延时的布线问题，在e l m o r e 时延模型下，研 究和实现了一个基于n 0 n h a n a n 点的时延驱动单线网布线算法( 删 t i m e d r i v e ns i n 9 1 er o u t i n ga l g o r i t l l m ) 。传统布线算法在搜索s t e i n e r 点时， 都基于h a n a n 点集，为了获得更加优化的布线解，我们的算法将s t e i n e r 点解空 间由h a n a n 点集( 有限集) 拓展到了n o n h a n a n 点集( 无限集) ，并提出了有效 的搜索策略以减少优化时间。同时算法具有自动绕障碍的能力以提高可布性。 ( 2 ) 研究和提出了时延驱动的多层总体布线算法。算法采用一种所谓的 叫l t i 一1 e v e l ( 多层次) 的先t o p d o w n ，再d o w n t o p 的“v ”字形工作流程，分 三个阶段完成布线：1 ) 粗化阶段，采用从上到下的方式逐级缩小问题规模，直 到到达能够处理的层次。粗化过程中主要进行资源估计、资源预留和t i l e 合并 工作。2 ) 在最粗层，进行全局线网( 相对于局部线网而言，指在最粗层可见的 线网) 布线。在最粗层可见的线网都是长线网、大线网，所以在最粗层进行处理 给予较高的布线灵活性。针对这些全局线网，论文提出了同时考虑拥挤度和时延 的总体布线算法。在7 礁豌4 算法的基础上，通过引入软边和移动s t e i n e r 点来推 迟最终解的固化时间，从而使得布线解更加具有全局观。3 ) 细化阶段。采用从 下到上的方式逐渐细化布线解，当重新到达最顶层，总体布线解确定。细化过程 中主要完成本地线网的布线和下层传递上来的全局线网布线解的细化。 ( 3 ) 初步研究了考虑噪声约束的过点分配方法。多层无网格区域布线中， 需要采用一个新的过点分配方法c p a ( c r o s s p o i n ta s s i g n m e n t ) ，以满足噪声 约束，最小化通孔数。称总体布线图上一整行或一整列t il e 为一个p a n e l ，c p a 算法依次处理各个p a n e l 。当处理单个p a n e l 时，算法首先根据障碍物信息将小 方块( t i l e ) 边界分成多个区段，再分两步解e p a 问题：c c p a ，1 1 1 r c s h o l d ) c o a r s c ns t e p e s t i m a f e r e s c r v e 0 ； e s t i m a t e r e s o u c e 0 ； m e 曜e t i l e s o ； ) e s t i m a i e r e s o u c e 0 ； 僧d b a lr o u t i i l gi nm ec o a r s e s t1 c v e l m nt h es r i d r aa l g o r i l h m sf o re a c h ts e e ni nt h ec o a r s e s tl e v e l a n dg e tt l l ef 伽t i r 培p a m ss e t ； r c p l a c et h el s h a p es e g m e n t si nt h er o u t i n gp a t h ss e t 谢t hs o f te d g e s ； s o f f e d g e a s s j 印m e n 唧嘶o r e p a r et ou n c o a r s e n d i s a s s e m b e l t h em u l t i p i n sn e t s b u i l ds 盯f o ra l ln e t se x c e p tt h e s en e t sr o u 删i nt h ec o a r s e s tl e v e l ； r 0 u g i 山a l y s i s n e t t r e e d e l a y o ；伽a l y s i se a c hn e t sd e l a y ( 论tt l l ed e l a yu p p e ra i l dl o w e r b o u n do fe a c hn e t ； b u i l dm s tf o rna n dp r o p a r et or 廿u pa n dr e r o u t e ； f o re a c hl e v e la tm eu l l c o a r s e i l i n gs t a g e 1 4 ) f b re a c hl o c a ln e tn 1 5 ) i f ( nv i o l a t e si t st i m i n gc 0 i l s t r a i n t s ) 1 6 ) m d d i f i e d n e l l l f c e o ；m o d 姆雠t h et o p o l o g y 仃e et os a t i s f y n i m ec o n s t r a i n t 1 7 ) p a t t e m r 0 u t i n 9 0 r 叫t i n gt h ek a l n e t 1 8 ) g l o b a l m a z e r o u t i n g o ；肌6 n ei h eg l o b a ln e t ) 1 9 ) o u 呻l j r c 鲫1 t o ； 图4 1 8 时延驱动的多层无网格总体布线算法伪码描述 表4 一l 测试电路 幻”d ” d 鼬 吣加n 屹坞 浙江大学博士学位论文 第网章时延驱动的多层总体布线算法 s 5 3 7 843 3 0 23 7 0 316 9 4 31 2 447 3 4 s 9 2 3 440 2 0 2 2 3 03 l4 8 627 7 4 4 1 8 5 s 1 3 2 0 765 9 0 x 36 4 03 3 7 8 169 9 5l o5 6 2 s