标准单元总体布线时障碍下的直角Steiner树方法

摘要

标准单元总体布线时障碍下的直角Steiner树方法属于集成电路计算机辅助设计技术领域，其特征在于：它首先将所有障碍视为不存在，求得待连线网的端点集在无障碍下的Steiner树即预－Steiner树；然后，使预－Steiner树中在障碍内部的树边绕过障碍，生成有障碍下的Steiner树；在生成有障碍Steiner树的过程中，根据图的拓扑结构，进行适当的预处理和后期处理，以在考虑时间效率下优化线长的优化问题。它解决了在待连线网有多个端点情况时标准单元总体布线时有障碍下优化了线长和时间效率的直角Steiner树构造方法。

说明书

技术领域

标准单元总体布线时障碍下的直角Steiner树方法属于集成电路计算机辅助设计即ICCAD技术领域，尤其涉及标准单元(SC)总体布线设计领域。

背景技术

在集成电路(IC)设计中，物理设计是IC设计过程中主要的一环，也是其中最耗时的一步。与物理设计相关的计算机辅助设计技术称为布图设计。在布图设计中，总体布线是一个极为重要的环节，它的结果对最后详细布线的成功与否和芯片的性能影响极大。

集成电路的设计规模目前正由超大规模(VLSI)、甚大规模(ULSI)向G大规模(GSI)方向发展，并出现了系统级芯片(SOC)的设计概念。最小直角Steiner树(rectilinear Steinerminimal tree，RSMT)构造方法的研究是VLSI/ULSI/GSI/SOC布图设计、尤其是布线研究中的一个重要问题。而在实际布线过程中，由于宏模块、IP模块以及预布线等都将成为障碍，使得考虑障碍的RSMT方法成为一个非常值得研究的问题。然而到目前为止，人们的研究多集中于无障碍的情况，相比之下对于带障碍的RSMT方法的研究还相对空白，有必要进行深入的研究。针对总体布线的实际应用，考虑障碍情况进行Steiner树构造方法的研究是总体布线中的关键问题之一，具有很大的实际意义。

在已报导和所能查阅到的国内外相关研究中，关于“考虑障碍的直角Steiner树构造方法”的研究情况可列举、分析、总结如下：

对于线网仅含有两个端点这种比较简单的情况，人们做了不少研究，而且其中已经有一些比较成熟的方法。

Lee于1961年提出了迷宫方法([C.Y.Lee，An Algorithm for Connections and ItsApplications，IRE Trans.On Electronic Computers，1961，346-365.])，可用于求解障碍下的两端线网布线中两端点之间的最短路径。但由于该方法在整个搜索中总是对称的，这增加了搜索所需的时间和存储空间。1978年，Soukup提出了一个带有固定意义的非对称搜索方法([J.Soukup，Fast Maze Router，Proc.Of 15^th Design Automation Conference，1978，100-102.])，提高了搜索效率。但该方法不能保证找到最优解。另一个改进的方法是Hadlock于1977年提出的，称为Hadlock最小迂回方法([Hadlock，A Shortest Path Algorithm forGrid Graphs，Networks，1977.7，323-334.])。上述两种改进的迷宫方法的时间与空间复杂度均为0(hw)，其中h和w是网格的数目。迷宫方法的最大缺点是要搜索较大的布图空间，所以要花费较大的时间和存储空间。它的优点是能在任何有解的情况下保证找到一个解。

为了克服迷宫方法的缺点，Hightower于1969年([D.w.Hightower，A solution to theLine Routing Problem on the Continuous Plane，Proc.Of the 6^th Design AutomationWorkshop，1969，1-24.])，Mikami和Tabuchi于1968年([Mikami K.and Tabuchi K.，AComputer Program for Optimal Routing of Printed Circuit Connectors，IFIPS Proc.，1968，H47，1475-1478])分别提出了线搜索方法。它的计算时间和空间复杂度均为0(L)，其中L为该方法所产生的线数。

另外一种比较有代表性方法的是文献[J.M.Ho，M.Sarrafzadeh and A.Suzuki，“An ExactAlgorithm For Single-Later Wire-Length Minimization”，Proceedings of IEEEInternational Conference of Computer Aided Design，pp.424-427，1990.]提出的单层详细布线中的最小化两端线网的方法。它使用一种称为“同伦变换(homotopictransformation)”的方法对线网进行优化变换，所谓的“同伦”就是不改变线网的整体布局。作者提出：当路径中不存在“空U”(三段连续的线段构成的形如字母U的线路称为一个“U”，“空U”即指在U形线路的中间那段向U内部仍有上移空间)时，便可断定为最短路径。这个方法只适用于两端线网的处理，它能得到最优路径。

三篇文献：[周智，有障碍的Manhattan空间中的最小Steiner树问题(硕士学位论文)。合肥：中国科学技术大学，1998.]、[周智，陈国良，顾钧。用0(tlogt)的连接图求有障碍时的最短路径。计算机学报，1999，22(5)：519-524.]和[周智，蒋承东，黄刘生，顾钧，“用Θ(t)的广义连接图求有障碍时的最短路径”，软件学报，2003，14(2)：pp.166-174.]中引入了广义连接图G_G，其平均复杂度为Θ(t)，其中t为障碍的极边数(多边形相邻的三条边e₁(x₁，x₂)，e₂(x₂，x₃)，e₃(x₃，x₄)，若和正好反向，则e₂即为极边)。G_G在复杂度上有一定的优势。在这些文献中提出了利用G_G来构造两端线网的最小Steiner树，另外也提出G_G可以用来构造多端线网，但是他们还没有具体实现。

相比之下，人们针对多端点线网提出的考虑障碍的直角Steiner树方法还相对很少。与两端点线网相比，多端点情况要复杂得多。尤其是在有障碍的情况下，很难在人们可以接受的时间内求得最优解。本专利申请所涉及的方法就是针对多端点线网的一种启发式方法，其复杂度为0(mn)，其中m和n分别为障碍个数和线网端点数。以下将列举目前已有的考虑障碍的多端点线网的方法，并与本专利申请所涉及的方法进行比较，以指出他们之间的区别。

文献[Chen Desheng，Sarrafzadeh M.A wire-length minimization algorithm forsingle-layer layout[A].In：Proceedings of IEEE/ACM International Conference ofComputer Aided Design(ICCAD)，Santa Clara，USA，1992.390-393.]对单层对布图中的多端线网进行了研究，提出了基于TPT转换和“线段可见性”概念下的最小化方法。其时间复杂度为0(max(mn，mlogm))，其中n和m分别是指定待连线网N和全部线网集L的线段数目。该方法比较简单，它在转换过程中保持了“拓扑结构”不变(topology preserving)。但拓扑结构的固定又限制了TPT转换的自由度，使结果在很大程度上依赖于转换前的初始布线，因而在某些情况下结果不太理想。本专利申请所涉及的方法除了与该方法的思路不同外，在时间复杂度相当的情况下，我们能求得更优的线长结果，请具体参见后面的“本发明方法效果的实验数据”中给出的实验数据对比及其说明。

文献[Yukiko KUBO，Yasuhiro TAKASHIMA，Shigetoshi NAKATAKE，Yoji KAJITANI.Self-reforming routing for stochastic search in VLSI interconnection layout[A].In：Proceedings of IEEE/ACM Asia-Pacific Design Automation Conference(ASP-DAC)，Yokohama，Japan，2000.87-92.]提出了使用flip和dual-flip技术来优化原有布线。在这篇文献中证明了利用flip和dual-flip可将连接线网的任意一棵树转换为任何其它形状的树，这使得该方法的转换比上述的TPT转换有更大自由度。但由于该方法采用模拟退火技术，使得执行时间非常长。它的时间复杂度大大于本专利申请所涉及的方法。

文献[Zheng S Q，Lim J S，Iyengar S S.Finding obstacle-avoiding shortest pathsusing implicit connection graphs[J].IEEE Transaction on Computer-Aided Design ofIntegrated Circuits and Systems.1996，15(1)：103-110.]引入一个强连接图G_C，其复杂度为0(e²)，其中e为障碍的总边数。它同时采用A*和基于“detour”值不改向进行启发。另外，三项专利：[Ranko Scepanovic，Cupertino；Cheng-Liang Ding，SanJose.Towardoptimal steiner tree routing in the presence of rectilinear obstacles，5491641，Feb.13，1996]，[Ranko Scepanovic，Cupertino；Cheng-Liang Ding，SanJose.Toward optimalsteiner tree routing in the presence of rectilinear obstacles，5615128，Mar.25，1997]，和[Ranko Scepanovic，Cupertino；Cheng-Liang Ding，SanJose.Toward optimal steinertree routing in the presence of rectilinear obstacles，5880970，Mar.9，1999]也都是利用一个相似的强连接图“escape graph”，通过迷宫方法或者是对最小生成树(spanningtree)进行Steiner化的方法来求有障碍下多点线网的Steienr树。这一类方法在障碍情况比较简单的情况下会有较好的求解效果，但在障碍形状较复杂、边数较多的情况下，它们所基于的强连接图将会变得非常复杂，求解效率就比较差。因此，这一类方法仅适用于障碍比较简单的情况。而本专利申请所涉及的方法能适用于各种复杂的障碍情况。

文献[Liu Jian，Zhao Ying，Shragowitz E，Karypis G.A polynomial timeapproximation scheme for rectilinear Steiner minimum tree construction in thepresence of obstacles[A].In：Proceedings of IEEE International Symposium onCircuits and Systems(ISCAS)，Scottsdale，USA，2002.781-784.]引入了几何优化方法中的Guillotine-cut技术。该方法在无障碍时复杂度为多项式时间。虽然该方法可以应用到有障碍的情况，但求解就不能在多项式时间内完成，还需进行复杂度简化的研究工作。

文献[Ganley J L，Cohoon J.P.Routing a multi-terminal critical net：Steinertree construction in the presence of obstacles[A].In：Proceedings of IEEEInternational Symposium on Circuits and Systems(ISCAS).London，UK，1994.113-116.]提出的观点是：由于3点和4点的情况比较简单，因此在多点情况下可将它们按一定的要求分成3点组或4点组来实现。对于有障碍下的Steiner树问题，greedy 3-Steinerization(G3S)的时间复杂度为0(k²n)，而greedy 4-Steinerization(G⁴S)的时间复杂度为0(k³n²)。其中n是可选的Steiner点数目，k是执行迭代的次数，效率较低。batched 3-Steinerization(B3S)成批地选择三点组，时间复杂度为0(rkn)，其中r为反复的次数，提高了求解效率。但如何选择三点组或四点组是这个方法的核心问题，它决定着该方法求解结果的好坏。在无障碍的情况下，通常采取的方法是将比较靠近的点归为一组，这个方法是比较合理的，得到的结果也比较好。但是在有障碍的情况下，选择点组时就需要综合考虑障碍以及点的分布情况。因此，如何选择合适点组的问题就复杂很多。然而，在该文献中并没有针对这个核心问题给出明确的解决方法。虽然该方法的时间复杂度还不是很高，但是需要再做后续优化工作才能使该方法得到优化的结果。

另外，文献[黄林，赵文庆，唐璞山。一种含浮动端点的斯坦纳树的构造算法。计算机辅助设计与图形学学报.Vol.10，No.6，1998.11.]在具体分析和方法描述中，没有针对有障碍情况的说明。

已进行过“新颖性检索”，检索报告见附件1。

发明内容

本发明的目的在于提出一种标准单元总体布线时障碍下的直角Steiner树方法。

本发明的总体思路是：首先将所有障碍视为不存在，求得端点集在无障碍下的Steiner树(我们称为预-Steiner树)并连接各端点；然后对预-Steiner树进行改造，使预-Steiner树中在障碍内部的树边绕过障碍，生成有障碍下的Steiner树。在生成有障碍Steiner树的过程中，还可以根据图的拓扑结构，进行适当的预处理和后期处理，以得到更好的构造结果。

本发明的特征在于：它首先将所有障碍视为不存在，求得待连线网的端点集在无障碍下的Steiner树即预-Steiner树；然后使预-Steiner树中在障碍内部的树边绕过障碍，生成有障碍下的Steiner树；在生成有障碍Steiner树的过程中，根据图的拓扑结构，进行适当的预处理和后期处理；具体而言，它依次含有以下步骤：

(1).初始化，计算机从外部读入以下预先设置数据：

总体布线单元GRC的行数N_nr，列数N_nc，

总体布线图GRG中所有顶点即GRC中心点的坐标V_nr，nc(x，y)，其中，nr，nc分别代表行和列，x，y是芯片平面的坐标，

GRG中每条边e_k的容量C_k，

电路中线网的总数Nsum，每条线网的网表NetlistIndex，

电路中障碍的总数Osum，每个障碍各组成边的位置ObstacleIndex；

(2).读出以下数据以生成GRG：

读出在布线芯片上划分GRC所必需的行数N_nr和列数N_nc，再读出在布线芯片上生成上述GRG所必需的各顶点的坐标值，同时，给上述顶点及连接每相邻两个顶点的边e_k编号；

(3).按读入程序，为上述每条线网编号；

(4).根据上述读入的电路中障碍的总数Osum及每个障碍各组成边的位置ObstacleIndex生成障碍列表；

(5).构造预-Steiner树，即在不考虑障碍的情况下对连线网的端点集求解得到预-Steiner树；

(6).计算得到预-Steiner树各边与障碍边的交点并存储，删除预-Steirer树中处于障碍内部的树边；

(7).预处理：根据障碍及预-Steiner树的情况，综合考虑线长和时间效率决定对预-Steiner树是否进行变换以及如何进行变换；

(8).根据步骤(7)得到的预处理树与障碍相交的情况，对树边进行变换即分别对各组的树边与障碍的交点绕障碍重新连接，得到有障碍下的Steiner树；

(9).后期处理：从优化线长出发，对上述有障碍下的Steiner树进行变换。

所述的步骤(9)后期处理，主要是去环处理和去“空U”处理，以进一步减小树的总长度。

本发明的方法有如下特点：

首先，本发明的方法能处理多端点(包括能处理两端点)的线网；能处理复杂障碍(包括能处理矩形或L形的简单障碍)的情况。即本发明方法的适用范围更广。同时，本发明方法并不像有些文献那样只给出了一个设想或思路雏形，而是一个能在具体装置(工作站)上运行的为总体布线过程服务的IC CAD工具，有具体的实施描述。

其次，与已有的考虑障碍的多端点线网Steiner树构造方法相比，本发明的方法在时间复杂度和线长这两方面有更好的性能。本发明方法的时间复杂度仅为0(mn)，m和n分别是障碍的个数和线网端点数；同时用本方法求解的线长结果也十分理想。本发明的方法在综合效果上优于已有方法，请具体参见后面的“本发明方法效果的实验数据”中给出的实验数据说明。

附图说明

图1：本发明核心部分流程图。

图2：变换预-Steiner树为有障碍下Steiner树的流程图。

图3：树边与障碍边的交点的几种情况示意图。

     (a)一条树边穿过障碍的交点情况；

     (b)在障碍内部有Steiner点时的交点情况；

     (c)有整条边在障碍内部时的交点情况。

图4：树边与障碍边相交的两种边界情况示意图。

     (a)树边仅有一端与障碍接触的情况；

     (b)树边有一部分与障碍边重合的四种可能情况。

图5：交点“分组”的示意图。

图6：预处理的例子示意图一。

     (a)预-Steiner树的一部分与障碍的两个交点p1，p2；

     (b)点S1和点S2间的一条最短路径。

图7：预处理的例子示意图二。

     (a)预-Steiner树的一部分与障碍的两个交点p1，p2；

     (b)去掉预-Steiner树位于障碍内部的部分；

     (c)无预处理时，最后生成的结果。

图8：预处理方法描述。

图9：预处理的例子示意图三。

     (a)预-Steiner树的一部分与障碍的两个交点p1，p2；

     (b)预处理过程；

     (c)有预处理时，最后生成的结果。

图10：net18的Steiner树构造过程示意图。

     (a)输入的待连线网端点和障碍；

     (b)预-Steiner树，以及它与障碍的交点情况；

     (c)去掉预-Steriner树位于障碍内部的部分之后的结果；

     (d)进行预处理之后的结果；

     (e)改变树边，使其绕过障碍的结果；

     (f)进行后期处理之后的结果即为最后的输出结果。

具体实施方式

首先具体分析本专利申请涉及的“考虑障碍的直角Steiner树方法”的核心思想。

在将GRG、电路中障碍以及线网的信息读入并进行处理后，本方法核心的部分就是构造Steiner树的过程，总流程框图如图1所示。该方法的思路与以往的方法不同，方法分两步来构造最后的结果树：第一步，忽略所有障碍，对线网端点生成初始的无障碍下Steiner树，即预-Steiner树；第二步，考虑障碍，对预-Steiner树进行改造，得到考虑障碍的Steiner树。以下分别介绍方法的两个步骤。

第一步：构造预-Steiner树，即在不考虑障碍的情况下对端点集求解得到Steiner树，相当于上述总过程中的第(5)步：

由于该步产生的预-Steiner树仅仅是最后结果的一个初稿，因此，选择构造无障碍Steiner树方法的原则是，在保证结果有一定的优化程度的基础上，重点考虑方法是否有好的时间效率。例如一个效率较高并且效果不错的方法显然比一个需要多花费很多的时间求出更优结果的方法合适。

根据这个原则，我们这样选择无障碍下Steiner树方法：当端点数不多时选择“DW方法”，它已公开发表于1972年的国际期刊，见：[Dreyfus S E，and Wagner R A，“The Steiner problemin graphs”，Networks，1972，1：195]。该方法是精确方法，求得的结果是最小Steiner树，并且在端点数较少的情况下计算时间较短。但当端点数较多时，上面这种精确方法的计算时间急剧上升，因此应该选择一些效率较高的启发式方，例如“1-Steiner方法”，见[A.B.Kahng，and G.Robins，“A new class of iterative Steiner tree heuristics with good performance”，IEEE Transactions on Computer Aided Design.11(7)：893-902，July 1992.]；或者“GTCA方法”，见[A.B.Kahng，Ion I.Mandoiu，Alexander Z.Zelikovsky，“Highly ScalableAlgorithms for Rectilinear and Octilinear Steiner Trees”，Proc Asia-Pacific DesignAutomation Conference(ASP-DAC)，2003]。

第二步：考虑障碍的影响，针对预-Steiner树中与障碍相交的部分树边作相应改造，求出有障碍下的Steiner树。这个部分对应于上述总过程中的第(6)至第(9)步，该步流程图如图2所示。其中，Proc1至Proc4依次对应于第(6)至(9)步。

Proc1和Proc3是该步方法的主要工作，而Proc2和Proc4则根据结果Steiner树的优化程度而定。Proc2中的预处理可针对不同的情况帮助减少路径长度，而Proc4中的后期处理中可做一些消除环及进一步减少路径长度的工作，它们的具体方法将在后面介绍。

1.Proc1和Proc3，是第二步方法的主体。首先计算得到预-Steiner树各边与障碍边的交点，对这些交点根据需要进行处理并存储(即：Proc1)；然后根据交点的情况，对边进行变换，得到有障碍下的Steiner树(即：Proc3)。

(1)在Proc1中处理树边与障碍边的交点时，需要考虑以下几种情况，分别如图3所示。

●一条树边穿过障碍，与障碍边产生两个交点。

●在障碍内部有Steiner点，这组边与障碍边的交点多于两个。

●有整条边在障碍内部的情况，这条边连接的必是两个Steiner点，则这组边与障碍的交点是这些通过障碍内部边连在一起的Steiner所在的边与障碍边的交点集。

另外，还要考虑一些边界情况。在程序中是通过障碍边来描述障碍的，并且规定由障碍边构成的封闭区域之内是非布线区，而由障碍边构成的封闭区域的外面部分包括障碍边均为可布线区。边界情况包括两种，分别如图4所示：

●树边仅有一端与障碍接触，此时处理为此边与障碍不相交。

●树边有一部分与障碍边重合，对于凸多边形有四种可能情况，在程序中都要分别加以处理。

(2)另外，根据Proc3的要求，还要提出一个对交点“分组”的概念。对一棵预-Steiner树与障碍边的交点进行分组的原则是：凡经过预-Steiner树内连于障碍内部而形成的部分交点属于同一组。只有属于同一组的交点在Proc3中去除障碍内树边后需要被重新连接。图5的例子中，{p₁，p₂，p₃，p₄}是一组交点，而{p₅，p₆}是另一组交点。

在Proc3中改变路径所做的操作是：先去掉处于障碍内部的边或边的一部分，然后绕障碍进行重连。重连的方法有多种：最简单的方法是求出一个最小路径将一个障碍上的所有交点(不分组)沿障碍边连接起来，由于这个方法将所有不同组的交点也连接在一起，因此可能产生一些不必要的连接，增长了路径长度。稍微复杂一点的方法可以对交点分组来处理，分别对每组交点选择绕障碍的最短路径进行重连。这个方法没有考虑到不同组的绕障碍路径的重叠造成的影响，因此更进一步的还可以考虑这个影响作更细致的处理，使得绕障碍的路径更短。

2.Proc2和Proc4，可根据结果优化程度的好坏选择使用该步骤。

若在第二步中仅仅进行Proc1和Proc3，则在一些情况下得到的结果可能会不太好。针对不同的情况进行不同的预处理可以帮助减短路径的长度。下面举例说明其中一个比较重要的问题：

图6(a)中是某棵预-Steiner树的一部分与障碍相交的情况，需要对边进行改变。显然我们可以看出，S1和S2间的最短路径长度是Manhattan距离，如图6(b)所示。

但是，若不进行预处理直接找出相交点并重连(即直接仅仅执行Proc1和Proc3)，如图7所示，则我们只能得到图7中(c)的结果，当情况很坏时，最后结果会比有障碍下最小Steiner树的情况差很多。

因此，为了改善结果，需要做一些预处理。预处理流程如图8所示。

图9显示的是上面例子进行预处理的过程和结果。p1不作调整，p2调整为p2’，经过预处理得到的结果如图9(c)所示，可见此时两点间路径长度为两点间最短距离。

后期处理主要是进行去环处理和去“空U”的处理，以进一步减小树的总长度。三段连续的线段构成的形如字母U的线路称为一个“U”，“空U”即指在U形线路的中间那段向U内部仍有上移空间。我们采用“TPT转换技术”。而去环处理的方法是从树根依次搜索找出环，并去掉环中最大的边。

下面结合一个MCNC(Microelectronics Center of North Carolina)标准电路线网的例子，说明本方法的全过程，如下：

为了实现，或者说是具体实施本项发明，我们给出以下关于发明实施的描述。

实施本发明的计算机系统：本发明所设计的为总体布线服务的软件要在一个具体的计算机系统上得以实施，该计算机系统具体描述如下。

一台Sun公司的V880型工作站；

Unix操作系统；

标准C编程语言；

Vi编辑器、gcc编译器、gdb调试工具等。

步骤(1)-(4)：预备工作。构造GRG网格；读入线网信息；读入障碍信息并处理这些信息。其中，除“读入障碍信息并处理这些信息”外的其他工作都与一般的标准单元总体布线的预备工作相同，详细描述见文献[已申请的国家发明专利：洪先龙，经彤，鲍海云，蔡懿慈，许静宇。发明名称：基于关键网络技术优化时延的标准单元总体布线方法。申请日期：2002/01/15.申请号为：02100354.8.已于2002/07/24被公开。]和[已申请的国家发明专利：洪先龙，经彤，许静宇，张凌，胡昱。发明名称：考虑耦合效应进行时延优化的标准单元总体布线方法。申请日期：2002/12/17.申请号为：02156622.4.已于2003/05/07被公开。]中的介绍。这里只重点描述“读入障碍信息并处理这些信息”这项工作。

输入的线网信息：采用MCNC标准电路例子中的18号线网的网表表示(待连端点信息)，则有：

(net 18(vertexList 83 2    38 2    80 2    93 1))

——说明：其中的83，38，80，93给出了在GRG网格中待连端点号，这些端点在xy平面的坐标依次为：(1246，1312)，(972，656)，(428，1312)，(972，1488)。第83号顶点是漏点，第38号顶点是漏点，第80号顶点是漏点，第93号顶点是源点。它们的通式可表示为：

(net号(VertexList顶点号源点/漏点  ……))，

其中：数字1表示源点，数字2表示漏点。

针对18号线网所输入的障碍信息为：obstacle 1(ybound(800 1000)xbound(400 1000)h_edge(400 800，1000800；400 1000，1000 1000)v_edge(400 800，400 1000；1000 800，1000 1000))obstacle 2(ybound(1200 1400)xbound(600 1000)h_edge(700 1200，9501200；600 1250，700 1250；950 1250，1000 1250；600 1350，700 1350；9501350，1000 1350；700 1400，950 1400)v_edge(600 1250，600 1350；7001200，700 1250；700 1350，700 1400；950 1200，950 1250；950 1350，950 1400；1000 1250，1000 1350))

——说明：输入的障碍信息给出了障碍ID号和对各个障碍的描述，即包括障碍在x和y方向的最大值和最小值，障碍的所有水平边和竖直边。

图10(a)为输入线网net18和障碍的示意图，图中给出了待连线网端点的坐标，以及障碍的各端点坐标。

读入这些信息后，经过处理，存于相应的数据结构中。

步骤(5)：根据待连线网端点构造预-Steiner树。

例如由net18求得的预-Steiner树为：

Net ID 18

(972，1488)----->(972，1312)

(972，1312)----->(1246，1312)

(428，1312)----->(972，1312)

(972，656)----->(972，1312)

——说明：“(972，1488)----->(972，1312)”描述的是预-Steiner树的一条树边，它的两个端点在xy平面上的坐标分别为(972，1488)和(972，1312)。其余类似。这棵预-Steiner树共有4条树边。

图10(b)为net18的预-Steiner树的示意图，图中给出了树的各端点坐标，以及此树与障碍的交点坐标。

步骤(6)：计算预-Steiner树与障碍的交点。并删除处于障碍内部的树边。

经过计算，net18的预-Steiner树与障碍1和障碍2的交点分别为：

Net ID 18

obstacle 1

intersections：(972，800)：1，(972，1000)：1

obstacle 2

intersections：(600，1312)：2，(972，1250)：2，(972，1350)：2，(1000，1312)：2

——说明：障碍obstacle1和obstacle2与net18的预-Steiner树相交。各交点表示为(x，y)：link_No，其中(x，y)表示交点在xy平面上的坐标值，link_No表示此交点所在的组号(同一组的交点需要在后边改变树边的步骤中重新连接在一起，具体可参见前面“具体实施方式”节中的第1(2)条目中的关于“分组”概念的分析)。

相应的，预-Steiner树处于交点之间的障碍的部分被删除，仅保留其处于障碍外部的部分，如下所示：

Net ID 18

Part of the tree out of the obstacles：

(972，1488)----->(972，1350)

(972，1250)----->(972，1000)

(972，656)----->(972，800)

(1000，1312)----->(1246，1312)

(428，1312)----->(600，1312)

变化示意图如图10(c)所示，图中给出了各树边的端点坐标。

步骤(7)：预处理过程。根据预-Steiner树与障碍相交的情况，对障碍外部的预-Steiner树部分中的一些树边进行改变。

经过计算，以下原树边被新树边替代：

           原树边                           新树边

(972，1250)----->(972，1000)    (1000，1250)----->(1000，1000)

因此，经过预处理后得到的处于障碍外部的预-Steiner树的部分为：

Net ID 18

Part of the tree out of the obstacles：

(972，1488)----->(972，1350)

(1000，1250)----->(1000，1000)

(972，656)----->(972，800)

(1000，1312)----->(1246，1312)

(428，1312)----->(600，1312)

经过预处理过程后的障碍外部的预-Steiner树参见图10(d)，图中给出了各树边的端点坐标。

步骤(8)：改变路径。这一步所做的工作就是交点绕障碍的重新连接。

重连交点得到的新树边为：

Net ID 18

Part of the tree reconnecting the intersections：

(600，1312)----->(600，1350)

(600，1350)----->(700，1350)

(700，1350)----->(700，1400)

(700，1400)----->(950，1400)

(950，1400)----->(950，1350)

(950，1350)----->(972，1350)

(972，1350)----->(1000，1350)

(1000，1350)----->(1000，1312)

(1000，1312)----->(1000，1250)

(1000，1000)----->(1000，800)

(1000，800)----->(972，800)

这样，改造后的Steiner树由这两部分构成：保留的(并有可能经过步骤(7)改造的)处于障碍外部的预-Steiner树部分和由步骤(8)得到的重连交点得到的新树边。改造的Steiner树如下所示，此Steiner树连接所有端点并避开障碍。

Net ID 18

(600，1312)----->(600，1350)            <1>

(600，1350)----->(700，1350)            <2>

(700，1350)----->(700，1400)            <3>

(700，1400)----->(950，1400)            <4>

(950，1400)------>(950，1350)           <5>

(950，1350)----->(972，1350)            <6>

(972，1350)----->(1000，1350)           <7>

(1000，1350)----->(1000，1312)          <8>

(1000，1312)----->(1000，800)           <9>

(1000，800)----->(972，800)             <10>

(972，1488)----->(972，1350)          <11>

(972，656)----->(972，800)            <12>

(1000，1312)----->(1246，1312)        <13>

(428，1312)----->(600，1312)          <14>

——说明：“(600，1312)----->(600，1350)”描述的是Steiner树的一条树边，“<1>”是这条边的序号。其余类似。图10(e)为改造后的Steiner树，图中标出了各边的序号。

步骤(9)：后期处理。对树中的环以及“空U”进行处理。

处理的结果为：如下所示的原树边被新树边代替。

           原树边               处理原因                   新树边

(950，1400)----->(950，1350)    形成“空U”     (950，1400)----->(972，1400)

(950，1350)----->(972，1350)                    (972，1400)----->(972，1350)

(972，1488)----->(972，1350)                    (972，1488)----->(972，1400)

经过后期处理后，得到的有障碍下的net18的Steiner树如下所示。这就是采用本发明方法的最终结果。

Net ID 18

(600，1312)----->(600，1350)            <1>

(600，1350)----->(700，1350)            <2>

(700，1350)----->(700，1400)            <3>

(700，1400)----->(972，1400)            <4>

(972，1400)----->(972，1350)            <5>

(972，1350)----->(1000，1350)           <6>

(1000，1350)----->(1000，1312)          <7>

(1000，1312)----->(1000，800)           <8>

(1000，800)----->(972，800)             <9>

(972，1488)----->(972，1350)            <10>

(972，656)----->(972，800)              <11>

(1000，1312)----->(1246，1312)          <12>

(428，1312)----->(600，1312)            <13>

——说明：“(600，1312)----->(600，1350)”描述的是net18在障碍下的最终结果Steiner树的一条树边，它的两个端点在xy平面上的坐标分别为(600，1312)和(600，1350)，“<1>”是这条边的序号。其余类似。所求得的net18的障碍下Steiner树共有13条树边。

图10(f)给出了net18最终结果的Steiner树示意图，图中标出了各边的序号。

本发明方法效果的实验数据

进行实验的计算机系统具体描述如下：

    一台Sun公司的V880型工作站；

    Unix操作系统；

    标准C编程语言；

    Vi编辑器、gcc编译器、gdb调试工具等；

MCNC电路中的线网作为测试例子，9个线网的测试结果数据列举如下：

    Net ID        线网       RSMT      RSMTO      Ours      Redundancy

                 端点数      [1]        [2]       [3]       [4]

    C2net22        2         442        754       754       0％

    C2net33        2         1332       1332      1332      0％

    C2net2         3         3572       3828      3828      0％

    C2net17        3         1160       1188      1188      0％

    C2net504       4         856        1256      1256      0％

    C2net59        3         2028       3208      3268      1.87％

    C2net609       4         2054       2894      3004      3.80％

    C2net67        5         1880       2064      2156      4.46％

    C2net177       6         2660       2660      2790      4.89％

[1]RSMT：无障碍下的RSMT长度

[2]RSMTO：有障碍下的RSMT长度

[3]Ours：本发明方法生成的有障碍下的RSMT长度

[4]Redundancy＝(Ours-RSMTO)/RSMTO*100％

从上述测试结果可计算得到本发明方法求解的布线树的线长冗余Redundancy的平均值为1.67％。同时，对所有例子的求解执行时间均有：≤1秒。

针对上述9个线网，本发明方法与Chen Desheng等的“TPT”[5]方法(请参见“背景技术”中的介绍)的测试结果比较列出如下：

Net ID          线网          TPT             Ours            Comparison

               端点数         [5]             [3]             [6]

C2net22          2            902             754             19.00％

C2net33          2            1332            1332            0％

C2net2           3            3906            3828            2.03％

C2net17          3            1368            1188            15.15％

C2net504            4            1580            1256            25.80％

C2net59             3            3254            3268            -0.43％

C2net609            4            3004            3004            0％

C2net67             5            2418            2156            12.15％

C2net177            6            3008            2790            7.81％

[5]“TPT”方法求解生成的有障碍下的RSMT长度。

[6]Comparison＝(TPT-Ours)/Ours*100％

从上述测试结果对比可以看出：两种方法的时间复杂度相当，但本发明方法所求解得到的线长结果明显优于“TPT”方法。