一种时钟网络布线的曼哈顿平面化切割线生成方法

摘要

本发明为一种适用于斜线划分的时钟网络布线的曼哈顿平面化切割线的生成方法。该方法把欧几里得平面上的连线转化到曼哈顿平面上，获得平面化的时钟树，构成切割线布线通道网络。本发明通用性强，可根据输入产生输出自动进行，算法简约而严密。

主权项

1、一种时钟网络布线的曼哈顿平面化的切割线生成方法，设z为平面上给定的n个点的集合，其拓扑结构为T，已知这些点的某个欧几里得连接方式Y，将Y转换成曼哈顿平面上这n个点的连接X，使得这种连接X满足以下条件：保持Z的拓扑结构T不变，保证X得平面化；其特征在于以一棵子树来说，其具体步骤如下：步骤1：基本切割线的生成确定本层切割线的基本方向：Cd(0)为初始切割线的方向，设定为垂直或者水平，Cd_M(S)和Cd_N(S)为从本层子树的父节点S引向左右两个子节点M和N的切割线方向，取上层切割线方向Cd_S(S-1)的正交方向为本层切割线方向，并根据切割线方向引曼氏连线到基本子树的子节点；步骤2：根据障碍区确定可布线区域(a)障碍区归类：根据障碍区的顶点在布线区域中的分布情况，将障碍按照水平和垂直分布归类，同时我们得到相应虚实顶点的分布情况；(b)障碍区合并：将所有的相同类型的障碍区域的边界合并起来，得到所有垂直障碍区域的集合即最大垂直障碍区VON(S)和所有水平障碍区域的集合即最大水平障碍区HON(S)；(c)可布线区域的生成：根据垂直和水平障碍区域的相交情况：1)不相交，2)虚实顶点互交3)虚顶点互交三种情况应用可布线区域的生成规则：规则1：当垂直和水平障碍区域不相交的时候，由垂直和水平障碍区域的边界构成的多边形就是可布线区域；规则2：如果有且只有一个为虚顶点，保持相交点为实顶点的障碍区边界，将公共障碍区和实顶点相邻的两条边按照一定宽度D拓展和虚定点的两条邻边重新构成一个矩形区域，在相交点为虚定点的障碍区中去除此部分得到新的障碍区边界；规则3：如果两个相交点都是虚顶点，选定其中一个到本障碍区所属布线区距离最小的虚顶点，对这个顶点所在障碍区进行调整，调整方法如法则2种所述，其中实顶点用另一虚顶点代替。如前所述在此合并得到新的调整后的水平和垂直障碍区；通过上述规则1，2，3的反复运用，就可以找到所要求的曼哈顿平面直线所在的通路，根据此通路调整基本切割线就得到最终切割线；步骤3：切割线连通每一层的下层切割线完成并返回到本层后，判断两层切割线是否相连，如果不相连，则扩展本层切割线，使得相邻两层切割线相连通，使最终的切割线成为一个连通的布线网络通道。