（通信与信息系统专业论文）运用于vlsi中的新型网表—距离聚类分割技术.pdf

上海大学硕士学位论文 摘要 自从大规模集成电路进入百万门级别设计之后，超大规模集成电路的设计 就成为一项工序繁琐、耗时长久的电子设计过程。因此，减小设计的复杂度及缩 短设计周期成为了制约v l s i 设计的重要瓶颈之一。 为了解决这一瓶颈问题，诸多的方法被加入到v l s i 设计的整个过程当中， 其中尤其以布局过程中的改进作为重点研究的突破口。一种比较常见的方法就是 在布局前期处理过程中进行器件聚类处理，从而减少了所需处理的器件数量及认 证周期。这种方式已经被广泛的运用到百万门级别以上的大规模集成电路布局设 计当中。 但是，传统的布局聚类方法往往只考虑到布局方式的一种特性，如：网表， 局部相关度，树型结构图等等。无法吸收更多的全局信息来进行聚类处理，丧失 了大量布局信息，因此所产生的布局结果不甚完备，为后期精布局、布线带来先 天性的不足。有很大的改进空间。 本论文提出的新方法是基于多种布局参数作为聚类的考虑因素，以物理距离 作为聚类依据的方法。而且最后的实验数据结果也为今后的研究者提供了更多通 过物理参数的引入、进一步对全局变量进行控制的可能性。本论文的创新之处在 于提出了一种多参数布局聚类的新方式，这对聚类布局向更快、更好的方向发展 起到了重要的作用。 新方法的关键技术有以下几个： 1 多参数比单参数更利于聚类的依据是什么? 2 如何寻找相关程度较高的两种或者多种参数作为聚类的依据? 3 如何在原有的聚类布局研究平台中引入多参数聚类? 4 多参数聚类的适应度如何? 5 多参数到底比单参数或者无聚类布局提高了多少性能? 在研究过程中，首先利用过去的研究成果，并提出了有效物理距离聚类这一 个概念作为聚类依据，并完成了对物理距离理论上及算法上的详细研究，且有效 的定义了实际测量的物理距离及布局板的元素位置参量，然后在实际操作中引入 物理距离及过去研究中的网表到聚类处理中，从而完成了新方法的实现。最后的 v i 上海大学硕士学位论文 实验利用了传统的网表参量、新引入的物理距离参量和一部分的元素面积参量相 互的组合作为整体的聚类依据。最终的实验结果表明，新方法大大提高了聚类分 割布局的各种性能参数，对于某些布局实验数据性能提高值达到了7 0 多，而 且对于不同的数据库都有一定程度的提高。 另外，在实验测试中，还利用了一些其他具体的布局方式产生的中间结果作 为聚类的测试数据之一，目的是为了进一步地测试新方法对各种数据的适应度。 测试结果也比较理想。 实验结果表明，多参数聚类布局将会成为百万门级别预布局当中的一种全新 方法而得到推广及改进。当然整个实验中还存在着各种各样的疑问有待解决，本 实验室也会对此进行一定的深入研究及后期跟踪改进。 关键词：聚类，分割，网表，分割度，布局 v 上海大学硕士学位论文 a bs t r a c t s i n c ev l s ic i r c u i t sc o n t a i nh u n d r e d so f m i l l i o n so f t r a n s i s t o r s ，d e s i g n i n gav l s i c h i pi sa l le x t r e m e l yc o m p l e xa n dt i m e c o n s u m i n gt a s k i ti sv e r yi m p o r t a n tt or e d u c e t h ec o m p l e x i t yo ft h ed e s i g np r o c e s s o n eo ft h em e t h o d si st or e d u c et h en u m b e ro ft h ec o m p o n e n t st ob ed e a l tw i t h d u r i n gt h el a y o u td e s i g np r o c e s sb yc l u s t e r i n g i ti sw e l lk n o w nt h a td o i n gc l u s t e r i n g r e d u c e st h er u n n i n gt i m es i g n i f i c a n t l y , a n ds o m e t i m e si m p r o v e st h eq u a l i t yo ft h eh i g h l e v e ls y n t h e s i s ，t o o i th a sb e e nw i d e l yu s e di nv l s id e s i g n i n ga n dp r o v e dt ob et h e s u f f i c i e n ts o l u t i o n st oc o m p l e xp r o b l e m s h o w e v e r , t h ec o n v e n t i o n a lc l u s t e r i n ga l g o r i t h mi sb a s e do nb o t t o m u p t e c h n i q u e s ，w h e r el o c a lc o n n e c t i v i t yi n f o r m a t i o ni su s e dt of o r mc l u s t e r s t h a ti s ， h i g h l yc o n n e c t e dc e l l sa r em e r g e d b e c a u s et h em e t h o dm a k e su s eo fo n l yl o c a l c o n n e c t i v i t yi n f o r m a t i o n ，i ti sv e r ye f f i c i e n t ，b u tt h e r ei sm u c hr o o mf o ri m p r o v e m e n t s o ，w ep r o p o s ea n o t h e rc l u s t e r i n gm e t h o db a s e do nm o r ep l a c e m e n ti n f o r m a t i o n i no u rn e wc l u s t e r i n gm e t h o d ，c e l ll o c a t i o n sa r ec a l c u l a t e db yr e p e a t e d l ys o l v i n gt h e q u a d r a t i cp r o g r a m m i n g t h ea l g o r i t h mm a k e su s eo ft h ec e l lp o s i t i o n sd u r i n gt h e c a l c u l a t i o na n dd e c i d e st h es e to fc e l l st ob em e r g e d w ec o m b i n e dn e t l i s t sa n dc e l l p o s i t i o n st o g e t h e ra ss i n g l ei n f o r m a t i o nf o rc l u s t e r i n gb a s e do no n ep a r a m e t e r t h e r ew e r es t i l ls o m ep r o b l e m st od i s c u s sd u r i n go u rr e s e a r c h ： 1 w h ym u l t i p l ep a r a m e t e r sa r eb e t t e rt h a no n l yo n ep a r a m e t e rc l u s t e r i n g ? 2 h o wt of i n dt w oo rs e v e r a lm o s tc o m p a t i b l ec l u s t e r i n gp a r a m e t e r sj u d g i n gb y t h eg l o b a lp l a c e m e n ti n f o r m a t i o n ? 3 h o wt oc o m b i n eo u rn e wr e s e a r c hw i t ho u re x i s t e dq pp l a c e m e n tp l a t f o r m ? 4 w h a t st h ec o m p a t i b i l i t yo fo u rn e wr e s e a r c h ? 5 w h a t st h ee x t e n to fi m p r o v e m e n tc o m p a r e dt h en e t l i s t - d i s t a n c ec l u s t e r i n g w i t ht h eo t h e rt r a d i t i o n a lw a y ? t h ef i n a lr e s u l t sp r o v e dt h a to u rn e w c l u s t e r i n gm e t h o dp r o d u c e sb e t t e rs o l u t i o n s b e c a u s ei tm a k e sd e c i s i o nb a s e do nm o r eg l o b a li n f o r m a t i o nt h a nt h ec o n v e n t i o n a l 上海大学硕士学位论文 m e t h o dw h e r el o c a lc o n n e c t i v i t yi n f o r m a t i o ni su s e d i na d d i t i o n ，w ec a l lc h a n g et h e c o m b i n a t i o np r o p o r t i o no fo u rt w oc o n s i d e r e di n f o r m a t i o na n dc o n t r o lt h er e s u l ta s w e w a n t i no r d e rt oi m p r o v et h ep e r f o r m a n c eo fc l u s t e r i n g ，w ep r o p o s e dan e wi d e ao f c o m b i n i n gt w oc l u s t e r i n gi n f o r m a t i o n , c o n n e c t i v i t ya n dd i s t a n c e t h e r ea r en e v e ra n y r e l a t e dd o c u m e n t so nh o wt od ot h ec l u s t e r i n gu s i n gd i s t a n c ei n f o r m a t i o n t h e d e f i n i t i o no ft h ed i s t a n c eb e t w e e nc e l l si nh y p e r - g r a p hi sa n o t h e rb i gc h a l l e n g ei no u r r e s e a r c h f o r t u n a t e l y , o u rr e s u l tt u r n e do u tt ob eab i gl e a po ft h ec l u s t e r i n gm e t h o d s o m er e s u l t so fo u rn e wm e t h o da r ee v e nm o r et h a n7 0p e r c e n t i m p r o v e m e n t c o m p a r e dt ot h ec o n v e n t i o n a ln e t l i s to n l yc l u s t e r i n gd u et ot h ef a c tt h a tw eu s e dm o r e g l o b a li n f o r m a t i o n i na d d i t i o n ，i no r d e rt o t e s tt h ec o m p a t i b i l i t yo fo u rn e wr e s e a r c h ，w et e s t e ds o m em i d d l e s t e p so ft h er e s u l to fq pp l a c e m e n t ，t h e ni n p u t t e di n t ot h en c wc l u s t e r i n gp r o g r a m s u r p r i s i n g l y , t h ef i n a lr e s u l ta g a i nt u r n e do u tt ob es a t i s f i e d ，w h i c hc o u l db ea n o t h e re v i d e n c ep r o v e dt h a to u r n e w c l u s t e r i n gm e t h o dw o u l db eab r e a k t h r o u g hi fw ec a l lp l u n g em o r em o n e ya n dt i m ei n t oi t k e y w o r d s ：c l u s t e r i n g ，p a r t i t i o n i n g ，n e t l i s t ，c u t ，p l a c e m e n t i x 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名 本论文使用授权说明 期： 硝够 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签 新繇二_ 、i - r 期：型芦乃 i l l 上海大学硕士学位论文 1 1 研究背景 1 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 ) 大规模集成电路 设计产业已经从小规模整合s s i ( s m a l l s c a l ei n t e g r a t i o n ) 发展到今天的亿位元 整合g s i ( g i g a s c a l ei n t e g r a t i o n ，每一晶体板所含晶体数耋1 0 9 ) 甚至于兆位元整 合t s i ( t e r a s c a l ei n t e g r a t i o n ) 【l 】。如此迅猛的发展，使得传统整合技术对于超 大规模集成电路的布局技术显得力不从心。特别，在设计电路时必须考虑到消 减布局复杂度以及后期制造缺陷( m a n u f a c t u r i n gd e f e c t ) 问题【2 】。由于晶体数 的增加，在极小一块布局板上晶体之间的关联问题，可靠性问题，能耗问题将 成为首要解决的问题之一。这些都必须在版图设计( 1 a y o u t ) 阶段都有一定考 虑。换句话说，一个好的布局结果有利于后期的工业制造中的处理。可见布局 步骤在l s i 设计中有举足轻重的作用。 传统l s i 设计会经历版面规划( f l o o r p l a n n i n g ) 、布局( p l a c e m e n t ) 、布线 ( r o u t i n g ) 和封装( c o m p a c t i o n ) 【3 1 。如果在验证的最后表明设计失败的话， 可能需要重新经历版图设计过程，这样会使得设计周期大大增加。在技术发展 速度迅猛的今天，一个产品的成功与否可以说在版图设计阶段就已经决定好了。 所以说，如果可以在版面规划中得到更快更好的宏观布局结果，将对最终版图 设计结果有很大的影响。当然，随着晶体板数量的进一步提高，版图设计之初 的宏观布局当中也会出现如何减少计算量与优化计算结果等诸多问题有待解 决。并且，现在的版图设计往往配合高层次综合技术( h i g hl e v e ls y n t h e s i s ) 【4 】， 版图设计结果往往直接用于高层综合技术的评价当中。这就更要求版图设计之 后的结果快速而稳定。 上海大学硕士学位论文 1 1 2 布局方式划分 传统的布局方式可以分为：随机优化方式( s t o c h a s t i co p t i m i z i n gm e t h o d ) 及可决定化方式( d e t e r m i n a b l em e t h o d ) e 5 】。 随机优化方式从2 0 世纪6 0 年代就开始研究。早期的方法主要是解析方法 ( a n a l y t i c a lm e t h o d ) 【6 1 。由于当时计算机的计算能力不理想，只能采取一些假 设来使目标函数线性化。随着计算机技术的飞速发展，使得进行大规模的计算 成为可能，采用数值规划方法( n u m e r i c a lp r o g r a m m i n gm e t h o d ) 【7 】和利用迭 代技术【8 】，在满足一定约束条件的前提下，尽量搜索所有可能的情况，获得全 局最优解。该方法虽然可以得到最优解，但计算繁杂，效率很低。进入9 0 年代 以来，现代启发式方法( h e u r i s t i cm e t h o d ) 【9 】逐渐被引入，包括模拟退火法【1 0 】、 遗传算法【l i 】、神经网络法 1 2 】及t a b u 搜索法【1 3 】等，这些优化技术适合于解决纯 整数规划和混合规划问题，能够有效地处理不可微的目标函数，而且可以通过 经验、直觉和判断等来减小搜索空间，达到快速求解的效果。但是对于解决百 万门级别以上的布局问题来说，这种方法的运算还是过于冗长，往往是依靠经 验的积累才能真正完成一整套布局的全过程，得到近似最优解【l 4 1 。 因此9 0 年代后期，大规模集成电路全局布局更多的采用可决定化方式来进 行布局。一种比较常用的方法就是二次规划布局法( q u a d r a t i cp r o g r a m m i n g ) 。 它把布局问题转化成一种二次方程的求解方式，目的是为了把二维布局问题转 化成普通计算机可以容易处理的数学构造问题。 二次规划布局法是二次规划算法在大规模集成电路布局上的首次运用。最 初的想法非常简单的，就是为了把元素数字化以后，进行一定的位置定义，然 后试图寻找一种统一的解决方案来完成位置上的更替，实现布局。因此，最初 的二次规划布局法都是针对小规模的局部布局来实现的。因为当时的处理速度 有限，还难以完成几百万个行列式的向量解问题，常常结合随机优化方式来共 同处理【1 5 】。随着多层结构的引入以及自上而下分割法的普及，越来越多的实际 电路板采取了二次规划布局来进行宏观布剧1 6 】 【l7 】。因此，使得这种方式尽可能 的优化也渐渐成为了研究的重点之一。由于二次规划布局法速度更快，所以更 适合超大规模集成电路的布局问题当中。 2 上海大学硕士学位论文 此外，二次规划布局法本身是一种非常耗费计算量的布局方式，它将不停 的运算不同元素之间的位置方程，得到下一步的位置值。因此，如何比较快的 运算矩阵，也是提高二次规划布局法运算速度的关键所在。在论文的第一部分， 首先就将介绍一种新的l u 矩阵分解求解法( l uf a c t o r i z a t i o n ) 来改善传统的 二次规划布局法。 1 2 聚类技术的引入 1 2 1 聚类技术的发展 “聚类”( c l u s t e r i n g ) 这一概念，最早运用在数据挖掘领域，指的是将物理 或抽象对象的集合分组组成由类似对象组成的多个类的过程【1 8 】。作为一个数据 挖掘的功能，对于聚类的分析能作为一个独立的工具来获得数据的分布情况， 观察每个簇( c l u s t e r ) 的特点，集中对特定的某些簇做进一步的分析，此外， 聚类分析可作为其他算法的预处理步骤 1 9 】，这些算法再在生成的簇上进行处理。 聚类分析已经广泛地用在许多应用中【2 0 】 【2 1 1 ，如图像处理、模式识别、市场 研究等。通过聚类，人能够识别密集和稀疏的区域，因而发现全局的发布模式， 以及数据属性之间的有趣的相互关系。在商务上，聚类能帮助市场分析人员从 客户基本库中发现不同的客户群，并能用不同的购买模式来刻画不同的客户群 的特征。 在聚类技术未引入之前，二次规划布局的发展停滞了很长一段时间，研究 者总是不能在处理速度与处理质量之间找到一个比较好的平衡点。因此，为了 实现更好的布局结果，研究者最终引入了聚类技术到二次规划布局当中【2 2 】。相 对于大规模集成电路布局来说，要处理的数据就是布局板上的各个元素以及各 个元素之间的相应关系。一般运用于前期的宏观布局当中，为后期的精布局及 排线作好前期的准备。大规模集成电路的聚类就是将布局对象分组成多个类或 者簇进行处理，在同一个簇当中的对象之间具有较高的相似度，而不同簇中的 对象差别较大。因此，将聚类技术运用到大规模集成电路中的关键问题就是如 何寻找布局板元素之间的某一参数相关度问题，换句话说就是如何找到聚类依 上海大学硕上学位论文 据点。另外，聚类技术与版图布局的结合代表了一种新的自下而上的 ( b o t t o m u p ) 版图设计方法【2 3 】的出现。 迄今为止，研究人员已经提出了许多聚类算法【2 4 】， 2 5 】1 2 6 ，【2 7 】，大体上主要的 聚类算法可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于 网格的方法、基于模型的方法。由于聚类技术在超大规模集成电路布局中的普 遍运用，越来越多的研究专注于如何得到效率更高、效果更好的布局聚类分割 技术当中。其中比较普遍运用的就是网表聚类( n e t l i s tc l u s t e r i n g ) 技术。 1 2 2 网表聚类技术 网表聚类技术是现今非常常用的一种基于层次方法划分的聚类技术，是一 种将基本层次划分与模型构造划分相结合的聚类算法【2 引。这种技术试图将关联 程度高的元素在布局之前先聚类在一起，形成更高层次的簇。然后对低层次的 簇进行进一步的处理。本论文试图在网表聚类技术的概念基础上进行新的尝试 与改进。 本论文的第四章将具体描述网表聚类技术的技术特点，在这里先指出网表 聚类技术的近几年研究成果。网表聚类技术是s e o n gk s ，k y o u n gs j ，k y u n g c m 等在1 9 9 7 年提出的 2 9 1 。他们的实验结果证明了建立关联程度较高的网表 将大大的有助于聚类分割技术的提高，他们的论文中将网表聚类与传统的 f i d u c c i a - m a t t h e y s e sa l g o r i t h m 以及第三章将要介绍的e d g ec o a r s e n i n g ， h y p e r e d g ec o a r s e n i n g ，m o d i f i e dh y p e r e d g ec o a r s e n i n g 进行比较，比较结果表 明新的方法在布局分割度( c u t ) 性能上提高3 1 2 。 然后，c a p o 及f e n g s h u i 【3 0 】成功运用多层分割布局法( m u l t i l e v e l p a r t i t i o n i n gp l a c e m e n t ) 开辟了自上而下( t o p - d o w n ) 与自下而上( d o w n - t o p ) 相结合的布局技术。为了把两者相结合，h u 与m a r e k s a d o w a s k a 3 i 再进一步 吸收了网表聚类技术到这种多层分割布局中，形成了现在的网表聚类分割技术。 这种新技术大大降低了版面规划所需的时间，更为重要的是，这种新技术使得 原本已经很难得到的提高的布局分割用时得到了较大的提高。 近年来，越来越多的实验数据包也专门为网表聚类分割技术的研究而设计 4 上海大学硕士学位论文 出来【3 2 】，【3 3 1 。特别是超大规模数据平台的出现，更为聚类分割技术的研究做出了 极大的贡献。例如，1 9 9 8 年国际物理设计论坛( i n t e r n a t i o n a ls y m p o s i u mo n p h y s i c a ld e s i g n 【i s p d l ) 当中出现最大聚类数据实验包( b e n c h m a r ks u i t e ) 有 2 1 0 ，0 0 0 门；而到了2 0 0 5 年，这一数据被提升到惊人的2 , 5 0 0 ，0 0 0f - j ，足足增加 了十倍还要多。因此如何使得如此巨大的数据实验包得到快速、有效的宏观分 割布局结果，将是聚类分割布局技术中近1 0 年研究的重点之一。 在本实验室的过去研究中【3 4 】，也重点研究了如何把网表聚类技术运用到二 次规划布局当中，实验室有了自己独有的一套布局平台，并结合网表聚类，特 别在聚类搜寻中运用了b e s t - c h o i c ea l g o r i t h m 的搜索方式，详细概念将在第四 章中重点说明，比较详尽地论证了网表聚类的实用性问题。而且，将网表聚类 与二次规划布局法结合后证明比传统分割布局在平均分割度上有1 3 的提高， 在分割处理时间上有5 5 的用时下降。 在网表技术的研究中发现【35 1 ，当网表中的元素被聚类成簇的时候，由于聚 类搜寻方法及搜寻条件的局限，往往使得原本在物理距离上离得非常近的两个 元素在合并的时候却合并到了不同簇当中。出现这样的情况后，过去的研究中 试图在树型结构中找到改进的可能，但发现无论如何改进，因为每一张不同的 网表只能表现元素在各自相应的网表中的相对关系，而且很多关联度较高的元 素对在物理距离上并不是最近的，有鉴于此，有必要扩大聚类条件的设置，让 合并的元素尽可能的是关联程度最高的元素。 1 3 新想法的提出 从上一节的分析中可以知道，如果仅仅考虑的网表作为聚类的依据，这种 依据虽然可以较快速的得到比较好的簇结果，但是只吸收了每一网表内的局部 关联信息( 1 0 c a lc o n n e c t i v i t yi n f o r m a t i o n ) ，而忽视了其他全局关联信息( g l o b a l c o n n e c t i v i t yi n f o r m a t i o n ) ，因此是一种不完备的方法。当然布局问题永远是一 个n p h a r d 的问题 3 6 1 ，任何的布局方案永远只是无限接近于最优解而已，仍 然具有很多的提高空间。 其实，可以作为聚类参考依据的元素很多，比如：元素间相关度，元素间 上海大学硕士学位论文 的物理距离，元素面积大小，元素群密度，元素布局的优先级别等等。问题是 如何来处理两种不同参量间的相互作用问题，也就是说多聚类元素间的搭配问 题。 本论文将考虑更多的全局信息来进行聚类布局处理，并将常用的网表聚类 技术以及一种全新的距离聚类方法结合在一起，合称之为网表一距离式聚类技 、术。这种新方法是基于多种布局参数作为聚类的考虑因素，以物理距离作为聚 类依据的新方法。而且由于二次规划布局法是一种可决定化方式的布局，这也 使得多参数布局聚类依据比较容易在二次规划布局法中实现。因为只需修改相 应的限定方程组或者二次多项式的限定求解函数，或者只需要修改一个简单的 值即可改变多种布局聚类限定条件。从而寻找不同效果的布局聚类结果。 本研究课题的最大创新之处在于提出了一种多参数二次规划布局聚类的新 方式，这对聚类布局向更快、更好的方向发展起到了重要的作用。最终的实验 结果表明，本研究课题的新方法对聚类布局技术的各种性能指标上有较大的提 高。 1 4 章节安排 为了使论文的研究成果比较容易为读者所接受，论文将分为以下四个部分。 第一部分的本章节属于背景介绍与论文概况的介绍部分。大体上介绍了本 研究的相关知识及国内外的研究情况。 第二部分包括第二章，将详细介绍l u 矩阵分解求解法，并运用于实际的 二次规划布局式程序布局平台，实现二次规划布局的性能提高。 第三部分包括第三章和第四章，将重点介绍一些比较传统的聚类方法，并 指出其中的一些不足之处和值得改进的地方。在这一部分中，将介绍h m e t i s 超图分割算法包，这个分割算法包将用于最后的实验当中。 本论文的最后一部分将介绍全新的网表一距离式聚类技术的新方法及完成 的实验情况。论文的最后一章将作为整篇论文的总结，并提出了有待进一步研 究的一些方向。 6 上海大学硕士学位论文 第二章l u 分解矩阵解法运用于二次规划布局 广泛运用于大规模集成电路布局技术中的二次规划布局是一种对计算量非 常敏感的布局技术。它的布局结果往往显著地依赖于整体物理认证时间。二次 规划布局技术中的每个环节的旨在减少计算量的技术研究是二次规划布局技术 提高的关键所在【3 7 1 。特别是一些关键步骤以及占有计算量极大的步骤，更是成 为提高二次规划布局技术的主要突破口。例如二次规划布局技术中最关键的网 表( n e t l i s t ) 超图( h y p e r g r a p h ) 函数集矩阵解处理问题一直是阻碍二次规划 布局技术性能进一步提高的瓶颈问题之一。在本章中，将首先简要的回顾一下 二次规划布局技术的技术特征与发展状况，然后重点介绍一种新型的快速矩阵 问题求解方法：l u 分解法。本章的最后还将这种新型的矩阵求解方法应用于 实际的二次规划布局平台，最后的实验结果证明新型的矩阵求解方法比传统使 用的g a u s s i a n s e i d e l 矩阵求解方法在计算量与计算速度方面有很大的提高。 2 1 大规模集成电路的二次规划布局 二次规划布局是在大规模集成电路布局中比较常用的一种经典布局方法。 这种方法运用二次程序优化构造二次线性方程式。它是第一种把布局问题转化 为二次线性方程式的布局方法。它首先把布局板上的元素构成一组线网式数据， 通过线网中的数据间的关联程度及一定的二次方程构造准则建立一系列相应的 二次线性方程组。在建立及求解二次线性方程组的时候，应尽可能多的考虑到 布局板全局的信息数据及数据间的关联度问题。 2 1 1 网表中的元素超图 普通的大规模集成电路图可以被表示为超图。用符号h ( v ，e ) 表示。在 这里，一个簇可以表示为在超图中的元素及网表的递归方式。任何一个大型电 路可以被表示为一张超图的形式，在超图中v 表示各种电路中的元素或者超图 7 上海大学硕士学位论文 中的一条边，e 表示网表中的一个线网。一张完备的超图可以被转化为一系数 矩阵( c o e f f i c i e n tm a t r i x ) 。具体将在第三章详细介绍关于超图与系数矩阵的转 化问题。 2 1 2 二次规划布局 二次规划布局的线性方程部分可以由图2 1 表示的这些步骤组成。首先，为 了得到比较完善的初始布局结果，反复地通过网表来建立、修改、求解线性方 程组并修改相应的下一步网表内容，以求每次得到最优化的中间布局结果。当 然每次更新之前，必须测试一定相关的控制布局系数，从而控制下一步的q p 初始更新值。在实验室中实际的二次规划布局程序中，如图所示，在每次更新 结束后测量了布局的元素密度( c e l ld e n s i t y ) 【3 8 】作为控制参数。 依据数据建立相 应的线性方程组 通过限制条件解 出所有的线性方 程组 评估布局板上的 元素密度参数 通过密度参数更 新线性方程组右 边的系数集 解更新过的线性 方程组 图2 1 二次规划布局的主要步骤 严格来说，二次规划布局过程中对计算量敏感区有两个部分，一个是具体 上海大学硕士学位论文 求解线性方程组的过程，另一个是控制参量更新过程。本章所改进的只是求解 线性方程这一过程而己。其实在研究中发现，也可能只人为改变线性方程组的 右系数值，而不用每次测量布局控制系数，从而达到相应的效果，如果可以实 现这样的改进的话，更将大大的提高二次规划布局的处理速度，这将成为继续 二次规划布局研究的重点所在。 另外，二次规划布局的其他程序包括p i n 配置( p i na s s i g n m e n t ) 。p i n 配置 就是为了把线性方程组得到的结果安排在相应的布局板上，在配置之中一般要 对布局进行一定的横纵轴划分及分块设置( c h i pa r e ad i v i s i o n ) 。详细将在第五 章的实验中说明。 2 1 3 线性方程组 通过上面的介绍，可以了解到线性方程组在二次规划布局当中占有非常重 要的地位。网表转换到相应的线性方程组、线性方程组的更新、线性方程组进 行p i n 配置等等一系列的步骤，线性方程组运算性能的优劣将直接联系到二次 规划布局的整体性能。下面将具体介绍一下线性方程组的问题。 运用于二次规划布局中的线性方程组可以被认为是一种二维独立的方程组 方式。具体可以由下面的等式1 1 表示。式中的c 是由所有元素所组成的网表 按照一定的规则转换而成的。六及六是相应的控制布局系数得到的两组x ，y 向 量方程或者向量组。后面介绍的实验中将以元素密度函数作为控制向量。 白+ 凡= 0 一 ( 1 i ) c v + f = 0 y 图2 2 是运用二次规划布局得到的一些中间结果，左图是所有元素的原始布 局情况，当执行每一次的q p 线性方程组计算周期后，都会使线性方程组中相 应的元素位置信息得到变化，再通过p i n 配置，完成元素位置的相对变化。然 后运算每个元素周围的元素密度，更新线性方程组的右端系数为z 及，产生 新的方程组，如式1 2 。图2 2 右图是经过2 0 0 次q p 线性方程组运算后或称为 2 0 0 次q p 扩散周期后( q p d i s t r i b u t i o nc y c l e ) 的中间布局结果。 9 上海大学硕士学位论文 + 正= 0 + = 0 ( 1 2 ) 通过以上的分析，可以明显的看到，对式( 1 1 ) 和式( 1 2 ) 线性方程组的 运算性能问题将是提高二次规划布局的主要问题之一。 图2 2p i n 配置的q p 初始步骤和2 0 0 次q p 扩展周期后的中间步骤 2 2l u 分解运用于二次规划布局 2 2 1 线性方程组的传统分解解法 如何有效的求解线性方程组问题一直是困扰应用数学的几大问题之一，在 早期的求解方法中，线性化( 1 i n e a r i z e ) 与数据的输入输出操作占有了绝大部 分的运算时间 3 9 1 。随着计算机设备能力的提高，直接运算法( d i r e c tm a t r i x s o l u t i o n ) 4 0 】渐渐成了主流，程序简单运算相对较快的高斯消元法( g a u s s i a n e l i m i n a t i o n ) ，t i n n e y w a l k e r 算法广泛的运用于线性方程组的运算当中【4 1 1 。但 是随着超大规模集成电路规模的日益复杂，传统的直接运算法有时往往占有了 将近9 0 的布局时间，整个v l s i 布局的性能被大大的降低。于是，又引进了 迭代法( i t e r a t i v em a t r i xs o l u t i o n ) 4 2 】。比如：高斯塞德尔法( g a u s s s e i d e i ) 和雅可比法( j a c o b i ) 。实验证明，这些方法确实可以有效的提高超大规模集成 电路布局的性能问题，而且当电路规模进一步增大后，迭代法的运算时间只不 过呈现线性增加的上升而已，仍旧不失为一种比较理想的方法。然而，本论文 i o 上海大学硕士学位论文 所研究运用l u 分解的方法代替原来的迭代法，由于大大减少了运算填充面积， 通过最终的实验证明，这种方法虽然在程序源代码中添加了一定量的程序，但 是最终的测试结果还是非常另人满意的。 2 2 2 线性方程组的l u 分解解法 l u 分解方法 4 3 1 的核心把所给的方程组a x - - b 通过基本矩阵变化转换成下 三角矩阵l 矩阵与上三角矩阵u 矩阵，下面是一个比较形象的l u 分解简例。 a = a i l 口l ，q 。 a r i 口，r a m a l 口a l l 1 乞。0 1 u r r “m ( 1 3 ) 矩阵的元素为， q ，= ， _ ，= l ，2 ，胛 ( 1 4 ) a 的第r 行元素主对角线以右元素( _ ，= ，z ) 为 口d = k = ，一，甩 七= l 同样，可知a 的第r 列元素主对角线以下元素( i = ，+ 1 ，刀) 为 = 匕 i = r + l ，万 七= l r = 1 ，2 ，刀一1 显然，r = l 时， a 订2 l u l l i = 2 ，3 ，l 并综合以上分析，式( 1 4 ) ( 1 5 ) 可得： r - i = k + ( 1 ) 七互l 式( 1 6 ) ( 1 7 ) 可得： ( 1 5 ) ( 1 6 ) ( 1 7 ) ( 1 8 ) 上海大学硕士学位论文 r l = 乞+ 乞 综上可以推导出： “l = 口l _ ，= 1 ，2 ，疗u 的第一行 毛= 盟i = 2 , 3 ，l 的第一行 u i l r 1 = 一“ 七= l r l 靠一k 0 = 型一 u r r r = 1 ，2 ，n j = ，n u 的第，行 r = 1 ，2 ，z 一1 i = ，+ 1 ，ll 的第，列 ( 1 9 ) ( 1 1 0 ) ( 1 1 1 ) ( 1 1 2 ) ( 1 1 3 ) 称上述分解过程为l u 分解。 对于线性方程组a x = b ，系数矩阵非奇异，经过l u 分解后a = l u 。再经过 变换可以转换为以下两个三角形方程组： 砂= b阪= y ( 1 1 4 ) y 为中间未知向量。根据式( 1 1 0 ) ( 1 1 1 ) ( 1 1 2 ) ( 1 1 3 ) 的计算可以得到中间 未知量y 的结果 y l = 6 l y 2 = 6 2 1 2 1 y l r - i y r = b r 一乞乃 厂= 2 , 3 ，甩 然后代回求解x 的最终值 ，一只 一 u ”一u , j x j t 2 u 1 2 ( 1 1 5 ) ( 1 1 6 ) 上海大学硕士学位论文 2 2 3l u 分解解法的优势 图2 3 高斯塞德尔法与l u 分解法的主要编码 图2 3 是高斯塞德尔法与l u 分解法的主要编码的核心算法，从算法中可 以看出，虽然对于程序复杂度来说，高斯塞德尔法更为简单，但是对于运算速 度来说，可以明显的看出，由于l u 分解每次更新的只是行与列的k + l 到n 的 元素，总共( n k - 1 ) 个。而高斯塞德尔法则是每次必须进行两组数列求和，然后 还要算出一个补充因子b i ，进行逐个更新。理论分析上来说，运算速度将会大 大的低于l u 分解。 另外，测量编码的核心运算部分的性能，以运算面积( c o m p u t a t i o na r e a ) 为比较重要的一个衡量不同方法之间性能的参数。图2 4 是三种常用不同矩阵 上海大学硕士学位论文 求解方法的运算面积。i 代表行列式的纵轴，j 代表行列式的横轴，k 代表本次 循环的要处理的对角线元素位置。阴影部分为算法每次填充的矩阵面积，也就 是每次完成行列式计算后改变的元素部分，面积小表明需要进行的计算量少。 虚线部分对应的每次填充计算所涉及到的元素。比较三种不同的矩阵分解法， 可以很明显的看出，l u 分解法每次填充( f i l l - i n s ) 的面积最小，也就是l u 分 解法为何可以实现较快运算结果的主要原因之一。 j叫 f一 ( a ) g a u s s i a ne l i m i n a t i o n f7fvfffffff ( b ) t i n n e y - w a l k e r j _ 卜 入 ?ik ( c ) l uf a c t o r i z a t i o n 图2 4 三种不同线性方程组解法的运算面积比较 1 4 上海大学硕士学位论文 2 2 4 实验结果 为- j n 试新方法在实际二次规划布局过程当中的性能，在实验中，新引入 的l u 分解法被运用到实际的二次规划布局平台当中，然后测试了一些比较常 用的v l s i 布局数据包。进行比较的数据为运行了原先使用的高斯塞德尔法的 v l s i 布局数据包。测试环境如下表所示： 高斯塞德尔法与l u 分解法测试数据包表示在下面的表2 1 中。 表2 1 c e l l e x t c e l l n e t l ug s 布局测试数据包条件