一种实现版图验证中密度检查的方法

摘要

本发明涉及一种快速实现版图验证中密度检查的方法，属于IC CAD工具中版图验证领域。密度检查是IC CAD工具版图验证中设计规则检查(DRC)中的一种图形操作。密度检查的基本含义是检查某一层图形的面积在总的区域面积中所占的百分比。有些密度检查要求计算层的图形位于另外一个对照图形层内部时面积计算才有效。它的描述方式是：Density被计算图形层Inside of对照图形层。在这种条件下，密度计算实现难度大。本发明提出了针对上述条件的密度检查实现方法，可以大大提高密度检查有对照层的计算效率。

权利要求

1.版图验证中密度检查的一种快速分桶实现方法，用于检查被计算层图形位于对照图形层内部的面积在对照图形层面积中所占的百分比，其特征在于该方法具体步骤如下：(1)自左向右扫描对照层，计算对照层图形的边框；

(2)按照对照层图形的图形数目确定分桶原则，划分均匀的两维的桶，将对照层图形的边框分配到桶中；

(3)自左向右扫描被计算层，在每个被计算层图形结束时，计算该被计算层图形位于哪个桶内，查找该桶内的对照层图形，针对每个对照图形的边框执行循环步骤(4)、(5)、(6)；

(4)临时层TemLayer1＝该被计算层图形，TemLayer2＝该对照层图形边框所围成的矩形图形，TemLayer3＝And TemLayer1 TemLayer2；

(5)以TemLayer3的面积作为计算密度的分子，以TemLayer2的面积作为计算密度的分母，计算比值；

(6)判断比值是否符合约束，如果符合，该对照层图形即为结果，进行输出。

说明书

一种实现版图验证中密度检查的方法

技术领域

[0001] 密度检查是IC CAD工具中版图验证中设计规则检查(DRC)中的一种图形操作。本发明属于IC CAD工具中版图验证领域。

背景技术

[0002] 集成电路(IC)设计的后期包括版图设计和版图验证，而这两项功能是EDA工具中的重要环节；版图验证是根据版图设计规则、电学规则和原始输入的逻辑关系对版图设计进行正确性的验证并且可以通过对电路和参数的提取，产生电路模拟的输入文件进行后模拟，以进一步检查电学性能。

[0003] 密度检查是版图验证中设计规则检查(DRC)中一种常见的检查，它的基本含义是检查某一层图形的面积在总的区域面积中所占的百分比。当该检查没有其它限制条件时，实现比较简单。但是，有些密度检查要求在计算面积时增加一些附加条件，比较典型的条件是要求计算层的图形位于另外一个对照图形层内部时面积计算才有效，它的描述方式是：

[0004] Density被计算图形层Inside of对照图形层

[0005] 在这种条件下，密度计算实现难度大。本发明提出了针对上述条件的密度检查实现方法，可以大大提高密度检查有对照层(Density Inside of Layer)的计算效率。

[0006] 假设按照一般的实现方法，密度检查中有对照层的实现步骤是：

[0007] 1、形成对照层的图形；

[0008] 2、对每个对照层的图形做循环，执行步骤3、4、5、6、7；

[0009] 3、自左到右扫描版图，寻找被计算图形层和对照图形层的图形公共部分，即计算两层图形“逻辑与”的结果；

[0010] 4、将步骤3的结果作为新的输入层，累加其面积作为计算密度的分子；

[0011] 5、计算当前对照图形层图形边框的面积，以其作为计算密度的分母；

[0012] 6、计算比值；

[0013] 7、判断是否符合约束，得到符合预期的结果，加以输出。

[0014] 这种实现方法的弊端在于实际应用的情况往往是对照图形层的图形数目巨大，由于需要多次循环重复检查，因此计算效率不高。

[0015] 例如，假设被计算图形层的图形数目为10万个，对照图形层的图形数目为10万个，采用上述方法，共需要检查10万x10万＝100亿次图形，计算量十分庞大，效率太低。

[0016] 为了解决上述问题，本发明提出了一种高效的实现方法。

发明内容

[0017] 本发明针对版图验证中密度检查带有对照层(Density Inside Layer)一般方法需要进行mxn次计算(m为对照层图形总数，n为被计算层图形总数)速度较慢的问题，提出了一种高效的实现方法。

[0018] 本发明的总体思路：从密度检查的应用目的出发，将mxn次计算降为a*(m+n)次计算(m为对照层图形总数，n为被计算层图形总数，a为常数，它远远小于m，n)。被计算层、对照层分别扫描，只处理一遍。为了快速确定被计算层位于哪个对照层的范围内，利用版图分布具有均匀性的原理，引进桶的概念，确定较优的分桶方案，确保每个桶中的对照层图形数量较少，达到迅速定位的效果。每个被计算层图形一次只与一个有交迭关系的对照层图形做“逻辑与”。

[0019] 本发明包含以下主要步骤：

[0020] 1、自左向右扫描对照层，计算对照层图形的边框；

[0021] 2、按照对照层图形的图形数目确定分桶原则，划分均匀的两维的桶，将对照层图形的边框分配到桶中；

[0022] 3、自左向右扫描被计算层，在每个被计算层图形结束时，计算该被计算层图形位于哪个桶内，查找该桶内的对照层图形，针对每个对照图形的边框，执行循环步骤4、5、6；

[0023] 4、临时层TemLayer1＝该被计算层图形，TemLayer2＝该对照层图形边框所围成的矩形图形，TemLayer3＝And TemLayer1 TemLayer2；

[0024] 5、以TemLayer3的面积作为计算密度的分子，以TemLayer2的面积作为计算密度的分母，计算比值；

[0025] 6、判断比值是否符合约束，如果符合，该对照层图形即为结果，进行输出。

[0026] 上述方法与一般方法的显著不同点在于，一般方法为了寻找两层图形之间是否有公共部分，需要遍历搜索所有的图形，而本方法，寻找两层图形的公共部分，仅仅需要搜索图形临近区域的相关图形，大大减少了计算量，提高了计算效率。

[0027] 例如，假设被计算图形层的图形数目为10万个，对照图形层的图形数目为10万个，采用本发明方法，假设在两维空间上划分了均匀的100x100个桶，平均每个桶内有10个图形。在寻找对照层图形与被计算层图形的公共部分时，平均每个图形只需要查找10遍，就可以查找完毕。总的查找次数为：10x(10万+10万)＝200万次，远远小于一般方法的10亿次。

附图说明

[0028] 图1原始版图

[0029] 图2对照层图形的边框

[0030] 图3分桶方案

[0031] 图4在桶内检查密度

[0032] 图5临时层TemLayer1

[0033] 图6临时层TemLayer2

[0034] 图7临时层TemLayer3

[0035] 图8结果层具体实施方式：

[0036] 以下结合附图说明本发明具体实施方式。设原来的版图如图1所示，图中所示的layer1为被计算层，layer2为对照层。假设命令为DENSITY layer1 constaint Inside of Layer layer2。

[0037] 第1步自左向右扫描layer2，计算layer2图形的边框。结果如图2所示；

[0038] 第2步按照layer2图形的图形数目确定分桶原则，划分均匀的两维的桶，将layer2图形的边框分配到桶中。结果如图3所示；

[0039] 第3步自左向右扫描layer1，在每个layer1图形结束时(扫描线位于layer1图形在X方向上最靠右的线段的右端点时)，计算该layer1图形位于哪个桶内，查找该桶内的每个layer2图形的边框，执行步骤4、5、6。结果如图4所示；

[0040] 第4步临时层TemLayer1＝该layer1图形，TemLayer2＝该layer2图形边框，TemLayer3＝And TemLayer1 TemLayer2。TemLayer1结果如图5所示。TemLayer2结果如图6所示。TemLayer3结果如图7所示；

[0041] 第5步以TemLayer3的面积作为计算密度的分子，以TemLayer2的面积作为计算密度的分母，计算比值；

[0042] 第6步判断比值是否符合约束，如果符合，该对照层图形即为结果，进行输出。结果如图8所示。

[0043] 通过本发明公开的一种快速实现版图验证中密度检查的方法，提出了针对具有对照层(Density被计算图形层Inside of Layer对照图形层)的密度检查实现方法，大大提高了密度检查有对照层的计算效率。