VLSI布局结构表示研究进展

摘 要：超大规模集成电路技术的迅猛发展迫切需要高性能CAD工具——电子设计自动化软件工具的支持。布局是布图设计中一个极为重要的环节。目前，在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中，布局结果的好坏直接影响整个布图设计，因此如何高效地表示布局结构，从而提高布局质量成为布图设计中的一个国际上的研究热点。文中介绍并分析了当前国内外比较流行的布局结构的表示方法研究工作的进展情况。

关键词：VLSI；布局；结构表示；模拟退火

前 言

布图设计过程包括划分、布图规划、布局、布线、压缩等。随着制造工艺进入了深亚微米工艺阶段，电路的尺寸和复杂度迅速增加，布图规划和布局的地位显得比以往更加重要。(1)布图规划和布局是布图设计过程中的早期阶段，其完成质量的优劣对布线工作的顺利完成乃至最终芯片面积和性能的影响非常之大；(2)混合模式(MixeD Module Problem，MMP)的设计越来越多；(3)模拟电路和数模混合电路在芯片设计中的比例大幅度增加；(4)知识产权( IP)模块在VLSI设计中的应用增加；(5)多芯片模块(MCM)问题也日益受到重视。这些都为研究布图规划乃至布局工具提出了更高的要求。

布图规划技术的产生主要是由于BBL(Building Block Layout)模式分级设计的需要。BBL模式又称宏单元模式，是设计中最灵活的一种方法。在这种布局模式中，单元或模块可以有任意的形状和尺寸，可以安排在芯片的任意位置上而且没有固定的布线区域，因此具有更高的布局密度。

BBL布局的过程就是将一组模块或单元安置在芯片合适的位置上，使芯片的面积最小、模块间的连线最短并容易布通。其输入一般包括：(1)一个由模块或单元组成的集合A= { M₁，M₂，.，M_m}，其中每个模块是有固定边长的矩形或其他形状的硬模块，或是面积固定而长宽比可以变动的矩形软模块。每一模块M_i均有一个引线端的集合Pi= { p_i1，p_i2，.}，其中每个引线端pij都被安置在模块的边界上。对属于电源线网的引线端，会记录其所需的最大吸纳电流和允许的最低电压；( 2)网表N= { L₁，L₂，.}，其中每个线网L_i是一个引线端的集合。属于同一个线网的引线端将由布线工具把它们连结在一起；(3)由用户给定的各种约束条件，如芯片的长宽比或芯片的最大长(宽)度等几何方面的约束，关于引线端或压焊块的约束，以及一组路径或一组线网上的最大时间延迟即所谓时延的约束等。给定输入以后，需要确定所有模块的位置和方向，使得在满足所有约束条件的情况下，达到芯片面积的最小化。进入深亚微米乃至超深亚微米工艺阶段后，性能驱动或时延驱动的算法已经成为布图设计的热门课题。但由于约束或限制条件增多，设计过程中要考虑的因素也大大增加，因此其复杂程度是前所未有的，更有效的时延估计模型和时延驱动算法还有待于进一步的深入研究。其中布局结构的表示成为算法的核心部分，也成为EDA( ElecTronic Design Automation)工作者研究的热点课题。

布局结构

BBL布局结构通常有两种：一种是可二划分的结构( Slicing)；另一种是不可二划分的结构(Non-Slicing)。


图1　两种布局结构

Slicing结构是具有特殊性的布局结构。如果一个布局具有这种结构，那么可以通过递归地使用垂直或水平划分线，把芯片或划分芯片后得到的矩形划分为两个部分，直到划分芯片所得到的每个子区域中只包含一个模块，如图1a所示。这种结构可以方便地使用二叉树或波兰表达式的数据结构来表示，其布局解空间为O( m! 2^{3m- 3}/m^1.5)；但是这种结构不具有一般性，因此可能会浪费芯片的面积。

Non-SLicing
Non-Slicing结构包括所有可能出现的布局结构，是一种更为一般的布局结构，如图1b所示。使用Non-Slicing结构可以获得更高的布局密度，具有更大的优越性。

由于Slicing结构只能解决部分布局问题，它是Non-Slicing结构的子集，因此对Non-Slicing结构的布局结构表示研究成为热点。本文仅对Non-Slicing结构的布局结构表示的研究进展进行论述。

布局结构表示研究进展

求解Non-Slicing结构的布局问题，就是要在众多的解中寻找一个满足设计约束条件的、最优的解。随着电路规模的迅速增大，模块数越来越多，要在合理的时间内找到最优解是不可能的，只能找到次优解。因此如何表示解，如何降低冗余解，从而降低解空间，成为求解布局问题的热点。

布局表示就是用字母或数字代表各模块，并将其用一定的数据组织形式(如序列、树、图等)组织起来从而表达模块之间的几何位置关系。对应着一个模块布局的序列、树或图称为编码。从编码到模块布局的映射称为解码。所有可能的编码形式称为这个布局表示法的组合空间或解空间。在20世纪90年代中期以前，研究者提出了一些针对Non-Slicing布局问题的表示法，但这些表示法的效果都不够好。直到。995年SP和1996年BSG被提出后，Non-Slicing布局表示法的研究出现了一个高潮，许多新的表示法纷纷提出。如1999年的O-tree和SG；2000年的B-tree，CBL和Q-sequence；2001年的TCG和TwinBinary Tree；2002年的TCG-S；最近仍有一些新的表示法推出。

序列对
1995年，Murata等提出了序列对( SequencePair，SP)布局表示法。

SP是指由所有模块的2个排列构成的一个布局。一个布局可以通过从右上角至左下角的一组轨迹(称为正轨迹)定出模块的一个排列次序ecadf b，如图2a所示；同时通过从左上角至右下角的一组轨迹( 称为负轨迹)定出模块的另一个排列次序f cbeaD，如图2b所示。这两组排列就构成了一个SP(Γ₊，Γ_- )= { ecadf b，f cbead}。图2所示为图1b的SP表示。

图2　布局的SP表示

给定一个SP，可以惟一地确定模块之间的水平约束图与垂直约束图，即确定了一个布局。对m个模块的布局问题，所有SP的集合构成布局问题的解空间，共含有( m!)²个SP，每个SP都可以在O( m²)时间内对应到一个布局，其中至少有一个SP对应最优的布局。从SP的表示，根据组合数学的知识可知，不同的SP可以得到同一个布局(通过旋转、映射等)。因此，SP表示的解空间有很大的冗余度。尽管有如此缺陷，但它为解决Non-Slicing结构的布局问题提供了有力的手段。由于SP表示布局结构直观、简单，并且表现出很多模块间的几何位置关系，因此通过对SP的分析，Tang等提出了一些改进的算法，其解码时间复杂度为O( mlglgm)。

我们课题组对SP的结构表示进行了研究，分析了一些等价的SP，从而使解空间降低，并将其用于解决带软模块的布局问题；还将禁忌算法用于求解基于SP布局问题，取得了一些研究成果。2001年，Lin等提出了TCG( Transitive Closure Graph)表示法。TCG是一个用两个约束图来表示布局的表示法。给定一个布局，并对各个模块编号，根据模块相对的上下左右位置关系画出水平和垂直约束图，就得到了该布局的TCG表示。反过来，给定一个TCG，可以直接在TCG水平约束图和垂直约束图基础上，利用图论中的最长路径算法去计算各个模块的左下角的坐标，从而得到一个布局。

应该指出的是，TCG与SP可以相互转化，且与SP一样，给定一个TCG表示，可以得到一个惟一的布局。

TCG克服了SP的缺点，它限定了那些没有接触的、呈对角模式的模块之间的位置关系，使它们要么为垂直关系，要么为水平关系。给定一个布局，TCG不会像SP那样得到多个表示，而只会得到一个TCG表示。TCG也是有冗余的。对m个模块的布局问题，TCG的解空间为( m!)²，解码时间为O( m²)。与SP相比，TCG更加直观，符合人的直觉思维。在处理有约束布局问题(如边界约束和预放置约束等)时比较方便。但TCG使用图来表示时与SP用序列表示相比，会耗用更多的存储空间，并且其扰动操作也十分复杂，不利于算法的实现。

2002年，Lin等对TCG做了改进，提出TCG-S。即在保留TCG原来两个约束图的基础上，又引入SP的Γ_- ，从而提高算法的效率，减少计算时间。文献中证明，TCG-S的解码时间复杂度为O( mlgm)。但该算法同样存在存储空间过多和对图的操作比较复杂的问题。

变形网格

图3　BSG结构

1996年，Nakatake等提出了变形网格(Bounded-Sliceline-GriD，BSG)表示法。BSG给出了模块之间的位置关系。一个BSG是由一些水平或垂直的线段组成，这些线段就称为BSG-线段。BSG-线段将平面划分成为一个个的区域，称为BSG-区域。每一个BSG-区域都由两个相邻的、上下错开一半的、垂直的BSG-线段和两个相邻的、前后错开一半的、水平的BSG-线段相围而成，如图3所示。BSG区域可分为两类：一类是形状像p的，如图3中的区域A；另一类的形状接近于q，如图3中的区域B。一个由P行和q列BSG-区域组成的BSG称为P×q的BSG，记为BSG_P×q，如图4所示)。对于任意一对垂直的BSG-线段，它们的左右关系可以通过水平BSG约束图和垂直BSG约束图来确定。

图4　BSGP×q

在布局过程中，先将模块安置在BSG-区域内，然后根据所放置模块的长和宽计算出水平和垂直BSG约束图每一边的权值。计算出的水平和垂直方向的最长路径即是芯片的宽和高。

对于m个模块的BBL布局问题，只要P×q≥m，就可以将模块安置在BSG_P×q上，但是，只有当P≥m且q≥m时，才能保证BSG_P×q的所有安置包含最优的布局。对于BSG_P×q而言，计算一个布局的时间复杂度为O( P×q)。为了保证最优布局，其计算的复杂度同样为O( m²)。m×m的BSG的解空间为C( m²，m)，这个数目远远大于( m! )²。正是由于m×m的BSG结构的解空间过于庞大，一般在实际中选用适当的P，q在BSG_P×q上进行处理。

由于BSG结构的特点，它比较适合处理区域布线问题，因此有了同时解决布局和总体布线问题的新思路。

通过对BSGP×q结构的分析发现，其可供搜索范围有限，改变原点的安排位置将使得搜索的空间增大。

阶梯网格

图5　阶梯状网格

1999年，阶梯网格( Stairway GriD，SG)由黄钢提出。SG是指如图5所示的阶梯状网格，将排列好的模块从左下至右上依次放置在最中心的网格上。SG在给出模块的排列顺序的同时，还给出一个长度为m- 1的0，1序列L1，这个0，1序列给出了从第二个模块开始的每个模块与其前一个模块的上下或左右关系。0表明该模块应放置在其前一个模块之上，而1表明该模块放置在其前一个模块之右。如图6所示的阶梯形状的模块编码为L1= 011011

图6　由L1决定的相邻模块

模块的排列S和L₁仅仅决定了模块与其排列中前一个模块的关系，并未给出与其他模块之间的关系。从第三个模块开始，若一个模块a与其前一个模块b是水平关系，则模块a与前面的、排在b左边的模块依次进行比较，直到确定某个模块(或没有模块)是排在a左边的模块为止；若一个模块a与其前一个模块b是垂直关系，则模块a与前面的、排在b下面的模块依次进行比较，直到确定某个模块(或没有模块)是排在a下面的模块为止。用L2决定从第三个模块开始的每个模块与排在前一个模块之前的有关模块之间的关系，其长度为2m- 6的0，1序列。

SG结构是由一个m个模块的排列S和一个长度为3m- 7的0，1序列L组成的，记为( S，L)。0，1序列L的前m- 1个序列记为L₁，后面的序列记为L₂，显然，阶梯网格结构的解空间的数目为O( m! 2^{3m- 7})。它的解空间远比序列对小，两者之比约为O( m^1/2( m/8e)^m)。其时间复杂性为O( m)。该结构表示法已被用于解决带软模块、带预置模块等具有约束条件的布局中。

O-tree
1999年Guo等提出O-Tree布局表示法。O-Tree是一带根的有向树，它的根是一个虚根，其各子树T₁，.，T_m在树中的顺序很重要，采用深度优先搜索(DepthFirsTSearch，DFS)，因此T₁，.，T_m的顺序决定了采用DFS遍历树的顺序。

O-Tree的编码用二元组( T，π)表示。对m个模块的布局，需用长度为2m的二进制串构成T，π表示m个模块的一种排列。在T中，“0”表示沿树枝下降，“1”表示沿树枝上升。图7所示为7个节点的O-Tree(不包括根节点)。

图7　7个节点的O-tree

　　根据图7，可以得到该树的二元组( T，π)=(00110100011011，adbcegf )，编码采用从左到右DFS遍历。当搜索完一个分支，回溯时遇到分支节点就转向另一分支搜索，直到所有节点均被访问，最后回到根节点，编码结束。

在O-Tree中各分支表示模块间的垂直关系，分支内表示模块间的水平关系。图8所示为由二元组编码得到的布局。

图8　O-tree表示的布局

对于m个模块的BBL布局问题，每一节点的标号需要lgm位表示，因此共需要m(2+lgm)位存储二元组( T，π)。其中，T需要2m位，π需要mlgm位。O-Tree的解空间是O( m! 2^{2m- 2}/m^1.5)，计算复杂度为O( m)。

O-Tree只能表示一种具有LB(LefTBottom)压缩特性的特殊布局结构，每次转换需要对模块进行向左和向下的额外的压缩操作。

角模块序列
2000年洪先龙等首先提出了Mosaic布局结构，以及可以用于解决Mosaic布局问题的角模块序列(Corner Block LisT，CBL)表示法。

如果某模块位于一个布局的最右上角区域，则称该模块为该布局的角模块。CBL是一个三元组( S，L，T)，其中，S是m个模块构成的序列，L是S中所对应的模块的T-连接方向。T-连接由该布局的角模块的左边和下边所在的划分线组成。如果该T-连接可以由T型逆时针旋转90°得到，则称该T-连接的方向为垂直方向；如果该T-连接可以由T型逆时针旋转180°得到，则称该T-连接的方向为水平方向。如果角模块为水平方向，移动它的左边界到芯片的右边框删除该角模块，并拖动其左边界的牵连T-连接到右边框；如果角模块为垂直方向，移动它的下边界到芯片的上边框删除该角模块，并拖动其下边界的牵连T-连接到上边框。牵连T-连接的信息用二进制串TI来记录。二进制串T_i由连续的。和一个表示结束的0组成，连续。的个数表示牵连T-连接的个数。

对于一个布局，可以通过不断地删除其角模块得到它的CBL；反之，根据其CBL可以得到其布局。图9所示为D模块的删除操作。插入操作与删除操作相反。图10所示为一个Non-Slicing结构以及相应的CBL。

如果有m个模块，则角模块序列S的长度是m，L的长度是m- 1，T序列长度为2m- 3。CBL的总存储量不超过m(3+[lgm])位。CBL的解空间为O( m!2^{3m- 3}/m^1.5)，其计算复杂性为O( m)。

由于CBL起初只能解决无空模块的Mosaic布局问题，具有局限性，因此后来我们课题组又对其进行了改进，提出了一种增强型ECBL( ExtendeDCornerBlock List)，并对ECBL做了大量的研究，取得了一些成果。

Mosaic布局的提出引起了广大研究者的兴趣，有不少研究者在Mosaic布局上开展工作。2000年，SakanushI等提出了一个针对Mosaic布局的、类似于CBL的表示法Q-sequence。2001年，Yao等分析了Mosaic布局的组合情况，指出Mosaic布局构型与BaxterNumber的关系，并在此基础上提出了一个与Mosaic布局一一对应的表示法TwinBinary Tree。

B-tree
2000年，Chang等提出B-tree布局表示法。

B-tree实际上是B-Tree的变形，也是一种二叉树。它的根不像O-Tree树是一个虚根，而是对应布局的左下角模块。从根模块开始，递归地构造其左子树和右子树。在根模块右边且与其相邻的模块在左分支上，在根模块上边且与其相邻的模块在右分支上，直到所有模块都表示在树上为止，即可得到一棵B-tree。图11所示为由12个模块组成的一个布局，图12所示为图11的B-tree结构。


　　反之，由B-tree可以惟一地得到一个布局。它的这种“一对一”的关系阻止了它对疑似解的搜索。B-tree反映了模块间的“右”和“上”关系，采用二叉树表示非常简单。它的解空间与O-tree的解空间一样，是O( m!2^{2m- 2}/m^1.5)，而计算复杂度为O(1)。B-tree同O-Tree一样是基于树结构的一种表示方法，它在研究带几何约束的布局问题中得到研究。从B-tree的特点来看，它应该有较好的研究和应用前景。

各种布局表示法研究成果的比较
上述布局结构表示方法的共同特点是可以解决Non-Slicing布局问题，它们的差异表现在解空间的大小、编码的效率、编码与布局之间的转换时间等。它们都有各自的优缺点，因而被研究人员广泛使用。布局结构的表示对提高布局质量起着重要作用，这就要求我们去研究更好的表示方法，最大限度地降低解空间的冗余度，使在求解过程中尽量减少对同一解的搜索。

除了上面介绍的布局表示法之外，研究人员最近又提出了角序列(Corner Sequence，CS)和单序列( Single Sequence，SS)表示法。CS实际上是CBL的一个变种；而SS只是在理论上对布局中各模块的关系进行了理论分析，并没有用于实际。表。所示为一些表示法用标准Benchmark 测试例子进行实验的结果(除BSG外)，由于这些结果是在不同的软硬件环境下进行的，并且优化目标为面积，因此只能作为参考。表。中，面积单位为mm²，时间单位为s。

表1　不同表示法研究结果的比较

　　从表1中可以看到，在解的质量和时间上没有一种表示法达到统一，即在解的质量和运算时间上都优于其他表示法，这是由布局问题的复杂性决定的。目前，SP表示法由于具有表示简洁、直观和良好的几何关系等特点，在求解布局相关问题上得到广泛的研究和应用。

总结和今后的工作

不同的表示法有不同的解空间和不同的冗余度，它们的解码操作和扰动操作的效率也不一样，所以表示法有了优劣之分。我们认为衡量一个表示法优劣的条件有6个：(1)解空间是有限的；(2)表示法的解空间包括最优解；(3)解码操作不能太复杂，最好能在线性时间内完成；(4)对编码的扰动操作不能太复杂；(5)表示法的冗余度要小；(6)存储空间复杂度要小。

条件(1)，(2)保证了搜索过程有找到最优解的可能。上述表示法均满足条件(1)。而对条件(2)则需要注意：最优解因问题而不同。有些表示法能包含某个目标下的最优解，而在另一个目标下却不一定。典型的如O-Tree和B-tree，它们都是将模块向下和向左尽可能地压缩以得到最小面积，其优点是减小了解空间的大小，代价是它们不能表示所有的布局方式。在以布局面积最小为目标的情况下，它们的解空间能包括最优解，但如果同时考虑布线效果的话，则它们不一定包括最优解。

条件(3)～ (5)一起影响了表示法的时间复杂度。条件(3)表明了从编码到布局的时间复杂度。显而易见，如果该操作太复杂，则一定会耗费大量计算时间。而条件(4)表明了从一个解变换为另一个解的时间复杂度，其中有两种情况值得说明：(1)有些表示法不能保证任意一个解都能映射到一个可实现的布局；(2)有些表示法的任意一个解都能对应一个可实现的布局，但其扰动的操作太复杂，如TCG和TCG-S，因为它们都是基于图的表示法，所以要从一个图变换为另一个图会有较复杂的操作。条件(5)是由于冗余会导致无效的搜索步骤，增加计算量。布局问题已被证明为NP问题，是典型的优化问题。对于这类问题，传统的确定性的优化方法在布局规模较大时已无能为力了，这就必须采用非确定性优化算法，在布局问题中广泛应用的、最典型的是模拟退火算法。几乎上面介绍的布局结构表示都是用模拟退火算法来求解的。

随着智能优化算法的发展，涌现出像遗传算法、神经网络、蚁群算法和禁忌算法等方法，它们被用于求解NP问题，如TSP( Traveling Salesman Problem)问题，其求解质量和效率比以往方法有很大提高。因此人们纷纷将它们用于求解其他NP问题。我们也做了这方面的研究，如基于序列对的布局结构表示，采用禁忌算法求解；将蚁群算法、遗传算法等用于布线，都取得了较好的结果，但解的稳定性是一个值得研究的问题。

在研究布局结构的表示时，结合先进的智能优化算法，以解决更大规模的布局问题，这将是我们今后的研究方向。