基于图示符的处理系统及处理基于图示符的数据的方法

摘要

一种用于处理与产生超大规模集成电路(VLSI)设计相关的基于图示符的数据的系统和方法。所提供的系统包括：串行化系统，用于将图示符设计数据的输入区域转换为伪字符串；以及模式搜索系统，通过分析由串行化系统产生的伪字符串来识别图示符设计数据中的匹配模式。模式搜索可包括例如预定义模式搜索和冗余模式搜索。

说明书

技术领域

本发明总的来说涉及处理L3GO VLSI设计，更具体地说，涉及使L3GO设计串行化并执行模式匹配的系统和方法。

背景技术

L3GO(使用网格图示符几何对象的布局)是正在进行的用于改善VLSI设计的可制造性的项目。L3GO提供受限的对象集合，其描述电路连接和装置，称为图示符(glyph)。L3GO具有三种类型的图示符，包括：

1、条状图示符，其是在两个网格点之间绘制的1维线段，例如，用于描述FET栅或用于互连。条状图示符的附属属性包括条属于哪一层、开始点和结束点、以及目标宽度；

2、接触图示符，其是在网格点设置的0维点，例如，用于描述垂直互连(接触和过孔)。接触图示符的附属属性包括：接触属于哪一层、指定接触如何排列在矩阵中的参数(例如，矩阵中的行数和列数)、每个接触的尺寸、分别在行与列之间的水平和垂直距离、矩阵中心相对于图示符位置的可选偏移；以及

3、区域图示符，其是2维的与轴对齐的矩形，矩形的顶点位于网格点上，例如，用于描述扩散区域。

除了它们特定的属性之外，图示符可携带“设计意图”属性，例如，网络名称、它们的重要性等级等。称为“加工(elaboration)”的处理将图示符的集合变为几何形状(pre-data-prep掩模形状)。模式用于描述图示符配置，例如，接触图示符具有某些置于条状图示符的属性，而条状图示符具有另一组属性。“加工”基于一组参数来创建所述配置的形状，例如，其可在M1条上创建焊接点，并在焊接点上创建4个冗余的过孔。

预定义模式的标识是加工处理的关键要素，因为其显著提高计算要求。L3GO设计中的可能配置与基于形状的VLSI设计相比是有限的。这表示在设计中可通过模式的多个布局的标识来避免冗余的计算。

然而，作为几何对象的L3GO特征(点、条、边界等)的直接描述不能使其自身实现模式的有效识别。因此，需要有效的系统来执行L3GO特征的模式识别。

发明内容

本发明通过提供一种编码方案来解决上述问题以及其它问题，所述编码方案从几何计算创建伪字符串，以允许使用有效的一维模式识别方法，特别是使用后缀树。

在第一方面，本发明提供一种用于对超大规模集成电路(VLSI)设计进行操作的基于图示符的处理系统，包括：串行化系统，用于将图示符设计数据的输入区域转换为伪字符串；以及模式搜索系统，其通过分析由串行化系统产生的伪字符串来识别在图示符设计数据中的匹配模式。

在第二方面，本发明提供一种存储在计算机可用介质上的计算机程序产品，所述计算机程序产品用于在对超大规模集成电路(VLSI)设计的操作中处理基于图示符的数据，所述计算机程序产品包括：被配置为用于将图示符设计数据的输入区域转换为伪字符串的程序代码；以及被配置为用于通过分析从图示符设计产生的伪字符串识别在图示符设计数据中的匹配模式的程序代码。

在第三方面，本发明提供一种用于在对超大规模集成电路(VLSI)设计的操作中处理基于图示符的数据的方法，包括：提供用于输入图示符设计数据的扫描窗口；将扫描窗口定位于选择的输入区域上；将图示符设计数据的输入区域转换为伪字符串；搜索用于匹配伪字符串的后缀的后缀树；以及将匹配后缀存储在库中。

附图说明

通过下面结合附图进行的对本发明各个方面的详细描述，本发明的这些和其它特点将会变得更加易于理解，其中：

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

图2示出根据本发明实施例的L3GO设计数据以及相关的一组串行间隔。

图3示出根据本发明实施例被分解为一组邻近的矩形的图2的L3GO设计数据。

图4示出用于显示根据本发明实施例的对L3GO数据进行编码的示例性处理的流程图。

图5示出用于显示根据本发明实施例的使用滑动窗口定位匹配模式数据的示例性处理的流程图。

具体实施方式

现在参照附图，图1示出具有L3GO处理系统18的计算机系统10，其分析L3GO设计数据30并识别匹配模式数据32，它们可提高由加工系统34执行的处理。应注意：尽管L3GO处理系统18被显示为独立的处理，但是它可集成到加工系统34中。还应注意到：尽管参照基于L3GO的系统描述了所示实施例，但是本发明可应用于任何当前已知或将来研发的用于产生VLSI设计的基于图示符的系统。

L3GO处理系统18包括串行化系统20，用于将L3GO特征(即，图示符)转换为串行化数据，随后，可由搜索设施来分析所述串行化数据以识别匹配模式。在所示出的实施例中，描述两个模式搜索系统，包括：预定义模式搜索系统22和冗余模式搜索系统24，稍后将对其进行更详细描述。预定义模式搜索系统22识别L3GO设计数据30中匹配已知补片模式的模式。冗余模式搜索系统24识别在L3GO设计数据30中重复的模式。应注意到：本发明并不受限于特定的模式匹配技术，其它目前已知或将来研发的基于字符串的搜索技术均落入本发明的范围中。

串行化系统20提供编码方案(在此也称为“图示符串行化”)，其从几何信息创建伪字符串，以允许使用有效的一维模式识别技术。L3GO设计数据30包括排好顺序的平面序列，每个平面用于一个设计层。串行化系统20计算用于具有轴平行边界的区域的内容的伪字符串。为了创建串行化编码，串行化线或轴被定义，在不失一般性的情况下(w.l.o.g)，串行化线或轴被选择为坐标系统的x轴，在所述坐标系统中定义了模式。

图2示出串行化处理如何将L3GO设计数据40的输入区域44编码为伪字符串。在该简化的示例中，L3GO设计数据40包括：区域图示符56、第一条状图示符48、第二条状图示符50、第三条状图示符52和接触图示符54。为了示例的目的，在L3GO设计数据40以下示出一组相应的串行化间隔42，其最终用于定义L3GO设计数据40的输入区域44的伪字符串。在该示例中，串行化间隔42包括15个间隔，在此示为交替的括号：()、[]、()等。在交替的括号类型之间的转换相应于输入区域44中的L3GO图示符特征。每个间隔最终将被分配信息，即，伪字符，以完成伪字符串。

应注意：在最简单的情况下，输入区域44是矩形。相邻的矩形将形成相邻的输入区域44。然而，只要确保对于相同的上下文，相同的输入区域44被选择，则对除了沿着串行化线46的接触矩形之外的序列的使用也是可行的。

每个串行化间隔42是输入区域44中的特征到串行化线46的投影，即，每个间隔必然与沿着串行化线46的图示符特征的位置相应，所述串行化线46穿过输入区域44。串行化线46通常沿L3GO特征(即，区域图示符的条状图示符或边界)定位。在这种情况下，串行化线46置于与条状图示符48共线。然而，可采用任何串行线的放置，例如，可将其置于通过输入区域44的中间。

如可从图3所示，与输入区域44相交的L3GO特征(在此称为侵入方)被垂直投射到串行化间隔42(用箭头60表示)。与串行化线相交的所有投影也形成间隔。接触图示符或垂直条状图示符的投影形成长度0的闭合的间隔-表示为方括号“[]”。区域图示符或垂直条状图示符的投影形成大于0的长度的开放间隔-表示为圆括号“()”以及两个长度0的闭合的间隔-表示为“[]”。如果特征到串行化间隔42的投影没有全部包括在串行化间隔42中，则形成部分开放的间隔。

针对编码考虑的输入区域44可由此被看作沿着串行化线46接触但是不重叠的矩形序列。在图3中作为示例示出，其中，基于输入区域44中的特征的位置描绘并形成7个矩形r1-r7。

基于通过投影获得的间隔的集合，将侵入方的集合编码为“伪字符串”，其包括交替的长度0的闭合间隔“[]”和长度大于0的开放间隔“()”。第一闭合间隔总是形成在串行化线42的开始，通过串行化间隔42的末尾来形成编码中的最后闭合间隔。

通过用于创建长度0的间隔的投影以及用于创建长度大于0的间隔的投影的开始和末尾来形成其它闭合间隔。

假设分割为交替的闭合和开放间隔l，则通过其投影与分割的间隔l相交的图示符的集合来定义伪字符串中的“伪字符”。每个投影表征为：(1)被投影的内容，(2)其驻留在哪个级别，以及(3)其距离串行化线46的偏移。排序的惯例确保每个列表的成员具有规范(canonical)的线性排序，存在多个排序惯例的可能性。

图2示出产生15个字符的伪字符串的示例。将符号分配给每个侵入方，其中，每个符号代表如下描述。

B-与串行化线共线的图示符48。

R-区域图示符56。

X-接触图示符54。

V-垂直图示符50。

H-具有偏移的水平图示符52。

分别用索引l和r来表示投影的左端和右端，用没有格式的字母来表示开放的段。例如，符号V可表示描述’y、M1、S、[)、+0.3、0.5’，其表示

.侵入方与串行化线垂直(布尔值y/n)

.侵入方在级别M1上

.侵入方是条状图示符(类型S、R、X)

.较低端可见，上端不可见

.对串行化线的偏移为0.3长度单位，位于串行化系统之上

.在模式中考虑的图示符片段的长度为0.5单位(在这种情况下，其到达输入区域的边界，这是由于它的第二端不可见，所以这一数字在某种程度上是冗余的)。

如所标注的，伪字符串包括15个伪字符，c1、...、c15。用li来表示与字符ci关联的间隔的长度。每个伪字符表征为：其相应的间隔的类型、间隔(如果为开放)的长度以及其投影与间隔相交的侵入方的列表L。在上述示例中，如下形成字符串：

1.[]，O，L＝{}

2.()，l2，L＝{}

3.[]，O，L＝{Bl}

4.()，l4，L＝{B}

5.[]，O，L＝{B，Rl}

6.()，l6，L＝{B，R}

7.[]，O，L＝{B，Rr}

8.()，l8，L＝{B}

9.[]，O，L＝{B，X}

10.()，l10，L＝{B}

11.[]，O，L＝{B，Hl，V}

12.()，l12，L＝{B，H}

13.[]，O，L＝{Br，H}

14.()，l14，L＝{H}

15.[]，O，：＝{H}

由于在编码与侵入方集合配置之间存在一对一对应，所以可按照所述伪字符串形式来表示模式。例如，从接触沿着两个方向至少延伸1x的M1轨迹上的接触补片为(B作为用于轨迹的符号，X为用于接触的符号)：

·()，lx，L＝{B}

·[]，O，L＝{B，X}

·()，lx，L＝{B}

即，lx＜＝l8，lx＜＝l10，这是图示符串行化的子字符串。应注意：这种编码形式可表示图示符与形状的任何配置(形状必须按照规范的形式分解为矩形和三角形，其中，与串行化线平行和垂直地进行切割)。

这一处理的优势在于以下情况：设计以网格为主，并且L3GO设计中的对象是高度受限的。切实可行的惯例为串行化线被布置得：

.沿着条状图示符，从而原点在设计坐标系统中位于条的左下端。

.在点图示符上是水平或垂直的，从而点图示符位于原点。

.沿着最大连接点的集合，从而边缘的左下端位于原点。

作为进一步的限制，可将输入和输出区域限制为矩形，其一对边与串行化线46平行。其它惯例也是可行的，例如，如果允许非垂直的几何形状，则所有串行化线必须为水平或垂直，并且条或边缘的左下端必须位于原点，从而条或边缘位于第一象限。

图4示出用于显示编码L3GO数据的示例处理的流程图。首先，在步骤S1，定义输入区域，例如，窗口(x1，y1)，(x2，y2)。接着，在步骤S2确定输入区域的内容，即，L3GO特征。在步骤S3，将输入区域的左端和右端投射到串行化线上。在一示出的实施例中，串行化线是中心线，定义为(x1，(y1+y2)/2，x2，(y1+y2)/2)。接着，在步骤S4，基于输入区域中特征的位置形成宽度w的串行化间隔，其中，对于端点的投影，w＝0，在端点的投影之间，w＞0。

对于每个串行化间隔，采取以下步骤。在步骤S5，将投射到间隔上的特征按照规范排序，在步骤S6，将规范的排序散列到固定大小的值(例如，32比特)。一旦所有的间隔均被处理，则在步骤S7输出伪字符串。

根据按照上述方式串行化L3GO设计数据30的能力，可容易地定义匹配模式数据32。一种用于实现上述处理的技术涉及使用预定义模式搜索系统22(图1)。一旦输入区域44被串行化，则串行化线的原点的选择提供模式的锚点，即，原点定义设计中所述串行化线可能位于的点的特征。一示例为M1条的开始。根据是否期望进行子模式搜索，伪字符串可用于分别构建后缀树或特里结构。后缀树或特里结构(即，能够按照可被有效搜索的形式保存字符串的数据结构)在本领域是已知的，因此不在此进行详细讨论。

编码的完整列表还提供可能的锚点类型的列表。如果子模式受关注，则可行的锚点类型的列表更加通用，从而其覆盖所有模式的所有特征，不仅仅是模式中的第一特征。

因此，预定义模式搜索系统22(图1)首先扫描L3GO设计数据以找到锚点的潜在位置，即，与从模式集合获得的可能锚点的特征匹配的设计中的所有点。在每个这种点上，放置垂直化线，输入区域和它的侵入方被确定，并且配置被串行化。从在设计位置的串行化获得的伪字符串随后用于在后缀树或特里结构中进行搜索以找到匹配。

用于模式匹配的第二种技术涉及使用冗余模式匹配系统24。通过使用上述串行化方案，可找到在L3GO设计数据30中多次出现的配置。

在这一方法中，可采用扫描线来穿过L3GO设计数据30，将具有标准化输入区域的串行化线置于特征位置，例如，条端和边界端，并确定每个输入区域的侵入方。可通过潜在特征的长度或通过预先选择的值来选择串行化线的末端。扫描线使用间隔树来找到输入区域的部分之间的侵入(输入区域为与轴平行的矩形)。当串行化线的输入区域离开扫描线时，它的所有侵入方已知。

一旦串行化线的所有侵入方已知，则伪字符串被确定。应注意：侵入方的相同集合允许系统计算具有减小尺寸(通常为涉及设计种的倾斜或轨迹距离的宽度变化)的输入区域的多个伪字符串。

为了找到多个同时出现的配置，目前找到的字符串编码的集合按照允许有效搜索子字符串的方式来进行组织。为了这一目的，可使用后缀树28。后缀树28允许冗余模式搜索系统24找到查询字符串q的最大前缀P，作为存储在后缀树28中的字符串集合S的子字符串。搜索时间为O(|q|)。因此，设计中所有串行化编码的后缀树28允许冗余模式搜索系统24用对子字符串的一个副本的引用来替换多个同时出现的相同子字符串。通常，VLSI设计的编码中的字符串具有很大程度的重叠，从而不独立地存储字符串是有益处的。相反，当重叠被添加到后缀树28和合并重叠字符串时找到所述重叠，这会更好。这显著减小了后缀树28的大小，还允许系统找到更大的模式。

此外，由于VLSI设计的大小较大，所以，即使在通过合并重叠字符串而获得减小的情况下也不期望一次性存储整个设计的编码。滑动窗口系统26(诸如在LZ77压缩算法中所使用的)减少存储要求。为此，当从扫描线获得串行化时，填充后缀树28，包括合并重叠字符串。对于后缀树28的每个入口(entry)，保持它的任何贡献者的最右端坐标。如果以后缀树入口存储的坐标是扫描线位置的左侧距离w(假设是右到左的扫描)，w是滑动窗口的宽度，则入口被丢掉。

使用引用来代替副本的好处取决于引用的部分有多大以及其出现的频率。一旦在选择的成本模型中找到用作引用是有益处的子字符串，则其被移到另一后缀树28，其永久地收集包含冗余地出现的子字符串的字符串。可使用成本模型来确定哪种处理是有益处的：将新的入口添加到永久集合中，或者最终使用已经提出多次的较小的子字符串。

滑动窗口方式需要动态后缀树，其对于添加和删除操作的序列保持O(N)大小的复杂性，但是不保持O(N)成本的复杂性。但是对于实际的实施，对于所指出的入口的添加和删除，O(S2)的复杂性应该是足够的，这是由于在没有丢失显著的益处的情况下可将字符串大小限定为常数。

成本模型取决于如何使用多个同时出现的配置。一种方案在于创建附加单元，并用所述单元的实例来替换同时出现的配置。除了存储讨论的图示符的集合之外，单元需要附加的资源。此外，实例需要资源。为了使引入新的单元产生益处，例如，用于减少存储，用实例替换固有图示符的集合必须减少使用的资源量。此外，通过用实例替换模式的副本产生的所有节约的总和必须多于对附加单元的成本的补偿。

在另一方案中，可考虑计算成本。可对于较大的模式计算解，对于任何子模式，可设置所述解的一部分。

图5示出用于显示使用滑动窗口系统26来定位匹配模式数据的示例处理的流程图。对于L3GO设计数据中的每个潜在的编码位置，采取以下步骤。首先，在步骤S10，将上下文区域(即，窗口)中的数据编码为伪字符串S。接着，在步骤S11，在后缀树R中搜索S的所有后缀。在步骤S12，使用成本函数来获得后缀匹配的最佳子集Q。在步骤S13，将子集Q存储在库P中，在步骤S14，用对库P的引用来替换内容区域。在步骤S15，将伪字符串S存储在后缀树R中。最后，在步骤S16，从后缀树R去除落入滑动窗口之外的先前编码的伪字符串，以限制和约束R的大小。

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

I/O 14可包括用于向/从外部资源交换信息的任何系统。外部装置/资源可包括任何已知类型的外部装置，包括：监视器/显示器、扬声器、存储器、另一计算机系统、手持装置、键盘、鼠标、声音识别系统、语音输出系统、打印机、传真机、寻呼机等。总线17提供计算机系统10中的每个部件之间的通信链路，其同样可包括任何已知类型的传输链路，包括：电链路、光链路和无线链路等。尽管没有示出，但是可将其它部件并入计算机系统10中，诸如高速缓冲存储器、通信系统、系统软件等。

可通过网络(诸如互联网、局域网(LAN)、广域网(WAN)、虚拟专用网(VPN)等)提供对计算机系统10的访问。可经由直接硬线连接(例如，串口)或经由可采用任何有线和/或无线传输方法的组合的可寻址连接来进行通信。此外，可使用传统网络连接，诸如令牌环、以太网、WiFi或其它传统通信标准。此外，可通过基于传统TCP/IP报路的协议来提供连接。在这种情况下，以太网服务提供者可用于建立互连。此外，如以上所指出的，可在客户机-服务器或服务器-服务器环境中进行通信。

应理解：可提供本发明的教导，作为基于预订或收费的商业方法。例如，可通过向提供这里描述的功能的服务提供者来创建、维护和/或采用包括L3GO处理系统18的计算机系统10。也就是说，服务提供者可提供如上所述的模式匹配。

应理解：可通过硬件、软件或硬件以及软件的组合来实现这里描述的系统、功能、机制、方法、引擎和模块。可通过任何类型的计算机系统或被用来实现这里描述的方法的其它设备来实现它们。硬件和软件的典型组合可以是具有计算机程序的通用计算机系统，所述计算机程序在被加载和执行时，控制计算机系统从而实施这里所述的方法。或者，可采用专用计算机，其包含用于实现本发明的一个或多个功能任务的专用硬件。在另一实施例中，可按照分布方式(例如，通过诸如互联网的网络)来实现本发明的部分或全部。

还可将本发明嵌入计算机程序产品中，其包括实现这里所述的方法和功能的所有特征，并且当被载入计算机系统时，其能够实施这些方法和功能。该上下文中出现的术语(诸如计算机程序、软件程序、程序、程序产品、软件等)表示指令集合的以任何语言、代码或符号的任何表示，所述指令意在促使具有信息处理能力的系统直接执行特定功能，或在以下两个处理之一或全部之后执行特定功能：(a)转换为另一语言、代码或符号之后；和/或(b)以另一原料形式进行再生之后。

已经为了示例和描述的目的提供了本发明的上述描述。并不是为了将本发明穷尽或限制到这里公开的具体形式，很明显，可进行许多修改和变型。本领域的技术人员将清楚的所述修改和变型旨在包括在由权利要求限定的本发明的范围之内。