CN111125993A - 一种满足最小Cut数量约束的布线方法 - Google Patents

Abstract

一种满足最小Cut数量约束的布线方法，包括以下步骤：1）读取布线参数，确定各个布线层的最小通孔数的约束；2）将需要连接的源点加入到待扩展结点的队列中，确定待扩展结点的队列；3）确定当前费用最小的结点，沿各方向扩展结点，并计算扩展代价；4）根据计算的代价总值最小的原则生成通孔，进行布线。本发明支持多通孔布线，有助于提高芯片制造良率；支持针对多孔的避障，提高对布线空间的利用；对于通孔数的拆解，能够有效地减少设计规则检查。

Description

一种满足最小Cut数量约束的布线方法

技术领域

本发明涉及EDA设计技术领域，特别涉及一种满足最小Cut数量约束的布线方法，以在满足设计规则检查（Design Rule Check，DRC）的前提下，最小化布线空间。

背景技术

由于芯片规模的增大和工艺需求的增加，EDA工具成了芯片设计领域必不可少的辅助工具。在布线阶段，EDA工具的首要目标是实现不同模块之间的连接关系。EDA工具在实现连接关系的同时还需要满足设计规则，因为设计规则直接影响最后的芯片制造。

最小Cut数量约束为EDA工具中众多设计规则之一。最小Cut数量约束是通孔生成时对通孔中cut数量的要求，而通孔中cut的数量影响着芯片制造的良品率（通孔就是在氧化物层上的孔，用于连接上下层金属，cut就是在这个连接处有多少个孔，在最小Cut数量约束中要求一个通孔至少由n个(n由约束的具体值决定)cut组成。在EDA布线工具中布线器常常会面临需要连接位于不同金属层的电子元器件，这就要通过通孔实现模块的跨层连接。原有的布线过程中，布线器无视多孔的多种通孔生成方式，直接取其中占用面积最大的通孔生成方式进行判断是否与障碍物产生DRC，这种方法极大的浪费布线空间。

发明内容

为了解决现有技术存在的不足，本发明的目的在于提供一种满足最小Cut数量约束的布线方法，在满足DRC的前提下，最小化布线空间。

为实现上述目的，本发明提供的满足最小Cut数量约束的布线方法，包括以下步骤：

1）读取布线参数，确定各个布线层的最小通孔数的约束；

2）将需要连接的源点加入到待扩展结点的队列中，确定待扩展结点的队列；

3）确定当前费用最小的结点，沿各方向扩展结点，并计算扩展代价；

4）根据计算的代价总值最小的原则生成通孔，进行布线。

进一步地，所述步骤3）进一步地包括以下步骤：

21）根据最小通孔数的约束，确定通孔组合方式，表示为行*列的形式；

22）获取当前层通孔的几何参数，计算不同的通孔组合方式下的查询区域；

23）遍历各个通孔组合方式下的查询区域，判断是否存在障碍物，判断是否会产生DRC，计算代价值。

进一步地，所述几何参数，包括cut的宽度、高度、cut沿x和y方向上的间距、通孔沿x和y方向上的间距。

进一步地，所述查询区域的宽度=cut宽度*通孔中cut的列数+cut沿x方向间距*（通孔中cut的列数+1）+2*通孔沿x方向间距，所述查询区域的高度=cut高度*通孔中cut的行数+cut沿y方向间距*（通孔中cut的行数+1）+2*通孔沿y方向间距。

进一步地，所述步骤23）进一步包括，针对每一种行*列的通孔排布方式，可以根据通孔的其他参数生成top层、bottom层和cut层的矩形，再通过数据结构查询top层、bottom层和cut层的矩形区域内是否存在障碍物，判断是否会产生DRC。

进一步地，所述步骤23）进一步包括：

如果产生DRC则为扩展的结点的代价加上惩罚值；

如果存在一种摆放方式使得区域内无障碍物，则扩展结点不增加额外代价；

如果所有的摆放方式的查询区域内都存在障碍物则不需要增加额外的代价。

进一步地，所述步骤4）进一步地包括，选择使得最后生成的通孔需要的代价最小的打孔组合方式进行打孔、布线。

更进一步地，所述当前费用=前一个结点的费用+从前一个结点扩展到当前结点的费用，其中，从前一个结点扩展到当前结点的费用=根据扩展方向产生的基础费用+违反DRC产生的费用。

为实现上述目的，本发明还提供一种满足最小Cut数量约束的布线的装置，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的程序，所述处理器运行所述程序时执行上述的满足最小Cut数量约束的布线方法的步骤。

为实现上述目的，本发明还提供一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行上述的满足最小Cut数量约束的布线方法的步骤。

本发明具有以下技术效果：

1. 支持多通孔布线，有助于提高芯片制造良率；

2. 支持针对多孔的避障，提高对布线空间的利用；

3. 对于通孔数的拆解，能够有效地减少DRC。

本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，并与本发明的实施例一起，用于解释本发明，并不构成对本发明的限制。在附图中：

图1为根据本发明的满足最小Cut数量约束的布线方法的流程图；

图2为根据本发明的布线工艺层几何约束设置页面示意图；

图3为根据本发明的实施例的基于最小Cut数量约束的不同打孔组合方式示意图；

图4为根据本发明的布线处的详细示意图；

图5为根据本发明的根据通孔计算所需查询区域的示意图；

图6为根据本发明的布线效果图。

具体实施方式

以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

图1为根据本发明的满足最小Cut数量约束的布线方法的流程图，下面将参考图1，对本发明的满足最小Cut数量约束的布线方法进行详细描述。

在步骤101，确定各个布线层的最小通孔数的约束。

在该步骤中，读取布线参数，获得对于各个布线层的最小通孔数的约束。

在步骤102，确定待扩展结点的队列。

在该步骤中，将需要连接的源点加入到待扩展结点的队列中，确定待扩展结点的队列。

在步骤103，确定当前费用最小的结点，沿各方向扩展结点，并计算扩展代价。

在该步骤中，从步骤102中确定的待扩展结点的队列中取出当前费用最小的结点，沿各方向扩展结点。

本发明实施例中，所谓费用，是指根据从一个结点到另一个结点的线长和布线过程中由于违反DRC而额外产生代价综合考虑计算出来的一个值，反映了两个结点之间的这条路径的优劣程度，一般来说都是希望最后布线结果的费用越低越好；所述根据扩展方向产生的基础费用，包括线长因素，以及当前层XY方向走线的优先级不同而产生的XY方向走线的代价不同。

在计算当前费用时，根据当前费用=前一个结点的费用+从前一个结点扩展到当前结点的费用来进行计算，其中从前一个结点扩展到当前结点的费用=根据扩展方向产生的基础费用+违反DRC产生的费用。

在扩展结点时，总共是沿north\south\west\east\up\down六个方向扩展结点，只有结点在沿上下方向进行扩展时需要通过打孔进行换层。

当结点沿上下方向扩展时，查询在当前位置生成通孔时是否会产生DRC，如果产生DRC则为扩展的结点的代价加上一个较大的惩罚值。

其中查询范围根据通孔组合方式确定，具体地，取得当前层所需的最小通孔数N，将N拆解成ROW*COL的形式，其中，ROW表示通孔的行数，COL表示通孔的列数。对于同一个N，可以拆分成多个ROW*COL的形式，需要将这些可能一一遍历。

在该步骤中，还需获取当前层通孔的其他参数，如单个通孔的宽度和高度以及通孔之间的间距，以计算查询区域。

针对每一种ROW、COL的通孔排布方式，可以根据通孔的其他参数生成top层、bottom层和cut层的矩形。

再通过数据结构查询top层、bottom层和cut层的矩形区域内是否存在障碍物，判断是否会产生DRC。

在步骤104，根据步骤103计算的代价总值最小的原则生成通孔，进行布线。

在该步骤中，选择最优的打孔组合方式，其中按照不同的打孔组合方式生成矩形块的步骤与步骤103类似。在生成矩形后计算违反DRC的值，选择值最小的方式生成通孔。

本发明在将找到的路径转换为版图的阶段中，在需要换层的位置选择最优的打孔组合方式，使得在满足通孔数量的情况下尽可能不产生DRC。

下面结合一个具体实施例，具体说明本发明的布线方法：

首先，读取cut相关参数

图2为根据本发明的布线工艺层几何约束设置页面示意图，如图2所示，程序读取相应的布线的参数。以图2中所示表格第3行为例，程序从中读入M2层到M1层之间的通孔信息，M2层x方向外框为0，y方向外框为0.04，M1层x方向外框为0，y方向外框为0.04，M2层到M1层之间最小通孔数为2。

然后，根据最小通孔数，搜索布线路径。

根据最小通孔数的不同组合方式，分别计算需要查询的区域。具体地，获取当前层最小通孔数N，如前所述，将N拆解成ROW*COL 的形式，其中，ROW表示通孔的行数，COL表示通孔的列数。对于同一个N，可以拆分成多个ROW*COL的形式。图3为根据本发明的实施例的基于最小Cut数量约束的不同打孔组合方式示意图，如图3所示，当前层最小通孔数N=6，那么就存在4种打孔组合方式，分别为2*3，3*2，1*6，6*1。不同的打孔组合方式所需要查询的区域也有所不同，所以需要遍历所有的打孔组合方式。

如图4、图5所示，以2*3作为布线方式，则可以如此计算需要查询区域的长宽：

即，查询区域的宽度=cut宽度*通孔中cut的列数+cut沿x方向间距*（通孔中cut的列数+1）+2*通孔沿x方向间距，查询区域的高度=cut高度*通孔中cut的行数+cut沿y方向间距*（通孔中cut的行数+1）+2*通孔沿y方向间距。

确定查询区域以后，查询当前层的该区域内的是否存在障碍物。如果存在一种摆放方式使得区域内无障碍物，则扩展结点不增加额外代价；如果所有的摆放方式的查询区域内都存在障碍物则不需要增加额外的代价。

最后，进行布线。

在需要换层的位置，选择最优的打孔组合方式，使得最后生成的通孔需要的代价最小。寻找方式与搜索布线路径阶段的方式类似，同样通过尝试所有通孔排列方式，计算需要查询的区域范围，查询范围内是否存在其他的障碍，最后从中选择最优的打孔组合方式，在满足DRC的前提下，最小化布线空间。

最后生成的结果如图6所示，可以看到通孔距离M1层和M2层的障碍物分别为0.141和0.135，均大于0.1的spacing约束。

利用本发明的布线方法进行布线后，所有通孔中的cut的数量等于用户给定的最小Cut数量约束的值；在布线过程中实时查询打孔区域，节省存储空间；布线过程中考虑到所有通孔排列方式，从中选择最优的打孔组合方式，在满足DRC的前提下，最小化布线空间。

本发明还提供一种满足最小Cut数量约束的布线的装置，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的程序，所述处理器运行所述程序时执行上述的满足最小Cut数量约束的布线方法的步骤。

本发明还提供了一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行上述的满足最小Cut数量约束的布线方法的步骤，所述满足最小Cut数量约束的布线方法参见前述部分的介绍，不再赘述。

本领域普通技术人员可以理解：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (10)

1.一种满足最小Cut数量约束的布线方法，其特征在于，包括以下步骤：

1）读取布线参数，确定各个布线层的最小通孔数的约束；

2）将需要连接的源点加入到待扩展结点的队列中，确定待扩展结点的队列；

3）确定当前费用最小的结点，沿各方向扩展结点，并计算扩展代价；

4）根据计算的代价总值最小的原则生成通孔，进行布线。

2.根据权利要求1所述的满足最小Cut数量约束的布线方法，其特征在于，所述步骤3）进一步地包括以下步骤：

21）根据最小通孔数的约束，确定通孔组合方式，表示为行*列的形式；

22）获取当前层通孔的几何参数，计算不同的通孔组合方式下的查询区域；

23）遍历各个通孔组合方式下的查询区域，判断是否存在障碍物，判断是否会产生DRC，计算代价值。

3.根据权利要求2所述的满足最小Cut数量约束的布线方法，其特征在于，所述几何参数，包括cut的宽度、高度、cut沿x和y方向上的间距、通孔沿x和y方向上的间距。

4.根据权利要求2所述的满足最小Cut数量约束的布线方法，其特征在于，所述查询区域的宽度=cut宽度*通孔中cut的列数+cut沿x方向间距*（通孔中cut的列数+1）+2*通孔沿x方向间距，所述查询区域的高度=cut高度*通孔中cut的行数+cut沿y方向间距*（通孔中cut的行数+1）+2*通孔沿y方向间距。

5.根据权利要求2所述的满足最小Cut数量约束的布线方法，其特征在于，所述步骤23）进一步包括，针对每一种行*列的通孔排布方式，可以根据通孔的其他参数生成top层、bottom层和cut层的矩形，再通过数据结构查询top层、bottom层和cut层的矩形区域内是否存在障碍物，判断是否会产生DRC。

6.根据权利要求2所述的满足最小Cut数量约束的布线方法，其特征在于，所述步骤23）进一步包括：

如果产生DRC则为扩展的结点的代价加上惩罚值；

如果存在一种摆放方式使得区域内无障碍物，则扩展结点不增加额外代价；

如果所有的摆放方式的查询区域内都存在障碍物则不需要增加额外的代价。

7.根据权利要求1所述的满足最小Cut数量约束的布线方法，其特征在于，所述步骤4）进一步地包括，选择使得最后生成的通孔需要的代价最小的打孔组合方式进行打孔、布线。

8.根据权利要求1所述的满足最小Cut数量约束的布线方法，其特征在于，所述当前费用=前一个结点的费用+从前一个结点扩展到当前结点的费用，其中，从前一个结点扩展到当前结点的费用=根据扩展方向产生的基础费用+违反DRC产生的费用。

9.一种满足最小Cut数量约束的布线的装置，其特征在于，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的程序，所述处理器运行所述程序时执行权利要求1-8任一项所述的满足最小Cut数量约束的布线方法的步骤。

10.一种计算机可读存储介质，其上存储有计算机指令，其特征在于，所述计算机指令运行时执行权利要求1-8任一项所述的满足最小Cut数量约束的布线方法的步骤。

Images