基于图形的处理系统及用于处理基于图形的数据的方法

摘要

用以处理与生成超大规模集成电路(VLSI)设计有关的基于符号的数据的系统和方法。提供一种系统，其包括通过使用图案描述语言来定义可变图案以创建符号版图的系统；以及能够在符号版图的可变图案中识别潜在的匹配的基于图形的图案匹配系统。

说明书

技术领域

本发明总体上涉及L3GO VLSI设计的处理，更具体地涉及一种通过使用可变图案来生成L3GO版图、并进行L3GO版图的基于图形的图案匹配的系统和方法。

背景技术

L3GO(使用栅格符号几何对象的版图)是一个正在进行的用以提高VLSI(超大规模集成电路)设计的可制造性的项目。L3GO提供描述电路接线和器件的对象或图案的有限集合(restricted set)，被称为符号(glyph)。L3GO具有三种符号类型，包括：

1.直线(Stick)符号，其是在两个格点之间画出的一维线段，例如，用来描述FET栅极或互连。直线符号的附加属性包括直线属于哪一层、开始和结束点，以及目标宽度；

2.接点(contact)符号，其是位于格点的0维点，例如，用来描述垂直互连(接点和通路)。接点符号的附加属性包括接点属于哪一层，以及指定一个矩阵内的接点如何布置的参数，例如，矩阵内行和列的数目、每个接点的大小、每个列和行之间的水平和垂直距离、以及矩阵中心相对于符号位置的可选偏移量；以及

3.区域(area)符号，其是二维的、顶点位于格点的轴对齐矩形，例如用来描述扩散区域。

在它们的特定属性之外，符号能够表达“设计意图”属性，例如，连线(net)名、它们的重要性等级等等。一个被称为确立(elaboration)的处理将符号集合转换为几何对象(数据预处理前掩模形状，pre-data-prep mask shapes)。

一个图案描述一种符号结构，例如，具有一定属性的接点符号位于具有其它属性集合的直线符号之上。确立处理基于参数集合创建这种结构的形状，例如，确立处理可以在M1直线上创建焊盘以及在焊盘上创建四个冗余通路。由于VLSI设计中转换符号图案的计算复杂性，预定义或匹配图案的识别是确立处理中的关键部分。

L3GO设计的操作面临两个突出问题：图案的可变性，以及模糊的解决方案。为了支持考虑到多个设计特征之间的交互的基于图案的设计操作，仅仅使用具有明确或固定大小的图案是不可行的。为了覆盖所有可能大小的结构可能需要数万个图案。因此，图案必须支持属性可变规范，例如，距离，其值在基于拓扑标准的图案布置被找到时被确定。

此外，经常存在应用于大部分情况的基本修改，例如，扩展线的末端。但是在一定的环境下，例如，如果线的末端存在特定交互，则期望有不同的解决方案。在这种情况下，一个图案是另一个的细化(refinement)，从而两个图案相互匹配。必须有允许构造重叠图案复杂集合的明确解决方案的机制。

发明内容

本发明通过提供将图案表示为可变对象，将图案映射为能够被检索和分组的图形，并且提供不同图案分组的布置(placement)优先级的方案来解决上述及其它问题。

在第一方面，本发明提供一种基于符号的处理系统，包含：通过使用图案描述语言来定义可变图案以创建符号版图的系统；以及基于图形的图案匹配系统，用以在符号版图的可变图案中识别潜在的匹配。

在第二方面，本发明提供一种存储在计算机可用介质上的用以处理基于符号的数据的计算机程序产品，包含：被配置成通过使用图案描述语言来定义可变图案以创建符号版图的程序代码；以及被配置成在符号版图的可变图案中识别潜在的匹配的程序代码。

在第三方面，本发明提供一种处理基于符号的数据的方法，包含：提供具有可变图案的符号版图；将每个图案编码为图案图形，并将每个图案图形存储在图案字典中；将符号版图编码为其中节点表示规范特征以及边缘表示特征之间的交互的版图图形；以及比较图案图形中的特征和图案字典中的数据以识别潜在的匹配。

附图说明

从下面结合附图对本发明的各个方面所做的详细描述中，本发明的这些和其它特征将会被更加容易地理解，附图中：

图1描述了具有根据本发明实施例的L3GO处理系统的计算机系统。

图2描述了表示根据本发明实施例的处理L3GO数据的方法的流程图。

图3描述了根据本发明实施例的用以移动PCNC“T”的规则的应用示例。

具体实施方式

现在请参考附图，图1描述了具有用以生成和处理L3GO设计数据30的L3GO处理系统18的计算机系统10。L3GO处理系统18包括定义L3GO版图内的可变图案的系统20，以及识别L3GO版图内的匹配图案的基于图形的图案匹配系统35。请注意尽管示例性实施例通过参考基于L3GO的系统来描述，但本发明可以应用于任何现在已知或以后开发的用以生成VLSI或其它类型的设计的基于符号的系统。还请注意尽管L3GO处理系统18被作为独立的过程而示出，但其一部分可以被集成到确立系统或处理中。

I.图案描述语言

定义可变图案的系统20通过提供可变LG3O图案可以被定义的机制的图案描述语言33来实现。这减少了存储成千上万个不同形状的属性的需求。作为替代，具有可变参数的通用形状集合可以被提供，其接着可以被设计者选择并且定位。根据本文的目的，术语可变图案指的是其中一个或更多参数(如大小)直到最后版图通过确立过程而生成时才被解决的符号(直线、点或区域)。

图案描述语言33的两个特征包括规则集34和图案规范36的使用。本文所述的是实现图案描述语言33的示例性语法。然而，能够理解本文中讨论的特定语法并非用于限制，也就是说，在不脱离本发明的范围的前提下不同的语法变化可以被使用。请注意RX、PC和CA涉及与制造过程中使用的光刻掩模相对应的VLSI设计层的名称。

每个目标层，也就是，被作为确立处理的主要输出而被制造的层，需要一个规则集34。在本文所描述的示例性实施例中，规则集标识符是目标层的名称，并且规则集34的内容被括弧“{}”框住。规则集34的主体包括以所列顺序排序的下述声明：

●一个基本输入声明。基本输入声明的内容被括弧“{}”框住。其内容是一个表示L3GO层的一个或更多标识符的逗号分隔列表。基本输入是一个主要与目标层相关的L3GO层的集合，即，由规则集转换的层的集合。

●一个上下文输入声明。其主体，被括弧“{}”框住，包含一个表示L3GO层的零或更多标识符的逗号分隔列表。上下文输入是一个影响基本输入至目标层的转换的L3GO层的集合。

●一个单位声明。其主体，被括弧“{}”框住，以纳米为单位详细说明了在图案规范中使用的长度单位。这个单位被用于规则集34的所有距离规范。

●任意数量的图案声明(下面被描述)。

一个PC规则集34的示例如下所示：

Ruleset(PC){

BaseInput{PC_L3GO，PCNC_L3GO}

ContextInput{CA_L3GO，RX_L3GO}

Units{1 nm}

Pattern{...}

 ...  

 }

基本输入和上下文输入之间的区别能够被用于覆盖(coverage)检查。例如，需要规则集34利用其输出区域覆盖所有基本输入的需求保证所有输入特征在图案中被考虑。

图案规范36由图案的拓扑描述组成，其基本地描述了设计特征以及设计特征之间的关系。图案规范36的剩余部分提供附加过滤标准。图案规范36由关键字“Pattern”，其后是被圆括号“()”框住的图案标识符以及其后是被括弧“{}”框住的图案主体组成。图案主体具有多个部分，每个部分被括弧“{}”框住，其必须以固定的顺序出现。下面是图案规范36的一个示例：

Pattern(patternname){

Parameters{...}

Elements{...}

Anchor{...}

Relations{...}

Constraints{...}

InputRegion{...}

OutputRegion{...}

Result{...}

Transforms{...}

}

图案规范36的每个部分在下面被说明。参数部分声明变量。被作为变量名称声明的字符串可以被使用在元素规范和约束中，并且它们的实际值由图案布置来确定。例如：

Parameters{L，W，P}

在图案中，变量能够以两种形式出现。如在参数部分指定的，变量必须出现一次，并且这种引用是其定义使用。定义使用确定图案的哪个属性为具有实际对应图案元素的图案布置的参数分配值。变量的定义使用可以仅仅出现在元素声明中。

具有作为引用使用的前缀“％”的变量还可以出现很多次。当图案匹配出现时引用使用简单地应用由定义使用捕捉的值。变量的引用使用可以出现在元素、输入区域、输出区域、约束和结果部分中。

图案的元素部分列出了作为图案一部分的符号和部分符号。每个声明具有等式的形式并且将符号指定给(部分)符号。下面的段落描述了不同的元素声明。

1.直线

声明：sticksuffix(layer，(x，y)，direction，length，width，extint，crit(...))声明一个直线或部分直线，取决于后缀。如果没有后缀，这表示完整的直线符号。其它可能的后缀是开始、结束以及片段，分别表示直线符号的开始、结束以及内部。坐标(x，y)始终位于特征的开始部分，也就是说，对于向右结束的直线结束点位于(x+length，y)。

所有形式的直线符号具有以下参数(arguments)：

●直线所在的输入层。

●直线的位置，通过其x和y坐标表示。

●直线的方向，左、右、上或下中的一个。

●直线，或直线部分的长度。这是定义没有前缀％的变量的合适地方。

●直线的宽度。这是变量的合适布置。(这意味着输入中的直线必须具有宽度属性，否则规则集必须指定默认值)。

●表明(extint)元素是否与输入区域交叉(entry int)，不与输入区域交叉(ext)或两者都有(entry dnc)的规范。

●crit()参数列出了对图案匹配很关键的交互(intersect，mindist(min，max))。如果这里列出一个交互，例如交叉，则以这种方式与图案布置中的元素交互的符号集必须完全匹配所列的图案交互。否则附加的交互符号不会导致不匹配。在crit()声明中列出的每个交互能够将层作为参数，其将由这种crit-entry所覆盖的关键交互限制到特定层。

2.点矩阵

声明：pointmatrix(layer，(x，y)，Nx，Ny，Ox，Oy，Dx，Dy，size，extint，crit(...))声明一个点矩阵符号。点矩阵符号具有以下参数：

●点矩阵符号所在的输入层。

●点矩阵符号的原点位置，通过其x和y坐标表示。

●点矩阵符号中通路的数目，Nx和Ny。

●矩阵的中心与原点的偏移量，Ox和Oy。

●点矩阵符号中通路的节距，Dx和Dy。

●单个通路的正常大小。

●与直线声明类似的与输入区域的关系的规范。

●crit()参数列出了与直线声明类似的的交互。

3.边界

声明boundarysuffix(layer，(x，y)，direction，length，extint，crit(...))声明一个边界或部分边界，取决于后缀。如果没有后缀，这表示完整的边界边缘。其它可能的后缀是开始、结束以及片段，分别表示矩形符号的边界边缘的开始、结束以及内部。所有形式的边界具有以下参数：

●边界边缘所在的符号的输入层。

●边界的位置，通过其x和y坐标表示。

●边界边缘的方向，左、右、上或下中的一个。边界边缘始终被定向以使在沿着边界从其开始点进行到其结束点时相应区域的内部在其左边。

●边界边缘，或边缘部分的长度。这是定义没有前缀％的变量的合适地方。

●与直线声明类似的与输入区域的关系的规范。

●crit()参数列出了与直线声明类似的的交互。

下面是一个声明直线、矩阵和边界的例子：

Elements{

A＝stickstart(PC_L3GO，(0，0)，right，100，W，ext，crit())；

B＝pointmatrix(CA_L3GO，(P，0)，1，1，0，0，0，0，S，int，crit(intersect)；

C＝boundarysegment(RX_L3GO，(％P，Q)，down，2^*Q，int，crit(intersect)；

}

锚点(anchor)部分指定了锚点的类型，被括弧“{}”框住，其作为图案匹配的种子(seed)并且定义图案所指明的坐标系统的原点。锚点部分的主体指定了作为图案种子的元素，以及所述元素的哪一部分与原点交叉。锚点始终位于坐标(0，0)并且点沿着X轴的正方向。

锚点有两种类型的规范。第一种锚点规范具有<element:part>的形式。element是来自元素部分的元素标识符，第二部分是下列说明符中的一个：

●s：开始点或直线或边界。

●e：直线或边界的结束点。

●i：直线或边界的内部。

●p：点矩阵的位置。

第二种锚点规范具有<element#element>的形式。这个规范描述了锚点的位置位于两个特定元素交叉的地方。例如：

Anchor{A:s}

Anchor{A#C}

关系部分指定了直线之间的交互。所列元素的每个可能配对必须存在关系。每个声明具有这样的形式：element:part relationtypeelement:part。

多个关系通过逗号分隔。每个关系声明指定哪些元素具有交互而关系类型指定发生的交互的类型。元素(element)是指元素部分定义的标识符。下面的例子举例说明了语法。

A intersects B，

B manhattanmindist(100，200)C，

D disjoint E

存在以下类型的关系：

●manhattanmindist(min，max)：表明在被指出的符号部分之间的最小Manhattan距离必须最小为min且最大为max。max必须大于或等于min并且两个值都必须大于0。

●mindist(min，max)：表明在被指出的符号部分之间的以无穷级(L-infinity)作为度量的最小距离必须最小为min且最大为max。max必须大于或等于min并且两个值都必须大于0。

●交叉(intersect)是mindist(0，0)的特例。

●不相交(disjoint)或没有交叉表明在指定的元素部分之间没有交互。

正关系(即，交叉并且基于距离的)必须形成元素的生成树。

约束部分允许对表达式的值的限制规范，表达式的值必须在特定的闭区间之内。例如：

％L-％M in[0，infty]；

％Q in[-infty，0]；

标识符infty表示正无穷。

输入区域部分列出了图案的输入区域。输入区域仅仅被允许被在元素部分作为int或dnc列出的输入层上的符号所交叉。输入区域的声明具有InputRegion{...}的形式。

区域被指定为能够接触(即，邻接)，但不能交叉的矩形的集合。语法如下：rect((xlow，ylow)，(xhigh，yhigh))，其中xlow、ylow、xhigh、yhigh表示矩形左下和右上的坐标。这些坐标的值必须由或者常量或者变量(前面具有前缀‘％’的变量)的引用使用来表示。多个rect规范必须由逗号分隔。被限制为单层的区域能够被指定为LAYER＝{...}。例如：

InputRegion{

rect((-50，-125)，(50，125))，

RX_L3GO＝{rect((-75，-75)，(％P，75))}

}

输出区域部分列出了图案的输出区域。输出区域的声明具有OutputRegion{...}的形式。除了对层没有限制是被允许的之外，输出区域的语法和输入区域的语法完全相同。

转换部分列出了图案可能出现的坐标转换。转换部分的声明具有Transforms{...}的形式。在括号内，进行一个或更多的下列转换声明，由逗号分隔。

●标识：标识转换。

●rot90，rot180，rot270：围绕坐标系统的原点的三个正交旋转。

●镜像：x轴的镜像。

●mrot90，mrot180，mrot270：具有后续旋转的x轴上的镜像。

请注意每个转换，包括标识，必须被清楚地列出。对于被列出的每个转换，一个规则被生成，其中元素规范以及区域和结果的几何组件被转换。请注意变量也被转换，也就是说，(X，Y)的规范被转换为用于“镜像”的(X，-Y)。当值被确定，任何坐标的交换或求反被考虑。请注意约束部分不被转换。

为了让图案描述语言33允许使用变量来描述图案，下列要求也是必须的。第一，变量仅仅用于点特征的位置和线特征的封闭端。第二，输入区域必须为空，除非与在元素部分作为int或dnc列出的符号相交叉。第三，作为图案结果的点集合必须被输出区域覆盖。第四，如果关系类型被列出为关键，则在关系部分指定的连接必须在设计中针对每个接点被完全匹配。例如，具有列出为关键的交叉的由单个直线末端组成的图案不匹配作为“L”一部分的直线末端。请注意交互区域增加了仍然可以导致不匹配的附加过滤器。

II.基于图形的图案匹配

一旦L3GO版图通过使用上述的图案描述语言33来定义，所述版图能够被确立系统处理以生成VLSI设计。如上所述，在L3GO版图中识别匹配的图案的能力大大减少了确立处理的计算成本。因此，基于图形的图案匹配系统35被用来查找匹配的图案。

基于图形的图案匹配系统35的核心使用回溯(backtracking)算法以在版图图形中查找图案图形。回溯是约束满足问题的标准策略。这种应用的一个有趣的方面是在回溯问题的期间不是所有被约束的变量的值都是已知的。也就是说，在相应的版图对象被找到时图案图形的节点的一些属性不是已知的。

图案编码系统22提供L3GO图案至图案图形的转化，版图编码系统23提供L3GO版图(即，设计)至版图图形的转化。图案编码系统22将图案元素直接转化为节点，以及将节点之间的关系转化为边缘(即，图案图形)。节点具有元素的指定属性，边缘具有交互的类型，例如，它们相互交叉等等。节点属性中的每个值，即，开始坐标、长度、宽度属性等等，被编码为表达式。存在多种类型的表达式：

●如果图案中提供一个数值，则表达式是常量。

●如果表达式是变量(没有％前缀)的定义布置，其参照存储变量值和它们的状态的位置(slot)被记录为未初始化的变量。初始时，所有的变量都是未初始化的。

●如果包含变量使用(具有％前缀)的表达式被提供，表达式参照变量被转化为字节码。

针对每个指定的转换创建一个单独的图案。图案元素中的每个属性被转换。对于开始点，x和y坐标在必要时被交换和求反，方向被改变并且点符号矩阵的属性被转换(通过交换和求反的偏移点，行和列以及节距的数目仅仅被交换)。请注意对于变量(使用和定义布置)符号的改变分别被记录为1或-1的因数。对于以下部分发生转换：元素，输入和输出区域，以及结果。约束不被转换。

接着对于每个图案，基于其锚点计算一个关键字(key)，即，锚点所在的层，以及在锚点是交叉等的情况下的锚点特征(开始或结束)。接着基于那些锚点关键字将图案存储在字典中。每个图案图形被存储有一个相关联的锚点关键字。

版图编码系统23，其将L3GO版图编码为图形，首先需要L3GO版图的规范表示的创建。点矩阵被指定为是规范的，但区域和直线符号必须被处理。对于具有区域符号的每层，区域符号被合并(unioned)，接着连接组件的轮廓被作为线段的集合来计算。这些线段是区域符号的规范特征。

直线通过两个阶段来被规范。首先所有平行的和重叠的直线在它们的宽度属性相同时被合并。如果宽度不相同，具有较大宽度的符号擦除具有较小宽度的直线的重叠部分。在第二个阶段，直线被断开，从而直线之间的仅有交互出现在直线末端。

具有与关系距离和关键声明距离中的最大值相等的交互距离的侵入(intrusion)检索在由规范过程获取的特征集合上执行。规范后的特征被映射至节点；侵入被映射至边缘并且具有与边缘相邻的两个特征之间的最小距离。上述处理的结果形成了版图图形。

对于每个图案，计算来源于锚点特征(即，预匹配节点)的生成树。生成树的构造建立了被用于回溯算法的顺序。生成树是图案图形的子图形。

图案检索系统24通过扫描所有规范后的特征(即，边界线段、直线和点矩阵点)来查找在版图图形中匹配的所有图案。对于每个特征，子图形检索系统24查找图案字典以查看是否存在其锚点与线段、直线末端或点矩阵点中的一个相匹配的图案。如果存在位于线特征(边界段和直线)的交叉处的锚点，扫描执行交叉检索(例如，使用扫描线算法)以查找潜在的锚点，并且使用交叉点以在图案字典中检索。

对于其锚点匹配版图图形的当前位置的所有字典项，子图形检索被启动。子图形检索开始于预匹配，即，提供潜在的锚点位置的一或两个元素被分别映射至在图案中定义锚点的一或两个元素。

●将预匹配作为开始点，执行回溯。请注意该算法必须查找每个图案匹配；在相同锚点位置的相同图案可能有多个匹配。

●回溯算法依照生成树顺序获取没有被匹配的下一个节点Q并且查找在生成树中对应其在前节点(predecessor)P的版图节点L(P和L在这个点是匹配的)。

●L的所有邻居被进行匹配测试。

●如果潜在的匹配被找到(由于未初始化的变量到目前不是所有的节点属性都已知)，匹配移动到下一个未匹配的节点Q并且进入步骤1。

●如果在L的任何邻居中没有匹配被找到，其不匹配在前节点P并且继续把P作为一个未匹配节点。

●如果全部匹配被找到，最后一个匹配被反转并且回溯继续。请注意对于每个匹配的版图节点所述算法必须保持追踪哪些邻居已经被试过从而当回溯到那个节点时其继续新的组合。

请注意上面所述的回溯算法的一个挑战是并不是做决定所需的所有属性在匹配完成时是已知的。因此，为了获得相当好的性能，回溯分支必须被尽早剪除。因而，对于每个完成的匹配，当前定义的变量值被确定并且被用来测试。当匹配没有完成时，变量被相应地重置为未定义状态。建立匹配的第一个标准集合是元素的拓扑和它们的关系。因为不是所有的变量值都是已知的，并且因此不是所有的条件都能够被测试，所以这种最初的“局部”匹配处理可能创建后来被发现是不正确的匹配。只要匹配被创建，值被指定给变量，并且当匹配被反转时，这些指定被反转。

通常，变量确定元素的实际大小，例如，对于终止于触碰它的第一个CA的直线开始，触碰相同直线的其它CA在版图上距离更远并且因此版图图形中的相邻不是真正合格的图案候选。因此，变量赋值能够实际上具有对匹配处理的拓扑组件的影响。

部分图案匹配以布置(placement)的形式来实现。布置包含对图案、版图中图案锚点所在的位置的坐标以及具有变量的值和状态的位置的集合的引用。在匹配过程中，每个新的匹配创建新的布置(可能具有更多初始化的变量)，并且前面的布置被存储在堆栈。为了回溯，布置的老版本被从堆栈中取出。

如果全部匹配被找到，所生成的最后布置的所有变量被初始化。接着一系列附加(further)过滤器被进行如下应用：

●不是生成树的一部分的图案关系(即，边缘)被验证。

●元素的关键交互被测试。

●约束被估计。

●输入区域的内容被检查。

冲突解决系统26提供当两个或更多图案具有重叠的输出区域时解决冲突的机制。子图形检索系统(即，图案检索阶段)的结果是图案布置的完整集合，也就是说，该集合包含所有潜在的匹配。图案布置由所放置的图案和图案锚点适合于创建布置的版图的坐标组成。

如上所述，经常存在这样的情况：或者是相互之间的精细级别不同或者是具有重叠部分的多个图案相互匹配。在每组图案中(如规则集34所定义)，基于图案优先级必须找到布置的有效集合从而不存在模糊。当两个图案的输出区域重叠时两者之间相互冲突。当它们的输出区域重叠时具有更高优先级的图案布置禁止具有更低优先级的图案布置。优先级可以基于组内规范的顺序而确定。

布置的完整集合通过下面的方法被缩减为布置的有效集合：

●图形被构造，其中布置是节点并且输出区域之间的重叠是边缘。

●具有最大优先级的节点被选择。其禁止更低优先级的所有邻近匹配，因此这些节点从图形中被移除。

●第二个步骤被重复直到图形不包含任何边缘。

请注意具有相同优先级的图案布置能够相互重叠。既然所有图案(及它们的转换)具有唯一的优先级，因此只有相同图案的两个布置能够重叠。

组覆盖系统28提供基于它们的优先级而覆盖组的机制。每个组是在规则集34中定义的一系列图案，并且每个组的优先级可以按照组被定义的顺序来确定。在解决图案(组)之间的冲突之后，如上所述，结果是很多有效布置的集合，每个组一个集合。组覆盖系统28基于它们的优先级来覆盖组。

●具有最低优先级的组被选择并且为该组生成结果。

●下一个未被处理的组G(具有下一个更高的优先级)的输出区域被选择，其输出区域被合并，并将结果从到目前为止所计算的结果中减去(差分运算)。接着结果G被相加(合并)。

●步骤2被重复直到所有的组被处理。

请注意顺序较高的组实际上能够通过它们输出区域的空部分而从前面组中移除部分结果。

图2描述了本发明方法的流程图。在步骤S1，具有可变图案的L3GO版图通过使用图案描述语言来被创建，如上所述。在步骤S2，每个图案被编码为图案图形并且与相关联的锚点关键字一同被存储在图案字典中。在步骤S3，整个L3GO版图被编码为其中节点表示规范特征并且边缘表示相邻特征之间的交互的版图图形。在步骤S4，通过比较版图图形中的特征和图案字典中的数据，进行子图形检索。在步骤S5，对于具有未被定义的变量的图案任何部分图案匹配被管理(例如，使用堆栈的剪枝)。在步骤S6，在多个图案匹配版图图形中的一个特征的情况下，冲突通过图案优先级方案来解决。在步骤S7，形成布置的图案组之间的冲突基于组优先级方案来解决。

III.规则集

如上所述，RX、PC和CA涉及与制造过程中使用的光刻掩模对应的VLSI设计层的名称。每个层包括图案规范的规则集。

RX规则保证接点被足够数量的RX所覆盖。在这个示例性实施例中，只有水平RX边界边缘被改变，并且如果CA矩阵点位于水平RX边界，该RX边界被移出60纳米。确立后的CA接点从点位置延伸45纳米，在扩展RX在垂直方向从接点延伸至少15纳米之后。RX在水平方向上必须从确立后的接点边界延伸至少55纳米。

还存在必须满足与RX的交互的限制点矩阵。其“引用点”位于RX图形的内部或边界的CA点矩阵的所有点必须在相同的RX连接组件的内部。作为特例，具有对水平RX边界的引用的CA矩阵必须严格地具有一行点(即，因为它是一维的)。具有RX内而不是位于边界的引用的具有一个点位于边界的点矩阵能够最多具有2行和2列。

只具有一个组的RX规则集生成与RX L3GO的区域符号合并的附加结果形状。规则集的语法如下：

Ruleset(RX_ADD){

BaseInput{RX_L3GO}

ContextInput{CA_L3GO，PC_L3GO}

Units{1 nm}

CA规则能够从概念上被划分为两种类型，与RX交互的接点和与PC交互的接点。对于引用点与RX_L3GO区域符号交叉的点矩阵，矩阵的所有点必须与RX_L3GO的相同连接组件交叉。如果矩阵具有一个点触碰RX_L3GO的边界，那么：(1)边界必须水平；(2)如果矩阵的引用点位于边界则矩阵必须严格地具有一行并且垂直偏移量为0；以及(3)矩阵必须最大是2乘2(并且偏移少于x和y节距的一半)。

如果PC移动时引用点与PC_L3GO或PCNC_L3GO符号交叉的点矩阵必须移动。CA规则集只有一个组并且被定义如下语法：

Ruleset(CA){

BaseInput{CA_L3GO}

ContextInput{RX_L3GO，PCNC_L3GO}

Units{1 nm}。

PC规则具有定义PC层的多个组，并且被定义如下语法：

Ruleset(PC){

aseInput{PC_L3GO，PCNC_L3GO}

ContextInput{RX_L3GO，BP_L3GO，CA_L3GO}

Units{1 nm}。

PC规则集的第一组确立水平PC线。第二组考虑可能已经被移动的CA而为CA创建PC覆盖盘(pad)。第三组使用内部以及交叉点分解以处理PCNC_L3GO及其与PC_L3GO的交互。交叉点责任“区域(area)”为宽度和高度是PCNC目标宽度的区域。图3描述了包括因为太靠近邻居而必须被移动的PCNC“T”的PC规则的示例性应用。执行这种移动的代码片段如下所示：

Pattern(PCNC_T_Move){

Parameters{L1，L2，W1，W2，W3，W4，Y}

Elements{

A＝stickstart(PCNC_L3GO，(0，0)，up，L1，W1，dnc，crit(none))

    B＝stick(PCNC_L3GO，(-C_PCNC_HPUSHD，Y)，up，L2，W2，

dnc，crit(none))

    C＝stickstart(PCNC_L3GO，(0，0)，right，C_PCNC_WIDTH/2，

W3，dnc，crit(none))

    D＝stickstart(PCNC_L3GO，(0，0)，down，C_PCNC_WIDTH/2，

W4，dnc，crit(none))

}

Anchor{A:s}

Relations{

A:sie mindist(C_PCNC_HPUSHD，C_PCNC_HPUSHD)B:sie，

A:s intersect C:s，

A:s intersect D:s，

B:sie disjoint C:sie，

B:sie disjoint D:sie，

C:s intersect D:s

}

Constraints{

％Y-C_PCNC_WIDTH/2 in [-infty，C_PCNC_VPUSHD]，

％Y+％L2+C_PCNC_WIDTH/2 in[-C_PCNC_VPUSHD，infty]

}

InputRegion{

PCNC_L3GO＝{rect((-(C_PCNC_HPUSHD-1)，-

C_PCNC_WIDTH/2)，(0，C_PCNC_WIDTH/2))，

rect((0，1)，((C_PCNC_HSAVED-1)，C_PCNC_WIDTH/2))，

rect((0，-C_PCNC_WIDTH/2)，(C_PCNC_HSAVED-1，-1))}，

PC_L3GO＝{rect((-(C_PCNC_HPUSHD-1)，-

C_PCNC_WIDTH/2)，(0，C_PCNC_WIDTH/2))，

rect((0，1)，((C_PCNC_HSAVED-1)，C_PCNC_WIDTH/2))，

rect((0，-C_PCNC_WIDTH/2)，(C_PCNC_HSAVED-1，-1))}

}

OutputRegion{

rect((-C_PCNC_WIDTH/2，-

C_PCNC_WIDTH/2)，(C_PCNC_WIDTH/2，C_PCNC_WIDTH/2))

}

Result{

rect((-C_PCNC_WIDTH/2+C_PCNC_MOVE，-C_PCNC_WIDTH/2)，

(C_PCNC_WIDTH/2，C_PCNC_WIDTH/2))

}

Transforms{identity，rot180，mirror，mrot180}

}

图3示出了图案“PCNC_T_Move”的显示(visualization)，图案显示在左侧，生成的结果和图案的输出区域显示在右侧。大小标记(箭头以及小距离的＞＜)与如上所示的图案代码中的变量和常量对应。变量在图案代码的“Parameter”部分被声明，常量被从外部定义并且取决于制造技术。请注意以这种方式编码的整个规则集能够通过仅仅更新常量的定义而被更新为新的技术参数。

通常，计算机系统10(图1)可以包含任何类型的计算机系统并且可以实现为客户端和/或服务器的一部分。计算机系统10通常包括处理器12、输入/输出(I/O)14、存储器16，以及总线17。处理器12可以包含单个处理单元，或被分布在一个或更多位置，例如，客户端和服务器上的一个或更多处理单元。存储器16可以包含任何已知类型的数据存储和/或传输介质，包括磁性介质、光学介质、随机存取存储器(ROM)、只读存储器(ROM)、数据缓存、数据对象等等。而且，存储器16可以位于包含一个或更多类型的数据存储的单个物理位置，或以各种形式分布在多个物理系统。

I/O 14可以包含与外部资源交换信息的任何系统。外部设备/资源可以包含任何已知类型的外部设备，包括监视器/显示器、扬声器、存储装置、其它计算机系统、手持设备、键盘、鼠标、语音识别系统、语音输出系统、打印机、传真机、寻呼机等等。总线17提供计算机系统10中每个组件之间的通信连接并且同样的可以包含任何已知类型的传输连接，包括电连接、光连接、无线连接等等。尽管未示出，附加组件，如缓冲存储器、通信系统、系统软件等等，可以被合并在计算机系统10中。

对计算机系统10的访问可以通过网络如因特网、局域网(LAN)、广域网(WAN)、虚拟专用网络(VPN)等来提供。通信可以经由直接硬线连接(例如，串行端口)，或经由可以使用有线和/或无线传输方法的任何组合的可寻址连接来发生。而且，常规的网络连接，如令牌环、以太网、WiFi或其它常规的通信标准可以被使用。连接还可以通过常规的基于TCP/IP套接字的协议来提供。在这个实例中，因特网服务提供商可以被用来建立互连。而且，如上所述，通信可以发生在客户端-服务器或服务器-服务器环境中。

应该理解，本发明的教导可以作为商业方法以订购或付费的方式提供。例如，包含L3GO处理系统18的计算机系统10可以由为客户提供本文所述功能的服务提供商创造、维护和/或配置。也就是说，服务提供商可以提供如上所述的基于图形的图案匹配。

能够理解本文所述的系统、功能、机制、方法、引擎和模块能够以硬件、软件，或硬件和软件的组合来实现。它们能够被用以执行本文所述方法的任何类型的计算机系统或其它装置来实现。硬件和软件的一个典型组合是具有下述计算机程序的通用目的计算机系统，所述计算机程序在被装载和执行时，控制计算机系统从而使其实现本文所述的方法。或者，包含用以实现本发明的一个或更多功能任务的特定硬件的专用计算机可以被使用。在另一实施例中，本发明的部分或全部能够以分布式的方式实现，例如，通过如因特网的网络。

本发明还可以包含在计算机程序产品中，其包含使得本文所述的方法和功能被实现的全部特征，并且其在被装载至计算机系统时能够实现这些方法和功能。本文中的术语如计算机程序、软件程序、程序、程序产品、软件等等的含义是意图导致系统具有信息处理能力的一组指令的任何语言、代码或符号的任何表达式，所述信息处理能力或者直接或者在下述处理的一种或全部之后来执行特定功能：(a)转换为其它语言、代码或符号；和/或(b)以不同的材料形式再现。

对本发明的上述描述是出于示例和描述的目的。其不是排它性，也不是意图限制本发明为所公开的精确形式，并且明显的，各种修改和变化是可能的。这种对于本领域普通技术人员来说明显的修改和变化被包括在所附权利要求所限定的本发明的范围内。