# US 2013/0159949 A1 · High performance design rule checking technique

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159949 A1
- Document ID: US20130159949A1
- Status: Published application
- Kind: A1
- Application number: 13/718,527
- Filed: 2012-12-18
- Published: 2013-06-20
- Earliest claimed: 2010-12-03
- Assignees: Synopsys, Inc.
- Inventors: Zuo DAI; Dick LIU; Ming SU
- Web page: https://patentgrep.com/patent/US20130159949A1

## CPC

- G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36)
- G06F 2111/04: Constraint-based CAD
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Roughly described, a design rule data set is developed offline from the design rules of a target fabrication process. A design rule checking method involves traversing the corners of shapes in a layout region, and for each corner, populating a layout topology database with values that depend on respective corner locations. After the layout topology database is populated, the values are compared to values in the design rule data set to detect any design rule violations. Violations can be reported in real time, while the user is manually editing the layout. Preferably corner traversal is performed using scan lines oriented perpendicularly to edge orientations, and scanning in the direction of the edge orientations. Scans stop only at corner positions and populate the layout topology database with what information can be gleaned based on the current scan line. The different scans need not reach each corner simultaneously.

## Claims

### Claim at position 1

1-24. (canceled)

### Claim 25

A method for checking a set of layout design rules on a region of an integrated circuit layout, the layout including a plurality of shapes each including edges in a plurality of different orientations, each of the edges having endpoints at respective locations in the layout, endpoints of edges in a first one of the orientations being first endpoints and endpoints of edges in a second one of the orientations being second endpoints,
for use by a computer system having access to a design rule data set indicating constraint values of design rules in the data set, the method comprising the steps of:
the computer system scanning the layout region in a first dimension which is perpendicular to the first edge orientation, so as to encounter first endpoints of the edges having the first orientation;
in response to encountering each of at least a first subset of at least two of the first endpoints, the computer system populating a layout topology database with values in dependence upon the respective first endpoint location;
the computer system scanning the layout region in a second dimension which is perpendicular to the second edge orientation, so as to encounter second endpoints of the edges having the second orientation;
in response to encountering each of at least a second subset of at least two of the second endpoints, the computer system populating the layout topology database with values in dependence upon the respective second endpoint location;
after the layout topology database has been populated with values in dependence upon the first endpoint location of all endpoints in the first subset of endpoints, and values in dependence upon the second endpoint location of all endpoints in the second subset of endpoints, the computer system comparing values in the layout topology database to values in the design rule data set to detect any violations of design rules in the set of design rules; and
where a design rule violation is detected, reporting it to a user.

### Claim 26 (depends on 25)

A method according to claim 25, wherein the step of the computer system scanning the layout region in a first dimension comprises the step of the computer system scanning the layout region so as to encounter the first endpoints in a monotonically varying position in the first dimension.

### Claim 27 (depends on 26)

A method according to claim 26, wherein the step of the computer system scanning the layout region in a second dimension comprises the step of the computer system scanning the layout region so as to encounter the second endpoints in a monotonically varying position in the second dimension.

### Claim 28 (depends on 25)

A method according to claim 25, wherein each of the first endpoints has a position in the first dimension,
and wherein the step of the computer system scanning the layout region in a first dimension comprises the step of the computer system jumping only among positions in the first dimension which match positions in the first dimension of first endpoints.

### Claim 29 (depends on 28)

A method according to claim 28, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
wherein the first subset of first endpoints includes all endpoints of the first edges which endpoints coincide with corners of the islands.

### Claim 30 (depends on 28)

A method according to claim 28, wherein the second endpoints each have a position in the second dimension,
and wherein the step of the computer system scanning the layout region in a second dimension comprises the step of the computer system jumping only among positions in the second dimension which match positions in the second dimension of second endpoints.

### Claim 31 (depends on 30)

A method according to claim 30, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
wherein the first subset of first endpoints includes all endpoints of the first edges which endpoints coincide with corners of the islands
and wherein the second subset of second endpoints includes all endpoints of the second edges which endpoints coincide with corners of the islands.

### Claim 32 (depends on 31)

A method according to claim 31, wherein the step of the computer system jumping only among positions in the first dimension which match positions in the first dimension of first endpoints, comprises the step of the computer system jumping only monotonically among positions in the first dimension which match positions in the first dimension of first endpoints,
and wherein the step of the computer system jumping only among positions in the second dimension which match positions in the second dimension of second endpoints, comprises the step of the computer system jumping only monotonically among positions in the second dimension which match positions in the second dimension of second endpoints.

### Claim 33 (depends on 28)

A method according to claim 28, wherein the step of the computer system jumping only among positions in the first dimension which match positions in the first dimension of first endpoints, comprises the step of the computer system jumping only monotonically among positions in the first dimension which match positions in the first dimension of first endpoints.

### Claim 34 (depends on 25)

A method according to claim 25, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
and wherein the step of the computer system scanning the layout region in a first dimension avoids first endpoints which do not lie on an island contour.

### Claim 35 (depends on 25)

A method according to claim 25, wherein the step of the computer system scanning the layout region in a first dimension, completes before the step of the computer system scanning the layout region in a second dimension, begins.

### Claim 36 (depends on 25)

A method according to claim 25, wherein the step of the computer system scanning the layout region in a first dimension, and the step of the computer system scanning the layout region in a second dimension, are performed concurrently.

### Claim 37 (depends on 25)

A method according to claim 25, wherein the plurality of orientations consists of first and second orientations which are perpendicular to each other.

### Claim 38 (depends on 25)

A method according to claim 25, wherein a design rule violation is detected in the step of the computer system comparing values.

### Claim 39

(canceled)

### Claim 40

A system for checking a set of layout design rules on a region of an integrated circuit layout, the layout including a plurality of shapes each having shape corners at respective locations in the layout, comprising:
a computer system having access to a design rule data set indicating constraint values of design rules in the data set, the computer system further having access to computer instructions and data which, when applied to the computer system, perform the steps of:
scanning the layout region in a first dimension which is perpendicular to the first edge orientation, so as to encounter first endpoints of the edges having the first orientation;
in response to encountering each of at least a first subset of at least two of the first endpoints, the computer system populating a layout topology database with values in dependence upon the respective first endpoint location;
scanning the layout region in a second dimension which is perpendicular to the second edge orientation, so as to encounter second endpoints of the edges having the second orientation;
in response to encountering each of at least a second subset of at least two of the second endpoints, the computer system populating the layout topology database with values in dependence upon the respective second endpoint location;
after the layout topology database has been populated with values in dependence upon the first endpoint location of all endpoints in the first subset of endpoints, and values in dependence upon the second endpoint location of all endpoints in the second subset of endpoints, comparing values in the layout topology database to values in the design rule data set to detect any violations of design rules in the set of design rules; and
where a design rule violation is detected, reporting it to a user.

### Claim 41

(canceled)

### Claim 42

A computer program product for checking a set of layout design rules on a region of an integrated circuit layout, the layout including a plurality of shapes each having shape corners at respective locations in the layout, for use by a computer system having access to a design rule data set indicating constraint values of design rules in the data set, the computer program product comprising
a computer readable medium having stored thereon a plurality of software code portions and data which when executed by the computer system perform the steps of:
scanning the layout region in a first dimension which is perpendicular to the first edge orientation, so as to encounter first endpoints of the edges having the first orientation;
in response to encountering each of at least a first subset of at least two of the first endpoints, populating a layout topology database with values in dependence upon the respective first endpoint location;
scanning the layout region in a second dimension which is perpendicular to the second edge orientation, so as to encounter second endpoints of the edges having the second orientation;
in response to encountering each of at least a second subset of at least two of the second endpoints, populating the layout topology database with values in dependence upon the respective second endpoint location;
after the layout topology database has been populated with values in dependence upon the first endpoint location of all endpoints in the first subset of endpoints, and values in dependence upon the second endpoint location of all endpoints in the second subset of endpoints, comparing values in the layout topology database to values in the design rule data set to detect any violations of design rules in the set of design rules; and
where a design rule violation is detected, reporting it to a user.

### Claim 43 (depends on 40)

A system according to claim 40, wherein the step of the computer system scanning the layout region in a first dimension comprises the step of the computer system scanning the layout region so as to encounter the first endpoints in a monotonically varying position in the first dimension.

### Claim 44 (depends on 43)

A system according to claim 43, wherein the step of the computer system scanning the layout region in a second dimension comprises the step of the computer system scanning the layout region so as to encounter the second endpoints in a monotonically varying position in the second dimension.

### Claim 45 (depends on 40)

A system according to claim 40, wherein each of the first endpoints has a position in the first dimension,
and wherein the step of the computer system scanning the layout region in a first dimension comprises the step of the computer system jumping only among positions in the first dimension which match positions in the first dimension of first endpoints.

### Claim 46 (depends on 45)

A system according to claim 45, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
wherein the first subset of first endpoints includes all endpoints of the first edges which endpoints coincide with corners of the islands.

### Claim 47 (depends on 45)

A system according to claim 45, wherein the second endpoints each have a position in the second dimension,
and wherein the step of the computer system scanning the layout region in a second dimension comprises the step of the computer system jumping only among positions in the second dimension which match positions in the second dimension of second endpoints.

### Claim 48 (depends on 47)

A system according to claim 47, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
wherein the first subset of first endpoints includes all endpoints of the first edges which endpoints coincide with corners of the islands
and wherein the second subset of second endpoints includes all endpoints of the second edges which endpoints coincide with corners of the islands.

### Claim 49 (depends on 48)

A system according to claim 48, wherein the step of the computer system jumping only among positions in the first dimension which match positions in the first dimension of first endpoints, comprises the step of the computer system jumping only monotonically among positions in the first dimension which match positions in the first dimension of first endpoints,
and wherein the step of the computer system jumping only among positions in the second dimension which match positions in the second dimension of second endpoints, comprises the step of the computer system jumping only monotonically among positions in the second dimension which match positions in the second dimension of second endpoints.

### Claim 50 (depends on 45)

A system according to claim 45, wherein the step of the computer system jumping only among positions in the first dimension which match positions in the first dimension of first endpoints, comprises the step of the computer system jumping only monotonically among positions in the first dimension which match positions in the first dimension of first endpoints.

### Claim 51 (depends on 40)

A system according to claim 40, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
and wherein the step of the computer system scanning the layout region in a first dimension avoids first endpoints Which do not lie on an island contour.

### Claim 52 (depends on 40)

A system according to claim 40, wherein the step of the computer system scanning the layout region in a first dimension, completes before the step of the computer system scanning the layout region in a second dimension, begins.

### Claim 53 (depends on 40)

A system according to claim 40, wherein the step of the computer system scanning the layout region in a first dimension, and the step of the computer system scanning the layout region in a second dimension, are performed concurrently.

### Claim 54 (depends on 40)

A system according to claim 40, wherein the plurality of orientations consists of first and second orientations which are perpendicular to each other.

### Claim 55 (depends on 42)

A product according to claim 42, wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a first dimension comprise code portions and data which when executed by the computer system perform the step of scanning the layout region so as to encounter the first endpoints in a monotonically varying position in the first dimension.

### Claim 56 (depends on 55)

A product according to claim 55, wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a second dimension comprise code portions and data which when executed by the computer system perform the step of scanning the layout region so as to encounter the second endpoints in a monotonically varying position in the second dimension.

### Claim 57 (depends on 42)

A product according to claim 42, wherein each of the first endpoints has a position in the first dimension,
and wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a first dimension comprise code portions and data which when executed by the computer system perform the step of jumping only among positions in the first dimension which match positions in the first dimension of first endpoints.

### Claim 58 (depends on 57)

A product according to claim 57, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
wherein the first subset of first endpoints includes all endpoints of the first edges which endpoints coincide with corners of the islands.

### Claim 59 (depends on 57)

A product according to claim 57, wherein the second endpoints each have a position in the second dimension,
and wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a second dimension comprise code portions and data which when executed by the computer system perform the step of jumping only among positions in the second dimension which match positions in the second dimension of second endpoints.

### Claim 60 (depends on 59)

A product according to claim 59, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
wherein the first subset of first endpoints includes all endpoints of the first edges which endpoints coincide with corners of the islands
and wherein the second subset of second endpoints includes all endpoints of the second edges which endpoints coincide with corners of the islands.

### Claim 61 (depends on 60)

A product according to claim 60, wherein the code portions and data which when executed by the computer system perform the step of jumping only among positions in the first dimension which match positions in the first dimension of first endpoints, comprise code portions and data which when executed by the computer system perform the step of jumping only monotonically among positions in the first dimension which match positions in the first dimension of first endpoints,
and wherein the code portions and data which when executed by the computer system perform the step of jumping only among positions in the second dimension which match positions in the second dimension of second endpoints, comprise code portions and data which when executed by the computer system perform the step of jumping only monotonically among positions in the second dimension which match positions in the second dimension of second endpoints.

### Claim 62 (depends on 57)

A product according to claim 57, wherein the code portions and data which when executed by the computer system perform the step of jumping only among positions in the first dimension which match positions in the first dimension of first endpoints, comprise code portions and data which when executed by the computer system perform the step of jumping only monotonically among positions in the first dimension which match positions in the first dimension of first endpoints.

### Claim 63 (depends on 42)

A product according to claim 42, wherein each of the shapes in the plurality of shapes is specific to a layer, the single layer geometric union of the shapes in the plurality of shapes forming a plurality of islands, the islands each having a contour,
and wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a first dimension avoid first endpoints which do not lie on an island contour.

### Claim 64 (depends on 42)

A product according to claim 42, wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a first dimension, complete before the code portions and data which when executed by the computer system perform the step of scanning the layout region in a second dimension, begin.

### Claim 65 (depends on 42)

A product according to claim 42, wherein the code portions and data which when executed by the computer system perform the step of scanning the layout region in a first dimension, and the code portions and data which when executed by the computer system perform the step of scanning the layout region in a second dimension, execute concurrently.

### Claim 66 (depends on 42)

A product according to claim 42, wherein the plurality of orientations consists of first and second orientations which are perpendicular to each other.