（计算机应用技术专业论文）基于布线区域密度最小化的自动布线算法的研究.pdf

华中科技大学硕士学位论文 摘要 i ( 几乎所有的自动布线问题都是困难的n p 问题。在计算机技术和信息产业飞速 发展的今天，自动布线已被广泛应用于v l s i l s i 设计、逻辑图的绘制、印刷板的设 计以及网络的物理布线等领域；同时，由于当前现存的自动布线算法各有长处，也各 有局限，尚无一种布线算法能真正地完全满足人们的需求。从而使得对自动布线算法 的研究更有价值。口 ( 由于在整个布线过程中，布线区域的密度减少不仅意味着整个布线过程中的连线 总长度更短、布线成功率更高，而且对于v l s i l s i ，它还意味着更小的串扰、功耗 ，正， 和时延，对于逻辑图，它则意味着更高的布线质量和更好的布线效果。为此，搬瓶一。“ 出的布线算法就是以有效减小布线区域密度作为其目标，并对具有规则边界的区域和 具有不规则的边界的布线区域分别进行处理。 对于具有规则边界的区域，在确定系统的可布通性的基础上，对各布线子通道的 行列密度进行估计，尽量消除雍线单元的溢出，并实现了各单元列密度的均匀化：然 后以x 桶表和y 桶表作为基本的数据结构，提出了一种利用扫描线确定最终布线时 的走线道的布线算法，在确保布通率为1 0 0 的前提下，进一步减少了布线区域的密 度。 对于具有不规则的边界的布线区域，我们采用积木块布线算法对其实施布线，在 总体优化阶段，我们尽可能地提高了残余区的利用率，并通过积木块的平移和旋转等 方法使得熬个布线区域布线密度尽可能减小；在详细布线阶段，我们通过构造虚拟子 线网，灵活变换布线目标等方法，对布线区域进行了较充分地利用，从而有效地减小 了通道区的宽度，降低了整个布线区域的布线密度。 f 结合我们当前所开发的系统“分布式虚拟实验环境构造及设计型实验支撑平 台”，以数字逻辑虚拟实验环境中的逻辑图和实物台上各元器件的连接为例，阐述了 这一布线算法的具体实现。以实例说明这一布线的可行性和易操作性。人，一 关键词：自动布线；桶表i 虚拟子线网；残余区；通道密度 华中科技大学硕士学位论文 a b s t r a c t a l m o s ta l lo fa u t o m a t i cr o u t i n ga l g o r i t h m sa r ed i f f i c u l tk n o w na sn p p r o b l e m s t o d a y ，w i t ht h ea d v a n c e m e n to f t h ec o m p u t e r t e c h n o l o g ya n d i t i n d u s t r y ，a u t o m a t i cr o u t i n gi sw i d e l ys u p p l l e di ns e v e r a lv a r yo ff i e l d ss u c h a st h ev l s i l s id e s i g n ，t h ed r a w i n go fl o g i cd i a g r a m ，p c bd i a g r a m sd e s i g na n d t h ep h y s i c a lr o u t i n go ft h en e t w a r ee t c a tt h es a m et i m e ，s o m eo fa u t o m a t i c r o u t i n ga l g o r i t h m sh a v es o m ei i m i t a t i o na sw e l la st h e i rv i r t u e s ，a n dt h e y c a nn o ts a t i s f yp e o p l e sn e e dc o m p l e t e l y a 1 1t h a tm a k ei ti sw o r t hb e i n g r e s e a r c h e df a rm o r e i nt h ew h o l er o u t i n gp r o c e s s ，r e d u c i n gt h er o u t i n gd i s t r i c t sd e n s i t yis n o to n l ym e a nt h et o t a ll e n g t ho fa 1 11 i n e si s s h o r t e r ，t h er a t eo fs u c c e s s i sh i g h e r ，b u ta l s of o r t h ev l s i l s i ，i ts t i l lm e a n st oh a v eg o ts m a l l e r c r o s s t a l k ，p o w e ra n dt i m i n g 。a n df o rt h el o g i cd i a g r a m s ，i tm e a n st h eh i g h e r q u a n t i t ya n dt h eb e t t e re f f e c t b e c a u s eo fi t ，t h er o u t i n ga l g o r i t h mw eb r i n g f o r w a r dt h a ta i m sa tr e d u c i n gt h er o u t i n gd i s t r i c t sd e n s i t ye f f e c t i v e l y a n di t p r o c e e d st h er o u t i n gi nd i f f e r e n tw a yf o rr e g u l a ra r e aa n di r r e g u l a r a r e a f o rt h ed i s t r i c tw i t hr e g u l a rb o u n d a r y ，t h er o wo rc o l u m nd e n s i t yi sb e i n g e s t i m a t e da t f i r s t ，t h e ne l i m i n a t et h eo v e r f l o wi fi tt a k e sp l a c e ，a n d r e a l i z e st h eu n i f o r m i t yo ft h er o wo rc o l u m n a l lt h a tb a s eo nt h ea r e a s r o u t i n gb e i n gs u c c e s s a tl a s tw eb r i n gf o r w a r dak i n do fa l g o r i t h mt of i n d t h er o u t ei nt h ef i n a lr o u t i n gb yu s i n gs c a n1 i n eb a s e do nt h eb a r r e ll i s t t h i sa l g o r i t h mi sn o to n l ym a k es u r et h es u c c e s sr a t ei s1 0 0 b u ta l s or e d u c e t h ed e n s i t yo ft h er o u t i n ga r e a f o r t h ed i s t r i c tw i t h i r r e g u l a rb o u n d a r y ，w ea c c o m p l i s hr o u t i n gb y b u i l d i n gb l o c k s i nt h et o t a lo p t i m a lp h a s e 。w er e d u c et h ed e n s i t yo ft h e r o u t i n ga r e aa sp o s s i b l eb yas e r i a lo fw a ys u c ha si m p r o v i n gt h eu t i l i z i n g o ft h er e m n a n tc h a n n e la n dm o v i n go rc i r c u m g y r a t i n gt h eb u i i d i n gb l o c k i n t h ed e t a i lr o u t i n g ，w eu t i l i z et h e r o u t i n ga r e aa d e q u a t e l ya n dm i n i s ht h ew i d t h o ft h er o u t i n ga r e aa v a i l a b l yb yc o n s t r u c t i n gv i r t u a ls u b n e ta n d a l t e r i n gt h e o b j e c t f u n c t i o ne a s i l y 1 1 华中科技大学硕士学位论文 a t l a s t ，i n t h es y s t e m d is t r i b u t ev i r t u a l l a b o r a t o r yb u i l d i n g a n d d e s i g n a b l el a b o r a t o r ys y s t e m ，w ea c c o u n tt h er e a l i z a t i o no ft h i sa l g o r i t h m b y t h e e x a m p l e s u c ha st h e1i n k a m o n ge a c h u n i ti nt h e 1 0 9 i cd i a g r a mo r p r a c t i c a ld i a g r a mo nt h ev i r t u a ll a b o r a t o r y a n di tp r o v e do u ra l g o r i t h mi s u s e f u la n de a s yo p e r a b i1it y k e y , o r d s ：a u t o m a t i cr o u t i n g ：b a r r e l1 i s t ； v i r t u a ls u b n e t s ： r e m n a n ta r e a ；c h a n n e ld e n s i t y i i i 华中科技大学硕士学位论文 1 绪论 1 1 引言 自动布线是计算机设计自动化的一个重要环节，也是计算机辅助设计的一个重要 课题。随着计算机工业的飞速发展和大规模、超大规模集成电路的出现，芯片的集成 度越来越高，印刷电路越来越复杂，布线的难度也越来越大，已非人工布线所能及， 自动布线的研究工作也应运而生。 自1 9 6 1 年，c y , l e e ( 李氏) 发表了“路径连接算法及其应用”i i 】一文。为用计算机 实现自动布线开辟了道路。此后，除了李氏算法及李氏算法的各种改进型，4 】外，还 提出了线探索法【5 1 ，通道分配法【6 】，细胞结构法【7 1 ，拓扑类布线，饱和区合并法【8 9 j 等各种布线方法。其中李氏算法，线探索法和通道分配法较为实用。 李氏算法又称为迷宫算法( m a z e r u n n i n ga l g o r i t h m ) 或波扩法，实际上是图论中最 小路径算法在矩形网格上的一种应用。它本质上是一种遍历性质的逐点查找法，属于 “广探”。其优点是只要最短路径存在，就一定能找到，故丽其布通率高，线型好； 然而其缺点也是明显的，对于n n 的网格空间，它需要o ( n 2 ) 的运行时间和存储空间。 所以，尽管李氏算法有许多优点，但其固有的缺点迫使人们寻找新的解决方法。 相对于李氏算法，由d w h i g h t o w e r 最先提出的线探索法【5 j 可以认为是改善了性 能，因为它速度快，占用内存小，从而有效地节省了空间和时间，并使路径的拐弯数 达到最小( 在多层布线中这一点特别有用) 。然而它布通率较低，很多时候不能保证找 到路径，即使找到路径，一般也不是最短路径；要不就将有同迷宫算法一样的时空复 杂度。 7 0 年代初，通道分配法出现，它是一种从全局观点出发进行布线的算法，在此 方法中，整个布线场被分成一系列的布线区域通道区。通道区一般是平行通道， 它是由上、下两个边界和左、右两个开边组成韵矩形区域。边界上的出线端位鼹是固 定的，开边上的线网位置是浮动的，矩形的宽度在布线之前是未知的，在布线过程中 可以调整。布线时，我们依据一定的约束条件，按照一定的次序，逐一完成这些通道 区的布线。采用通道法布线，速度快，内存量小，走线规则、布通率介于线探索与迷 宫法之间，但使用导孔多，导孔压缩困难。 由于最一般的布线问题也几乎都是困难的n p 问题。而人们对布线过程提出的要 求通常是：在给定大小的区域内实现1 0 0 0 布通率，或在保证芯片的特定宽长比情况 下使布线区域面积最小，以及实现通孑l c v i a ) 数目最小化等，这些都使得布线问题更为 复杂。 华中科技大学硕士学位论文 同时，随着计算机技术和信息产业的飞速发展，自动布线算法的使用范围越来越 广泛，不仅在大规模集成电路、超大规模集成电路的设计中人们会使用到自动布线这 一算法，而且在版图设计、虚拟实验环境中的逻辑图绘制及实物图绘制中都不可避免 地要使用到自动布线算法。更为突出的是，在当前计算机网络迅猛发展的今天，网络 布线算法及其优化也逐渐成为人们所日益关注的焦点之一。 然而，时至今日，现存的布线算法虽然数量众多，但它们各有长处，也各有局限， 尚无一种布线算法能真正地完全满足人们的需求。如何综合这些算法，以获得一种新 型的具有高布通率、高速度、占用内存较少、使用导孔少的布线方法是p c bc a d 技 术的一个重要课题。 1 2 自动布线的数学模型 自动布线设计通常分总体布线和详细布线两个阶段。在每个阶段，如果有合适的 数学模型，即提出的目标函数能够真实地反映出布线的各种情况，则布线问题就可以 用数学的方法得到精确解答。遗憾的是，几乎所有的布线问题都被证明是n p 完备问 题，无法得到这一精确的数学模型。因此，用启发式原则在开发自动布线软件中占着 相当大的比重。 在详细布线方面，已经有了不少布线方法，许多都是基于启发式原则提出的。这 些方法有以下几类： 1 用贪婪方式布线 即布线时尽可能利用当前的走线道。如左边算法、g r e e d y 算法和d e t o u r 算法等。 该方式尤其适用于通道布线。 2 用专家知识布线 即将启发式的布线规则一条一条地列出，然后以基于规则的方式加以判断选择布 线路径，如w e a v e r 算法，双面两维布线算法等。 3 用图论知识或优化方法布线 即将布线问题近似地归结为一张图或一个目标函数来实现。如合并一匹配算法， 二分图法、区域布线法和整数优化法等。 4 用减少冲突的方法布线 即在充分考虑当前线网对未布线网的影响的基础上选取布线路径，如h s u 的2 一 d 算法，最小冲突法，m i g h t y 算法，b e a v e r 算法和样式布线法等。 实际布线时，上述几种方法往往是综合使用，并无严格界限区分。此外，还有用 物理过程模拟布线的方法，如波扩展法( 即李氏算法) ，模拟退火法等。 2 华中科技大学硕士学位论文 1 3 布线过程中应考虑的因素 如前所言，自动布线一般是借助于一些启发式原则来实现的。所以，在整个布线 过程中应考虑的因素就是这样一些启发式原则。 所谓启发式原则，就是模拟人的设计经验和思维方式的方法。对布线来说，该原 则可以不断地总结和摸索出。这里，我们提出几个主要的原则，并将其用“权”的方 式表达出。 值得注意的是，对下面每一项原则，重点不是权值的大小，而是要确定他们之间 的相对比例。因此，必须根据布线的实际情况，分清各项原则的轻重缓急，确定其选 择条件和相互间的比例系数。这样才能构造出接近实际的路径图，得出较优的布线解。 以下各项原则，主要是针对四边通道布线问题的h v 方式提出的。对于通道布线问 题，考虑的因素要简单得多，只要选其中某些项目就行了。 1 密度权w t d ( d e n s i t yw e i g h t ) 布线区某行列的局部布线密度越高，则通过该行列的线网数就越多，越容易 发生线网冲突，故布线时应尽量避免将连线段落在该位置上。 设l 为选择线段的长度，d e n 为该线段所处位置的行列密度，毛为密度权因子。 则密度权表达式为： w t d = f d d e n 1 2 约束权w t e ( c o n s t r a i n tw e i g h t ) 如果当前线网存在约束，即在垂直和水平方向上的约束图( b y 约束，对通道布线 为垂直约束图g v ) 中，线网节点不是一个孤点时，考虑约束权。 定义1 约束希望区是根据线网的水平垂直方向约束图决定的区域。设n 为线网所处的水 平垂直约束链上的节点数，l 为布线区的水平垂直边界长度，则约束希望区长度 定义为： l 。= l 1 1 设g 。( d ) 是随距离d 变化的约束函数，c 是常数，f c 是约束因子，则约束权定义为： w t c = f c ( g c ( d ) 十c ) 其中约束函数的意义为：对位于约束链下左半段的线网，我们希望连线段落在 约束希望区的下限( 即越靠近下左边界越好) ：对位于约束链上右半段的线网，希望 落在希望区的上限。 3 端点权w t t ( t e r m i n a iw e i g h t ) 如果当前线网的连线段对应着布线区边界上的连线端点，则有端点权。即尽量选 3 华中科技大学硕士学位论文 择不具有连接端点的行走线道或拐角距离连接端点远的行走线道。 设g t ( d ) 是距离d 的端点函数，c 为常数，是端点权因子，则端点权可定义为： w t t = g t ( d ) 十c 。 式中，端点函数g 。( d ) 曲线可用a 、k x 等函数表示。即连线段到端点的距离d 越 小时，端点权的变化就越明显。 4 推入权w t p ( p u s h i n w e i g h t ) 其概念是尽量将线网推入布线区域中间。由于布线区四周边界附近的走线道上线 网的活动自由度最低，线网路径的选择范围最小，故布线时应尽量腾出该区域让真正 需要的线网占用。 设酃( d ) 是距离d 的推入函数，f p 是推入因子，则推入权定义为： 、v t p = f p 。酃( d ) 须特别指出，本权值与线段的布线顺序密切相关。如果类似文献【1 0 1 那样，布线时 是逐渐从边界往里伸长。当有唯一路径时就选取了该路径，显然应考虑推出权( p u s h o u t w e i p l a t ) ，即将线网往外推，以让出更多的空间布其它线网。 5 目标权w t o ( o b j e e t i v ew e i g h t ) 如果连线段背离连线目标，应考虑目标权。即尽量使线网由起点出发，除若干特 殊情况外，始终朝向目标前进。 设d 是连线段偏离目标的距离( 称偏目距) ，是目标权因子，则目标权定义为： w t o = f o d 6 最短适应权w t s ( s h o r t f i t w e i g h t ) 根据贪婪式的启发原则，布线时应尽量考虑使用已用过的走线道。从而为后续布 线腾出更多地走线道。 设i e n g t h 是还未使用的走线道长度( 称可利用线轨长度1 ) ，是最短适应因子， 则最短适应权为： w t s = f s l e n g t h 7 长度权w t l ( l e n 【g t hw e i g h t ) 长度权是根据线网连线长度最短这一目标确定的。线网长度最短，既可以提高后 续线网的布通率，同时也改善了所布线网的线型。 设l e n g t h 为当前选择线段的长度，为长度因子，则长度权为： w t l = f i l e n g t h 当然，在不同的应用环境下，自动布线算法可能需考虑其他一些与具体应用相关 的因素，如在集成电路布线时，功耗、时延以及串扰往往也是用来衡量布线效果的一 4 华中科技大学硕士学位论文 些重要因素：而在逻辑图布线时，规范性、易读性、美观性则是不可忽略的重要因素， 有时甚至为了布线的效果令人满意，美观易读，而不一定要求得到的布线是最短的。 1 4 解决布线问题的思路 面对布线中各种n p 完备问题，人们已经提出了许多有效的解决方法。如图1 1 所示。 图1 1 六种解决布线问题的思路 一种解决思路是首先将复杂问题分解为一些援模较小的问题，分而治之，具体而 言，就是将整个布线过程分为总体布线和详细布线两步，先完成总体布线，再进行详 细布线，当然根据具体问题还可以继续划分。第二种解决思路是如何在已有算法的基 础上，同时布多个线网，加快算法的速度，如人们提出的各种并行布线算法，这些算 法同时布多个线网，算法速度确实有所提高。第三种思路是利用各种有效的智能算法， 如模拟退火、神经网络【挖l 、遗传算法【1 3 l 、网络流、整数规划和蚁群算法f h l 等来解决 一个具体问题，这样有望得到较小的时间复杂度和更好的布线质量。第四种思路是利 用计算机复杂的编程技术，如多进程或多线程等【i 卯，同时布多个线网，这样来提高算 法的速度。第五种思路是利用大规模并行处理计算机系统将传统串行算法改为适合在 多个c p u 上并行计算的并行算法，如共享主存m i m d 开关盒并行布线迭代改善法l l “。 第六种思路就是利用i n t e m e t 上强大的计算资源，实现基于w e b 的分布式布线环境， 缩短布线问题的解决时间。 其中，第一种思路是较传统的方法，同时它也是当前流行最为广泛、使用最为普 遍的算法，当前的许多自动布线器基本都是基予这一思路设计和实现的。但是其在布 线效率、布线质量等方面存在某些明显的缺陷。其它几种思路则是对这一传统的思路 的改进，尤其是第六种思路，是当前最为先进、也是实际可行的种思路，是e d a 发展的一个方向。 5 华中科技大学硕士学位论文 1 5 课题主要研究工作 本文在深入研究当前现存的各种自动布线算法的基础上，提出了一个通道密度最 小化的自动布线算法。并分别讲述了在标准的具有平行边界的通道和具有不规则边界 的通道中，其所采用的总体布线和详细布线具体方案。本论文共有六章，其中第一章 简要介绍了自动布线算法的研究意义及基本情况：第二章回顾了以前的总体布线算法 和详细布线算法，以及以前的并行布线算法；第三章论述了我们提出的针对具有标准 的平行边界的布线区域的以通道密度最小化为目标的自动布线算法：第四章论述的则 是对于具有不规则边界的布线区域，我们如何充分利用整个布线区域，从而降低整个 通道密度的算法；第五章中，我们介绍了在我们开发的虚拟实验环境中，如何利用该 思路完成数字逻辑实验平台的自动布线算法：最后第六章是总结。 本算法克服了以往的自动布线算法没有从整个系统的总目标出发来开展研究，从 而造成系统中某一子系统所服务的总系统的目标与前级或后级系统的目标不相一致 甚至互相矛盾的弊端。它不仅能用来解决简单的逻辑图布线、版图设计或一般的门阵 总体布线问题，在大规模集成电路( l s i v l s i ) 自动布图设计系统更显出其优越性。 6 华中科技大学硕士学位论文 2 布线算法的发展概况 2 1 布线问题 早期的自动布线算法基本上被应用于大规模集成电路( l s 0 或超大规模集成电路 ( v l s i ) 的设计之中。在v l s i 设计中，布线过程是物理设计中布局之后的重要步骤， 布局确定了模块在芯片上的位置和模块上各引脚的位置，并通过网表提供了各引脚间 的互连信息。布线过程就是实现各模块间的连接。布线过程可以分为总体布线和详细 布线两个步骤，总体布线为每个线网寻求一个布线路径，而详细布线则为每个线网分 配实际的通道和过孔。总体布线把每条线网的各部分合理地分配到各个布线通道中 去，并明确定义各布线通道区中的布线问题。各通道布线问题在详细布线时由通道布 线器( 算法) 完全布通。 若布局结果有一个可二分的结构，详细布线时仅需要通道布线器完成最终布线。 对不可二分的布局结果，在一些通道的结合处则需要一些开关盒算法( s w i t c h b o x ) 。 一个开关盒是一个四边上都有引脚的矩形。这时，布线问题分为了总体布线、通道布 线和开关盒布线。 区域布线是直接在一个区域内( 可多层) 进行布线。一个区域布线算法可以没有 总体布线过程i l 卜2 l 】。但是布线在一个阶段进行，通常只能解决规模较小的问题，对 诸如b b l 布图模式的问题通常是不可行的。对现代电路来说，“分而治之”的方法更 加实际。 2 2 以前的总体布线算法 总体布线又称为概略布线( 1 0 0 s em u t i n g ) ，它是以使整个布线设计的布线完成率 尽可能高或整个布线设计完成后芯片的面积尽可能小为优化目标。总体布线是要把每 条线网的各部分都合理地分配到各个布线通道区中去，并明确定义各布线通道区中的 布线问题。 总体布线问题是一个典型的图论问题，布线区域及其布线的容量，区域之间的相 互关系等都可以抽象为一张布线图，通常布线图可以分为三类。 第一种是网格图模型，如图2 1 所示。这种模型最简单，整个芯片被划分为一个 m n 的矩阵，每个单元由一个结点表示，结点间有水平和垂直边连接。各线网的引 脚都映射到这些结点中。这时的总体布线问题是寻找一条路径来连通网格图中的相应 结点。这种模型在标准单元、门阵列布图模式下工作得非常好。另外，这种模型可以 结点。这种模型在标准单元、门阵列布图模式下工作得非常好。另外，这种模型可以 7 华中科技大学硕士学位论文 在扩展后用以解决多层布线问题。然而，网格图模型在b b l 布图模式下不见得是一 个优选的模型。 圈2 i 一播墨曩矗 第二种模型是布图规划图模型。一个布图规划图可以从布局结果构造出来，在布 局结果中的一个模块由一个结点来表示，若两个模块相邻，那么对应的两个结点之间 便有一条相邻边，同样，各引脚也被映射到结点中。图2 2 是一个布图规划图模型的 一个例子。布图规划图模型常用于为模块间的布线容量建模，这种模型对连线长度估 计的结果不能令人满意。 ( b 第三种是通道相交模型。这是一种最为常用而又能准确表达信息的模型。给定一 个版图布局，我们可以定义通道相交图( 又叫总体布线圈) g = ( v ，e ) ，其中v 是 版图中一个通道与另一个通道的相交点的集合。若v v i ，v je v ，并且这两个结点间 存在一个通道，那么v i 和v j 相邻，即在通道相交图中有一条边e i j e 连接v i 和v j 。如 图2 3 所示。 i i：舆i 壁 l 圈| _ 捆2 3 曩避搬蹦盥 ( b ) 8 华中科技大学硕士学位论文 各模块上的引脚映射到总体规划图相应的边上形成新的结点，这样总体规划图便 被扩展为一个带有布线所需信息的总体布线图。 总体布线算法的目标是为每个线网找到一个大致的路径，在满足各种约束的条件 下，它为每个线网分配合适的通道。首先从布局结果定义一个布线图，边和结点对应 芯片上的通道或布线区域，然后，各线网的引脚被映射到图中，最后开始对每个线网 进行布线。算法成功结束后生成的是连接各个线网的子图。 若所有线网按某种顺序一个一个地布线，这就是串行算法。显然，后布的线网面 临着更大的约束，选择的余地较小，这就是线网排序问题。串行算法本身存在着较严 重的顺序依赖性。要彻底避免线网排序问题，普通可以采取随机技术或者同时布所有 的线网。【2 2 】中提出一种解决总体布线的整数规划方法，他们采用布图规划图，将布 线问题转化为一个整数规划问题，通过解整数规划问题，在满足约束的条件下完成了 布线。但是，当问题规模增大时，解决整数规划的时间成指数增长，因此，必须将问 题分解为几个子问题进行求解。各个子问题分别求解，最后综合起来解决原来的问题。 许多总体布线算法基于网格图或网格结构 2 3 2 蜘，网格图很简单，并且很直观，对 标准单元、门阵列和门海阵列电路非常适合。网格图的精确程度依赖于网格的大小， 网格可以小到为一个布线道，但这样会增加问题的规模。对大电路来说，网格图不太 实际。通常，网格图不适合用于b b l 模式总体布线。 从布图布局结果来形成的布线图能更加精确的描述b b l 布图模式的电路。最精 确的布线图是通道相交图扩展成的总体布线图。 2 6 】中采用了总体布线图。 总体布线图的本质问题是寻找最优的布线路径。对两端线网，可以采用线探测方 法，迷宫技术和a 搜索技术【2 7 l 。对于多端点线网，总体布线可以定义成一个寻求连 接树的问题。有一种办法是先将多端点线网分成几个两端点线网，然后分别采用最短 路径方法加以求解，这种方法的结果不太好。另一种方法是用最小生成树来求解线网 的连接1 2 ”。最自然的方法是用斯坦纳( s t e i n e r ) 树来求解布线问题。斯坦纳树是一棵 连接待定要求点集合和一些其它成为斯坦纳点的连接树，其中斯坦纳点的数量是任意 的。由于它具有比其它方法求得的连接树总长度更小的优点，往往被用来作为在总体 布线中构造连接树的方法。所以，总体布线问题可以看作是在一个总体布线图中，在 期望目标函数最优化的条件下，针对每条线网寻找一棵斯坦纳树的问题。通常一个典 型的目标函数就是所选择的连接树的总长度最小。 若在总体布线图上不存在满足通道容量线网集合的可行解，则布局必须进行调 整，一般的总体布线问题可以定义如下： 9 华中科技大学硕士学位论文 给定一个网表n = n l ，n 2 ，n 。 ，和一个总体布线图g = ( v ，e ) ，对任意n n n ，l i n ，找到一棵斯坦纳树t ，使得y l ( i ) 最小，同时应满足u ( e ) c ( e j ) ，e j 蜀 e 。其中，l ( t i ) 为斯坦纳树t 的长度，l ( t i ) = y f ( p ) ，l ( e i ) 为边c i 的长度；u ( e j ) 是 嚣 通过通道边e j 的线网数，它由式子：u ( e ) = 宇x 决定，如果 在。中则= 1 ；否 篇1 , i e j t x i j 则x i j = o 。 常见的总体布线算法有以下几种：串行布线，并行布线，动态资源竞争，静态资 源竞争，t o p _ d o w n 。b o t t o m - - u p 等。 串行布线是一次性布线方法。这种方法一次只考虑一条线网，缺乏全局性，如果 布线顺序安排得不合理，则可能导致布不通。 并行布线方法虽然在初布阶段对各线网是并行处理的，但在重布阶段要涉及到顺 序问题，如果顺序处理不当，则可能使迭代过程发散，布线失败。 动态资源竞争方法无需处理线网的顺序，重布过程亦然。但是由于动态资源竞争 方法的控制系统较复杂。实现起来很困难，执行时间也比其它方法要长。所以这种方 法对于规模较大的布图设计会有一定困难。 由于静态资源竞争方法对溢出区所作的分析是全局性的，所以该方法整体合理性 较好，且符合线网在芯片上分配均匀的要求。然而，在构造可能通路时缺乏预见性， 删除冗余通路所花时间较长，另外，增加可能通路需要的存贮空间也相应增加。 t o p - - d o w n 层次布线方法是依照自顶向下的原则处理总体布线问题，这种方法速 度很快，而且和线网的顺序无关，但它要求芯片上通道容量和管脚均匀分布，另外， 由于决策过程是自顶向下的，所以上层的错误决定会影响下层的处理，产生连锁反应。 文献【2 9 】提出了一种由快速初布和重布组成的总体布线方法。其中初布采用的是 b o t t o m - - u p ( b p 自下而上) 的处理原则。该方法在为各线网构造通路时是独立的，避免 了确定线网的顺序，由于初布阶段采用了自下而上的层次布线方法，所以速度较快。 但由于这种方法是从局部向总体进行布线的，因而它缺乏全局性在某些情况下，虽 然局部达到了最优，但有可能总体效果很差，这将使重布时间很长。 进入深亚微米工艺技术后，由于时延已成为了影响芯片性能的重要因剥3 0 】，因此 人们提出了时延驱动的总体布线算法【3 卜3 2 1 。另一方面，由于几何尺寸不断减小，互 连线放置更加紧密，因此相邻线网间的耦合电容显著增加。由此导致的串扰噪声在高 性能电路设计中已引起人们的极大关注。若不进行优化，串扰会引起信号延迟、逻辑 不稳定。甚至电路功能不正常。因此人们提出一些在总体布线阶段考虑串扰的总体布 1 0 华中科技大学硕士学位论文 线算法。 2 3 以前的详细布线算法 详细布线( d e m i l e dr o u t i n g ) 确定线网中各个网段在布线区域中的具体位置，从而 完成线网在布线区域的最后定位。 根据布线区域的不同，详细布线主要分为通道布线和开关盒布线两种。通道有两 条边，线网的引脚分布在这两条边上。开关盒也叫四边通道，线网的引脚分布在布线 区域的四周。 2 。3 1 详细布线的技术 详细布线采用的基本布线技术有三种。 第一种是盲目搜索算法。m o o r e l 3 3 1 在1 9 5 9 年为迷宫问题引进了最短路径算法，也 就是一个广度优先搜索算法。李氏算法首先将m o o r e 算法用于基于网格的线网布线 中。 第二种是最好优先的搜索算法- a 算法【3 4 1 。与盲目搜索算法不同，a 算法度量 从源点到目标点期望路径的长度，并且总是扩展具有最小度量值的网格。扩展在到目 标点的度量的指引下进行，因此，这种算法也叫定向搜索算法或最好搜索算法。若最 短路径存在，a + 算法保证能将其找到。 第三种是双向搜索算法。双向搜索算法相对于无方向的搜索算法的优势是搜索的 范围更小。 2 3 2 详细布线采用的数据结构 详细布线运用的数据结构主要有三类： 第一类：基于网格的数据结构； 第二类：基于线的数据结构； 第三类：基于t i l e 的数据结构。 基于网格搜索的算法使用网格点作为布线资源，因此将占用大量的内存来存放布 局，其空间复杂度为n tx n 2 。其中n l 和n 2 分别为舨图的长和宽。基于网格的算法 容易实现，却因为搜索空间( n ix n 2 的网格平面) 太大而导致很高的时间复杂度。 基于线的搜索( l i n e b a s e ds e a r c h ) 使用线段作为布线资源，因此占用的内存使 用网格点作为布线资源的迷宫算法明显减少。基于线搜索的算法是从源点和目标点产 华中科技大学硕士学位论文 生两个直线表s l i s t 和t l i s t ，产生的线不能穿过障碍物。如果s l i s t 中的直线和t l i s t 中的 相交，那么搜索就结束；否则，继续产生新的直线。这些直线要起源于s l i s t 与t l i s t 线上的“逸出点”。新的s l i s t ( t l i s t ) 线要与原s l i s t ( t l i s t ) 线相交。若搜索结束，从目 标点回溯找到源点，从而形成一条通路。线的产生是在水平和垂直方向交替进行的。 所用的数据结构，常常是两个表，一个用于存放水平线，另一个用于存放垂真线。若 从源点到目标点之间存在通路，基于线的搜索算法保证能够找到其中一个，但是由于 路径形状的简单性，找到的通路也许不是最短的路径。基于线搜索的算法一般比基于 网格点的算法快。 角勾链数据结构是o u s t e r h o u t 提出来的f 3 5 】。如图2 4 所示，一个矩形区域有四个 指向其邻接区域的指针，其中左下角有两个指针分别指向左边和下边的模块，其右上 角有两个指针分别指向右边和上边的模块。角勾链可以有效地表示和管理实区域和空 区域，它要求将空区域分割成矩形。沿着每个实方块的水平边向左右两个方向作水平 分割线，直到碰到一个实方块的垂直边或版图的垂直边界。这种分割可使分割得到的 空区域在水平方向尽可能长，并且保证了空区域的分割是唯一的。 叠蹦一勾 l h 基于t i l e 的数据结构( 角勾链) 以无网格的模式来表示版图，因而在设计规则上 有很强的灵活性，线宽和间距都是可变的。然而，操作和管理角勾链数据结构较基于 网格和基于线的数据结构更难一些，另外，设计规则检查也相对较难。 2 3 3 几种通道布线算法 通道布线算法又可细分为两层通道布线算法和多层通道布线算法两大类。 2 3 3 1 常见的两层通道布线算法 对于两层通道布线算法，常见的则有左边算法【6 】、狗腿算法【3 们、合并算法【37 1 、贪 婪算法【3 8 】、层次式迭代算法f 3 9 】和r e e d 提出的y a c r 2 算法等。 1 左边算法( l e f te d g ea l g o r i t h m ，l e a ) 1 2 华中科技大学硕士学位论文 最初由h a s h i m o t o 和s t e v e n s 提出，是最早的通道布线算法。左边算法不允许用 狗腿，不允许有垂直约束，当然也不允许有循环约束。在左边算法中，我们首先把要 布的网的干，按照它们的左端点的升值排序。放置时，总是按从通道的顶边到底边的 顺序，把网分配到第一个能容纳它的轨道上去。布干的过程只限于一层，另一层被用 来做垂直的连接用。事实上，对于一个没有垂直约束的双层通道布线问题，左边算法 能得到一个具有最小通道高度的解。 2 狗腿算法( d o g l e ga l g o r i t h m ) 为减少通道的高度，d e u t s c h 提出了狗腿布线算法。该算法允许多端线网和垂直 约束的存在，有些多端线网可以分成一组两端线网。我们总是努力把狗腿引入的位置 置于通道边的引脚位置上，这样可以减少不必要的狗腿，也可以减少通孔的引入和线 网电容。值得一提的是，狗腿的引入并不一定会减少通道密度( 即轨道的数目) ，不 适当地引入狗腿反而会增加通道密度。通过寻找最少的狗腿数及加入的位鼍而最小化 通道密度是一个n p 完全问题。 该算法的时间复杂度为o ( n l 0 9 2 n + n d ) ，n 是多端网分成两端网后的两端网的数目， d 是所用的轨道数。它可以应用于无网格模型布线中。实验结果表明，狗腿算法的结 果优于左边算法，通常会减少轨道数。 3 合并算法( m e r g i n ga l g o r i t h m ) 合并算法( n e t m e r g e c h a n n e lr o u t e r ) 是1 9 8 2 年由y o s h i m u r a 和k u h 共同提出的， 它是一个适用于双层通道布线的算法。 该算法的基本思想是在通道布线时，对于具有水平约束的两个线网必不能布在一 个轨道上，而不具有水平约束的两个线网可以布在一个轨道上。我们从左到右扫描一 个待布通道，把不能共享一个轨道的若干个网先布好；然后，考虑把能与已布线网共 享轨道的线网布上去。在整个布线过程中我们同时考虑水平约束图和垂直约束图。把 各个轨道分配给各个线网的同时，简化垂直约束图中各个约束关系。合并算法不加入 狗腿，不能处理垂直约束图中存在环的情形。 这里需引入一个叫带区( z o n e ) 的概念。带区是由许多相邻的列组成。在每一个 带区中，新的待布线网与先前已布的线网结合起来，组成合成线网( c o m p o s i t e n e t ) 。 最后，轨道就是分配给这些合成线网，每个合成线网占有同一轨道。合并算法通过通 道带区生成、线网合并和轨道分配等步骤完成。 4 贪婪算法( g r e e d ya l g o r i t h m ) 在左边算法和狗腿算法中都有较苛刻的约束条件。一个网的整个干或多端子网的 干必须占有同一轨道。r i v e s t 和f i d u c c i a 提出了一种新的算法思想。这种算法允许同 1 3 华中科技大学硕士学位论文 一线网可以有好几个干，即两端线网或多端线网的两端予网不必一定要完整地布在一 个轨道上，而是可以同时占有若干轨道。分布在各个轨道上的同一线网的轨道从左到 右尽可能早地用狗腿连接起来，这个算法称为贪婪算法( g r e e d ya l g o r i t h m ) 。这里的 狗腿的加入位置也不必如狗腿算法中的要求，而是允许狗腿出现在每一列上。贪婪算 法的执行是从通道的左边开始，一列一列地过去。在每一列上，算法“贪婪”地尽可 能多地利用每一列，在布完这- y u 的所有线网后，再移到下- y u 去。 5 层次式通道布线算法( h i e r a r c h i c a lc h a n n e lr o u t i n g a l g o r i t h m ) 1 9 8 3 年b u r s t e i n 和d e l a v i n 提出了一个双层通道布线的算法，称为层次式通道布 线算法( h i e r a r c h i c a lc h a n n e lr o m i n ga l g o r i t h m ) 。该算法始终运用“分而治之”的方法， 把一个m n 网格的布线问题化简成2 n 网格的布线问题。该算法复杂度为o ( i n pi ) ，n p 为线网集合。 6 y a c r 2 算法 y a c r 2 算法中定义了一个垂直覆盖因子，用来表征垂直约束违犯所需的通道数。 算法采用左边算法将水平网段分配到通道中，这样每列中垂直约束因子的总和最小。 最后将水平网段和引脚连接起来，过程中用到了两个基于模式的迷宫布线算法和一个 纯迷宫算法。y a c r 2 缺少一个拆线重布阶段，因而难以得到最好的结果。 2 3 3 2 多层通道布线算法 多层的通道布线算法【4 3 】有c h a m e l e o n ，m u l c h ，r o b u s t ，d e n s i t y b a s e d ，t r i g g e r s ， m i s e r 和c o n t o e r b a s e d 。 算法c h a m e l e o n 是两层布线算法y a c r 2