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

摘要

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

主权项

1. 标准单元总体布线时障碍下的直角Steiner树方法，其特征在于：它首先将所有障碍视为不存在，求得待连线网的端点集在无障碍下的Steiner树即预-Steiner树；然后使预-Steiner树中在障碍内部的树边绕过障碍，生成有障碍下的Steiner树；在生成有障碍Steiner树的过程中，根据图的拓扑结构，进行适当的预处理和后期处理；具体而言，它依次含有以下步骤：(1). 初始化，计算机从外部读入以下预先设置数据：总体布线单元GRC的行数Nnr，列数Nnc，总体布线图GRG中所有顶点即GRC中心点的坐标Vnr，nc(x，y)，其中，nr，nc分别代表行和列，x，y是芯片平面的坐标，GRG中每条边ek的容量Ck，电路中线网的总数Nsum，每条线网的网表NetlistIndex，电路中障碍的总数Osum，每个障碍各组成边的位置ObstacleIndex；(2). 读出以下数据以生成GRG：读出在布线芯片上划分GRC所必需的行数Nnr和列数Nnc，再读出在布线芯片上生成上述GRG所必需的各顶点的坐标值，同时，给上述顶点及连接每相邻两个顶点的边ek编号；(3). 按读入程序，为上述每条线网编号；(4). 根据上述读入的电路中障碍的总数Osum及每个障碍各组成边的位置ObstacleIndex生成障碍列表；(5). 构造预-Steiner树，即在不考虑障碍的情况下对连线网的端点集求解得到预-Steiner树；(6). 计算得到预-Steiner树各边与障碍边的交点并存储，删除预-Steiner树中处于障碍内部的树边；(7). 预处理：综合考虑线长和时间效率决定对预-Steiner树是否进行变换以及如何进行变换，即：根据障碍及预-Steiner树的情况，对预-Steiner树与障碍的交点以及预-Steiner树处于障碍外部的相应部分进行修改，首先，对预-Steiner树与障碍的每一个交点p，先找到通过预-Steiner树在障碍外部的部分上并与该交点相连的Steiner点或线网端点S，且满足点S与交点p之间的预-Steiner树部分没有其他的Steiner点或者线网端点，然后，如果能找到这样的线网端点S，则对交点p以及处于点p和点S之间的预-Stiener树部分进行修改，即将点p沿障碍边移动到障碍边上离点S最近的一点p′，将点p′作为预处理后更新的交点，同时随着点p的移动，与它相连的预-Steiner树的边也要作相应的平移或缩短，最后，如果不存在这样的线网端点S，那么交点p必然是通过预-Steiner树在障碍外部的部分与另一个交点q相连，于是，对点p以及处于点p和点q之间的预-Steiner树部分进行修改，即在障碍外部的预-Steiner树的各部分中，找到离点p最近的一个Steiner点或者线网端点S，将点p沿障碍边向靠近点S的方向移动，同时对与点p相连的预-Steiner树的边L作相应的平移或缩短，一旦边L随着点p的移动开始增长、或者点p已经移动到障碍边上离点S最近的位置，则停止移动p，我们设此时点p的新位置为p′，则点p′为预处理后更新的交点；(8). 根据步骤(7)得到的预处理树与障碍相交的情况，对树边进行变换即分别对各组的树边与障碍的交点绕障碍重新连接，得到有障碍下的Steiner树；(9). 后期处理：从优化线长出发，对上述有障碍下的Steiner树进行变换。