（应用数学专业论文）超大规模集成电路物理设计中的直角斯坦纳树问题.pdf

摘要 摘要 本文首先介绍了超大规模集成电路的物理设计流程，在此基础上引出直角 斯坦纳树问题。许多已知算法考虑了有障碍的直角斯坦纳树问题，但是对于布 线区域存在边界的情况并没有涉及。布线区域的边界不能简单地看作一维障碍 的拼接，因为这样会把凹的边界切割下去，从而使导线跑到布线区域外边。同 时，在布线区域边界不规则时会带来不必要的运算。 本文介绍的赋权李算法就很好地克服了这个问题。该算法的时间复杂度 为o ( n 2 ( 佗4 - m ) 2 l o g ( n + m ) ) ，其中n 是终端的个数，仇是障碍和边界的顶点个数 之和。 同时本文提出了最小凸多边形的技术， 证明了在这个最小凸多边形中存在最优解， 次优解。 大大缩减了布线区域的面积，并且 然后利用改进的赋权李算法，给出 本文提到的算法，可以在运算中剔除不需要考虑的障碍，从而进一步减小 运算规模。实践证明，该算法在布线区域边界不规则，且终端成对角线状排列 时，能获得最高的效率。 对于多层布线的模型，本文将赋权李算法扩展到三维，同时将最小凸多边 形的技术扩展到最小凸多面体，通过调整扩展的h a n a n 格对应边的权重，从而 达到了减少通孔的目的。 最后本文给出了在更高维空间的直角斯坦纳树问题的定义，和相应的最小 凸多面体的构造。 关键词：布线，直角斯坦纳树，障碍，边界，扩展h a n a n 格，赋权李算法 i a b s t r a c t a b s t r a c t a tf i r s t ，t h i st h e s i si n t r o d u c e st h ev l s ip h y s i c a ld e s i g np r o c e s s ，b a s e do n t h i sl e a d st ot h er e c t i l i n e a rs t e i n e rt r e ep r o b l e m m a n yk n o w na l g o r i t h m st a k e i n t oa c c o u n tt h er e c t i l i n e a rs t e i n e rt r e ep r o b l e mw i t ho b s t a c l e s ，b u tt h e r ei sl i t t l e c o n s i d e r a t i o no ft h eb o u n d a r y t h eb o u n d a r yo ft h er o u t i n ga 。r e ac a n n o tb e s i m p l yr e g a r d e da st h es p l i c e do b s t a c l e so fo n e - d i m e n s i o n a l ，b e c a u s et h i sw i l lg o o i lc u t t i n gt h ec o n c a v eb o u n d a r y , s ot h a tw i r e sr u nt ot h er e g i o no u t s i d et h e r o u t i n ga r e a a n di tw i l lb r i n gu n n e c e s s a r yo p e r a t i o n si nt h ec a s eo fi r r e g u l a r b o u n d a r yo ft h er o u t i n ga l e a i nt h i st h e s i s ，t h ep r o b l e mc a nb ew e l lo v e r c o m eb yt h ew e i g h t e dl e e a l g o - r i t h m ，t h et i m ec o m p l e x i t yo fw h i c hi so ( n 2 ( n + m ) 2l o g ( n + m ) ) ，w h e r e 死i st h e n u m b e ro ft e r m i n a l s ，mi st h en u m b e ro fv e r t i c e so fo b s t a c l e sa n db o u n d a r y a tt h es a h l et i m e ，t h em i n i m u mc o n v e xp o l y g o nt e c h n o l o g yi sp r o p o s e di n t h i st h e s i s i tg r e a t l yr e d u c e st h er o u t i n ga r e a ，a n dp r o v e st h ee x i s t e n c eo ft h e o p t i m a ls o l u t i o nw i t h i nt h em i n i m u mc o n v e xp o l y g o n ，a n dt h e nc o m p u t e ss u b - o p t i m a ls o l u t i o nb yt h ew e i g h t e dl e ea l g o r i t h m t h ea l g o r i t h mm e n t i o n e dh e r e i nc o u l dg e tr i do ft h eo b s t a c l e st h a ti su s e l e s s i nt h eo p e r a t i o n ，t h u sf u r t h e rr e d u c i n gt h ec o m p u t i n gs c a l e p r a c t i c eh a sp r o v e d t h a tt h er o u t i n ga l g o r i t h mr u n si n h i g h e re f f i c i e n c yw h e nt h eb o u n d a r yo ft h e r o u t i n ga r e ai si r r e g u l a r ，o rt h et e r m i n a l sa r ea r r a n g e di nad i a g o n a l s h a p e da r r a y f o rm u l t i l a y e rr o u t i n gm o d e l ，t h i st h e s i se x t e n d st h ew e i g h t e dl e ea l g o r i t h m t ot h r e e - d i m e n s i o n a l ，w h i l et h et e c h n o l o g yo fm i n i m u mc o n v e x p o l y g o ne x t e n d e d t ot h eo n eo fm i n i m u mc o n v e xp o l y h e d r o n b ya d j u s t i n gt h ec o r r e s p o n d i n ge d g e w e i g h to ft h ee x t e n d e dh a n a n 瓯d ，w ea c h i e v et h eo b j e c t i v eo fr e d u c i n gt h e n u m b e ro fv i a s f i n a l l y , t h i st h e s i sg i v e st h ed e f i n i t i o no ft h er e c t i l i n e a rs t e i n e rt r e ep r o b - l e n ai nm o r eh i g h e r - d i m e n s i o n a ls p a c e ，a n dt h ec o r r e s p o n d i n gs t r u c t u r eo ft h e i i i a b s t r a c t m i n i m u mc o n v e xp o l y h e d r o n k e yw o r d s ：r o u t i n g ，r e c t i l i n e a rs t e i n e rt r e e ，o b s t a c l e s ，b o u n d a r y , e x t e n d e d h a n a ng r i d ，w e i g h t e dl e ea l g o r i t h m a m ss u b j e c tc l a s s i f i c a t i o n ( 2 0 0 0 ) ：0 5 c 0 5 ，0 5 c 8 5 ，6 8 w 2 5 ，6 8 w 3 5 i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：罗孝弓 年6 月悟日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： f 一。一一一一”- ：内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长l o 年，可少于1 0 年) ；机密 k 2 0 年( 最长2 0 年，可少于2 0 年) l 。，。， 。，。一。j 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 丐杨 乙9 。c i 年6 月必日 c h a p t e r1 v l s i p h y s i c a ld e s i g na u t o m a t i o n 1 1t h ev l s id e s i g np r o c e s s v l s io rv e r yl a r g es c a l ei n t e g r a t i o nr e f e r st oat e c h n o l o g yt h r o u g hw h i c h i ti sp o s s i b l et oi m p l e m e n tl a r g ec i r c u i t si ns i l i c o n c i r c u i t sw i t hu pt oam i l l i o n t r a n s i s t o r s t h ev l s it e c h n o l o g yh a sb e e ns u c c e s s f u l l yu s e dt ob u i l dm i c r o - p r o c e s s o r s ，s i g n a lp r o c e s s o r s ，s y s t o l i ca r r a y s ，l a r g ec a p a c i t ym e m o r i e s ，m e m o r y c o n t r o l l e r s ，i oc o n t r o l l e r s ，a n di n t e r c o n n e c t i o nn e t w o r k s p r e s e n t - d a yv l s it e c h n o l o g yp e r m i t si st ob u i l de n t i r es y s t e m sw i t hh u n d r e d o ft h o u s a n d so ft r a n s i s t o r so i las i n g l ec h i p f o re x a m p l e t h ei n t e l8 0 2 8 6m i c r o - p r o c e s s o rh a so v e r1 0 0 ，0 0 0t r a n s i s t o r s ，t h e8 0 3 8 6h a s2 7 5 ，0 0 0t r a n s i s t o r s ，a n dt h e 8 0 4 8 6h a sa p p r o x i m a t e l y1 , 0 0 0 ，0 0 0t r a n s i s t o r s t h er i s cp r o c e s s o rf r o mn a - t i o n a ls e m i c o n d u c t o rn $ 3 2 s f 6 4 1h a so v e ram i l l i o nt r a n s i s t o r s n o w ，t h e4 5n m 8 - c o r e “e n t e r p r i s e ”x e o np r o c e s s o ro fi n t e lh a s2 3b i l l i o nt r a n s i s t o r s i n t e g r a t e dc i r c u i t so ft h ea b o v ec o m p l e x i t yw o u l dn o th a v eb e e np o s s i b l e w i t h o u tt h ea s s i s t a n c eo fc o m p u t e rp r o g r a m sd u r i n ga l lp h a s e so ft h ed e s i g n p r o c e s s t h e s ec o m p u t e rp r o g r a m sa u t o m a t em o s to ft h ed e s i g nt a s k s d e s i g n i n g av l s ic h i pw i t ht h eh e l po fc o m p u t e rp r o g r a m si sk n o w na sc a d ，o rc o m p u t e r a i d e dd e s i g n d e s i g na u t o m a t i o n ( d a ) ，o i lt h eo t h e rh a n d ，r e f e r st oe n t i r e l y c o m p u t e r i z e dd e s i g np r o c e s sw i t hn oo rv e r yl i t t l eh u m a n i n t e r v e n t i o n c a da n d d ar e s e a r c hh a sal o n gh i s t o r yo fo v e rf o u rd e c a d e s s o m eo ft h ee a r l i e s tc a d 1 s o f t w a r ed e a l tw i t hp l a c e m e n to fl o g i cm o d u l e so np r i n t e dc i r c u i tb o a r d s ( p c b s ) a n df i n d i n ge l e c t r i c a lp a t h st ow i r et h ei n t e r c o n n e c t i o n s l o g i cm i n i m i z a t i o nw a s a l s oa ni m p o r t a n tf a c e to fe l e c t r o n i cd e s i g n ，s i n c ee l i m i n a t i n ge v e nah a n d f u l o fl o g i cg a t e sr e s u l t e di ns i g n i f i c a n tc o s ts a v i n g s a st e c h n o l o g yh a sc h a n g e d f r o ms m a l ls c a l ei n t e g r a t i o n ( s s i ) t ov e 巧l a r g es c a l ei n t e g r a t i o n ( v l s i ) ，t h e d e m a n do fd e s i g na u t o m a t i o nh a se s c a l a t e d ；t h et y p e so fd e s i g na u t o m a t i o nt o o l s h a v ea l s om u l t i p l i e dd u et oc h a n g i n gn e e d s f o re x a m p l e ，i nt h el s ia n dv l s i d o m a i n s ，i ti si m p o r t a n tt os i m u l a t et h eb e h a v i o ro fac i r c u i tb e f o r et h e c i r c u i th a s b e e nm a n u f a c t u r e d ；t h i si sb e c a u s ei ti si m p r a c t i c a lt ob r e a d b o a r dac i r c u i to fl s i c o m p l e x i t yi no r d e r t ov e r i f yi t sb e h a v i o r t h er a p i dc h a n g i n gt e c h n o l o g yh a sa l s o r a d i c a l l yt r a n s f o r m e dd e s i g ni s s u e s f o ri n s t a n c e ，i nt h el s i v l s it e c h n o l o g i e s ， i ti sn o tv e r yi m p o r t a n tt os a v eo nt r a n s i s t o r s ；t h ec o s tr e d u c t i o nt h r o u g hl o g i c m i n i m i z a t i o ni su n l i k e l yt ob es i g n i f i c a n tw h e nt h et o t a ln u m b e ro ft r a n s i s t o r s i si nt h eo r d e ro fam i l l i o n o nt h eo t h e rh a n d i ti si m p o r t a n tt os a v eo n i n t e r c o n n e c t i o nc o s t s s i n c ew i r e sa r ef a rm o r ee x p e n s i v ei nv l s it h a nt r a n s i s t o r s a sar e s u l to fs n s t a i n e dr e s e a r c h g r o u p sa l lo v e rt h ew o r l df o ro v e rf o u r a n dd e v e l o p m e n te f f o r t sb yan u m b e ro f d e c a d e s an u m b e ro fs o p h i s t i c a t e dd e s i g n t o o l sa r ea v a i l a b l et o d a yf o rd e s i g n i n gi n t e g r a t e dc i r c u i t s ，a n dw ea r eb r i s k l y m o v i n gt o w a r d sc o m p l e t ed e s i g na u t o m a t i o n i nt h i st h e s i s ，w ea r ec o n c e r n e d w i t ha l g o r i t h m sf o rv l s id e s i g na u t o m a t i o n ，w i t ha ne m p h a s i so np a y s i c a ld e s i g n a u t o m a t i o n p h y s i c a ld e s i g no fa ni n t e g r a t e dc i r c u i tr e f e r st ot h ep r o c e s so f g e n e r a t i n gt h ef i n a ll a y o u tf o rt h ec i r c u i t n e e d l e s st os a y , p h y s i c a ld e s i g ni so f v i t a li m p o r t a n c e ，a n dal i o n ss h a r eo fd e s i g na u t o m a t i o nr e s e a r c hh a sg o n ei n t o d e v e l o p i n ge f f i c i e n ta l g o r i t h m sf o ra u t o m a t i n gt h el a y o u tp r o c e s s s i n c et h ec o m p l e x i t yo fv l s ic i r c u i t si si nt h eo r d e ro fm i l l i o n so ft r a n s i s t o r s ， d e s i g n i n gav l s ic i r c u i ti su n d e r s t a n d a b l yac o m p l e xt a s k i no r d e rt or e d u c e t h ec o m p l e x i t yo fd e s i g np r o c e s s ，s e v e r a li n t e r m e d i a t el e v e l so fa b s t r a c t i o n sa r e i n t r o d u c e d m o r ea n dm o r ed e t a i l sa b o u tt h en e wd e s i g na r ei n t r o d u c e da st h e d e s i g np r o c e s sf r o mh i g h e s tt ol o w e s tl e v e l so fa b s t r a c t i o n s t y p i c a ll e v e l so fa b - s t r a c t i o n st o g e t h e rw i t ht h e i rc o r r e s p o n d i n gd e s i g ns t e p sa r ei l l u s t r a t e di nf i g u r e 1 1 a si n d i c a t e di nf i g u r e1 1t h ed e s i g ni st a k e nf r o ms p e c i f i c a t i o nt of a b r i c a - t i o ns t e pb ys t e pw i t ht h eh e l po fv a r i o u sc a d t o o l s c l e a r l yi ti sn o tp o s s i b l et o 2 c h a p t e r1 v l s ip h y s i c a ld e s i g na u t o m a t i o n s i td o w nw i t hp a p e ra n dp e n c i lt od e s i g nam i l l i o n t r a n s i s t o rc i r c u i t ( o rc h i p ) a h u m a ne n g i n e e rc a nr e a s o na b o u tah a n d f u lo fo b j e c t sa tb e s t i ti se a s yf o rah u - m a ne n g i n e e rt ot h i n ki nt e r m so fl a r g e rc i r c u i tm o d u l e ss u c ha sa r i t h m e t i cu n i t s ， m e m o r yu n i t s ，i n t e r c o n n e c t i o nn e t w o r k s ，a n dc o n t r o l l e r s d e s i g n i n gac i r c u i ta t t h i sl e v e lo fa b s t r a c t i o ni sk n o w na sa r c h i t e c t u r a ld e s i g n c a d s u b p r o b l e ml e b e h a v i o r a l ( a r c h i t e c t u r a l ) r e g i s t e rt r a n s f e r ( 1 0 9 i c ) c e l l ( m a s k ) a r c h i t e c t u r a ld e s i g n l l o g i c ad e s i g n i p h y s i c a ld e s i g n l f a b r i c a t i 。n i b e h a v i o r a lm o d e l i n ga n d s i m u l a t i o nt o o l f u n c t i o n a la n dl o g i cm i n i m i z a t i o n ， l o g i cf i t t i n ga n ds i m u l a t i o nt o o l s t o o l sf o rp a r t i t i o n i n g ， p l a c e m e n t ，r o u t i n g ，e t c f i g u r e1 1 l e v e l so fa b s t r a c t i o n c o r r e s p o n d i n gd e s i g ns t e p 1 2 p h y s i c a ld e s i g n p h y s i c a ld e s i g no fac i r c u i ti sp h a s e t h a tp r e c e d e st h ef a b r i c a t i o no fac i r c u i t i nm o s tg e n e r a lt e r m s ，p h y s i c a ld e s i g nr e f e r st oa l ls y n t h e s i ss t e p ss u c c e e d i n g l o g i cd e s i g na n dp r e c e d i n gf a b r i c a t i o n t h e s ei n c l u d ea l lo rs o m eo ft h ef o l l o w i n g s t e p s ：l o g i cp a r t i t i o n i n g ，f l o o r p l a n n i n g ，p l a c e m e n ta n dr o u t i n g t h ep e r f o r m a n c e o ft h ec i r c u i t ，i t sa r e a ，i t sy i e l d ，a n di t sr e l i a b i l i t yd e p e n dc r i t i c a l l yo nt h ew a y t h ec i r c u i ti sp a y s i c a l l yl a i do u t t ob e g i nw i t h ，c o n s i d e rt h ee f f e c to fl a y o u t ( p l a c e m e n ta n dr o u t i n g ) o nt h et i m i n gp e r f o r m a n c eo fac i r c u i t i na ni n t e g r a t e d c i r c u i tl a y o u t ，m e t a la n dp o l y - s i l i c o na r eu s e dt oc o n n e c tt w op o i n t st h a ta l e e l e c t r i c a l l ye q u i v a l e n t b o t hm e t a la n dp o l yl i n e si n t r o d u c ew i r i n gi m p e d a n c e s t h u saw i r ec a ni m p e d eas i g n a lf r o mt r a v e l i n ga taf a s ts p e e d t h el o n g e rt h e 3 c h a p t e r1 v l s ip h y s i c a ld e s i g na u t o m a t i o n w i r e ，t h el a r g e rt h ew i r i n gi m p e d a n c e ，a n dl o n g e rt h ed e l a y si n t r o d u c e db yt h e w i r i n gi m p e d a n c e w h e nm o r et h a no n em e t a ll a y e ri su s e df o rl a y o u t ，t h e r ei s a n o t h e rs o u r c eo fi m p e d a n c e i fac o n n e c t i o ni si m p l e m e n t e dp a r t l yi nm e t a l l a y e r 1a n dp a r t l yi nm e t a ll a y e r2 ，av i ai su s e da tt h ep o i n to fl a y e rc h a n g e s i m i l a r l y , i fac o n n e c t i o ni si m p l e m e n t e dp a r t l yi np o l ya n dp a r t l yi nm e t a l ，ac o n t a c t b e c o m e sn e c e s s a r yt op e r f o r mt h el a y e rc h a n g e c o n t a c t sa n dv i a si n t r o d u c ea s i g n i f i c a n ta m o u n to fi m p e d a n c e ，o n c ea g a i nc o n t r i b u t i n gt ot h es l o w i n gd o w no f s i g n a l s l a y o u ta f f e c t sc r i t i c a l l yt h ea r e ao fac i r c u i t t h e r ea r et w oc o m p o n e n t st o t h ea r e ao fa ni n t e g r a t e dc i r c u i t t h ef u n c t i o n a la r e a ，a n dt h ew i r i n ga r e a t h e a r e at a k e nu pb yt h ea c t i v ee l e m e n t si nt h ec i r c u i ti sk n o w na st h ef u n c t i o n a l a r e a f o ri n s t a n c e ，i nt h ee x a m p l eo ft h es e r i a la d d e r ，t h ef u n c t i o n a lm o d u l e sa r e t h ef u l l a d d e r ，t h er e g i s t e r s ，t h em u l t i p l e x e r s ，t h edf l i p - f l o p ，t h ec o u n t e r ，a n d t h el o g i cc i r c u i t sn e c e s s a r yt oi m p l e m e n tt h ec o n t r o lp a t h t h ea r e ao c c u p i e d b yt h e s em o d u l e sc o n s t i t u t e st h ef u n c t i o n a la r e ao ft h ec i r c u i t t h ew i r e su s e d t oi n t e r c o n n e c tt h e s ef u n c t i o n a lm o d u l e sc o n t r i b u t et ot h ew i r i n ga r e a j u s ta s t h e ya f f e c tt h ep e r f o r m a n c eo ft h ec i r c u i t ，l o n gw i r e sa n dv i a sa l s oa f f e c tt h ea r e a o fc i r c u i t ag o o dl a y o u ts h o u l dh a v es t r o n g l yc o n n e c t e dm o d u l e sp l a c e dc l o s e t o g e t h e r ，s ot h a tl o n gw i r e sa r ea v o i d e da sm u c ha sp o s s i b l e s i m i l a r l y , ag o o d l a y o u tw i l lh a v ea sm u c ha sp o s s i b l ea sf e wv i a sa sp o s s i b l e t h ea r e ao fac i r c u i th a sd i r e c ti n f l u e n c eo nt h ey i e l do ft h em a n u f a c t u r i n g p r o c e s s w ed e f i n ey i e l dt ob et h en u m b e ro fc h i p st h a ta r ed e f e c t f r e ei nab a t c h o fm a n u f a c t u r e dc h i p s t h el a r g e rt h ec h i pa r e a ，t h el o w e rt h ey i e l d al o w y i e l d w o u l dm e a nah i l g hp r o d u c t i o nc o s t ，w h i c hi nt u r nw o u l di n c r e a s et h es e l h n gc o s t o f t h ec h i p t h er e l i a b i l i t yo ft h ec h i pi sa l s oi n f l u e n c e db yt h el a y o u t ，f o ri n s t a n c e ， v i a sa r es o u r c e so fu n r e l i a b i l i t y , a n dal a y o u tw h i c hh a sal a r g en u m b e ro fv i a si s m o r el i k e l yt oh a v ed e f e c t s f u r t h e r ，t h ew i d t ho fam e t a lw i r em u s tb ec h o s e n a p p r o p r i a t e l yb yt h el a y o u tp r o g r a mt oa v o i dm e t a lm i g r a t i o n i fat h i nm e t a l w i r ec a r r i e sal a r g ec u r r e n t ，t h ee x c e s s i v ec u r r e n td e n s i t ym a yc a u s ew e a r i n g a w a y o fm e t a l ，t a p e r i n gt h ew i r es l o w l y , r e s u l t i n gi na no p e nc i r c u i t 4 c h a p t e r1 v l s ip h y s i c a ld e s i g na u t o m a t i o n 1 3 r o u t i n g t h et w op r i n c i p a ls t e p so fp h y s i c a ld e s i g na r ep l a c e m e n ta n dr o u t i n g p l a c e - m e r i ti st h ep r o c e s so fa r r m l g i n gt h ec i r c m tc o m p o n e n t s0 1 1al a y o u ts u r f a c e p l a c e m e n tc o n s i s t so fa s s i g n i n gt h ec e l l so ft h ec i r c u i tt of i x e dl o c a t i o n so ft h e c h i p ，w h i l er o u t i n gc o n s i s t so fi n t e r c o n n e c t i n gt h ec e l l sc o n s i s t e n t l yw i t ht h ec i r - c u i tn e t l i s t a l lo ft h em a t h e m a t i c a lm o d e l so ft h ep l a c e m e n tp r o b l e mg a v er i s e t on p h a r dp r o b l e m s i ti sf o rt h i sr e a s o nt h a th e u r i s t i ca p p r o a c h e sa sw e l la s h i e r a r c h i c a ld e c o m p o s i t i o na r eu s e dt of i n das o l u t i o n ( u s u a l l ys u b - o p t i m a l ) t o t h ep l a c e m e n tp r o b l e m s i m i l a r l y , a l lo ft h em a t h e m a t i c a lf o r m u l a t i o n so f