超大规模集成电路避障碍的直角Steiner树方法

摘要

超大规模集成电路避障碍的直角Steiner树方法属于集成电路计算机辅助设计技术领域，尤其超大规模集成电路布线设计领域，其特征在于：提出基于完全Steiner树(FST)的端点划分方法，然后在划分出来的每个子集中针对不同情况分别使用蚁群方法和贪婪FST方法构造子Steiner树，最后用detour方法的思想来连接所有的子Steiner树。该算法能处理多端点(包括能处理两端点)的线网；能处理复杂障碍(包括凹多边形障碍)的情况；能够在较短时间里很好地处理大规模问题。它实现了在待连接线网有多个端点情况下的超大规模集成电路布线时避障碍的优化线长与时间效率的直角Steiner树构造方法。

主权项

1.超大规模集成电路避障碍的直角Steiner树方法，其特征在于，它依次含有以下步骤：(1)初始化，计算机从外部读入如下预设数据：线网的信息：线网编号，线网中需要连接引脚的物理位置，用二维笛卡儿坐标表示，即为端点；障碍信息：形成障碍的多边形的点列；(2)根据线网的端点用GeoSteiner3.1的开发包构造完全Steiner树集合，用FST表示，简称F；(3)端点划分：删除步骤(2)得到的集合F中所有与障碍相交的FST，得到新的FST集合，用F’表示，其中，相连的FST把端点划分成n个分离的子集Ti，i＝1，...，n；(4)构造子树：对步骤(3)得到的每个子集Ti，根据形成Ti的FST集合构造子Steiner树，用Si表示，这一步要根据端点数量分别采用下面两种方法：(4.1)对于端点数量小于20的子集Ti，采用基于蚁群的方法构造子树，其步骤依次如下：(4.1.1)设定：子集Ti的边上的初始信息素值，用τ表示，τ即为信息素值；(4.1.2)在各Ti中的各端点处放置1只蚂蚁，并予以编号，用antName表示；同时，每一只蚂蚁维护一个禁忌表，记录已经访问过的点；设定迭代次数的最大值；(4.1.3)任选一只蚂蚁m，通过下式计算出选择每个与m相邻的顶点的概率，i表示蚂蚁m所在的顶点，j表示顶点i的相邻顶点，(i，j)表示连接顶点i和顶点j的边，p_i，j表示蚂蚁m选择顶点j作为下一个要到达的顶点的概率：其中，集合N是顶点集合，它是由所有通过Ti上的边与当前蚂蚁m所在顶点相连，并且不是它所访问过的顶点组成的；η_j^m：当前蚂蚁m在顶点i时，与蚂蚁m相连的顶点中的某一顶点j的可见度： ${\eta }_j^m=\frac{1}{c(i,j)+\gamma ·{\psi }_j^m}$ψ_j^m：从顶点j到当前所有其他蚂蚁已经访问过的顶点的最短距离，为已知量，c(i，j)：从顶点i到顶点j的长度，τ_ij：边(i，j)上的信息素浓度的更新值：τ_i，j＝(1-ρ)·τ_i，j+ρ·Δτ_i，jΔτ_ij：在每选定一边时，其上所增加的信息素的量：其中，c(S₁)是当前所保留的最小直角Steiner树的总线长，E₁是它的边集合；上述的α、β、γ、ρ、Z皆为常量，预先设定，其范围如下：α∈[1，5]，β∈[1，5]，γ∈[1，4]，ρ∈[0，1]，Z∈[1，∝]，其中，α、β、γ、Z是整数，ρ是实数；上述tabulist是禁忌表，ktabulist(m)表示不在m的禁忌表中的点k的可见度；(4.1.4)依照步骤(4.1.3)得到的概率p_ij，蚂蚁m选择所要通过的边(i，j)；(4.1.5)把顶点j添加到蚂蚁m的禁忌表中；(4.1.6)若前蚂蚁m遇到另一只蚂蚁m’，就把蚂蚁m从蚂蚁集中去掉，并把m的禁忌表中的端点添加到另一只蚂蚁m’的禁忌表中；(4.1.7)更新边(i，j)上的信息素的含量；(4.1.8)迭代次数加1，重复步骤(4.1.2)-(4.1.8)，一直迭代到设定的迭代次数的最大值为止；(4.2)对于端点数量大于20的子集Ti，采用基于FST的贪婪搜索策略构造子树，依次含有下列步骤：(4.2.1)删除与障碍相交的FST，剩下的FST称为候选FST，再计算所有候选FST的渴求度](t)：                     η(t)＝c(t)^λ/t(t)^ω其中，t表示需要计算渴求度的FST，c(t)表示t的总线长，t(t)是FST的端点数，λ和ω是常量，预先设定，其范围如下：λ∈[1，4]，ω∈[1，4]，其中，λ、ω是整数；(4.2.2)选择候选集合渴求度最小的FST，即f，并将f加入到当前解集合Y中；(4.2.3)删除候选FST中所有与f不兼容的FST，这里，两棵树不兼容是指两棵树包含两个或两个以上的相同端点，或者有一条或一条以上的边重叠；(4.2.4)删除端点集合中所有被f覆盖的端点；(4.2.5)如果候选FST集合不为空，则重复(4.2.2)-(4.2.4)的步骤，选择新的FST加入到当前解中，直到候选FST集合为空；(4.2.6)如果端点集合中还有剩余元素，则将它们加入到当前解中；(5)利用最小折返值方法，即detour方法，计算每两个子树之间的最短路径，从而把Si，i＝1，...，n，连接成一棵完整的Steiner树，计算两子树之间的最短路径的方法是：对于属于这两棵子树的所有端点，两两求最短路径，取其中最短的那条路径作为两子树之间的最短路径；计算两个端点，即点s到点t，之间最短路径的方法有以下步骤：(5.1.1)根据障碍和端点s、t构造逃逸图，这里，逃逸图是由障碍的水平边和竖直边向两端扩展，直到遇到障碍，这样扩展后的线段相交形成的一种连接图；(5.1.2)初始化候选点集合为点{s}，已访问点集合为空，设置当前点为s；(5.1.3)把所有与当前点在逃逸图上相邻且未访问过的点加入到候选点集合中，根据下面的规则计算这些新加点的折返值：有向边u→v折返值的定义：给定一条有向边u→v和一个最终目标点t，设L为通过点t且与有向边u→v相垂直的直线，则：当u，v在L的同侧，且u到L的距离远于v，则u→v的折返值＝0；当u，v在L的同侧，且u到L的距离近于v，则u→v的折返值＝线段u→v的长度；当线段u→v与L交于w，则u→v的折返值＝线段w→v的长度；于是，点的折返值可以这样定义：从源点出发到目标点的寻路过程中，某一点的折返值即为从源点到该点的所有路径的折返值之和；(5.1.4)在候选集合中选择折返值最小的点q加入到访问点集合中，设置当前点为q；(5.1.5)如果最终目标点t不在候选点集合中，则重复步骤(5.1.1)-(5.1.4)；(5.1.6)如果最终目标点t在候选点集合中，则把t加入到访问点集合中，这样找到的最短路径就是访问点集合中的点列按照被加入的先后顺序所组成的路径。