（应用数学专业论文）电路划分算法的研究及其在逻辑图布局中的应用.pdf

摘要 摘要 当前集成电路设计领域，不断发展的工艺技术将电路原理图的结构、规模 提高到更加复杂、多样的状态，这就要求研究人员根据复杂的需求不断改进甚 至开发出新的布局布线、逻辑综合及验证工具，开发出更加适合业务定制的物 理设计算法及可靠的集成电路设计软件产品。本文主要研究了集成电路物理设 计中的电路划分问题和逻辑图布局问题，并将电路划分应用到逻辑图布局系统 中，探讨了在小规模电路逻辑图布局中结合应用电路划分的可行性。 本文首先简要介绍了集成电路物理设计的主要内容，并对物理设计中的电 路划分、电路布局问题做了详细阐述。其次，在电路划分问题的研究中，根据 电路原理图图论模型化这一思想，将电路划分问题转化为数学中图的划分问题， 利用成熟的图论划分算法，解决了划分问题。先后介绍了基于顶点移动的f m 优 化算法、基于贪婪策略的初始划分算法( 如g r e e d yg r o w i n gp a r t i t i o n i n g 和 m i n m a xg r e e d yp a r t i t i o n i n g 算法) 。本文重点研究了f m 算法。在满足固定比例 因子这一约束下，综合考虑划分集合各自的顶点数和形成的割边数这两个因素， 对f m 算法中标杆点的选择和算法结束条件进行了改动，提高了划分的稳定性， 实验结果表明无论是平均时间耗费还是平均割边数，都要优于原f m 算法。最后， 本文详细介绍了应用于逻辑图布局系统的串布局算法，并将改动的划分算法与 串布局算法相结合，用于对电路逻辑图进行布局，考察了对小规模电路逻辑图 应用划分的可行性。 关键字：大规模集成电路电路划分f m 启发式算法电路逻辑图布局 a b s t r a c t a b s t r a c t t om e e tt h ed e m a n df o rc o m p l e xr e q u i r e m e n to nl a t e s ti cd e s i g nt e c h n o l o g y , e n g i n e e r sn e e dt oi m p r o v et h ee x i s t i n gt o o l sa n de v e nt oa d o p tn o v e lp h y s i c a ld e s i g n a l g o r i t h m sf o rp l a c e m e n t , r o u t i n g ，l o g i cs y n t h e s i sa n dv e r i f i c a t i o n t h e s en e w a l g o r i t h m sw i l lb eu s e dt od e v e l o pr e l i a b l es o f t w a r ep r o d u c t sf o rv l s id e s i g n t h i s t h e s i si sd e v o t e dt ot h es t u d yo fc i r c m tp a r t i t i o n i n gf o rv l s id e s i g na n dc o m p o n e n t p l a c e m e n tf o rs c h e m a t i cd i a g r a mg e n e r a t i o n f i r s t l y , w ed i s c u s st h em a i nc o n t e n t so fv l s ip h y s i c a ld e s i g nb r i e f l ya n d i n t r o d u c et h ea l g o r i t h m so fp a r t i t i o n i n ga n dp l a c e m e n ti nd e t a i l t r a d i t i o n a l l y , t h e c i r c u i tp a r t i t i o n i n gp r o b l e mi sf i r s tt r a n s f o r m e di n t ot h eg r a p hp a r t i t i o n i n gp r o b l e mb y m o d e l i n gac i r c u i ta sag r a p h , a n dt h e ni sd o n eb ya p p l y i n gm a t u r ea l g o r i t h m sf o r p a r t i t i o n i n gg r a p h s a m o n gt h e s ea l g o r i t h m s ，f mh e u r i s t i c ，g r e e d yg r o w i n g p a r t i t i o n i n ga n dm i n m a xg r e e d yh e u r i s t i ca res e q u e n t i a l l yd i s c u s s e di nt h i st h e s i s w em a k ef u r t h e rr e s e a r c ho nt h er a t i oc u t p a r t i t i o ns t r a t e g yo ff m b yc o n s i d e r i n gt h e n u m b e ro fn o d e si nt w op a r t i t i o n sa n dt h en u m b e ro fc u t sb e t w e e nt h e mu n d e rt h e c o n s t r a i n to fr a t i o n , w ea l t e rt h es t r a t e g yo fs e l e c t i o no ft h eb e s tn o d e t h e ni tw a s u s e df o rp a r t i t i o n i n gb e n c h m a r kc i r c u i t ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e p a r t i t i o n i n gq u a l i t yw a si m p r o v e dg e n e r a l l yi nb o t hr e d u c i n gc u tv a l u ea n dr u n n i n g t i m e n e x t ，w ei n t r o d u c e dt h ep l a c e m e n ta l g o r i t h mt og e n e r a t eas c h e m a t i cd i a g r a m a u t o m a t i c a l l yb a s e do ns t r i n g so fc o n n e c t e dm o d u l e s f i n a l l y , w ep o i n to u tt h e f e a s i b i l i t yo fc i r c u i tp a r t i t i o n i n gi nt h ea p p l i c a t i o n so fp l a c e m e n to fs m a l ls c h e m a t i c d i a g r a m k e yw o r d s ：v l s i ，c i r c u i tp a r t i t i o n i n g ，f mh e u r i s t i c , s c h e m a t i cd i a g r a m ， p 1a c e m e n t i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：斗孛、弓钦 朋年s 月咖日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：碧童；致 础年岁月和e t 第一章引言 第一章引言 1 1 选题背景和意义 信息技术( i n f o r m a t i o nt e c h n o l o g y , i t ) 作为强大的社会生产力，在推动经济发 展、社会进步方面起到了至关重要的作用，而集成电路( i n t e g r a t e dc i r c u i t ，i c ) 产 业是当今信息技术发展的核心和基础。 集成电路按规模可分为小规模集成电路( s s i ) 、中规模集成电路( m s i ) ，大规模 集成电路( l s d 、超大规模集成电路( v l s i ) ；按照电路用途可分为通用集成电路 和专用集成电路( a p p l i c a t i o n ss p e c i f i ci n t e g r a t e dc i r c u i t ，a s i c ) ；按照电路性能可 分为数字集成电路和模拟集成电路；按制造方法分为全定制a s i c ( f u l l c u s t o m a s i c ) 、半定制a s i c ( s e m i c u s t o ma s i c ) 、可编程a s i c ( p r o g r a m m a b l ea s i c ) 。 无论何种集成电路，其设计流程基本上都是一样的，主要分为系统描述、结构 设计、功能设计、逻辑设计、电路设计、物理设计、制造、封装测试等主要阶 段。其中物理设计是一个非常重要的环节，它主要是将电路的结构网表信息转 化为具体的版图，并满足布局合理，走线清晰的要求，同时符合一定的设计规 则。 本文来源于我在芯晟( 北京) 科技有限公司先进技术部实习期间所参与研 发的集成电路物理设计系统。该系统主要是针对中等规模( 包含1 0 ，0 0 0 5 0 ，0 0 0 个元器件) 的集成电路进行布局布线。该系统采用传统的集成电路物理设计结 构，分为电路划分、布局、布线、紧凑化处理及提取验证等几个重要步骤，详 细过程见图1 1 。其中电路划分、布局、布线三个模块是系统的核心部分，电路 划分( c i r c u i tp a r t i t i o n i n g ) 是将各单元分组形成多个模块，以使处理问题的规模缩 小。主要是因为一个芯片上可能包含几万个、几十万个甚至上百万个晶体管或 门电路，加之存储空间和设计能力的局限性。各模块的大小及每个模块中包含 的电路单元由划分算法确定。电路划分的目标是将电路中的元器件分配到不同 的集合中，同时满足各集合间的连接线网数目最小。我的主要工作就是设计并 实现适当的电路划分算法，对给定的网表结构，解决电路划分的问题；这也是 本文的重点研究方向。同时，作者尝试着将这种电路划分与电路逻辑图算法相 结合，应用到小规模电路( 包含几十个、上百个元器件的电路) 的逻辑图布局中， 第一章引言 考察了划分在小规模电路的逻辑图布局中的可行性及其划分效果。 图1 1 集成电路物理设计系统结构图2 0 】 1 2 文献综述 电路划分( c i r c u i tp a r t i t i o n i n g ) 是把一个电路划分成若干个适当规模的较小子 电路，以降低问题的复杂度和规模，提高处理效率。电路划分问题实际上对应 图的最优划分问题，目前普遍应用的算法主要分为两类： 1 种子增广法 由一个或若干个种子元器件开始，按照元器件之间的连接关系逐步扩大结 群，在达到一定程度后停止扩展，最终形成一个分拆。停止扩展的准则主要有 三种：一种是对分拆中元素个数进行限制，一种是对分拆内部连线条数进行限 2 第一章引言 制，一种是对分拆与外部的连线条数进行限制。 2 迭代改进 在已有分拆的基础上，通过改变一组元器件所在的分拆来逼近优化目标。 通常是采用交换不同分拆中的元器件对的方式，如果交换后更接近优化目标， 则交换，否则不交换，优化目标可取为不同分拆之间的连线条数。 种子增广法属于构造性算法，用于产生初始划分，再应用图论算法或者其 它组合优化算法对初始化分进行改进。这类算法简单易操作，而且速度较快， 一般用于用户对系统的响应有较快要求而对划分要求不高的情况。目前比较有 代表性的算法有g r e e d yg r o w i n gp a r t i t i o n i n g 5 1 和m i n m a xg r e e d y p a r t i t i o n i n g 5 1 。两者对规模比较小的电路划分尤其有效，但当处理较大规模的电 路时，则需要很多的时间，效率较低；另一方面，前者自始至终通过对当前分 拆中的元器件计算内连接数来确定下一个要添加的元素，当分拆中的元素越来 越多时，计算量也随之急剧增加。后者则针对这一问题，对前者进行了改进， 设置了一个标杆，如果当前分拆所含的元器件的个数增加到一定程度，超过了 标杆值，则不再计算当前分拆中元素的内连接数，而是改为计算分拆以外的元 器件的内连接数，选择其中内连接数最少的，同时与当前分拆的连接关系最强 的元素作为下一个要添加的元素，减小了计算量，提高了算法的效率。 迭代改进类算法属于二次优化算法，主要是对已经构造出来的划分进行迭 代优化，提高划分的质量，主要用于中小规模电路的划分或者用户对划分要求 高的情况。这类算法中比较经典的有k l 3 】和f m t 4 】算法。k e m i g h a l l 和l i n 提出 了交换顶点对的优化思想，简称k l 算法，其计算的复杂性为o ( n 3 ) ，以为图中 的顶点个数，该算法是图的划分( 2 分) 中一个成功有效的启发式算法，此后的优 化算法大多是对k l 算法进行改进。该算法收敛性很好，但是结果不稳定，离散 性很大，因此限制了k l 算法所能解决问题的规模【2 们。s e h w e i k e r t 和k e m i g h a n t l 8 】 在上述算法的基础上提出了线网割模型烈e tc u tm o d e l ) ，并提出了一种n e t - c u t 电路模型，该模型适合用于连接多个单元的电路线网结构，是k l 算法在一定程 度上的推广。后来，f i d u c c i a 和m a t h e y s e s 4 】提出了f m 算法，引入了单元的移动 增益，并将算法的复杂性提高到线性复杂度，极大地提高了算法的效率。f m 算 法速度很快，但是f m 算法的随机性很强，稳定性比较差，对优化后形成的新 划分的顶点规模控制较差。k r i s h n a m u r t h y 1 9 】在f m 算法的基础上引进了具有预 测性的多级增益模型( m u l t i l e v e lg a i nm o d e l ) ，该模型能更精确地选择使得切割集 3 第一章引言 数目达到更小的单元。d u t t a 和d e n 9 1 7 把一种基于概率的启发式算法引人f m 算 法，使解的质量得到进一步提高。2 0 0 3 年p a t k a r 8 】等提出了一种比例划分与f m 划分相结合的划分算法，得到了很好的结果。尽管传统的电路划分算法在实际 应用中都得到了很好的应用，但仍然没有一种算法在任何情况下都优于其它电 路划分算法，各有优缺点，所以很多技术人员开始研究混合算法，其目的是在 划分结果和划分速度上都得到很好的效果，也是研究的一个主要方向。 电路逻辑图布局( p l a c e m e n t ) 是根据当前电路的元器件的大小及与其他元器 件之间的连接关系，按照一定的布局规则，确定出当前元器件的相对位置。该 问题属于n p 难题，因此得到较好的布局结果相当困难，随着电路规模的增大， 问题的复杂性也随之提高，这对布局算法的求解结果和计算效率提出了更高的 要求。目前广泛应用的布局算法主要是延展扩张算法，主要是采取一定的策略， 不断的延伸，扩张，直到达到一定的条件约束而停止，最后将所有的元器件的 位置都确定。 无论是电路划分还是布局，他们都属于约束组合优化问题，这类问题均属 于n p 难题，因此找到问题的最优解相当困难，本文的重点即在结合原来各种经 典算法的基础上，对他们进行某些适应性改动，使得问题能够得到更好的解。 1 3 研究思路和论文结构 文章首先介绍了目前集成电路设计的发展现状，介绍了其中涉及的诸多环 节，并对集成电路设计中主要环节物理设计进行了探讨，其中主要是从算 法角度出发，对两个主要的组成部分( 电路划分、单元布局) 进行了研究。 在电路划分部分，重点讨论了f m 启发式优化算法、随机划分方法、g r e e d y g r o w i n gp a r t i t i o n i n g 5 1 和m i n - m a xg r e e d yp 删廿o i l i n g 【5 】初始划分方法，并对f m 算法进行了某些尝试性改动，提高了划分的稳定性和平均性能。在电路逻辑图 布局部分，则重点讨论了传统的布局算法，并分析了它们的局限性，并提出了 具有更高适应性的串布局算法。 本文的研究思路共分三个部分： 第一章为引言，分别介绍了文章的选题背景及意义，有关物理设计的文献 综述，以及文章所研究的主要内容及结构安排。 第二章主要探讨了电路原理图自动布图系统中的电路划分算法，介绍了电 4 第一章引言 路划分的定义和分类，以及电路划分的意义和目的、划分原则和各种划分算法， 并对f m 算法进行了某些适应性改动，增强了对划分规模的考虑，使得划分更稳 定；同时，将其与基于超图模型的多层划分算法相结合，应用到中等规模( 包 含1 0 ，0 0 0 - , 5 0 ，0 0 0 个元器件) 的电路划分问题中。 第三章介绍逻辑图布局问题及其算法，在对传统的布局算法进行分析的同 时，将我们的划分算法应用n d , 规模电路的布局问题中，考察了划分在小规模 电路的布局中的可行性。 结尾对文章的研究进行总结并对未来工作进行展望，并明确了划分、布局 等诸多待解决的问题及未来研究方向。 5 第二章电路划分 第二章电路划分 电路划分在v l s i 设计中是非常重要的一步，它主要是在集成电路的设计过 程中，将整个电路图系统划分成若干的小系统，将元器件划分到多个集合中， 一是降低所要处理的问题的规模，减小所要处理的问题的复杂性；二是快速地 将系统进行分类，识别出具有某些特征的元器件集合。 通常，电路划分问题是将电路的元器件按照某种约束将电路划分为k ( k 2 ) 个子集，使各个集合中的元器件数目相同，这一问题称为电路的k 分问题。这里， 我们只研究k = 2 的划分问题，即将电路等分为两个子集合的问题。电路中有n 个单元和m 个网，一个网连接同一信号线上的所有单元，欲将这些单元划分至 2 个子集中，最终使得被切割的边或网的数目达到最小。 2 1 电路划分问题的数学模型 首先可以用数学中的赋权图和超图来描述电路，从而将电路的划分问题转 化为图的划分问题或者超图划分问题。 2 1 1 电路划分的赋权图模型 用图中的顶点代表电路中的元器件，图中的边代表电路的元器件之间存在 连接关系，边的权值代表元件间连线的数目。我们将电路模型化为赋权图后， 同时就可以将电路的划分问题转化为赋权图的划分问题：将图二分，使得每个 划分包含图中一半的顶点，同时跨越这两个划分的边的数目最少。 给定图g = ( v ，e ) ，哆v 是顶点集v 中的顶点；e i j = ( m ，v ，) e 是边集e 中 的边，连接m 和；w ( v ，v ，) y 是边巳，- ，的权值，表示顶点和的连接关 系，如果这两个顶点有连接关系，则该权值为l ，否则为o ；将图g 中的顶点划 分至两个集合巧和砭，使得： 1 kuk = v ，巧n v = a 2 1 i 巧| - i 临1 目标函数：m i n i m i z e l e ( v ，v j ) 叶。巧m e 屹e ) i ) 6 第二章电路划分 2 1 2 电路划分的超图模型 超图是普通图的推广，将普通图中边的概念推广到超图中超边的概念。所 谓超边，就是一条边可以连接多个顶点的边，我们把这种连接关系定义为超边， 记为h y p e r e d g e 。形式上，超图定义如下： h y p e r g r a p h ：h = ( y ，e ) ( 2 1 ) 其中v 是超图中一系列的顶点组成的集合，与普通图中的顶点定义一致。e 是超图中一系列的超边组成的集合。与普通图不同的是，这样的超边可以同时 连接多个顶点。在这个定义下，我们可以看出，普通图是超图的一种特例，它 们的边都是度都为2 的超边。大多数情况下，一个超图中超边的度都不小于2 。 对于电路，它的连接关系用网表来实现，描述网表最好的模型则是使用超 刚2 2 1 ，g = ( v ，e ) 代表电路中的元器件的集合，e 为超边集，代表各个网的集合， 一个网连接同一信号线上的所有元器件。这样，电路划分问题就转化为超图划 分问题：将图二分，使得每个划分包含图中一半的顶点，同时跨越这两个划分 的超边数目最少。 给定超图h = ( v ，e 。) ，v i v 是顶点集y 中的顶点；e e 是边集e 中的边， 包含一组顶点；s i z e ( e ) 是边e 的度，表示边e 的包含的顶点个数。将超图日中 的顶点划分至两个集合鼠和凰，使得： 1 qu 马= h ，qr 、h 2 = g 2 1 i 骂j _ i 马临1 目标函数：m i n i m i z e ( 1 e e ip 同时包含q 和马中的顶点) i ) 图2 1 电路图与相应的超图模型6 1 7 第二章电路划分 2 2 图的划分 图的划分问题是一个经典的数学问题，这一问题一直是相关专家、学者研 究工作的一部分。图的k 分问题是n p 难【l 】问题，同样，二分问题作为其中的一 个特例，也是n p 难【2 】的；而找到该问题的一个近似解也是n p 难的。目前在这 一问题上广泛采用的算法大多是启发式算法，主要有两类，一类是基于某种策 略的初始划分算法，通过不断地将顶点移动到不同的集合中，对图直接进行划 分。另外一类是迭代优化算法，建立在已经形成的划分之上，通过某种策略， 对划分进行优化。 比较经典的优化算法有k 锄j 曲孤l i n 3 】启发式算法和f m 4 启发式算法。 k e m i 曲a n l i n 启发式算法的核心思想是通过交换顶点对来减小割边数。该算法 首先产生随机初始划分，将顶点均分在两个集合中；在优化阶段，该算法在两 个集合中各选取一个顶点进行成对交换，将割边的增加定义为交换的增益。每 次分别在两个集合众选取增益最大的两个顶点进行交换，并记录增益的累积值， 同时将它们锁定。重复上述过程，直到所有的顶点被锁定。然后回到累计增益 最小的一点上，将此前锁定的顶点对进行交换。其算法复杂性为u l l ij 。该算 法收敛性很好，但是结果不稳定，离散性很大，而且算法效率比较低，因此限 制了k l 算法所能解决问题的规模。f i d u c c i a 和m a t t h e y s e s 4 】提出了f m 算法， 引入了顶点的移动增益这一概念，该算法也是首先产生初始划分，优化基础则 不再采用交换机制，而是采用顶点的移动来改进划分的质量，该算法的算法复 杂性d ( ie1 ) 刚，速度很快，但该算法对最终划分的顶点的数目约束不大，而且 随机性很大，不稳定。本文即是在对f m 算法进行详细研究的基础上，对f m 算 法中的某些移动条件、终止条件进行了改动，提高了算法的稳定性，同时，我 们的实验结果表明，对于规模为1 0 ，0 0 0 , - , 5 0 ，0 0 0 的电路来说，我们算法较f m 算 法具有更好的平均性能。下面一节我们详细介绍f m 算法。 2 3f i d u c c i a m a t t h e y s e s 启发式算法 f i d u c c i a m a t t h e y s e s 4 启发式算法本质上来说，是迭代式算法。该算法是一 个优化算法，以一个已经形成的初始划分为前提。f m 算法具有d ( iei ) 级的算 法复杂性。在深入探讨该算法之前，我们首先介绍一下相关的概念及其符号表 8 第二章电路划分 不。 权数：表示两个图中两个顶点v ；和v ，之间的连线数。如果这两个顶点之间有 连接关系，则其值为1 ，否则为0 。 f1 1 ，；与1 ，不相连 w ( v i ，v j l ，2 o ：，与，不相连 ( 2 2 ) 顶点的内连接：对于位于某个集合s e t 中的顶点v ，除顶点v 外，所含的顶 点全部位于集合s e t 中的超边的个数。 i n t e r n a l ( v iv i g s e t = w ( v j ，1 ，)( 2 3 ) v ，s e t 顶点的外连接：对于位于某个集合s e t 中的顶点v ，除顶点v 外，所含的顶 点都不位于集合s e t 中的超边的个数。 e x t e r n a l ( v f ) v f e 跏= w ( v f ，v ，) ( 2 4 ) ，e s e t 割边：对于图中的任意一条边，如果它的两个顶点分别位于不同的集合中， 则称这条边为割边。 移动增益：对于位于某个集合s e t 中的顶点v ，当把该点从s e t 中移动到另 一个集合中时，所带来的总的割边数的增加值。 g a i n ( v l ) ”嘲= i n t e r n a l ( v f ) 一e x t e r n a l ( v 】f )( 2 5 ) 对于一个给定的划分，f m 算法不断地对其进行迭代，在每一次迭代过程中， 该算法在每个集合中找出一系列顶点，使得将这些顶点移动到另一个集合中后， 能够减少总的割边数，以提高划分的质量，我们将这样的一轮迭代过程称为一 个f mp a s s 。然后，以这一轮迭代过后形成的结果为下一轮迭代的输入，该算 法就是不断地重复这样的f m p a s s 过程，直至划分结果不再改进为止。f m 算 法过程 图示如下： 图2 2f m 算法 9 第二章电路划分 可以看出，f m 算法核心是f mp a s s 过程，有三个主要组成部分：( 1 ) 计算 所有顶点的g a i n ，也就是将该点移动到另一集合中所带来的总的割边数的增加 值。( 2 ) 对g a i n 最小的点进行移动。( 3 ) 更新所有被移动的点影响到的顶点的g a i n 。 现在，我们详细介绍一下f mp a s s 过程： 初始时，将每个项点的状态设置为“未锁定，也就是说每个元素都是可以 移动的。该算法迭代地选择一个尚未被锁定的且g a i n 值最小的顶点，然后将该 点移动到另一侧。当一个顶点1 ，被移动后，我们就锁定该点，并更新与该点相联 接的所有尚未被锁定的顶点的g a i n ；同时记录该点移动后，图中的割边数。直 到所有的项点都被移动后，我们查看所有的割边数纪录，找到最小的割边数对 应的顶点，同时将所有该点之后才移动的点重新移回它们最初所属集合。这样， 一轮迭代过程结束，形成了新的划分，我将该划分作为下一轮迭代过程的开始。 如果采用适当的数据结构，将使该算法的一次f mp a s s 过程的复杂性达到 o ( i e | ) 【4 】。 f m 算法基于图的一个初始划分，即它的前提是，对于我们要处理的图，它 的顶点已经初步被划分到2 个集合中。通常，初始划分可以将图中的顶点直接 进行均分，一个集合包含图中一半的顶点，另一半顶点直接划分至第二个集合。 也可以采用随机选择的方法来形成初始划分集合。这种情况下，我们随机的选 出图中一半的顶点，形成一个集合；另一个集合自然也就形成了。这样的划分 策略也是大家常用的方式。下面一节我们主要介绍f m 中使用的对图直接进行划 分的初始划分方法。 2 4 直接划分 2 4 1g r e e d y g r o w i n gp a r t i t i o n i n g 贪婪生长算澍5 】来自于直观的种子生长模式。就好像一个植物的种子，从根 生长，慢慢长出枝叶，蔓延开来。该算法始于一个所谓的“种子，就是一个具 有某种特性的顶点。然后围绕该种子以广度优先的方式遍历图，并扩展成为一 个集合，直到其中包含了一半该图的顶点。该算法的算法复杂性为叭le 。该 算法通常用于生成一个图的初始划分，然后将该划分作为参数传递给其它优化 算法，例如我们前两节所介绍的k l 与f m 优化算法。 1 0 第二章电路划分 为了理解该算法，我们给出如下定义： 邻接点：一个顶点v 的邻接点就是邻接于所有以该点为顶点的边的顶点组 成的集合。 a d j a c e n t ( v ) = p vie ( v ，1 ， ) ，e y 五， ( 2 6 ) 集合s e t 的内涵：给定图的一个划分s e t l 和s e t 2 ，位于s e t l 中且与s e t 2 中 顶点有连接关系的顶点组成的集合称为s e t l 的内涵。 b o u n d a r y ( s e t l ) = 1 ，s e t lije ( v ，y - ) ，e 勋2 e ) ( 2 7 ) 集合s e t 的外延：给定图的一个划分s e t l 和s e t 2 ，位于s e t 2 中且与s e t l 中 顶点有连接关系的顶点组成的集合称为s e t l 的外延。 f r o n t i e r ( s e t l ) = v s e t 2je ( v ，v - ) ，e & 订e ) ( 2 8 ) g r e e d yg r o w i n gp a r t i t i o n i n g 算法本质上是一种贪婪算法，它不断地在图的遍 历过程中寻找满足某种贪婪策略的顶点，并将该顶点加入正在扩张的集合。该 算法首先选择一个初始种子，形成一个集合，我们称之为初始集合，记为s e t g 剩余的所有顶点组成另一个集合，记为& 如。然后，我们以一种广度优先的方 式，寻找下一个需要加入中的顶点v e r t e x 。删，使得当v e r t e x 。甜，加2 s e t i 打 后，割边数( 见k e r n i g h a n - l i n 启发式算法中定义) 增加最少，即g a i n ( 见 g e r n i g h a n - l i i l 启发式算法中定义) 值最小的顶点。直到s e t , 甜中包含了图中一半 的顶点。其中额外的工作是对s e t i 甜的外延中的顶点按照g a i n 的非降序进行排 序，此时具有最小的g a i n 值的顶点被选出，加入到& k 中。当我们加入一个顶 点v 后，与该点相连的位于s e t , 。的外延中的顶点的g a i n 被更新，同时，与该点 相连的不在s e t ，打的外延中的顶点被加入& 的外延中。 我们可以看出，g r e e d yg r o w i n gp a r t i t i o n i n g 也是对初始种子的选择敏感的， 即初始种子的选取对最终生成的划分的质量影响较大，即对所生成的划分的割 边数的多少比较大。该算法的一种典型应用是采用不同的初始“种子”，独立的 运行若干次，最后选择割边数最少的那种划分作为最终结果。 该算法的伪代码见附录a 。 2 4 2m i n - m a xg r e e d yp a r t i t i o n i n g m i n m a x 5 启发式贪婪算法同样也是用于对一个图进行初始划分。我们可以 第二章电路划分 将其简单的视为g r e e d yg r o w i n g 算法的“双胞胎兄弟 版本。该算法初始时，选 择两个“种子 ，形成以这两个种子为核心的集合。并按照n e e d yg r o w i n g 的“生 长方式轮流扩展，直到分别包含图中一半的顶点。不同于g r e e d yg r o w i n g 算法 的是，对于一个集合s e t ，m i n - m a x 算法在选择需要添加的下一个顶点时，使用 了如下定义： 顶点v 与集合s e t 的连通度：我们将与顶点v 相连的，另一端点位于集合 s e t 的边的个数称为顶点v 与集合s e t 的连通度 c o n n ( v , s e t ) 爿 e ( v ，1 ，i ) ，e 融目i ( 2 9 ) 在g r e e d yg r o w i n g 算法中，我们选择下一需要加入的顶点时，主要考虑该 顶点是否具有最小的g a i n 。我们知道，与一个顶点v 相连的割边越多，内边越 少，那么该顶点的g a i n 就越小。同理，对于一个集合s e t 来说，m i n - m a x 在选 择下一个需要加入的顶点时，则优先选择与该集合连通度大，同时与另一个集 合连通度小的顶点。 对于一个集合s e t ，该算法有两种方式来从所有的候选者中选择需要添加的 顶点。第一种，我们称为f i r s t m i n ，首先选出一组具有与s e t 连通度最大的顶点， 之后再从这些顶点中选择与另一个集合的连通度最小的顶点；第二种，我们称 为f i r s t m a x ，首先选出一组具有与另一个集合连通度最小的顶点，之后再从这些 顶点中选择与s e t 连通度最大的顶点。在开始时，对于任何一个集合来说，与该 集合中的顶点相邻接的顶点比较少，f i r s t m a x 比f i r s t m i n 更有效【l 0 1 。 f i r s t m a x ( s e t t o a 积，s e t o 髓) r a i n 卜m i n ，e 眦。醯c o n n ( v ，s e t o t h 盯) c a n d i d a t e s6 - - y s e 乞鼢妇ic o n n ( v ，s e t o , h ) = m i n h l a x 卜m a x v e 砌池胁c o n n ( v ，s e 削) v e r 鲍砀绷卜f i r s tv e r t e x 1 ，c a n d i d a t e sic o n n ( v ，s e 砝) = m a x ) r e t u r n v e r t e ) c r h n m 图2 3f i r s t m a x 过程 1 2 第二章电路划分 m i n - m a x g r e e d yg r o w i n gp a r t i t i o n i n g s e t l f u n cp l a c e p a r t i t i o n ( g o ，g 1 ，p a r t i t i o np ，p a r t i t i o n sp s e t ) 取p 的扇入妇( p ) 与肚缃交集，记为s e t c h o s e n i n 。 i 如e t c h o s e n l n 中横坐标最大的点，并记录其横坐标值为x _ m a x _ i n 。 取瑚扇出o u t ( p ) 与p s e 钓交集，记为s e t c h o s e n o u t 。 取s e t c h o s e n o u t 中横坐标最小的点，并记录其横坐标值为x _ m i n _ o u t 。 确定瑚坐标，使如下条件成立： ( 1 ) p 位于x _ m a x _ i n 和x _ m i n _ o u t 。 ( 2 ) g o 与g 1 之间距离最短。 ( 3 ) p 和p s e t 的所有串构成的集合彼此没有重叠。 这样，布局既能反应元器件之间的联系强弱，又能保证信号流从左向右。 ) 至此，我们描述了串内元器件布局的算法，现在，我们给出一个按照该算 法布局的效果图( 见图3 1 0 ) ，大致如下： 图3 1 0 元组内串布局效果示意图 第三章电路逻辑图布局 为了考察该算法的对小规模的电路逻辑图的布局情况，我们对该算法进行 了试验，采用了中心为航天标准化研究所所开发的逻辑图布图系统的测试网表， 一些例子的布局效果见附录，实验结果显示，将划分应用于小规模的逻辑图布 局中，是可行的，这在理论方面是有一定的意义的。 3 4 3 小结 前面几节，我们叙述了基于划分的电路原理图布局算法及其比较重要的子 算法，比较好的解决了采用有向图模型的电路逻辑图的布局问题。我们使用第 二章介绍的超图二分算法，不断地对图进行二分处理，迅速地减小所要处理的 问题的规模，使我们可以有效的处理各个子问题；然后，我们再将这些已经处 理好的子问题迭代地整合，最终使得原布局问题得以有效的处理。整个过程采 用了分而治之的策略。每个元器件的物理位置都被确定，元器件之间没有重叠 现象发生，同时将连接关系较强的元器件彼此相邻，这样也能使整个图的聚集 关系显示的一目了然，便于设计人员比较清晰的区分，方便后期处理。 第四章总结与展望 第四章总结与展望 4 1 总结 本文来源于我在芯晟( 北京) 科技有限公司先进技术部实习期间所参与研 发的集成电路物理设计系统。该系统主要是针对中等规模( 1 0 ，0 0 0 , - 5 0 ，0 0 0 个元器 件) 的集成电路进行布局布线。我的主要工作就是设计并实现适当的电路划分算 法，对给定的网表结构，解决电路划分的问题；这也是本文的的研究重点。同 时，作者尝试着将这种电路划分与电路逻辑图算法相结合，应用n d , 规模电路( 包 含几十个、上百个元器件的电路) 的逻辑图布局中，考察了划分在小规模电路的 逻辑图布局中的可行性及其划分效果。 下面就本文研究的内容简单回顾如下： 在电路划分问题的研究中，根据不同的电路数学模型，论述了适用于该模 型下的经典集成电路划分算法。在电路的有向图模型背景下，先后介绍了基于 单点移动思想的f m 电路划分优化算法、基于某种贪婪策略的g r e e d yg r o w i n g p a r t i t i o n i n g 随机划分算法及其后续改进算法一m i n m a xg r e e d yp a r t i t i o n i n g ，同 时，对f m 算法进行了某些尝试性调整，如f mp a s s 的中止跳出条件、局部最 优状态的选择和划分所含顶点的比例进行了修改，这对于规模稍大一些的电路 来说，节省的时间耗费是相当可观的，同时得到了更加符合比例划分的近似最 优解。 针对逻辑图布局问题，结合我们的划分算法，使用一种基于串布局的布局 算法，并对中心为航天标准化研究所开发的a g s d 系统的电路网表用例进行了 测试，对某些小规模的电路的布局效果还是很不错的，说明划分对小规模电路 的逻辑图布局也是可行的。 4 2 展望 本文所作工作对于整个电路逻辑图设计领域来说还远远不够，尤其是形成 软件产品来说还相差甚远。a s i c 技术的发展对电路逻辑图设计算法及软件产品 3 l 第四章总结与展望 的功能提出了更高的要求，表现为以下几个方面：电路模拟中器件模型、处理 规模和复杂结构在逻辑设计的过程中，对电路核心的识别、模拟和元器件定位 还没有得以很好的解决；对于电路模拟的结构划分，还没有很好的数学模型能 够刻画出来。从本文所作的工作出发，今后的努力方向或者需要注意的有以下 几点： 就电路划分而言，基于图模型的划分算法的研究已经基本成熟，而基于超 图模型的划分则还有可以提升的空间，可以在超图模型的划分算法上做进一步 的研究，比如超图对电路的模拟过程中，有意识地对某些核心模块进行预定义 的标识，这样在后续划分时，可以直接将它们作为一个单元进行整合，这一点 较单纯的有向图来说，在精细化模拟方面，有了很大的提高。另外，基于全局 观念的划分还有待提高，可以考虑将划分技术和布局技术结合起来，突破局部 最优的情况，形成一种全局算法观念，更好的突出电路的整体结构。 就布局问题而言，串布局算法是一种迁移式的尝试。元组划分的规则、元 组内串划分的规则、串内布局的规则和元组内串整合的规则等是将来需要考虑 的重点，本文在元组内串布局的整合设计上，串之间的连接关系及其对元组内 串布局的影响还有待进一步细化和研究。 除上述几项外，逻辑图设计中的布线模块对电路划分和布局模块的影响也 己不能忽视，布线部分的优劣很大程度上取决于布局算法的好坏，因此，在布 局算法的研究上，如何结合布线问题也是未来研究的一个重点方向。 3 2 致谢 致谢 在中心的三年研究生生活是我一生中永远难忘的经历，在这期间，中心为 我们学生们创建了很好的学习环境和学术氛围，在这里，我们可以领略到世界 上最前沿的学术课题，学 - - j 到最先进的学术思想。亲爱的同学们互相关怀，一 起学 - j 生活，一同进步成长，让我时常感动。 感谢敬爱的陈永川教授，他对学生的亲切关怀、言传身教，不仅向我们阐 释了什么是传道、授业，更让我明白了什么是解惑。陈老师严谨的治学态度， 务实勤勉的工作作风让我领悟了什么是做事和做人。在此，谨向敬爱的陈老师 表示衷心的感谢。同时，感谢中心的马老师、李老师和其它老师以及亲爱的同 学们在三年的学 - j 生活中给予我的关心、帮助