zzwoo@126.com
谪要：本文提出的算法是Kernighan最优通道布线算法[2]的一个推广，它使算法的适用范围由通常的矩形通道扩充到具有多段平行边界的通道，同时能保证结果最优。
0.引 言
通道布线算法是LSI和PCB自动设计中广泛应用的算法。目前已有的通道布线算法仅适用于边界为两条平行直线的矩形通道，如果边界不是一对平行直线，则已有的各种算法就不都适用，即使勉强用上去，也不能得到理想结果。本文提出的布线算法则可适用于边界形状为多段平行的通道（图１），且能保证结果为最优。
算法基础仍为分支限界法，但因边界条件的影响，分支规则与求界方法都必须在[2]，[4]，[5]所用算法基础上作很多变动。以下先讨论边界形状的改变对布线过程的影响，以及为解决遇到的各种困难所采取的措施，当对算法的主要环节有了认识后再给出算法的整体说明及基本框图，最后介绍算法的应用。
1.通道模型和布线目标
我们把边界由多段平行线段组成的通道简称为“崎岖”通道。图1就是一个这样的通道，其中边界上的黑点代表引线端（pin）的位置。崎岖通道的布线问题除了需要给出用来说明引线端间怎样互连的线网表（Net list）外，还必须给出一组能完整刻划边界形状的数据。这些数据可以这样得到：将通道最靠近中心线的边界线段延长直到两端（见图1 蓝线L1、L2），这—对平行线就将通道划分成三个区：上边界区、下边界区以及中间的等宽区。通道边界的形状就可由上下边界区各段的长度和宽度来刻划。如图1通道的上边界区由三段组成，它们自左至右长度分别为（5,5,4）,宽为（2,0,1）。下边界区也由三个段组成，它们的长分别为（2,6,6），而宽分别为（0,3,1）。这里段的长度用段中所含引线端数目表示，宽则用占有的行（track）数来表示。崎岖通道作为许多实际问题的抽象模型，其边界形状应是不变的，但通常允许两个边界相互分离或靠拢，使它中间的等宽区能够根据布线的实际需要确定宽度，以解决100％的布线率。最优岖通通道布线算法的任务是：在任何边界形状下，对任何无约束环的线网集，采用双层直干布线格式，产生行数最少的布线。
图1 崎岖通道模型
图2就是一个崎岖通道布线的一个实际例子。这一布线已为最优，因为通道在第9列（x=9）处已达最高线网密度5，每一个行中都布了线网，无法再使等宽区行数进一步减少。
图2 崎岖通道最优布线例子
2.启发式算法
下面我们来讨论怎样利用一般的通道布线算法来解决崎岖通道的布线问题，并考察是否能达到上述意义下的最优目标，也就是使布线所用的 track数目最少？
因边界形状不变，要减少布线占有的行数，就必须减少中间等宽区占用的行数。为此，因尽可能多地将线网布于上、下边界区，使留在中间等宽区布的线网最少。这说明，崎岖通道的布线方式应不同于从上到下或从下到上的布线方式，必须先布两边，再布中间。
以下介绍的方法，就是将整个通道划分成一些等宽的区域，然后按照由两边向中间的次序，利用一般的矩形通道的布线算法，对这些等宽的矩形区域进行布线。区域的划分以及布线的次序可以通过图3来说明。
图3中step0代表崎岖通道原始布线区域，其中尚未布下任何线网。 step1-step5 则已分别按上面所规定的布线次序一个一个地对所有矩形区域进行了布线 (填坑)。
对每—坑内的布线方法都是一样的：从未布线网中分划出此坑的所有可布线网 (一个左端为l、右端为r的线网a[l,r]在某坑[L,R]内可布，当且尽当[l,r]包含于[L,R]，并且所有约束a的线网或者已布或者也整个属于[L,R])，应用一般的通道布线算法对这些线网进行布线，布线结果有二种可能：(1)所有线网布完而坑未填满或刚好填满；(2)线网未完，坑已填满。
图 3 填坑算法执行过程
在第一种情况下，对此坑的布线就结束，继续下—坑的布线；在第(2)种情况下，则应根据应用算法而区别，如采用左边算法[1]、双边算法或倒限界部分优化的分支限界法[5]，则也无条件结束，把其余未布线网留到其后的区域去布；若采用Kernigan [2]、 Wada [4] 、各种 FOCR [5]等最优算法，则必须继续布下去，直到整个算法过程结束，再取其前面几行，把超出坑的容量的那儿行拆掉，留到其后的区域去布。
利用最优通道布线算法来填坑，可以保证留到其他区域去布的线网数最少，因而，一般地说，可以得到较好的最终结果，但是，这不能保证一定能得到最优解，有时甚至可能比使用非最优算法来布的结果还要差，以下图 4（A）就可以证明这一点。
图 4(B) 用左边算法填坑，结果为最优
这一崎岖通道只有上边界区一个坑（3到8列），深度为1。其可布线网为 ③④和⑤，当用最优算法在此区域布线时，线网④独占一行，③⑤合用一行，共 2行。但因坑的深度为1，故第2行的③⑤被拆去，放到等宽区与①②一起布。由于③垂直约束①和②，所以必须先布③，而⑤与③可共用一行；因①受③垂直约束，必须布在③下；②受①约束，又必须布在①下，如图4(A)所示，一共需要4行。相反，应用左边算法来布线，因③④⑤中③为最左线网，故③先布，这样就占用了整个坑（只有1行），把④⑤留到下面的中间区去布；因①④无垂直约束也未水平重叠，故可共用一行；同理②⑤也可同用一行。这样整个只用３行，获得了如图4(B)所示的最优结果（因 x=1,2 处均达到最大线网密度）。
由上例可知，要保证获得最优解，必须考察所有线网在整个通道内的所有可行布线。为此可利用各种最优布线算法来实现，如 [2]、[4]、[5]。这些算法的共同点是利用分支限界技术。但为了将它们应用到崎岖通道，需要解决一系列的共同问题。为了简单，下面仅就Kernighan的基本算法[2]来说明，看需要作怎样的调整才能用于崎岖通道布线。
3．崎岖通道最优算法－分支规则
分支规则由行的选择规则和行中所布线网选择规则确定。本算法采用的行的选择规则如下：先选择下边边界区最下边的行，由下向上（如图１中的 t1,t2,t3），一行行地布线，直到全部行用完或其中已无线网可用为止；然后，即转到上边界区，由上而下地选用各行，直到全部行用完或行中无可布线网为止，接着再由上而下地在中间等宽区布线，直到把所有线网布完，需要几行就用几行。
每一行中仍用左边算法的布线规则，由左向右，每次选择最左合法线网进行布线。但要说明，线网合法（legal）的含义已经和原来的不同：
(1) 在矩形通道布线时，一个未布线网只需考虑它与其他线网的垂直水平关系就可确定它的合法性，即在同一行中，只要最后所布线网与它不水平重叠，而任何未布的线网都不垂直约束它，则此线网就为合法，可以作为候选线网在该行上接着布线。但在崎岖通道中，为了确定一个未布线网是否合法，还必须同时考虑边界与此线网的垂直和水平关系。在本文后面我们将会说明，可以引进虚线网的概念，把边界的约束看成和线网之间相同的约束。
(2) 垂直约束概念在矩形通道布线时只有一种形式，不是由上而下就是由下而上，不会同时出现。但在崎岖通道布线时则有两种形式，当在上边界区和等宽区布线时必须采用从上到下的约束，而在下边界区布线时则必须采用从下到上的约束。如果仍然采用从上到下的那种约束图，则在由下而上布线时，应理解为下辈约束上辈，没有下辈或下辈已全布去的线网才为合法，例如对于图５，一开始 ③⑤⑥为合法（未考虑边界约束），布去③后为④合法，布去③⑤后，②合法，等。如果是从 上到下布线，则为一开始 ④①⑥为合法，布去①后为②合法，布去②后，⑤合法，再布④后③合法。
图5 统一的垂直约束图
4. 崎岖通道最优算法－分zone法则
将通道划分成 zone 可使求解紧凑，也有别的作用（见 [5] ）。一个 zone 就是通道的一个区间，在此区间中所有线网相互重叠，但将区间扩充后，就会出现不重叠的线网。具有共同 zone 的线网不能布于同一行。另一方面，任一线网不布（拆去）时，与此线网起于同一 zone 的线网都可代替它，由此 zone 开始布线。这些性质使一般通道布线时所有水平重叠关系都可以用 zone 来表示，不必详细考察列(coloum)，从而使问题规模缩小，有利于提高速度。
对于崎岖通道，如仅仅根据线网本身的水平重叠关系来分 zone ，就会破坏上述性质。如图 6 中，根据线网本身的水平重叠关系，整个通道划分为 3 个 zone ，其中第 3,4,5 列归为同一个 zone 中。但这样当其中的线网⑤不布时，与⑤起于相同 zone 的线网③却无法知道是否能代替⑤布于该 zone ，必须进一步检查线网与边界的精确列坐标后才能确定。这就给需要不断布线 - 拆线 - 布线的分支限界过程带来极大不便。为了克服这一点，我们设想在通道上下边界区的不可布线部分（图 6 浅灰色区域）被某些固定的线网占据着，这些线网（我们称为虚线网，见图 7 ）与实际的线网合在一起，再按原来的定义划分 zone 。
采用这样的分 zone 法， zone 的数目将会增加（增加的 zone 数不会超过通道段数的总和），获得的代价则是分支限界过程时无需再考察列坐标，有利于提高速度；同时，引入虚线网来代替不可布线部分后，不再需要考虑边界问题，边界区已经变成了等宽区，从而就有可能使用一般的通道布线算法来进行布线。
5．崎岖通道最优算法－求界法则
本算法应用了两种参数作为估算布线所需要的行数。这就是通道密度和动态界限。
通道在某 zone 的密度，就是通过该 zone 或以该 zone 为起点或终点的线网总数。按此定义，图 6 所示通道在 1-5 个 zone 中的密度依次为 (2,3,4,4,3) ，最大为 4 。但这样计算出来的通道密度用作崎岖通道布线需要的行数的下界很不正确，因为没有考虑边界对它的影响。实际上，即使一个线网也不布，上下边界区中的任何一行都是无法节省掉的。
为了得到通道密度的合理数值，我们仍可借助于 虚线网 的概念，即把 虚线网 和实际线网合在一起来统计 zone 中的线网总数。照此办法，图6的通道密度就成为（ 5,4,4,5,5 ） , 最大为5 ，显然已经完全精确了。
以上是对整个线网集的通道密度估算。在布线过程中，若已布去了 k 行，则在计算剩余集合的密度时，与此 k 行相应的虚线网也就不应计算在内。例如在图7中，当由下而上布线时，把线网4布在倒数第一行后，则剩余集合的密度估算就不再包括虚线网4和5，这样5个 zone 的密度就分别变成为（ 4,3,3,4,3 ）了。
下面再来讨论动态界限的计算。动态界限 以及和它联立递归产生的 静态界限 是建立在水平和垂直双重约束关系之上的复杂概念。它在估算布线需要行数时比线网密度具有更为精确的值。它的计算在文献 [2] 和 [5] 都有介绍，但在 [2]中 的描述不完整，无法用它来确切计算。 [5] 则用联立递归方式给出了 动态界限 和 静态界限 的确切定义，可以用它来一步一步地计算任何整个线网集或部分线网集的 动态 和 静态界限。
当用于崎岖通道布线时， 动态和静态界限 的计算需要考虑边界的影响和约束方向的改变，例如对于图７所示的线网集，当考虑从上到下的约束时，就应把原有约束关系图8( A) 改成为图8( B) 的形式，这里，位于通道上边界区的虚线网①② 约束着与它有 zone 重叠的实际线网 ②③⑥, 而位于下边界区的虚线网③ 和⑤ 则被它们上面的实际线网 ①②③⑥ 约束。
(A)...........................................................(B)
图8引入虚线网(右)来重新确定垂直约束关系
在进行布线时，由于 虚线网的加入，就把崎岖通道的上下边界区变成和等宽区完全一样的矩形区域，从而可以对虚线网和实际线网一起进行了分支求界。当一旦遇到虚线网时，由于它们的位置是固定的，实际不存在布线问题，但必须和真线网一样，去占领对应的zone，以防止其它线网布到上面去。同时，它们也和真线网一样，在确定其他线网的布线次序时就和实线网一样起作用，即，受到虚线网约束的线网也是不可布的，而一旦布掉了一个虚线网后，受它直接约束的线网就可以在下一行的布线中成为候选者。虚线网所产生的约束关系由布线进程来确定其是否存在。
6．崎岖通道最优算法：完整框图
以下是崎岖通道布线算法的框图，它是在快速最优通道布线算法（FOCR2）基础上改变得到，其中主要符号意义如下，没有提到的请参看参考文献5：《快速最优通道布线算法》：
DB0- 动态界限初值，即所有线网（包括实与虚）的动态界限。（DB0的计算需要与静态界限初值SB0的计算联立递归完成）； CD0- 通道密度初值； Tr - 通道内用于布线的行号，见图1左边的t； IV -通道上下边界区的段落号；Z - 线网水平重叠区（zone）；
n - 线网编号；F- 布线算法标志，F=1为快速布线，不保证最优，F=0不用快速布线，保证最优。缺省时F值为0；R - 布线标记，R=1为布线，0为 拆线（新结果不如此前最优结果时要拆线）；S - 已布线网总数；DB - 当前剩余线网的动态界限；Stk[] - 保存未能布下的线网堆栈；TRK1[] - 当前被布线网所在行；TRK[]- 当前已有最优布线结果。每次布完所有线网，如果优于此前结果，则就用TRK1[]数组更新TRK[]数组；当各种方式都考察完时，TRK[i],i=1 to N，就是整个布线结果。
图9 崎岖通道最优布线算法框图
本框图是根据实际程序画出来的（或者说，程序是按照此框图编写的），有些地方已相当详细，但没有给出DB、SB、CD（包括它们的初值DB0、SB0、CD0）的计算，也没有说明如何分zone、如何描述线网或描述上下边界区形状的数据结构等，所以仍非完整框图。要详细了解这些参数的计算请参看所列参考书。
7．崎岖通道最优算法：布线实例
以下是2个崎岖通道应用最优布线算法的实际结果。
图10A 崎岖通道布线， 实例１。此布线没有一处达到通道密度14，但为最优
图10 B 崎岖通道布线，实例２。此布线没有一处达到通道密度19，但为最优
8．崎岖通道最优布线：用途
通道布线算法推广到崎岖通道后，其应用范围就得到很多扩大，例如下面图11中的4种场合原来都无法最优布线，而推广后就可以进行最优布线了：
(１). LSI任意元胞设计时的各个通道的布线，见图11（A）；
(２). LSI多元胞设计时两个垂直通道的布线，见图11（B）；
(３). LSI多元胞设计或母片式设计时采用少数非标准单元时各相关通道的布线，见图11（C）（D）；
(４). 采用不同尺寸的集成电路的印刷电路板的通道布线，同图11（D）。
（A） （B） （C） （D）
图11 崎岖通道最优布线应用例子
参 考 文 献
5 Z.Z.Wu ,快速最优通道布线算法 (设计自动化会议,1982年昆明）