（计算机应用技术专业论文）超大规模集成电路划分算法研究.pdf

摘要 超大规模集成电路布图领域的划分问题是一个n p 完全问题，一般采用启发 式算法解决。目前，超大规模集成电路划分问题已经得到了广泛而深入的研究， 出现了许多较为有效的解决算法。在这些算法当中，组迁移算法以其简单有效得 到了最广泛的应用。但是随着电路规模的不断增大，研究人员开始更多的利用多 级层次划分策略解决该问题。 本文首先对已有的电路划分算法进行了介绍，尤其深入分析了基于多级层次 划分策略、运用组迁移算法进行电路划分的思想。在此基础上，提出了一种新的 多级层次划分算法。该算法首先从电路连接关系中抽象出超图模型，然后对所得 超图模型进行多级层次划分。在层次划分时，采用了多次塌缩优化的策略扩大搜 索空间，并在恢复优化时运用了贪婪策略，使得算法在避免局部最优的同时，仍 然维持了较低的计算时间。对i s p d 9 8 测试数据的仿真实验表明，该算法要比二 分法和简单的多块多级层次划分法更为有效。 关键词：多级划分超大规模集成电路超图 a b s t r a c t t h ep a r t i t i o n i n gp r o b l e mo fv l s ic i r c u i t si sn p c o m p l e t ea n ds om a n yh e u r i s t i c a l g o r i t h m sh a v eb e e nd e v e l o p e dt om a k en e a r - o p t i m a t h i sp r o b l e mh a sb e e nw i d e l y a n dd e e p l ys t u d i e da n dm a n ye f f i c i e n ta l g o r i t h m sa r ea v a i l a b l en o w t h es i m p l ea n d e f f i c i e n tg r o u p - m i g r a t i o na l g o r i t h m sa r ew i d e l ya d o p t e di ns o l v i n gt h i sp r o b l e m b u t w i t ht h er a p i d l yi n c r e a s i n gs c a l eo fv l s i ，m o r er e s e a r c h e r sh a v ei n v e s t i g a t e dt h e a p p l i c a t i o no fm u l t i l e v e lp a r a d i g mi nt h i sd o m a i n i nt h i sp a p e r , w ef i r s t l yi n t r o d u c e ds o m ee f f i c i e n ta l g o r i t h m so nt h i sp r o b l e m ， e s p e c i a l l yt h ev e r yo n e sb a s e do i lt h em u l t i l e v e lp a r a d i g m t h e nw ep r e s e n tan e w a l g o r i t h mb a s e do nt h a t b yt h i sa l g o r i t h m ，w ef a s tc o n s t r u c tah y p e r g r a p hf r o mt h e c i r c u i t t h e nt h eh y p e r g r a p hi sp a r t i t i o n e di nm u l t i l e v e lp a r a d i g m t oe x t e n dt h es e a r c h s p a c e ，s e v e r a lc o a r s e n i n gp h a s e sa r ea d o p t e d ag r e e d ym e t h o di sd e v e l o p e da n du s e d i nt h er e f i n e m e n tp h a s et oa v o i dt h el o c a l o p t i m aw i t hl e s st i m e e x p e r i m e n t so nt h e i s p d 9 8b e n c h m a r ks u i t es h o wt h a tt h ep a r t i t i o n i n g sp r o d u c e db yo u rs c h e m ea r eb e t t e r t h a nt h o s ep r o d u c e db yt h eb i s e c t i o no rs i m p l ek - w a ya l g o r i t h m s k e y w o r d ：m u r i l e v e lp a r t i t i o n v l s i h y p e r g r a p h 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：蝌 日期巩秒扩、哆 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名：斟们们午 剔磁轹南狄 日甄函一孑| 巧 日期孙留i 、 第一章绪论 第一章绪论 1 1 引言 19 5 8 年集成电路诞生以来，已经历了小规模集成( s s r ) 、中规模集成( m s i ) 、大 规模集成( l s i ) 的发展阶段，目前已进入超大规模集成( v l s i ) 阶段。 随着工艺技术的进步，单个芯片所集成的晶体管的数量在不断上升。据i t r s ( i n t e m a t i o n a lt e c h n o l o g yr o a d m a pf o rs e m i c o n d u c t o r s ) 2 0 0 4 年估计，到2 0 1 0 年， 在4 5 纳米工艺和1 伏工作电压下，片上系统( s o c ) 可以集成4 0 亿晶体管，频率 可以达到1 0 g h z 。并且，随着集成度的提高，集成电路设计的复杂性也越来越高， 伴随而来的是i p ( i n t e l l e c t u a lp r o p e r t y ) 核的广泛使用、导线延迟的迅速增加以及 对计算机辅助设计技术( c a d ) 的要求越来越高。 计算机辅助设计技术广泛应用于集成电路设计的各个过程当中，包括功能设 计、逻辑设计、电路设计、版图设计、设计验证和制造等过程。在整个设计过程一 中，版图设计( 或称为物理设计) 是其中重要的一环，它是在一定面积( 平方厘 米级以内) 硅片上完成的一个包含数百万乃至千万个晶体管的完整的数字系统或 数、模混合的电子系统。版图设计也是v l s i 设计中最费时的一步，它要把每个元 件的电路表示转换成几何表示。同时，元件间的连线也要被转换成几何连线图形。 我们把电路的几何表示叫作版图，而把版图的设计称为布图。由于布图的复杂性， 整个布图过程往往被分成包括划分、总体布局、详细布局等若干子步骤，每一步 骤完成布图的一部分。 布图算法是超大规模集成电路设计的基础底层问题，是现在被广泛使用并大 大提高了芯片设计周期的布图c a d 设计的重要基础。目前，为了缩短设计周期， 提高设计模块的可重用性，在工业界实际应用中，许多超大规模集成电路中均含 有一些已经预制好的大模块p 核如r a m ， r o m ， p l a 及d a t a p a t h 等，在布图 时便要求同时确定这些大模块与其它诸如逻辑门等小单元的位置，而这些大单元 与小单元的面积差别是极为悬殊的。图1 1 给出了i b m b e n c h m a r k s l 8 ( i b m l 8 ) 】中各 模块的面积分布的直接表示。 此时通常的平面布图( f l o o r p l a n n i n g ) 方法已不适用【2 1 ，于是就出现了所谓混 合模式( m i x e d s i z e ) 布图问题【2 3 1 ，众多研究者开始了对混合模式的布图算法的研 究， 2 超人规模集成电路划分算法研究 以期获得最优的布线以减少导线长度，控制导线时延，节省芯片面积。 两积大小，最小记为l 图1 1i b m l 8 测试数据模块面积分布 由于问题本身的规模巨大，受现有计算能力的限制，对所有模块直接进行初 始布局是根本不可行的。 为了压缩问题的规模，需要将所有的模块依据某种规则划分成现有初始布局 算法能够处理的规模( 通常为1 0 0 以内) 。于是便产生超大规模集成电路布图领域 中图的划分问题。划分算法是目前所有布图算法所必需的，是布图算法的基础。 可以说，后继的初始布局与详细布局的质量与划分算法所得到的划分结果的质量 是密切相关。 1 2 超大规模集成电路划分算法的研究现状与动态 根据算法应用的寻优策略，电路划分算法大致分为两类。一类算法从空集开 始，通过一次增加一个单元的方法来建立划分，这类算法是构造性算法；另一类 算法从任意初始划分开始，通过重复修改子模块中的单元来优化划分结果，这个 过程一直进行到满足约束条件为止，这类算法叫迭代改进算法。这里以研究后者 为主对划分算法做一介绍。 聚类算法属于构造性算法，这类算法将给定的顶点集进行聚类【3 1 1 4 1 ，每一个聚 类应当满足不同的标准，比如整个子模块的尺寸大小或者外连线的数目。要形成 一个聚类必须选择一个种子顶点对聚类进行初始化，从种子顶点的临近顶点中找 第一章绪论 3 出与之强连接的接点不断地增加到聚类中，如果聚类( 子模块) 的大小或者外连线的 数目超出预定的要求，则聚类过程结束。因为聚类是从一个种子顶点开始，所以 该算法是一种串行构造性算法，受搜索空间的限制，使用聚类算法得到的划分结 果质量不是很好，这是因为最终的划分中往往有来自不同类的稀疏顶点。聚类算 法简单易操作，而且速度较快，一般的聚类算法用于产生初始划分，再应用图形 算法或者其它组合优化算法对初始化分进行改进。 k e m i g h a n 和l i n 提出了组迁移( g r o u pm i g r a t i o n ) 算法【5 】思想，并设计了k l 算法，其计算的复杂性为n 2l o g ( n ) ，n 为图中的结点。该算法是二分的图划分中第 一个成功有效的启发式算法，以后的图形算法大多是对k l 算法进行改进。 s c h w e i k e r t 和k e m i g h a l l 在上述算法的基础上提出了线网割模型【6 1 ( n e tc u t m o d e l ) ，叙述了使用简单图形模型的缺点，提出了一种n e t c u t 电路模型，在这个 模型中，一个线网代表与同一信号线相连的所有元件的连接关系。考虑一个连接 三元件的网，如果按照图形模型理论，这个图将成为一个三顶点的连接图，如果 划分这个图，切割代价为三个边，然而，如果该电路使用n e t - c u t 模型，切割代价 仅为一个网。该模型适合用于连接多个单元的电路线网结构，使得k l 算法的应用 范围更广。 f i d u c e i a 和m a t h e y s e s t7 】提出了f m 算法，引入了单元的增益和面积的约束， 该算法也是首先产生初始划分，每次交换以单个单元从一个子集移动到另一个子 集进行，元件的移动要考虑是否满足约束条件，这样减小了计算量，降低了邻域 解空间。算法又通过一种桶排序技术( 数据结构) 使得改进的k l 算法的复杂性变 为o ( p ) ，p 为所有线网的所连单元数之和。f m 算法速度很快，但是f m 算法容易 陷于局部最优，且该优化方法仍然是单重优化。 k r i s h n a m u r t h y l 8 】在f m 算法的基础上引进了具有预测性的多级增益模型 ( m u l t i l e v e lg a i nm o d e l ) ，该模型能更精确地选择使得切割集数目达到更小的单元。 s a n c h i s t 9 】将上述方法用于多块划分中，与k l 算法和f m 算法相比得到了更好的效 果。d u t t a 和d e n g t t l o 】把一种基于概率的启发式算法引入f m 算法，使得f m 算法 提高了解的质量。 上述均为图形算法，图形算法的主要限制在于它们仅能应用在两路划分中， 大多不能应用于多路划分。为了进行k 路划分，必须对两路划分结果重复应用上 述算法，k 的值也必须是2 的次幂，而且划分过程要经历k 一1 次两路划分。即使应 用上述划分方法仍不能产生最优的划分结果，因为每次划分只考虑两个子集间的 最优划分，而不是全局最优划分。为了得到全局最优划分，学者们利用一些组合 优化算法解决划分问题，取得了一定的成果，如：神经网络模型、模拟退火算法、 自适应算法、遗传算法等。 4 超大规模集成电路划分算法研究 模拟退火算法】是一种迭代改进算法，在划分问题中，模拟退火也是从某种 随机初始划分开始，每一个新的状态通过从各个子集中随机地选择一个单元进行 交换得到，直到最终解的质量满足要求为止。切割集间线网的数目为评价解的好 坏度，算法中元件每移动一次，就对应一个解( 或状态) ，如果新的状态比旧的状态 好，则接受该状态，如果新状态比旧的状态差，则将这个状态下的好坏度与一随 机值相比决定该状态是否保留。模拟退火算法在一系列不同的阶段进行操作叫“温 度 ，每一阶段都有一个实际的温度值，算法从高温按照一个冷却表开始逐渐降温， 随着温度的降低那些增大代价函数的状态被接受的可能性越来越小。 a l p e r t 和y a o t l 2 】等提出了一种比较新的电路划分算法叫光谱分割算法( s p e c t r a l p a r t i t i o n i n ga l g o r i t h m ) 。这种算法是将电路的元件互联代价值用l a p l a c i a n 矩阵来表 示，通过求取其特征值和特征向量，并对特征向量进行分割来得到元件在不同子 集中分布情况。j a n y a n gc h a n g 和y u c h e nl i u 1 3 】等提出了两种解决多路划分的光 谱分割算法，实验证明这两种算法效果好而且速度快。算法通过把每一个元件映 射成多维向量的方式将电路划分问题转换为向量划分问题。这两种算法指出解决 向量划分的关键是首先把向量集看作一个聚类，从当前聚类中重复选择一个最大 代价改进的聚类，将它划分为两个新的聚类，当聚类的数量达到要求的划分数量 时，算法结束。 另外，基于遗传算法的电路划分算法也开始受到人们关注，该类算法不仅适 用于两路划分，也适用于多路划分，而且满足划分对子集的大小和面积要求。采 用整数编码，染色体中每个基因的编码为它的顶点编号，对于两路划分，染色体 中n 2 位以- f i ；j - ( 包含n 2 ) 的基因属于子集i ，后面的基因属于子集2 。算法采用顺序 交叉方法和交换变异策略，评估函数为子集间互连线的数量，得到了好的划分结 果。b y u n g - r om o o n 和c h u n - k y u n gk i m 0 5 1 6 】提出了一种遗传算法解决电路划分问 题，算法中解的编码起了重要的作用，技术的关键在于动态编码，编码本身起到 了进化作用，产生每一个新解前，都通过从包含不同编码的池中选择两个编码进 行组合，进而产生新的解，新解的产生主要是通过交叉算子完成。实验表明该遗 传算法在解决电路划分方面比当时发表的国内外算法都好。g e o r g ec h s i r a k o u l i s 和i o a n n i sk a r a f y l l i d i s t 。7 】等提出了一种v l s i 电路的遗传划分和布局算法，该算法 是自适应遗传算法，作者研究了算法搜索过程中的些参数变化，如种群大小、 交叉和变异率等。与标准遗传算法相比，自适应遗传算法在较短的时间内能产生 较好的划分结果。c h a r l e s j a l p e r t 和l a r sw h a g e n t l 8 】等提出了一种解决多路划分 的混合遗传算法，该算法和一般划分算法相比得到同样好的划分所需c p u 时间要 少。 在最新的研究中，g e o r g ek a r y p i s ，r a j a t a g g a r w a l 1 9 1 等人将超图理论应用于基 第一章绪论5 于二分法多层划分策略集成电路划分算法之中。用超图模型来描述电路连线结构， 不仅直观简单有效，而且可以很好的使联系紧密的电路模块不被分开，使进一步 的塌缩操作更有成效。 随后g e o r g ek a r y p i s 和v i p i nk u m a r 【2 0 】又将之前应用超图理论的两路划分算 法改进为多路划分算法。该算法首先将电路连接抽象成超图，然后利用先前使用 的两路划分方法，进行多层次的塌缩优化，并最终得到了初步优化的k 分图。然 后，再从全局着手，同时进行k 路迭代优化，为了提高效率，该步采用了贪心策 略，从而使陷入局部最优的问题得到了改善。 尽管传统的电路划分算法在实际应用中都得到了很好的应用，但是从上面的 分析可见，仍然没有一种算法在任何情况下都优于其它电路划分算法，各有优缺 点，所以很多技术人员开始研究混合算法，企图在划分结果和划分速度上都得到 很好的效果。混合算法大致分为两类，一类是利用某种典型的启发式算法产生初 始划分，再利用组合优化算法改进划分结果，使之达到全局最优。第二类是把两 种以上的电路划分算法结合起来，弥补了使用单一划分算法的缺点，达到了好的 划分效果。比如，s h a w k i a r e i b i 和a n t h o n y v a n n e l l i 2 l 】提出了两种解决电路划分问 题的混合算法，两种算法分别采用贪婪随机搜索技术和遗传算法产生初始划分， 再利用禁忌搜索技术对划分结果进行改进，两种混合算法都比单一算法产生解的 质量好，而且减少了计算时间。l t a oa n dyc z h a o 2 2 】提出了两种启发式电路划分 算法，文中比较了模拟退火算法、禁忌搜索算法及二者与s p a ( s t o c h a s t i cp r o b e a l g o r i t h m ) 算法的结合，并比较了几种算法的优劣。 上述的几种划分方法，通常将他们组合起来使用的，例如对于多级划分来说， 在每一步的恢复到原图的过程中，都可以使用k l f m 算法来完成。而在使用 k l f m 算法时，也可以使用塌缩算法来对每个区域内的联系紧密的子图进行塌缩， 以使交换顶点时交换的更有效率。 以上阐述了各种算法的基本理论，并分析了它们的优缺点。总的来说，聚类 算法和图形算法都属于简单的算法，因为其搜索空间小，所以速度快，但是得出 的划分结果并非全局最优；解决全局寻优的组合优化算法加大了搜索空间，尤其 是遗传算法，在某种程度上都能找到问题的最优解，但是划分过程相对长，但是 往往集成电路设计人员希望利用e d a 工具在较短的时间内得出较理想的划分结果， 因此设计一个好的电路划分算法就不能仅仅采用某一种电路划分方法，混合式电 路划分算法，将成为发展的趋势。 6 超大规模集成电路划分算法研究 1 3 论文主要研究内容和结构 已有的集成电路划分算法大多在处理电路单元面积相差不大的集成电路划分 问题时较为有效，但是在处理像图1 1 所示的含有大量的p 核等大单元的集成电 路划分问题时则大多表现不佳，因为要维持此类问题的负载平衡同时寻找最优解 是极为困难的。 在文献【1 9 1 和文献【2 0 】的基础上，本文设计了一种基于多层次k 分策略、运用超 图理论、通过对f m 算法的改进以及对边权重独特的改进运用来实现有效解决现 有的超大规模集成电路划分问题的算法。 由于现有超大规模集成电路的规模巨大，多层次划分策略成为了划分算法的 主流策略，其通过粗化积聚缩小规模，使得用于迭代优化的时间复杂度降低到能 够容忍的水平。并且，运用超图理论对原图进行粗化积聚，重新设计的边权重赋 予规则，使得在降低规模的同时，能够使粗化积聚所得到的积聚联系较为紧密， 减少了后继工作的复杂程度。通过k 分策略以及经过改进的适用于k 分策略的f m 算法，可以有有效避免局部最优的同时在较小的时间复杂度情况下获得符合约束 条件的优化划分结果。 通过对i s p d 9 8 放出的i b mb e n c h m a r k s 数据进行的仿真测试，本文提出的算法 在与其它算法的横向比较当中，得到的结果是具有优势的，尤其对于规模较大的 数据，优势较为明显。 本文以下各章节的基本内容组织如下 第二章：详细介绍了超大规模集成电路布图中图的划分问题的各种基本概念， 讲解了电路划分算法在v l s i 布图中的意义，并给出了一般意义上电路划分问题的 数学模型。然后该章详细讲解了几种基本的划分算法以及层次划分策略并介绍了 多级层次划分算法的一般步骤。 第三章：详细描述了本文所设计的算法并列出了仿真实验结果。这一章首先 介绍了如何将电路划分问题抽象成超图模型并转化为超图的划分问题。然后，按 照设计好的算法流程，分别描述本文设计的算法。并着重强调了我们设计的塌缩 算法以及用于恢复优化的基于f m 算法所设计的一种贪婪算法。 最后，在这一章里，还将对利用i b mb e n c h m a r k s 的测试数据所做的仿真与同 类算法做各类详细的比较与分析，通过比较分析，证明了我们的划分算法是有效 的。 第四章：总结了本文的主要内容，以及自己在超大规模集成电路布图领域中 图的划分方面所作的研究工作，并且明确了以后的研究方向。 第一章绪论7 本文的研究得到西安应用材料创新基金项目：混合模式超大规模集成电路布 局布线算法研究( x a a m 2 0 0 6 0 5 ) 的资助。 第二章超大规模集成电路划分算法概述 9 第二章超大规模集成电路划分算法概述 2 1v l s i 划分的基本概念和问题描述 电路划分在v l s i 设计中是经常遇到，是集成电路设计的关键一步。在v l s i 设计中被划分的对象一般是由口核( 宏单元) 或标准单元组成的电路，其目的是 将这些标准单元划分成两个或多个子集，以降低超大规模集成电路设计复杂性、 增强划分电路的可读性，更主要的是能够使布图时面积优化和线长优化变得简洁 高效。通常要求每个子集所包含的元件面积大致相等，划分结果使得这些子集之 间的内连线数目达到最小。因为电路划分问题属于n p 难题【2 4 l ，很难实现理想的 电路划分，虽然学者们围绕电路划分问题提出了大量的启发式算法，它们各有特 点，也各有缺陷，并没有形成一种具有权威性的划分算法。因此，寻求更加完善、 更加有效的电路划分新算法一直是广大i c 设计人员所关注的问题。 2 1 1v l s i 划分问题介绍 目前，应用于超大规模集成电路领域的图的划分算法大致可以分为两类，一 类用于f p g a 中进行图的划分，另一类则用于全定制、半定制集成电路中图的划 分。 对于前者，目前单个f p g a 芯片的门数在百万级，而单个超大规模集成电路 芯片的集成度已经达到了千万级乃到亿级。相比之下，f p g a 产品的门数太少， 当数字电路的规模超过了单个f p g a 芯片的有效门数时，必须采用划分的方法“分 而治之”才能实现有效的设计。对f p g a 来言，划分不仅可以将大规模的数字电 路在f p g a 中实现，而且可以通过对子系统的并行改进使得电路的维护修改复杂 程度降低，缩短设计周期。 而后一种划分，才是本文要着重讲述的。 对于定制电路，我们希望最终得到的芯片的面积尽量的小，因为，芯片成本 与芯片的面积是密切相关的。面积越小，选择的晶圆越小，成本则越低，而且影 响极为巨大。面积每增加一倍，成本则相应的成1 0 3 倍增长，这是一个惊人的数 字。因此，芯片设计制造厂商迫切需要通过对芯片的合理布局，争取用最小的芯 片面积来实现电路的逻辑功能。 目前，主流集成电路制造工艺已经进入了深亚微米阶段，纳米工艺阶段也即 将来临。随着芯片最小特征尺寸的不断减小，单个芯片所包含的电路模块也越来 1 0 超大规模集成r r d , 路“y j j ”9 - y 、 算法研究炮八础1 矢朱，巩峪舁7 石w l 九 越多，连线宽度变小，线长却越来越大。在深亚微米技术中，连线的时延己经大 大超过了门时延，成为影响整个芯片性能的重要因素。如何减少连线时延，实现 布图布线的最优化成了人们的迫切需求。人们对e d a 工具中自动布图的要求也 越来越高。 由于规模的巨大，现有的自动布图算法中，为了实现芯片面积的最小，导线 长度的最小，通常采用划分、布图规模和全局布图、详细布图的多层次流程来实 现，如图2 1 【2 3 】所示。由于现有的全局布图所采用的搜索优化算法，处理能力为 鼍i 阪级布局 图2 1多级布图过程示意图 百级，因此，对于动辄上百万的集成电路来说，需要先通过某种策略将整个电路 划分成规模符合全局布图要求的级别。为了使在以后布图过程中划分模块移动带 来对线长的影响最小，要求我们在这里的划分中应该尽量将关联度高的模块划分 到同一个积聚当中，使得不同积聚间的关联度最低。同时，为了减少以后总体布 图的复杂度，要求我们划分好的各积聚的面积保持在相对平衡的状态，容忍度一 般在上下百分之十左右。 第二章超人规模集成电路划分算法概述 2 1 2 电路划分问题的一般数学模型 可以用带权值的图模型来描述电路划分问题。电路中各模块代表图中各顶点， 元件间的连线代表图形中的边，顶点的点权值代表元件的大小，即面积，边的权 值代表元件间连线的数目。通常，划分问题是将图形中的顶点分到两个或者多个 不相连的子图中，子图中顶点权值的和不大于一个给定的容量，同时使得连接每 个子图的边的权值总和达到最小。 在本文中，电路抽象成一个稀疏的无向图g ( v ，e ) ，其中，v 是表示电路各 模块，包括宏单元的顶点的集合，e 是表示电路连线的无向边的集合。ivi 表示 图中含有的顶点数，v 中的顶点用v 1 ，v 2 ，v n 表示( 假设集合v 中有n 个顶点， 即ivi = n ) 。a i 表示顶点v n 的点权重，大小即为该顶点所表示的电路模块的面积。 用a g 表示图g ( v ，e ) 的点权重之和。 n - - - , a c 兰 a i式( 2 1 ) j - 一 i = 1 e 中的无向边用e h 表示。在图g ( v ，e ) 中，如果存在边 e h ，则称顶点v i ，v j 在无向边e h 上，或称无向边e h 包含顶点v i ，v j 。 所有与顶点v i 有边相连的顶点组成的集合称为v i 邻接点集，记为n i 。 将图g ( v ，e ) 划分成k 个子图( 亦称为积聚) g 1 ( v 1 ，e 1 ) ， g 2 ( v 2 ，e 2 ) ，g k ( v k ，e k ) ，记为划分蜷。子图g i 姒，e i ) 的顶点权重( 即电路模 块的面积) 为a i g ，顶点总数为n i 。所有由划分略所破坏的边称为划分所产生的割 ( c u t ) ，所有割的总数用c u t p 表示。 于是，我们搜索最小割的目标函数便可简单的表示为： m i n ( c u t p )式( 2 2 ) 同时划分问题必须满足以下约束条件： 1 每个顶点只能被划分到一个子图当中，如顶点v i 被划分到子图g j ，则v ：= 1 ， 否则v ：= o 。于是约束条件l 可表示为： k v ；= 1 ， 其中，1 i n式( 2 3 ) j - _ _ - i = 1 2 子集容量约束，即保持各划分子图的权重平衡，假设容忍因子为e ，则约 束2 可表示为： 1 2 超大规模集成电路划分算法研究 ( 1 ) 木百a c 0 ，则将结点对( a k ，b k ) 以后的单元对全部 放回原来的集合中，而将( a 1 ，b 1 ) ，( a 2 ，b z ) ，( a r ，b k ) 做真正的交换，使 割线网得到的g m a x 减少，然后将所有结点恢复为自由状态，并开始下一个p a s s ，一 直到某一个p a s s 的总增益g m a x o 为止。实验证明，只要经过5 6 轮即可结柬。 k f g m a x = g i式( 2 - 1 2 ) j 一 i = 1 k l 算法的一个主要的优点是它能够有效的越过局部最小点，因为即使一对 结点的增益为负值它也会进行交换，以免错过可能的最优解。但是它的线网模型 并不适用于具有超图性质的电路网表，其o ( n zl o g n ) 的时间复杂性也不适合 v l s i 电路划分。1 9 7 9 年s c h w e i k e r t 和k e r n i g h a n 在k l 算法的基础上提出了适用 于电路网表划分的线网模型。 2 f m 算法 1 9 8 2 年，f i d u c c i a 和m a t t h e y s e 提出了著名的f m 算法，对k l 算法进行了一 次重要的改进。 f m 算法的主要思路是针对k l 算法中的每次互换一对顶点，将其更改为， 每次将分割线一侧的顶点换到分割线另一侧去。交换的标准是： 1 ) 选择交换以后使图的负载平衡性改进最大的顶点，即使改进是负的； 2 ) 若顶点交换以后图的负载改进都一样，则选择交换以后使图的分割边权 最小的顶点。 将负载平衡作为第一标准是因为f m 算法不像k l 算法那样，每次互换一个 顶点对而不会有互换后负载差异变大的情况。 1 6 超大规模集成电路划分算法研究 图2 - 3 和图2 4 给出了f m 算法的示例。 e d g e - c u t m 6 c e d g e - c u t - 7 渤 e d 辨咤u 扣6 似 e d g e - c u t - - 8 图2 3f m 算法分割优化示意1 其中顶点的特征值计算如下：将此顶点交换到分割线的另山侧以后，图的分 割边将减少x ，则顶点的f m 特征值为x ，x 为负的情况说明此顶点交换以后， 图的分割边将增加lxi 。 f m 算法对于顶点权来说并不好判断，例如，如果对某个分割步骤来说，如 果交换以后图的分割边减少最多的顶点，却不是交换以后对图的负载平衡改进最 大的顶点，也就是说上面列举的标准2 与标准1 冲突。在这种情况下f m 算法并 没有给出较好的解决方案，具体应该如何优化，也是本文将要探讨的问题。 图2 3 给出了f m 算法的前几步，其中：a ) 是初始划分后的图；b ) 是对图的 顶点进行特征值计算之后的图；c ) 是交换第一个顶点之后的图；d ) 是交换2 个顶 点后的图。图中黑色的顶点即为交换过的顶点。每个小图的下方标记的e d g e c u t 是当前分割线经过的链路数，可以认为是顶点间的负载大小，因为在图示中边权 被忽略了。 第二章超大规模集成电路划分算法概述 1 7 标记在图中顶点上的数值是交换此定点后有关于分割边的增益值。对于这个 数值来讲，正负都是允许的。每次交换定点上数值最大的那个点，并在交换以后 更新整个图的定点的增益值，以查找下一个欲交换顶点。上图中欲交换的顶点是 空心点，交换后甩实心点表示。可以看到并不一定每次交换都可以使分割边的数 目减少。每一步的交换及其交换后的分割边、负载状况都将保存在一个队列中。 e d g e - g u t - 7 铆 e d g e - c u t 卅 伪 g d g e - c u t 硝 d f 辅g e - c u t - 2 图2 4f m 分割优化示例2 图2 4 给出了f m 算法的一个完整示例，在经过一共6 步的交换顶点以后， 得到了最优解。但是算法不会因此结束，而会进一步继续按照规则执行下去，直 到最后停止。而在图d 中表示的最优解被保存在了交换结果队列中，只需要在队 列中查找即可得到如图d 所示的最优解的分割情况。 f m 算法的时间复杂度被降到了0 ( p ) ，其中p 为电路线网端点( p e n ) 的数 目。可以看出对于大多数图来说，这是一个相当不错的改进。因为完全图的边数 才能达n o ( i v l 2 ) ，其中lvi 为顶点数，因此o ( p ) o ( 1 v 1 2 ) 。但是实际上，每次 交换完毕一个顶点以后，更新顶点增益权值，仍然需要o ( i v l ) ，所以实际上f m 算法仍然有相当大的改进空间。 同k l 算法一样，f m 算法同样要求进行多轮的优化工作。 18 18 超大规模集成电路划分算法研究炮八础侠朱，巩吧蚶咒u 刀异7 五w i 九 3 k r i s h n a m u r t h y - s a n c h i s 算法 针对上述缺点，k r i s h n a m u r t h y 将单元增益扩展为增益微量，或称为多级增 益( m u l t i l e v e lg a i n ) ，以考虑单元移动的潜在增益。其基本思想可以用图2 5 来 说明。图中a 、b 两个单元的直接增益都是l ，即将它们从集合i 中移到集合i i 中都会减少1 根割线网。但如先移动b 则只要再移动1 个单兀就可以再减少l 根 线网，而先移动a 则还要再移动4 个单元才能再减少1 根线网。这就意味着单元 a 、b 的潜在增益不同，且b 的潜在增益大子a 。k r i s h n a m u r t h y 采用多级增益来 反映它们的不同。对于图2 4 的电路而言，a 和b 的第一级增益( 也即实际的增 益) 都是l ，但第二级增益b 是1 ，a 却是o ，a 只有第四级增益才为1 ，因此b 的总增益大于a 。由于该算法在移动单元的同时考虑它对以后的移动造成的影响， 因此一般又称之为l a ( l o o k a h e a d ) 算法。 图2 5k s 算法的多级增益模型 l a 算法的结果的确较f m 算法有所改进，但算法引进了多级增益的同时也 带来了算法数据结构和时间复杂度的增加。多级增益算法的时间复杂度为o ( z p ) ， z 为增益向量的维数，p 为所有单元在超图中的度数( p 烈) 之和。在l a 算法的 基础上，s a n c h i s 将该算法进行了扩展以适用于多块划分的情况。s a n c h i s 还提出 了多块均一划分的思想，即同时对给定的k 个子电路进行优化处理，而不像以往 算法那样通过层次化的逐级二块划分产生多块划分。和l a 算法一样，s a n c h i s 算 法引入了更加复杂的数据结构，其算法时间复杂度也不理想，为o ( k l p ( 1 0 ak + v m a x l ) ) ，其中，为增益向量的维数，尸为所有单元在超图中的度数之和，k 为划 分块数，p m a x 为最大度数。 综上所述，组迁移算法因为其简单、易于实现的特点而得到广泛应用。但是 第二章超大规模集成电路划分算法概述1 9 它所具有的局限性又限制了它在超大规模集成电路划分中的应用：i n 算法和f m 算法简单、快速，但是没有考虑潜在增益；l a 算法考虑了多级增益，但是数据 结构过于复杂，在超大规模集成电路划分中实现困难。而且，这些算法应用于多 块划分的时候，由于每一步找到的仅是局部的最优解，无法使最终得到的解为全 局最优解，使划分的最终质量受到了限制。 2 3 2 多级层次划分算法 如同在第一章中中介绍过的一样，多级层次划分方法是通过粗化塌缩( g r a p h c o a r s e n i n gp h a s e ) 、初始划分( t n i t i a lp a r t i t i o np h a s e ) 和恢复优化( u n c o r s e n i n g r e f i n e m e n tp h a s e ) - - - 部分组合而成的。其中粗化塌缩算法主要是为了减少图的复 杂性，构建图的多级层次；初始划分是在将图粗化塌缩到一定程度以后，对被粗 化的图进行初次划分；恢复优化算法则是按照粗化塌缩层次一层一层将图恢复成 原状并且在恢复过程中逐层优化，针对一层展开的图的分割线附近的点或者整个 图中的点进行调整，以获得更优的结果。具体的算法思路如图2 6 【l9 】所示： 恢 复 初始划分 图2 6 多级二分法流程图 通常，多级划分算法要划分的图是有权图g o ( v o ，e o ) ，其划分过程中需要进行 2 0 超大规模集成电路划分算法研究 的三个步骤描述如下： ( 1 ) 粗化塌缩步骤： 将图g o ( v o ，e o ) 按照一定的方式转换成一系列的小图 g 1 ( v 1 ，e 1 ) ，g 2 ( v 2 ，e 2 ) ，g 3 ( v 3 ，e 3 ) ，g m ( v r m ，e m ) ，其中i v l i i v 2 i i v 3 i i v m l 。 ( 2 ) 初始划分步骤： 对图g m ( v r m ，e m ) 使用划分p m ，将图g m ( v r m ，e m ) 的顶点记v i 划分成大致相等 的两个部分。 ( 3 ) 恢复优化步骤： 将图g m ( v m ，e m ) 的划分p m 按照步骤p m 一1 ，p m 一2 ，p 1 ，p 0 的顺序将图 g m ，e m ) 恢复成图g o ( v 0 ，e o ) 。 下面将详细介绍前两个步骤具体所采用的方法，至于恢复优化步骤，将在下 一章中详述。 1 粗化塌缩步骤 在执行图的粗化塌缩步骤过程中，一系列的比原图拥有更少顶点和更少边的 图被建立起来。其中一些可能采用的塌缩的方法如图2 7 所示： “ 由图2 7 中描述的图粗化塌缩算法中我们可以看出来，塌缩算法实际上就是 将图的一个顶点集转换成一个顶点，当然，其中要求顶点集中的顶点组成的子图 是连通的。应当注意的是其中关于塌缩进行到下一步之后，顶点和边的权值应该 进行的更新，具体的变换准则如下： 1 其中涉及的顶点变换是将顶点集v r v t 转换成顶点v s ； 2 涉及边的变化是对于顶点i ，j ，如果e ( i ，j ) 不属于图g m ( v m ，e m ) ，且i 之 间有经过顶点集v 讥中的顶点的通路，则添加边e ( i ，j ) 到图g m + lv m + 1 ，e m + i ) a p ； 3 涉及到顶点权值变换是新顶点v s 的权值是顶点集合v v ，所有顶点权值的和； 顶点集合v v ，中的点被称为匹配顶点。 涉及到边权的变换是，新添加的边e ( i ，j ) 的边权是如下这些边的边权集合， 这些边满足：一个顶点是i 或者j ，另一个顶点在被塌缩的顶点集合v 0 中，当然， 如果顶点i 被另一个顶点集合v r v s 替代，则也一样变换成边的一个顶点在v r v s 中， 另一个在v v ，中即可，这样是说明当塌缩算法同时替代多个顶点集合或者顶点对时 使用的方式。 图2 7 的上半部分是初始图，未经过塌缩的图，其中粗线条表示的是欲塌缩 第二章超大规模集成电路划分算法概述2 1 边。下半部分是图经过一次塌缩后的状态图，正下标的e d g ew e i g h t 是指图的边 权和。 塌缩算法的考虑出发点多分为两类，一类是随机选取边或顶点；另一类是从 边权和顶点的连通情况出发的。 目前流行的塌缩算法中，均是以边作为塌缩单位的，也就是按照图2 7 中的 最左边的示意图所表示出来的算法。也即上述的四点变换事项中，欲塌缩顶点集 e d g ew e i g h t ：3 7 1 2 i 1 2 j1 2 j e d g e 雠i g h t ：3 0 a ：r a n d o mm a t c h i n g 1 2 i e d g ew e i g h t ：3 7 1 2 l 1 2 1 托l l l 睁w e i g h t ：2 1 b ：h e a v y - e d g em a t c h i n g 图2 7 两种图塌缩算法示例 中的元素个数为2 ，也就是一条边的两个顶点，此类算法称之为边塌缩算法。