[go: up one dir, main page]

CN1684073A - 允许进行与尺寸相关的规则检查的集成电路设计建模 - Google Patents

允许进行与尺寸相关的规则检查的集成电路设计建模 Download PDF

Info

Publication number
CN1684073A
CN1684073A CNA2004100947440A CN200410094744A CN1684073A CN 1684073 A CN1684073 A CN 1684073A CN A2004100947440 A CNA2004100947440 A CN A2004100947440A CN 200410094744 A CN200410094744 A CN 200410094744A CN 1684073 A CN1684073 A CN 1684073A
Authority
CN
China
Prior art keywords
core
interval
edge
size
shape
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CNA2004100947440A
Other languages
English (en)
Inventor
李·M·帕斯特尔
林德特·M·胡伊斯曼
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of CN1684073A publication Critical patent/CN1684073A/zh
Pending legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01R—MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES
    • G01R31/00—Arrangements for testing electric properties; Arrangements for locating electric faults; Arrangements for electrical testing characterised by what is being tested not provided for elsewhere
    • G01R31/28—Testing of electronic circuits, e.g. by signal tracer
    • G01R31/317—Testing of digital circuits
    • G01R31/3181—Functional testing
    • G01R31/3185—Reconfiguring for testing, e.g. LSSD, partitioning
    • G01R31/318533—Reconfiguring for testing, e.g. LSSD, partitioning using scanning techniques, e.g. LSSD, Boundary Scan, JTAG
    • G01R31/318566—Comparators; Diagnosing the device under test
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10—Digital recording or reproducing
    • G11B20/18—Error detection or correction; Testing, e.g. of drop-outs
    • G11B20/1816—Testing

Landscapes

  • Engineering & Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Tests Of Electronic Circuits (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Abstract

本发明涉及允许进行与尺寸相关的规则检查的集成电路设计建模。本发明提供一种对IC设计建模的方法、系统和程序产品，以将IC设计建模为以一致的方式包括诸如IC形状的局部宽度和间隔之类的尺寸。具体地，本发明使用沃龙诺依图的核心部分来将形状的边缘分割为区间，并向每一个区间分配至少一个尺寸，比如局部宽度和间隔。可以使尺寸分配作为对宽度和间隔设置的任何所需的定义，例如数值或者与连续尺寸相关的设计规则。可以进行以宽度和间隔的任意函数形式给出的与尺寸相关的间隔规则的设计规则检查。本发明可以应用于VLSI形状的宽度和间隔比较重要的任何地方，例如相对于单个边缘、相邻边缘、相邻形状，以及/或者对于在IC设计的不止一层当中的边缘。

Description

允许进行与尺寸相关的 规则检查的集成电路设计建模
技术领域
本发明总体上涉及集成电路设计，尤其是允许进行与尺寸相关的规则检查的集成电路设计建模。
背景技术
超大规模集成(VLSI)电路是使用计算机辅助设计系统进行设计的，所述系统允许设计者在进行更为昂贵的集成电路(IC)制造之前生成和测试电路设计。为了确保IC的正确设计，每一种设计系统和/或IC格式都包括每一个电路设计都必须满足的一套设计规则。也就是，每一个IC设计必须通过一个设计规则检查(DRC)。一种基本的DRC操作是与尺寸相关的规则检查(dimension-dependent rulechecking)。与尺寸相关的规则检查确保IC的部件的尺寸，也就是宽度和间隔，满足具体的尺寸参数，例如大小范围。在最为重要的与尺寸相关的规则检查中，有与宽度相关的规则和与间隔相关的规则，这些规则是为了防止部件过大、过小、过于靠近或者过于远离。
当前的DRC工具使用一维清晰度(可见性)(one-dimensionalvisibility)或者标准“形状膨胀”(shape-expand)和“形状收缩(shape-shrink)操作来产生VLSI形状的宽度和间隔。IC设计方面的进展导致IC部件的各种形状越来越复杂而不是简单的矩形。结果，定义什么是一个形状的“宽度”或者什么是形状之间的“间隔”变得越来越困难和不一致。尤其是，对任何多边形的宽度的传统数学定义是任意两个平行支撑线(line of support)之间的最小距离。这个定义意味着对于任何形状，基于其凸包(convex hull)，只有唯一的宽度。(注意，一般，IC非凸多边形可能比相关的凸包更“窄”，例如L形)。但是，这个定义对于非凸形状中的DRC来说并不合适，因为它对整个形状只分配唯一的凸包宽度。
在DRC方法使用一维(1D)可见性(清晰度)的情况下，竖直边缘附近的宽度或者间隔常常被其它竖直边缘判断为在水平方向该边缘是“可见”的。这种方法在某些情况下就足够了，但是其常常导致不一致的结果，因为1D可见性不适合表征形状的宽度。例如，对于任何到另一个边缘的距离在沿着长度的方向变化的边缘，导致宽度不一致或者不可确定。当前，对于除了矩形之外的任意形状的“宽度”，还没有一致的令人满意的定义。上述问题对于与间隔相关的设计规则是一样的。
对于“膨胀”和“收缩”操作，大多数现代形状处理工具具有将形状膨胀或者收缩给定的常量的功能。这些操作的结果被递增地用于确定宽度和间隔。这样的方法有几个问题。首先，膨胀和收缩操作只能对由轴线平行边缘构成的形状得到正确的宽度。一旦存在锐角，则结果会不正确。另外，膨胀和收缩操作只是在凸形的情况下简单。对于一般的非凸形状，即使是正交的，膨胀和收缩操作也比较困难，在计算时间方面更为昂贵。另外，膨胀和收缩操作只对给定的常量起作用，因此，对于标准形状一般需要对这些功能的许多调用。结果，与尺寸相关的规则检查变得非常麻烦和耗时。
与间隔相关的规则检查的一种方法是以由少量“桶”(散列元，存储区，bucket)给出的离散形式表达规则。“桶”是基于预定数值或者预定数值的范围的规则的实现。例如，用于间隔的“桶”可以要求：如果至少一个线的宽度大于一个值W，则间隔大于一个尺寸S。在另一个例子中，如果两条线都大于一个值W，则间隔大于或者等于尺寸S。使用膨胀/收缩方法来检查这种规则麻烦而费时。以函数的形式给出的(也就是非步骤或者非“桶装”的(non-bucketed))与宽度相关的间隔规则的检查通过应用这种方法会更加麻烦(如果还可能的话)。例如，不知道如何实现这样的与宽度相关的规则：要求两个相邻形状之间的间隔必须为其中一个形状的最大宽度的2倍减去10个单位。
除了上述问题之外，“桶”的使用导致IC设计难以制造。尤其是，使用“桶”的IC设计规则的实现导致两个问题。第一个问题是基于这样的前提条件：设计规则是在可制造的工艺的建立之前建立的，因此，设计规则代表了在设计时进行的工艺的假设和约定。但是，一般，工艺约束条件通常在实现制造时会偏差一些量。因此，合乎设计规则的布图设计可能在制造工艺的“工艺能力窗口”之外。要避免这个问题，就意味着所有特定的“桶”都在制造工艺能力范围之内，这导致第二个问题：生产率问题总是“放在桌面上”。尤其是，“桶装的”(bucketed)设计规则促使设计者所提供的是极限而不是最优值(假设工艺不允许与“桶”相同的功能)。尤其是，设计者实际上基于“桶规范(bucketspecifications)”来进行计算以确定使用什么尺寸的线路，而不是使用使功能性和性能要求最优化的尺寸的线路。结果导致并非最优的IC设计。
另一个与DRC相关的问题是，设计规则汇集了各种物理现象，每一种物理现象可能要求宽度和间隔的定义稍有不同，只要对这些定义能够以一致的方式加以对待。例如，在某些情况下，一种形状可能需要尽可能被评估为“瘦”，而在其它情况下它可能需要被尽可能评估为“肥”。当前，没有一种机制用于对DRC应用不同的宽度和间隔定义。
鉴于前述，在现有技术中需要一种对IC设计建模的方式，以允许进行与尺寸相关的设计规则检查而不管形状。如果能够实现宽度和间隔的不同定义也将是很有益的。
发明内容
本发明提供一种对IC设计建模的方法、系统和程序产品，以将IC设计建模为以一致的方式包括诸如IC形状的局部宽度和间隔之类的尺寸。具体地，本发明使用沃龙诺依图的核心部分来将形状的边缘分割为区间，并向每一个区间分配至少一个尺寸，比如局部宽度和间隔。可以使尺寸分配作为对宽度和间隔设置的任何所需的定义，例如数值或者与连续尺寸相关的设计规则。可以进行以宽度和间隔的任意函数形式给出的与尺寸相关的间隔规则的设计规则检查。本发明可以应用于VLSI形状的宽度和间隔比较重要的任何地方，例如相对于单个边缘、相邻边缘、相邻形状，以及/或者对于在IC设计的不止一层当中的边缘。
本发明的第一方面是一种用于集成电路设计的建模方法，包括下述步骤：将集成电路设计中的形状的边缘分割为多个区间；以及向每一个区间分配至少一个尺寸。
本发明的第二方面是一种集成电路建模系统，包括：将集成电路设计中的形状的边缘分割为多个区间的装置；以及向每一个区间分配至少一个尺寸的装置。
本发明的第三方面是一种计算机程序产品，包括计算机可用的介质，其中实现有用于对集成电路建模的计算机可读程序代码，该程序产品包括：将集成电路设计中的形状的边缘分割为多个区间的程序代码；以及向每一个区间分配至少一个尺寸的程序代码。
本发明的第四方面是一种集成电路检查规则评估系统，包括：将集成电路设计中的形状的边缘分割为多个区间的装置，该分割装置包括：使用第一度量体系生成形状的核心沃龙诺依图的装置，以及根据所述核心沃龙诺依图分割所述边缘的装置；使用第二度量体系向每一个区间分配至少一个尺寸的装置；以及使用所述至少一个尺寸评估检查规则的装置。
从下面对本发明的实施例的详细说明可以明了本发明的前述以及其它特点。
附图说明
下面结合附图详细描述本发明的实施例，其中类似的附图标记表示类似的部件，其中：
图1图示了沃龙诺依图的一个简化的例子；
图2A图示了使用L∞度量体系的一组多边形的外部沃龙诺依图(exterior Voronoi diagram)；
图2B图示了使用L∞度量体系的一个多边形的内部沃龙诺依图(interior Voronoi diagram)；
图3图示了使用欧几里德度量体系的锐角多边形(acute polygon)的内部沃龙诺依图(interior Voronoi diagram)；
图4图示了图3的锐角多边形使用L∞度量体系的内部沃龙诺依图(interior Voronoi diagram)：
图5A-5B图解了L∞度量体系的描述；
图6的为本发明的建模系统的框图；
图7是图6的建模系统的操作的流程图；
图8A-8E图解了对于图3的锐角多边形，图7的方法的用于说明的实施方式；
图9A图示了图2A和2B的形状的用于说明的局部宽度和间隔；
图9B-9C图示了图7的方法分别对于图2A和2B的一组多边形和一个多边形的说明性实施方式；
图9D图示了具有由凹顶点造成的瘦颈部的多边形的细节；
图10A-10D图解了说明性的包括非直角的边缘布置；
图11图示了包括工具L∞度量体系进行分割的图4的形状；
图12图示了具有凹顶点的多边形的细节；
图13图示了使用L∞度量体系进行分割、使用欧几里德度量体系分配尺寸的图4的形状；
图14A-14F图示了用于更窄的分割的图2B和图9C的形状。
具体实施方式
为了清楚的目的，下面的说明包括以下部分：I.概述；II.一般定义；III.系统概述；IV.方法；以及V.结论。
I.概述
IC设计规则计算机辅助设计(CAD)工具一般是用IC形状的边界工作的。本发明对此事实的利用是将形状的边缘分割为多个区间。然后，工具从形状的内部和/或外部的局部沃龙诺依图得到的离散相邻几何关系，对每一个区间分配一个尺寸，在一个实施例中该尺寸包括局部宽度和局部间隔。换句话说，可以将局部宽度和局部间隔映射到形状的边缘上。结果，形状的每一个边界点可以被分配一个唯一的宽度标记和一个唯一的间隔标记。
一个定义集来判断如何分割边缘以及如何对一个边缘分配宽度和间隔。定义集可以随着设计规则而变化。因此，宽度/间隔的分配可以反映有关设计规则的性质，不需要对于所有规则都是一样的。另外，每一个区间可以具有恒定的宽度/间隔值，或者可以被分配一个函数，比如到另一个边界/角部的距离，另一个尺寸的因子或者其它函数。一旦获得了宽度和间隔，它们就可以进行相互比较，以检查它们之间的任何种类的关系，尤其是，可以检查是否依从了连续尺寸相关设计规则(continuous dimension-dependent design rules)。
II.一般定义
如上所述，本发明应用沃龙诺依图来确定形状的尺寸也就是局部宽度和间隔。所谓“沃龙诺依图”可以是取决于其所应用的结构的多种形式。在最简单的例子中，见图1，一组位置(点)10a-10d的沃龙诺依图8包括更接近一个相应的位置例如10a而不是任何其它位置10b-10d的所有点。所得到的沃龙诺依图8包括区域12a-12d的一个集合，这些区域称为“沃龙诺依单元”(Voronoi cells)，它们将位置10a-10d所在的平面也就是纸面分割开。每一个沃龙诺依单元为凸多边形的形状(仅对点位置)，其边缘为位置10a-10d的等分线。每一个沃龙诺依单元12a-12d对应于一个位置10a-10d之一(或者为位置10a-10d之一所拥有)。同样，一个单元，例如12a中的所有点更接近对应的位置10a，而不是更接近任何其它位置10b-10d。
图2A-2B分别图解了正交形状的外部沃龙诺依图20和内部沃龙诺依图30。图2A图解了一组分离的多边形位置22A-22F，图2B图解了多边形122。图3和图4图解了一个锐角多边形形状34的内部沃龙诺依图40、90。在这里使用的术语“边界”指的是形状的外边界或者线，“边缘”指的是边界的组成部分。
如图2A所示，一组分离的多边形位置，也就是多边形22A到22F的外部沃龙诺依图20包括将包含多边形22A-22F的平面分割为沃龙诺依单元24A-24F。每一个沃龙诺依单元，例如多边形22A的24A，包括更接近多边形22A而不是任何其它多边形22B-22F的点的轨迹。也就是，它包括相邻多边形22B-22F(其它的未图示)的等分线。一个位置例如多边形22A的沃龙诺依单元被表示为一个“区”(reg(s)，“牌照”)，多边形22A被称为“区(牌照)”的拥有者。沃龙诺依图20的与两个沃龙诺依单元24A和24B邻接的一部分23被称为“沃龙诺依边缘”，包括单元的拥有者之间的等分线的部分。三个或者更多沃龙诺依边缘23相会的点26称为“沃龙诺依顶点”。虚线(阴影线)表示多边形22A-22F的分割，使得多边形22A的每一个边界，例如28A具有沃龙诺依图20的相应部分23。
见图2B、图3和图4，形状34(图2B中的多边形122)的内部的内部沃龙诺依图30、40、90被称为“中轴线”。形式上，“中轴线”是多边形内部的点[q]的轨迹，使得对象的边界上有至少两个点与[q]等距离并最接近[q]。
图1和图3的上述沃龙诺依图的说明是基于欧几里德度量体系。也就是，沃龙诺依距离是基于欧几里德度量体系的。本发明如下面所述，也可以基于L∞(L-infinity，L无限大)度量体系实现沃龙诺依图。见图5A到5B，在L∞度量体系中，两个点(图5A)p＝(xp，yp)和q＝(xq，yq)之间的距离为p和q之间的水平距离和垂直距离中的大值，也就是：
d(p，q)＝max[|xp-xq|，|yp-yq|]
直观地，L∞距离是接触p和q的最小方形的大小。任意两点之间的L∞距离小于或等于两点之间的欧几里德距离。另外，在L∞度量体系中，点p和线l(图5B)之间的距离是d(p，l)＝min[d(p，q)，q∈l]。两个多边形元素(点或者线)的L∞等分线是与两个元素具有相同的L∞距离的点的轨迹。
回到图4，基于L∞度量体系图解形状34的中轴线90。(图2B的中轴线30也是基于L∞度量体系)。通过比较图3和图4很容易认识到，L∞度量体系的使用简化了多边形对象的沃龙诺依图90，使之计算起来更简单。L∞沃龙诺依图是直线段的“骨架”，具有线性组合复杂性。尽管下面对本发明的方法的描述是基于一种或者另外一种度量体系，但是应当认识到，本发明的概念和运作不管使用的度量体系为何都是一样的，本发明不应限于任何特定的度量体系，而只受所附权利要求的限制。
对沃龙诺依图及其在临界区(关键区域)判断方面的应用的进一步说明可以见美国专利6,317,859和6,178,539，它们在此被引为参考。还可参考E.Papadopoulou等人的″The Leo Voronoi Diagram ofSegments and VLSI Applications，″International journal ofComputational Geometry and Applications，Vol.11，No.5，2001，503-528。
回到图2A、2B、3和4，沃龙诺依图30、40和90的“核心”50(用粗线表示)是在排除“不感兴趣的部分”之后剩下的部分。一般“不感兴趣的部分”(细线)是沃龙诺依边缘的与形状的边界52(图2B、3和4)相接的部分，例如相邻边缘之间的等分线。在具有锐角(也就是凹顶点)的IC形状的情况下，如图3和图4所示，“不感兴趣的部分”可以是连接到锐角56的等分线54的与该锐角56相隔特定距离的部分。从核心50排除的部分可以是灵活的，与应用相关。为了简明起见，核心50可包括不与形状34的边界52连接的所有沃龙诺依边缘23，也就是非相邻边缘之间的所有等分线和非退化等分线(non-degenerate bisectors)。退化等分线是两个共线水平/垂直边缘之间的等分线。但是，应当清楚，核心50是沃龙诺依图30、40、90的“令人感兴趣”的子集，其中，对是否“令人感兴趣”的分类可以对每一种应用而变化。
“点缺陷”是由微粒比如灰尘或者其它污染物在材料和设备中造成的，被分为两种：“多余材料”缺陷导致不同导电区例如图2A的22A-22F之间的短路，“缺失材料”缺陷导致例如图2B的多边形122中的开路。换句话说，“短路”是导致与形状的外部中的某些其它边缘桥接的缺陷，“开路”是导致形状的内部中的空隙(空白)的缺陷。见图3，点缺陷可以被建模为圆圈(仅对欧几里德度量体系)或者方形(图2A、2B和4中的L∞度量体系)形式的“核心元素(coreelement)”60。也就是，核心元素60可以，取决于所使用的度量体系，用圆圈或者方形表示。由于在实际中点缺陷具有任意形状，方形(L∞度量体系)缺陷模型对于大多数目的来说比较好。术语“核心盘(coredisk)”用来指欧几里德度量体系的圆圈，“核心方形”用来指L∞度量体系的方形，术语“核心元素”是二者的通称。
一个核心元素60在至少两点64接触边界52，并具有被称为核心点62的中心，核心点是形状例如图2B中的多边形122的核心50的成员。每一个核心点62用其到形状的边界52的距离的两倍，也就是其核心元素的直径，加权。也就是，每一个核心点62用相关核心元素60的半径的两倍加权。在欧几里德度量体系中，存在至多一个接触边界点(除了形状的凹顶点之外，凹顶点可以被多个核心元素60接触)的核心盘。与此相对照，在L∞度量体系中，可以有多于一个的方形接触边界点，例如见图12中的点p。具体地，在L∞度量体系中，在核心方形是轴线平行方形(axis-parallel squares)的情况下，沿着轴线平行边界边缘的边界点可以被多于一个的核心方形接触。“方形的半径”被定义为其边长的尺寸的一半。上述加权提供了一种将沃龙诺依图(内部或者外部)的尺寸信息(宽度或者间隔)映射到形状的边界的机制。
在核心点62在形状的内部时，一个核心元素60也可以被称为“最小开度”(minimal open)，因为∈＞0的核心元素60的(也就是由形状形成的线的)任何收缩使得核心元素60停止重叠任何边界点64，从而停止产生开路。∈是任意小的正数，收缩∈的意思是将缺陷的边缘向缺陷的内部移动一个距离∈。类似地，见图2A，在核心点62在形状例如多边形22A、22B的外部的情况下，“核心元素”60也可以被称为“最小短路(minimal short)”，因为核心元素60(也就是两个线之间的间隔)的任何∈＞0(定义同上)的收缩都使得核心元素60停止与形状22A、22B的任何边界点重叠，从而停止产生短路。
“定义集”是一个或者多个允许分割形状的边缘、对每一个区间分配至少一个尺寸(常数值或者函数)的定义。
在下面的说明中，将根据需要提供其它定义。
III.系统概述
见附图。图6是本发明的建模系统100的框图。建模系统100包括存储器112、处理器(PU)114、输入输出设备(I/O)116以及总线118。还可以提供一个数据库120用于存储与处理任务有关的数据。存储器112包括程序产品122，当程序产品122被PU 114执行时，包括将在下面详细说明的各种功能。存储器112(以及数据库120)可以包括任何已知类型的数据存储系统和/或传输介质，包括磁介质、光介质、随机存取存储器(RAM)、只读存储器(ROM)以及数据对象等。另外，存储器112(数据库120)可以驻留在包括一种或者多种数据存储器的单个物理位置，或者可以分布在多个物理系统上。PU 114可以类似地包括单个处理器或者分布在一个或者多个位置上的多个处理器。I/O 116可以包括任何已知类型的输入输出设备，包括网络系统、调制解调器、键盘、鼠标、扫描仪、语音识别系统、CRT、打印机、磁盘驱动器等。系统100中还可以包括另外的部件比如缓存、通信系统、系统软件等。
如图6所示，程序产品122可以包括区间分割器123，后者具有核心沃龙诺依图发生器124和分割发生器126以及尺寸分配器128。可以提供至少一个定义集130供系统100使用，如下所述。可以提供设计规则检查器132作为系统100的一部分，它或者可以被设计为独立的系统。其它系统部件134包括实现本发明所需的在这里没有描述的任何其它程序产品，例如用户接口、通信等。
将IC设计提供给建模系统100，并根据下述方法对其建模。应当认识到，建模系统100可以是独立的系统，或者作为现在已知的或者以后开发的较大的IC设计系统的一部分。
IV.方法
见图7，下面描述建模系统100的操作的流程图。下面首先描述图7的对图3和图4最初图示的、也示于图8A-8D的(任意锐角多边形)形状34的处理。形状34不太可能出现于VLSI设计中，但是有助于很好地理解整个方法。为了进一步方便理解，下面针对欧几里德度量体系描述对形状34的处理。之后结合图9A-9C描述图7的处理，图9A和9C分别类似于图2A和2B，提供了更合适的VLSI设计可能性。在后面的说明中，将说明L∞度量体系的使用。
无论在哪一种情况下，对形状的边界的分割和尺寸分配可以基于定义集130(图6)。对尺寸(宽度和间隔)的定义集可以随应用而变化。另外，所述定义集可能要求分配实际的数字或者是依赖于某些其它尺寸或者特性的函数。鉴于前述，下面讨论的定义集只是用于说明而已。
总的来说，所述方法包括：步骤S1：生成核心沃龙诺依图；步骤S2：将边缘分割为区间(宽度和/或间隔)；步骤S3：分配尺寸；步骤S4：进行设计规则检查。为了清楚简明的目的，下面在一个部分中描述分割和尺寸的分配。该部分包括有关不同的度量体系、形状结构和特殊情况的小节。
1.生成核心沃龙诺依图
见图8A，在第一步骤S1(图7)中，对于IC的给定层A的形状，用核心沃龙诺依图生成器124(图6)分别生成内部和/或外部沃龙诺依图40(也就是中轴线)和92的核心100、102。步骤S1可以被分为用于生成沃龙诺依图的步骤S1A，以及用于确定该沃龙诺依图的核心的步骤S1B。核心沃龙诺依图100、102的生成是基于欧几里德度量体系。可以例如根据在前面引为参考的美国专利No.6,317,859中描述的算法完成沃龙诺依图40、92的生成。可以根据一组用户定义的只选择各沃龙诺依图的感兴趣的部分的规则来完成核心100、102的生成。例如，如上所述，“不感兴趣的部分”(细线)可以是沃龙诺依边缘的连接到形状的边界52的部分，例如相邻边缘之间的等分线54。在IC形状具有锐角的情况下，“不感兴趣的部分”可以是连接到锐角56的等分线54的与锐角56相隔一定距离的一部分。同样，从核心100、102排除的可以是灵活的、与应用相关的。
图2A和2B还图示了分别用于外部和内部沃龙诺依图的核心50。但是，这些沃龙诺依图的生成是基于L∞度量体系。对于图2B，“不感兴趣的部分”(细线)可以是沃龙诺依边缘的连接到形状的边界52的部分，例如相邻边缘之间的等分线54。
2.分割为区间并分配尺寸
A.欧几里德度量体系的任意(锐角)形状多边形
回到图8A-8D，结合图7，图示了图3的形状34以用于说明所述处理。另外，提供了另一个形状94以讨论外部沃龙诺依图92。
对于任意形状的多边形，用于说明目的的定义集可以是：
定义1(任意情况)：形状P的边界上的点p的宽度是在形状P的内部中接触p的最小核心盘的尺寸。如果没有接触p的核心盘，则p被分配到当形状P的边界接下来在特定方向(顺时针或者逆时针)时核心盘所接触的最近的边界点的宽度。
定义2(任意情况)：形状P的边界上的点p的间隔是形状P的外部中接触p的最小核心盘的尺寸，如果没有接触p的核心盘，则p被分配到当形状P的边界接下来在特定方向(顺时针或者逆时针)时核心盘接触的最近的边界点的间隔。
在第二步S2(图7)，每一个形状的每一个边缘被分隔发生器126(图6)分割为至少一个区间。在一个实施例中，该步骤包括将每一个边缘用内部核心沃龙诺依图100分割为宽度区间，用外部核心沃龙诺依图102分割为间隔区间。见图8B，图示了分割为尺寸区间，在这里的情况下是宽度区间的形式的w1到w26的情况。
在一个实施例中，通过对核心100的顶点v(以后称核心顶点)投影(虚线投影104)(只图示了一部分)到形状34的相应边界投影点106(只图示了一部分)来进行分割。在这个例子中，应用分割规则来处理具体情况。分割规则一个举例的集合如下：
a)对于等分边缘e1和e2的核心等分线的每一个核心顶点v，将核心顶点v投影到两个边缘e1和e2，使得每一个投影都垂直于相应的边缘。见图8B，等分边缘52A、52B的核心等分线100A的核心顶点的一个例子是核心顶点v1。核心顶点v1到两个边缘52A、52B的投影104A、104B被图示为每一个投影104A、104B垂直于相应的边缘52A、52B。结果是宽度区间w15和w16在边缘52A上，区间w4和w6在边缘52B上。
b)对于等分边缘e1(或者多个边缘)与形状的凹顶点的核心等分线的每一个核心顶点v，将核心顶点垂直于边缘e1(或者多个边缘)投影。“凹顶点”是这样的顶点：连接形成该顶点的边缘的点的线段完全在该形状的外部，也就是顶点形成的角度大于180度。
见图8B，图示了等分边缘52C的核心等分线100B的一个举例的核心顶点v2，以及形状34的凹顶点w7。(注意，凹顶点被标记为区间，因为每一个凹顶点代表一个区间，这将在下面详细讨论)。在本例中，从核心顶点v2垂直于边缘52C进行投影104C，从而将边缘52C根据投影104C分割为宽度区间w12、w13。类似地，图示了等分边缘52A的核心等分线100C的核心顶点v3，以及凹顶点w7。从核心顶点v3垂直于边缘52A进行投影104D，形成区间w14和w15。根据核心顶点v2对区间w12和w13如下所述分配尺寸，并根据核心顶点v3对宽度区间w14和w15分配尺寸。
c)每一个凹顶点是其自己的区间。在图8B中，凹顶点被标记为区间w5、w7和w23。
回到图8B，投影104在形状的边界上确定了一系列区间。基于上述投影，产生区间w1到w26。应当认识到，可以修改投影规则以适应应用，上述规则只是用于说明的目的。
在示于图8C到8D的另一个实施例中，可以通过下述操作进行分割：生成中心在每一个核心顶点v的核心盘60，确定在核心盘60接触边界52而形成点的地方的点。图8C图示了对于形状34的多个核心点(不一定是核心顶点)的最小核心盘60(欧几里德圆圈)。在欧几里德度量体系中，至多有一个核心盘60接触边界点106(除了凹顶点外)。(在L∞度量体系中，有多于一个的核心盘60接触边界点。这里本发明可以使用最小核心盘60，以便分配尽可能小(最窄)的宽度/间隔值。但是，用户可以选择使用最大核心盘的尺寸，如果凹顶点的局部宽度要被忽略的话。)见图8D，本实施例提供了向边界52的核心顶点投影作为等效的分割，如上所述。
尽管上面的说明针对的是宽度区间，但是应当认识到，该过程可以对外部核心沃龙诺依图92重复，以便产生间隔区间。也就是，如图8B所示，从核心沃龙诺依图92的核心顶点向边界52投影以产生间隔区间例如s1。或者，如图8D所示，可以在每一个核心顶点画出核心盘60，核心盘接触边界52的点可以被用来产生间隔区间例如s1。？？？？？
接下来，在步骤S3，用尺寸分配器128(图6)根据选定的定义集130(图6)对每一个区间分配尺寸。应当认识到，尽管是用上面提供的特定定义集来分配实际的尺寸，但是定义集也可以分配作为函数的尺寸，例如宽度是尺寸X的宽度的两倍减去10nm。也就是，一个定义集可以包括一组分割然后分配函数的规则。对于沿着一个区间的每一个点p，投影到p的核心点，称为c(p)，限定一个尺寸。例如，返回图8B，例如在区间w9、w10、w11中的任意点的宽度被分配的一个尺寸等于相应的核心点，也就是顶点v4的加权(在这里，加权等于中心在v4的核心盘的直径)。这与上面的定义1是一致的。回到区间w6，沿着该区间分配给一个点p1的宽度具有由中心在核心点c(p1)的核心盘的直径给出的可变宽度。这与上面的定义1也是一致的。还根据定义1，对于不被核心盘接触的点p4，所分配的尺寸是当形状34的边界接下来在特定方向(顺时针或者逆时针)时核心盘所接触的最近的边界点的宽度。注意，任何沿着区间w9、w10、w11的点，核心点是核心顶点v4。
对于如上所述的凹顶点w5，w7和w23，每一个凹顶点本身是一个区间。在这种情况下，尺寸的分配是基于核心点的数量(或者核心点的权重)，也就是，对于两个相邻边缘中的每一个恰好是两个核心点，并且可能有由等分该凹顶点以及其它凹顶点(如果有的话)的沃龙诺依边缘产生的多个核心点。在一个实施例中，所分配的尺寸是基于这些核心点的权重中的最小值。例如，如图8E所示，两个凹顶点A、B可以在形状中产生一个非常瘦的颈部。对于凹顶点A，确定沿着核心顶点A产生的核心等分线的最小权重的核心点。例如，在图8E中，核心顶点A和B产生一个核心等分线100D(在箭头之间)，顶点A、B被赋予所图示的核心盘60的权重。
间隔尺寸的分配的方式是类似的。例如，如图8B所示，对于边缘52A上的点P2，该点的间隔是投影的核心点c(p2)也就是最大的核心盘接触点P2的权重，也就是从核心点c(p2)到点P2的距离的两倍。如果没有核心盘接触一个点，例如点P3，则所分配的间隔是核心盘所接触的最近边界点的间隔。
B.实用L∞度量体系的正交(VLSI)形状多边形
下面结合图2A、2B、9B、9C和9D描述实用L∞度量体系应用于正交形状的方法。用于正交形状多边形比如图2A-2B最初所示的多边形的方法与用于任意多边形的方法相同。但是，可以改变定义集以适应不同的形状，如下所述。图9A用双箭头分别图示了对于图2A和图2B所示的形状22A-22F的组合以及122，用于说明目的地重要局部宽度和间隔。图2A和2B图解了核心沃龙诺依图50，图9B和9C图示了实用核心沃龙诺依图50来分割和分配尺寸，如下所述。
如上所述，下面的说明将实用L∞度量体系而不是欧几里德度量体系。L∞度量体系的沃龙诺依图在实施时的计算比欧几里德度量体系容易得多。另外，大量的VLSI形状中包括轴线平行边缘或者倾斜+/-1(slope+/-1)(正交-45形状(ortho-45 shapes))的边缘。在这种情况下，L∞度量体系非常合适并且使用简单。在一般的IC设计包含不同于正交-45形状的趋向的情况下，容易进行到正交-45形状的近似以计算L∞度量体系沃龙诺依图。
可以根据提供“分割分布”的定义集来确定内部尺寸。对于较大的分割，在正交多边形的情况下，如图9B-9C所示，定义集可以是基于“最大空盘(方形)”分割分布(partitioning profile)。注意，下面的定义是从定义1和定义2在考虑到下述情况的前提下得到的：在L∞度量体系中接触正交边缘的核心方形不需要象在欧几里德的情况下那样是唯一的。一个定义集如下：
定义3(正交情形)：沿着形状P的边缘e的任意边界点p的宽度为完全被包含在P的内部的(沿着e的)接触p的最大方形的尺寸。
定义4(正交情形)：沿着形状P的边缘e的任意边界点p的间隔为完全在自由空间中(也就是不与P或者任何其它形状相交)的(沿着e的)接触p的最大方形的尺寸。
凹形角部是一种特殊情况，类似于欧几里德情形下的凹顶点。具体地，凹形角部具有与入射边缘上的任何其它点p一样的宽度/间隔，并且还具有一个角度宽度/间隔。因此，提出了下述定义来解决凹形角部的问题：
定义5(正交情形)：形状P的凹形角点p的角部宽度为完全被包含在P内部的角部在p的最大方形的尺寸。凹形角部p的宽度为入射到p的两个边缘的宽度和p的所述角部宽度中的最小值。
定义6(正交情形)：形状P的凹形角点p的角部间隔为完全被包含在自由空间中的角部在p的最大方形的尺寸。凹形角部p的宽度为入射到p的两个边缘的间隔和p的所述角部间隔中的最小值。
(应当认识到，可以改变所述定义集，通过对每一个顶点使用尽可能小的核心方形分割分布来确定区间分割和尺寸分配，来形成更小的区间和更小的尺寸。这导致对每一个边缘有更多的区间)。回到本发明的方法，在第二步骤s2(图7)，用分割发生器126将每一个形状的每一个边缘分割为尺寸区间。在一个实施例中，该步骤包括使用内部核心沃龙诺依图50(图2B)分割为宽度区间，以及使用外部核心沃龙诺依图50(图2A0分割为间隔区间。
回到图2A-2B，对于正交形状的多边形，分割为尺寸区间的操作包括评估或者扫描边缘例如边缘e的沃龙诺依单元，以识别该边缘e产生的沃龙诺依核心顶点v。例如，见图2B，多边形70的边缘e具有五个与之相邻的沃龙诺依顶点v1，v2，v3，v4，v5，并且，如图2A所示，多边形22A的边缘f具有与之相邻的沃龙诺依顶点v4，v5，v6。对于每一个遇到的沃龙诺依顶点v，如图2A和2B所示，生成中心在沃龙诺依顶点v的核心方形60。由于沃龙诺依图的生成是使用L∞度量体系，核心元素是方形。核心方形的边长为沃龙诺依顶点的权重的两倍，也就是与沃龙诺依顶点相同的核心点的权重的两倍。注意，该步骤等效于沿着方向+1和/或-1将核心顶点v投影到形状的边界上。是使用方向+1还是使用方向-1取决于边界边缘的斜率。
在一种实施例中，区间的产生可以基于所要的分割分布(partitioning profile)。这类似于前面对任意形状给出的简化处理。在此实施例中，例如，可以进行分割以使得区间尽可能大(较粗的分割分布)或者尽可能小(窄/精细分割分布)。在前一种情况下，评估每一个顶点的可能的最大空核心方形，以确定区间分割。例如，见图9B，对于边缘f，生成三个间隔区间s1，s2，s3，因为沿着边缘f可能有三个最大方向168，170，172(对于图2A中的核心顶点v4，v5，v6)。类似地，见图9C，对于边缘e，产生三个宽度区间w1，w2，w3，因为沿着形状的边缘e可能有三个最大核心方形162，164，166(对于图2B中的核心顶点v1，v3和v5)。在某些情况下，某些核心方形可能相互重叠，因为一个核心方形是用其整个边而不是只用其角部接触某个轴线平行边界边缘。例如见图9C中的核心方形177和核心方形164。在一个实施例中，对于核心方形的任何重叠部分，只保持最大加权的部分，取消较小的权重的部分。或者，可以实施其它用户定义的规则来处理核心方形重叠的问题。在图9C中，顶点v2和v4的核心方形177、178不提供顶点处的最大核心方形，因此被取消。对每一个边缘的内侧(用于宽度)和外部(用于间隔)重复上述过程。
接下来，在步骤s3，用尺寸分配器128(图6)对每一个区间分配实际尺寸或者函数尺寸。在一个实施例中，步骤S3包括实现一个定义集130(图6)以向每一个区间分配尺寸。如上所述，根据本发明，尺寸(宽度和间隔)的定义集可以根据应用而变化。另外，定义集可以要求分配实际的数字或者是依赖于某些其它尺寸或者特性的函数。应当认识到，用于将每一个边缘分割为区间的特定分割分布不要求实现相应的尺寸分配分布。例如，用户可以根据最大空核心方形分割分布来分割边缘以获得较大的区间，然后根据一个分配尽可能小的尺寸的定义集来分配尺寸。
见图9B，对于多边形22A的边缘f，根据定义4，对三个间隔区间s1，s2，s3中的任意点各分配其相应的三个最大方形168，170，172的尺寸。也就是，一个区间内的任意点p被赋予其独有的核心点c(p)(指的是投影到p的核心点)的权重。对于作为轴线平行边缘的一部分的任意p，c(p)是接触p的最大核心方形的中心。注意，方形168和172的尺寸受到水平尺寸的限制，而方形170受到竖直尺寸的限制。见图9C，对于边缘e，根据定义3，三个宽度区间w1，w2，w3中的任意点p各被赋予相应的最大核心方形(也就是投影到p的核心点)的宽度。注意，方形162和166的尺寸受到水平尺寸的限制，而方形164受到竖直尺寸的限制。
对于角部宽度，如图9C所示，根据定义5，点p的角部宽度是中心在p的、完全被包含在多边形内部的最大方形的尺寸。另外，角部p的宽度是入射到p的两条边缘g、h的宽度以及p的角部宽度中的最小值。对于角部间隔，如图9B所示，根据定义6，多边形22A的角部点p的角部间隔是完全被包含在自由空间中的、角部在p的最大方形178的尺寸。另外，角部p的间隔是入射到p的两个边缘f，i，也就是方形172或者176的间隔，以及p的角部间隔也就是在p的角部的方形178的尺寸中的最小值。注意，角部在角部p的最大空方形178给出了角部p的L∞最近邻元素，它可能与欧几里德最近邻元素不同。但是，二者之间的差异小，实践中可以忽略。一旦识别了p的L∞最近邻元素，就可以以正常的(欧几里德)方式报告数字距离，例如160A而不是160B。图9D中图示了角部宽度确定的另一个例子。在这种情况下，正交形状包括三个在凹形角部p的核心方形360A-C(虚线框)。在这种情况下，核心方形360B会用来限定角部p的宽度。
还应当认识到，可以向每一个区间分配一个确定其尺寸的函数而不是基于其相关核心方形的数字值。例如，图9B中的一个区间s1可以被赋予一个函数，该函数将其宽度分配为多边形228的宽度尺寸的2倍减去10nm。
1)正交-45度的处理
见图10A到10D，图示了包含45度边缘的形状的宽度的各种布置。该方法与上述方法相同。中轴线250、252的不包括在核心中的部分用虚线202图示。
图10A图示了核心250的对应于45度线的核心方形160A-D。在这个例子中，分割是基于沿着边界边缘最大的核心方形260A和260D，形成两个区间。
如图10B所示，对于对应于两个平行的45度线的区间，本发明可以使用一个核心方形200的之间。在两个平行45度线的情况下，欧几里德和L∞度量体系的值之间的差达到最大。为了模拟欧几里德距离，在这个例子中，核心方形的尺寸可以被定义为核心方形的对角线的长度。注意，对角线的长度等于两个平行45°线之间的欧几里德距离。在所有剩下的情况下，用相应的核心方形的边的长度确定尺寸。图10B和10C还图解了能够选择核心，也就是基于对什么感兴趣对什么不感兴趣来选择核心的好处。在图10B中，从核心250排除相邻边缘j，k的等分线202。这样，同一宽度w1可以被分配给整个45度边缘k，即使在接近锐角的地方也是这样。在图10C中，入射到锐角的等分线202的一部分204被包括在核心252中，这样，生成三个区间w1，w2和w3，其中向w3分配小竖直箭头206的常值。同样要注意，一旦获得了区间w2和w3，则可以按照需要分配任何近似欧几里德度量体系的合理的数值。
图10D图解了形成90度角的两个垂直45度边缘的情况，也就是对应于一个旋转的直角。这种情况的处理类似于图10A。
2)使用L∞度量体系的任意(锐角)形状多边形
见图11，图4的任意形状34被图示为包括根据L∞度量体系进行的分割。其中，L∞度量体系被应用于非正交形状，定义集可以是如下：
定义7(任意情形)：沿着形状P的边界的任意边界点p的宽度是在形状P的内部接触p的最大核心方形的尺寸。如果没有接触p的核心方形，则p被赋予核心方形所接触的最近边界点的宽度。
定义8(任意情形)：沿着形状P的边界的任意边界点p的间隔是在形状P的外部接触p的最大核心方形的尺寸。如果没有接触p的核心方形，则p被赋予核心方形所接触的最近边界点的间隔。
如上所述，必须对凹形角部予以特别关注。具体地，凹形角部本身代表一个区间。也就是，它们与边缘中的其它任何点p一样具有宽度/间隔，另外还具有角度宽度/间隔。因此，提出下面的定义来解决角部的问题：
定义9(任意情形)：形状P的凹形角部点p的角度宽度为角部在p的所有核心方形中的最小核心方形的尺寸。
见图12，取决于入射边缘的斜率，角部在一个凹形角部p的核心方形可以最多有三个。在正交情况下，恰好有三个核心方形的角部在p。
定义10(任意情形)：形状P的凹形角部点p的角度间隔为完全被包含在自由空间中、角部在p的最小核心方形的尺寸。
3)提高精度：L∞度量体系和欧几里德度量体系的组合。
由于形状大多数情况下是轴线平行的，并且因为L∞沃龙诺依图更容易计算，本发明优选使用L∞度量体系。在备选实施例中，如果需要更高的精度，可以实施对欧几里德度量体系的近似，如图13所示。首先，根据L∞度量体系，也就是基于在定义5-6中给出的中心沿着L∞核心的最大方形的定义，将形状的边界分割为区间。然后，可以用欧几里德度量体系分配尺寸。这种方法可以如下完成：考虑中心在核心点c(p)的核心方形D。点p1和p2是点p的邻元素，反之亦然。类似地，边缘e1和e2是点p的邻元素。可以不将核心方形D的边分配为p的宽度，而可以使用欧几里德度量体系。例如，可以使用由点p、边缘e1和边缘e2限定的圆的尺寸。或者，可以使用中心在核心点的圆的尺寸，或者点p和边缘e2之间的距离(用双箭头表示)，或者点p和边缘e1之间的距离(用双箭头表示)。
作为又一个例子，如图13所示，点p3和p4是相邻元素。可以不将核心方形D’的边分配为p3和p4的宽度，而可以使用点p4和边缘e1之间的欧几里德距离，或者中心在核心点c(p4)的圆的尺寸，或者核心方形D’的对角线，等等。
4)精细和窄分割
在特定应用中，宽度和间隔的焦点在于将一个形状周围的形状和间隔尽可能评估为“窄”的或者“瘦”的。具体地，在VLSI生产和关键区计算领域，广泛使用“短路”和“开路”的概念。如前面的定义部分所述，“点缺陷”导致短路或者开路，其中，“短路”是导致与形状外部的其它边缘桥接的缺陷，“开路”是导致形状内部的桥接的缺陷。另外，一个缺陷可以被建模为圆圈或者方形形式的核心元素。
为了在“窄”或者“瘦”评估方面实现本发明以进行分割和尺寸分配，可以使用下面的定义(对于L∞度量体系和欧几里德度量体系)：
定义11：形状P的任意边界点p的宽度是导致形状P的开路的、中心在p的最小核心元素(缺陷)的半径。边界点p的间隔是导致短路的、中心在p的最小核心元素(缺陷)的半径。
定义12：开路是完全覆盖一个核心元素的元素，该核心元素的中心在形状P的内部的核心点。短路是完全覆盖一个核心元素的元素，该核心元素的中心在形状P的外部的核心点。
回到前述方法，参考图14A到14E，下面说明基于定义11将边缘e分割为宽度/间隔区间。图14A图示了形状122(来自图2B和9C)的内部沃龙诺依单元124A(也被表示为reg(e)，并有阴影)。图14B图示了在沃龙诺依单元124A(也被标记为reg(e))内形状122的二阶沃龙诺依图390(虚线)，它是在reg(e)中被截顶的形状122的沃龙诺依图。沃龙诺依单元124A内的该二阶沃龙诺依图是这样生产的：在沃龙诺依图124A中延伸所有入射到沃龙诺依单元124A的等分线54，除了那些入射到核心50的断点62E的等分线之外，也就是除了那些与e相邻的边缘产生的等分线之外。用于单元12A内的开路的二阶沃龙诺依图是不仅排除了边缘e而且排除了形状122的与边缘e相邻的两个边缘的单元内形状122的二阶沃龙诺依图。为了简明起见，开路的二阶沃龙诺依图390可以被称为“二阶沃龙诺依图”或者“reg(e)内的二阶沃龙诺依图”。
Reg(e)内的二阶沃龙诺依图将边缘e分割为区间w1，w2，w3。每一个区间具有一个“主人”，也就是包括该区间的边缘、凹形角部或者核心沃龙诺依顶点。在图14C中，区间及其主人用双箭头表示。沿着区间w的任意点p的宽度简单地是p到该区间的主人的距离。在一个区间的主人是如图14E所示的核心点的情况下，将该核心点的权重加到该宽度的导数上，也就是，该宽度是中心在该核心点的核心盘的尺寸。
图14D图示了形状的每一个沃龙诺依单元的二阶沃龙诺依分割以及宽度区间。图14F图示了对于边缘e的3个区间获得的实际宽度值。注意，顶部和底部区间w1，w3具有恒定宽度，而中间区间w2具有可变宽度，该可变宽度等于沿着该区间的任意点p到水平边缘e’的距离。
应当认识到，尽管在图14A-14F中使用了L∞度量体系，当报告沿着一个区间的点及其主人之间的距离时，可以使用欧几里德度量体系。
在L∞度量体系的正交情形下，只有这部分的宽度/间隔定义等效于前一部分定义9-10的定义，如果我们总是选择接触点p的最小核心方形来导出其宽度的话。
3.设计规则检查
回到图7，分配了区间和相关的尺寸也就是宽度/间隔之后，可以使用数据，使用传统技术进行涉及宽度和间隔的任何设计规则检查。例如，可以比较任何单边缘的宽度和/或间隔尺寸，以检查涉及单边缘的宽度和/或间隔尺寸的规则。类似地，可以比较相邻形状对和/或相邻边缘对的宽度和/或间隔尺寸，以检查涉及相邻形状和/或边缘对的规则。
应当认识到，本发明不限于在IC的层A中的应用。在备选实施例中，对于涉及IC的不止一层(例如层A和层B)中的形状的规则检查，可以使用组合层的沃龙诺依图。例如，对于层A中的每一个边缘，可以用层B中的边缘使用组合沃龙诺依图得出间隔区间。这些间隔区间然后可以用于比较涉及层A和层B的检查规则。
V.结论
在前面的讨论中，可以理解，所讨论的方法步骤用执行存储在存储器中的程序产品122的指令的处理器比如系统100的PU 114执行。可以理解，这里描述的各种器件、模块、机制和系统可以用硬件、软件或者硬件和软件的组合实现，并且可以按照不同于图示的方式进行划分。它们可以实现为任何类型的计算机系统或者其它的适合执行这里所描述的方法的设备。硬件和软件的典型组合是同样计算机系统中装有或者在其中执行计算机程序来控制计算机系统使之执行这里所描述的方法。
或者，可以使用专用计算机，其中包含用于执行本发明的一个或者多个功能任务的专用硬件。本发明还可以被嵌在计算机程序产品中，其包括能够实现这里所描述的方法和功能的所有特征，并且在被装入计算机系统时能够实现这些方法和功能。在这里的上下文中，计算机程序、软件程序、程序、程序产品或者软件的意思是用于使具有信息处理能力的系统执行特定功能的一组指令的体现为任何语言、代码或者符号的表达，所述功能的执行是直接执行的或者是在进行以下操作后执行的：(a)转换为另一种语言、代码或者符号；(b)以不同的物质形式复制。
上面对本发明的描述结合了具体的实施例。显然，对于本领域的普通技术人员，有许多变型、修改和变化是显然的。因此，本发明的上述实施例只是用于说明而不是限制性的。在本发明的按照所附权利要求限定的实质范围内，可以作出各种变化。

Claims (31)

1.一种用于集成电路设计的建模方法，包括下述步骤：
将集成电路设计中的形状的边缘分割为多个区间；以及
向每一个区间分配至少一个尺寸。
2.如权利要求1所述的方法，其中，所述分割步骤包括：
产生所述形状的核心沃龙诺依图；
基于所述核心沃龙诺依图分割所述边缘。
3.如权利要求2所述的方法，其中，所述核心沃龙诺依图的生成以L∞度量体系为基础，所述分配以欧几里德度量体系为基础。
4.如权利要求2所述的方法，其中，所述分割步骤还包括：根据所述核心沃龙诺依图的每一个顶点的核心元素分割所述边缘。
5.如权利要求4所述的方法，其中，所述核心元素是最大可能核心元素和最小可能核心元素之一。
6.如权利要求5所述的方法，其中，在核心元素为最大可能核心元素的情况下，所述区间尽可能大，在所述核心元素为最小可能核心元素的情况下，所述区间尽可能小。
7.如权利要求1所述的方法，其中，所述至少一个尺寸包括每一个区间的宽度和每一个区间到相邻形状的间隔。
8.如权利要求1所述的方法，其中，所述尺寸是另一个尺寸的函数。
9.如权利要求1所述的方法，还包括使用所述至少一个尺寸评估检查规则的步骤。
10.如权利要求9所述的方法，其中，所述检查规则涉及下述中的至少一个：单个边缘，一对相邻边缘，以及在集成电路设计的不止一层中的边缘。
11.如权利要求1所述的方法，其中，所述形状的每一个凹顶点为一个区间。
12.一种集成电路建模系统，包括：
将集成电路设计中的形状的边缘分割为多个区间的装置；以及
向每一个区间分配至少一个尺寸的装置。
13.如权利要求12所述的系统，其中，所述分割装置包括：
产生所述形状的核心沃龙诺依图的装置；
基于所述核心沃龙诺依图分割所述边缘的装置。
14.如权利要求13所述的系统，其中，所护分割装置还包括根据所述核心沃龙诺依图的每一个顶点的核心元素分割所述边缘的装置。
15.如权利要求14所述的系统，其中，所述核心元素是最大可能核心元素和最小可能核心元素之一。
16.如权利要求15所述的系统，其中，在核心元素为最大可能核心元素的情况下，所述区间尽可能大，在所述核心元素为最小可能核心元素的情况下，所述区间尽可能小。
17.如权利要求12所述的系统，其中，所述至少一个尺寸包括每一个区间的宽度和每一个区间到相邻形状的间隔。
18.如权利要求12所述的系统，其中，所述尺寸是另一个尺寸的函数。
19.如权利要求12所述的系统，还包括使用所述至少一个尺寸评估检查规则的装置。
20.如权利要求19所述的系统，其中，所述检查规则涉及下述中的至少一个：单个边缘，一对相邻边缘，以及在集成电路设计的不止一层中的边缘。
21.一种计算机程序产品，包括计算机可用的介质，其中实现有用于对集成电路建模的计算机可读程序代码，该程序产品包括：
将集成电路设计中的形状的边缘分割为多个区间的程序代码；以及
向每一个区间分配至少一个尺寸的程序代码。
22.如权利要求21所述的程序产品，其中，所述分割代码包括：
产生所述形状的核心沃龙诺依图的程序代码；
基于所述核心沃龙诺依图分割所述边缘的程序代码。
23.如权利要求22所述的程序产品，其中，所述分割代码还包括：根据所述核心沃龙诺依图的每一个顶点的核心元素分割所述边缘的程序代码。
24.如权利要求23所述的程序产品，其中，所述核心元素是最大可能核心元素和最小可能核心元素之一。
25.如权利要求24所述的程序产品，其中，在核心元素为最大可能核心元素的情况下，所述区间尽可能大，在所述核心元素为最小可能核心元素的情况下，所述区间尽可能小。
26.如权利要求22所述的程序产品，其中，所述至少一个尺寸包括每一个区间的宽度和每一个区间到相邻形状的间隔。
27.如权利要求22所述的程序产品，其中，所述至少一个尺寸是另一个尺寸的函数。
28.如权利要求22所述的程序产品，还包括使用所述尺寸评估检查规则的程序代码。
29.如权利要求28所述的程序产品，其中，所述检查规则涉及下述中的至少一个：单个边缘，一对相邻边缘，以及在集成电路设计的不止一层中的边缘。
30.一种集成电路检查规则评估系统，包括：
将集成电路设计中的形状的边缘分割为多个区间的装置，该分割装置包括：
使用第一度量体系生成形状的核心沃龙诺依图的装置，以及
根据所述核心沃龙诺依图分割所述边缘的装置；
使用第二度量体系向每一个区间分配至少一个尺寸的装置；以及
使用所述至少一个尺寸评估检查规则的装置。
31.如权利要求30所述的集成电路检查规则评估系统，其中，所述检查规则是与宽度相关的间距规则。
CNA2004100947440A 2003-12-09 2004-11-17 允许进行与尺寸相关的规则检查的集成电路设计建模 Pending CN1684073A (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US10/707,373 2003-12-09
US10/707,373 US7240261B2 (en) 2003-12-09 2003-12-09 Scan chain diagnostics using logic paths

Publications (1)

Publication Number Publication Date
CN1684073A true CN1684073A (zh) 2005-10-19

Family

ID=34677008

Family Applications (1)

Application Number Title Priority Date Filing Date
CNA2004100947440A Pending CN1684073A (zh) 2003-12-09 2004-11-17 允许进行与尺寸相关的规则检查的集成电路设计建模

Country Status (2)

Country Link
US (2) US7240261B2 (zh)
CN (1) CN1684073A (zh)

Families Citing this family (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7194706B2 (en) * 2004-07-27 2007-03-20 International Business Machines Corporation Designing scan chains with specific parameter sensitivities to identify process defects
US20070124628A1 (en) * 2005-11-30 2007-05-31 Lsi Logic Corporation Methods of memory bitmap verification for finished product
US8261142B2 (en) 2007-03-04 2012-09-04 Mentor Graphics Corporation Generating test sets for diagnosing scan chain failures
US8316265B2 (en) * 2007-03-04 2012-11-20 Mentor Graphics Corporation Test pattern generation for diagnosing scan chain failures
US20080263489A1 (en) * 2007-04-23 2008-10-23 Canada Miles G Method to identify and generate critical timing path test vectors
US7987400B2 (en) * 2008-02-22 2011-07-26 International Business Machines Corporation Method for optimizing scan chains in an integrated circuit that has multiple levels of hierarchy
US8689070B2 (en) * 2009-05-17 2014-04-01 Mentor Graphics Corporation Method and system for scan chain diagnosis
JP5270458B2 (ja) * 2009-06-12 2013-08-21 ルネサスエレクトロニクス株式会社 故障箇所推定装置
JP2012145467A (ja) * 2011-01-13 2012-08-02 Renesas Electronics Corp 半導体集積回路及び電源電圧適応制御システム
CN103376405B (zh) * 2012-04-27 2015-09-09 国际商业机器公司 用于扫描链诊断的方法和装置
US9081932B2 (en) * 2013-02-01 2015-07-14 Qualcomm Incorporated System and method to design and test a yield sensitive circuit
US9372232B2 (en) * 2013-12-16 2016-06-21 International Business Machines Corporation Collecting diagnostic data from chips
CN105445641B (zh) * 2014-06-30 2018-03-27 国际商业机器公司 用于扫描链诊断的方法和装置
US10302697B2 (en) * 2015-11-19 2019-05-28 International Business Machines Corporation Automated scan chain diagnostics using emission
KR101837899B1 (ko) 2017-04-18 2018-03-13 연세대학교 산학협력단 스캔 체인의 고장을 진단하는 장치 및 방법
WO2020186214A1 (en) * 2019-03-13 2020-09-17 Synopsys, Inc. Single-pass diagnosis for multiple chain defects

Family Cites Families (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3375843D1 (en) * 1983-12-28 1988-04-07 Ibm Electrical-diagnosis method for a defect cell in a chain of cells of a shift register
US5598421A (en) * 1995-02-17 1997-01-28 Unisys Corporation Method and system for tracking the state of each one of multiple JTAG chains used in testing the logic of intergrated circuits
US5663967A (en) * 1995-10-19 1997-09-02 Lsi Logic Corporation Defect isolation using scan-path testing and electron beam probing in multi-level high density asics
US6016564A (en) * 1996-08-28 2000-01-18 Matsushita Electric Industrial Co., Ltd. Method of design for testability, method of design for avoiding bus error and integrated circuit
US6278956B1 (en) * 1998-04-30 2001-08-21 International Business Machines Corporation Method of locating a failed latch in a defective shift register
US6405355B1 (en) * 1999-03-24 2002-06-11 Synopsys, Inc. Method for placement-based scan-in and scan-out ports selection
US6308290B1 (en) 1999-05-20 2001-10-23 International Business Machines Corporation Look ahead scan chain diagnostic method
US6442720B1 (en) * 1999-06-04 2002-08-27 International Business Machines Corporation Technique to decrease the exposure time of infrared imaging of semiconductor chips for failure analysis
JP2001201543A (ja) * 2000-01-18 2001-07-27 Rooran:Kk スキャン・パス構築用プログラムを記録した記録媒体とスキャン・パスの構築方法及びこのスキャン・パスを組み込んだ演算処理システム
US6694454B1 (en) * 2000-06-30 2004-02-17 International Business Machines Corporation Stuck and transient fault diagnostic system
US6553524B1 (en) * 2000-07-12 2003-04-22 Hewlett Packard Development Company, L.P. Method for automating validation of integrated circuit test logic
US6901546B2 (en) * 2001-06-07 2005-05-31 International Business Machines Corporation Enhanced debug scheme for LBIST
US7010735B2 (en) * 2002-01-10 2006-03-07 International Business Machines Corporation Stuck-at fault scan chain diagnostic method
US7000163B1 (en) * 2002-02-25 2006-02-14 Lsi Logic Corporation Optimized buffering for JTAG boundary scan nets
US7308631B2 (en) * 2002-09-13 2007-12-11 Arm Limited Wrapper serial scan chain functional segmentation

Also Published As

Publication number Publication date
US7895487B2 (en) 2011-02-22
US20050138508A1 (en) 2005-06-23
US20070168805A1 (en) 2007-07-19
US7240261B2 (en) 2007-07-03

Similar Documents

Publication Publication Date Title
CN1684073A (zh) 允许进行与尺寸相关的规则检查的集成电路设计建模
CN1122902C (zh) 设计板金零件的装置与方法
Barequet et al. Repairing CAD models
US8516402B1 (en) Method and apparatus for automatically fixing double patterning loop violations
Zhang et al. Two-dimensional placement optimization for multi-parts production in additive manufacturing
US20110087350A1 (en) Methods and system for enabling printing three-dimensional object models
US8473874B1 (en) Method and apparatus for automatically fixing double patterning loop violations
US6898477B2 (en) System and method for performing adaptive modification of rapid prototyping build files
US6877146B1 (en) Method and apparatus for routing a set of nets
US8645107B2 (en) Automatic component insertion and constraint based on previous-use data
CN112008980B (zh) 一种3d打印模型处理方法及系统
US20200142384A1 (en) Method of printing a 3d model from point cloud data
US6829757B1 (en) Method and apparatus for generating multi-layer routes
CN101067872A (zh) 从三维逆向建模的源模型数据检测二维草图数据的方法
CN1380623A (zh) 用于分析和解释工程图的计算机自动处理
CN1869993A (zh) 具有若干面的模型化对象的计算机辅助设计方法
CN1916967A (zh) 产生具有所要求的几何连续度的参数化曲面的方法
Mahdavi-Amiri et al. VDAC: volume decompose-and-carve for subtractive manufacturing
US20100017007A1 (en) Apparatus and Method For Designing an Electrode Shape for an Electrical Discharge Machining Process
Canellidis et al. Evolutionary computing and genetic algorithms: Paradigm applications in 3D printing process optimization
CN1599907A (zh) 三维形状数据向单元内部数据的变换方法及变换程序
US11763524B2 (en) Layered meshing for additive manufacturing simulations
CN1636165A (zh) 光刻掩模位相冲突的解决方法
US8462176B1 (en) Automatic annotation generation
CN117371385B (zh) 邻近图形的确认方法、电子设备及存储介质

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C02 Deemed withdrawal of patent application after publication (patent law 2001)
WD01 Invention patent application deemed withdrawn after publication