# US 7,412,682 B2 · Local preferred direction routing

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

- Number: US 7,412,682 B2
- Document ID: US7412682B2
- Status: Granted
- Kind: B2
- Application number: 11/005,169
- Filed: 2004-12-06
- Published: 2005-12-08
- Granted: 2008-08-12
- Earliest claimed: 2004-06-04
- Assignees: Cadence Design Systems, Inc.
- Inventors: Anish Malhotra; Jonathan Frankle; Asmus Hetzel; Etienne Jacques
- Web page: https://patentgrep.com/patent/US7412682B2

## CPC

- G06F 30/394: Routing (G06F30/396 takes precedence)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Some embodiments of the invention provide a method for routing. The method defines at least one wiring layer that has at least two regions with different local preferred wiring directions. The method then uses the differing local preferred wiring directions to define a global route on the wiring layer. The two regions are a first region with a first local preferred wiring direction, and a second region with a second local preferred wiring direction. The global route traverses the first region along the first local preferred wiring direction and traverses the second region along the second local preferred wiring direction.

## Claims

### Claim 1

A method of defining global routes in an integrated circuit (“IC”) layout comprising a plurality of layers, the method comprising:
a) defining a routing graph that comprises (i) a plurality of edges along a first local preferred direction defined for a first region of a particular layer of the IC layout, and (ii) a plurality of edges along a second local preferred direction defined for a second region of the particular layer, wherein the first and second local preferred directions are different;
b) defining the capacities of a plurality of edges based on the different local preferred wiring directions of the two regions; and
c) defining a global route by performing at least one path search that uses the defined capacities of the edges to determine whether a particular edge from the plurality of edges comprises sufficient available capacity for a path expansion to use the particular edge, wherein a capacity defined for an edge is based on a maximum number of global routes allowed to use the edge.

### Claim 2 (depends on 1)

The method of claim 1, wherein performing the at least one path search comprises:
a) identifying a plurality of path expansions across the plurality of edges;
b) for each particular path expansion across each edge, determining whether the particular path expansion has enough capacity for another route to use the edge; and
c) when the particular edge has enough capacity, using the particular edge to define a particular route based on the path expansion.

### Claim 3 (depends on 2)

The method of claim 2, wherein performing the at least one path search further comprises foregoing the use of the particular edge to define the particular route based on the path expansion when the particular edge does not have enough capacity.

### Claim 4 (depends on 1)

The method of claim 1, wherein performing the at least one path search comprises identifying a plurality of path expansions across the plurality of edges.

### Claim 5 (depends on 1)

The method of claim 1, wherein performing the at least one path search comprises:
a) identifying a first path expansion across a first edge, wherein the first edge is associated with a set of regions in a particular layer;
b) determining whether the first path expansion across the first edge is along a set of local preferred directions of the set of regions associated with the first edge; and
c) when the first path expansion is along the set of local preferred directions, determining whether the first edge comprises sufficient remaining capacity for another path expansion.

### Claim 6 (depends on 1)

The method of claim 1 further comprising:
a) before performing the at least one path search, identifying a set of potential directions for expansions across each of a plurality of edges based on the local preferred directions; and
b) using the identified potential directions to identify a set of path expansions during the at least one path search.

### Claim 7 (depends on 1)

The method of claim 1, wherein each edge comprises an associated direction, the method further comprising:
a) before performing the at least one path search, using the local preferred directions to identify edges in the routing graph; and
b) using the identified edges to identify a set of path expansions during the at least one path search.

### Claim 8 (depends on 2)

The method of claim 2 further comprising reducing the particular edge's capacity after using the particular edge to define the particular route, in order to account for the edges's use by the particular route.

### Claim 9 (depends on 1)

The method of claim 1, wherein each edge is associated with at least one area in the IC layout, wherein defining the capacity of an edge comprises:
a) dividing the at least one area into a plurality of sub-regions;
b) generating lines to traverse across the at least one area based on local preferred wiring directions for the sub-regions, wherein the lines start at one set of sub regions; and
c) identifying the capacity of the edge based on a number of generated lines that terminate on another set of sub-regions.

### Claim 10 (depends on 9)

The method of claim 9, wherein at least one of the lines cannot traverse across the at least one area because of blockage.

### Claim 11 (depends on 1)

The method of claim 1, wherein each edge is associated with at least one area in the IC layout, wherein defining the capacity of an edge comprises:
a) determining whether the at least one area associated with the edge covers a boundary between two different regions with two different local preferred directions; wherein the two different regions comprise first and second regions;
b) when the edge covers the boundary between the two different regions, computing an estimated number of wire tracks that are incident on that boundary in the first region and an estimated number of wire tracks that are incident on that boundary in the second region; and
c) using the estimated numbers to define the capacity of the edge.

### Claim 12 (depends on 1)

The method of claim 1,
wherein each of the plurality of layers comprises at least two regions with different local preferred wiring directions, wherein defining the capacities of the plurality of edges based on the different local preferred wiring directions of the two regions comprises defining the capacities of the plurality of edges based on different local preferred wiring directions of different regions on different layers.

### Claim 13 (depends on 1)

The method of claim 1 further comprising defining, for the first region, a set of edges along the second local preferred direction at a boundary with the second region, wherein the set of edges is for facilitating traversal of the global route between the first and second regions.

### Claim 14

A computer readable medium storing a computer program for defining global routes in an integrated circuit (“IC”) layout comprising a plurality of layers, the computer program executable by at least one processor, the computer program comprising sets of instructions for:
a) defining a routing graph that comprises (i) a plurality of edges along a first local preferred direction defined for a first region of a particular layer of the IC layout, and (ii) a plurality of edges along a second local preferred direction defined for a second region of the particular layer, wherein the first and second local preferred directions are different;
b) defining the capacities of a plurality of edges based on the different local preferred wiring directions of the two regions; and
c) defining a global route by performing at least one path search that uses the defined capacities of the edges to determine whether a particular edge from the plurality of edges comprises sufficient available capacity for a path expansion to use the particular edge, wherein a capacity defined for an edge is based on a maximum number of global routes allowed to use the edge.

### Claim 15 (depends on 14)

The computer readable medium of claim 14, wherein the set of instructions for performing the at least one path search comprises a set of instructions for:
a) identifying a plurality of path expansions across the plurality of edges;
b) for each particular path expansion across each edges, determining whether the particular path expansion has enough capacity for another route to use the edge; and
c) when the particular edge has enough capacity,using the particular edge to define a particular route based on the path expansion.

### Claim 16 (depends on 15)

The computer readable medium of claim 15, wherein the set of instructions for performing the at least one path search comprises a set of instructions for foregoing the use of the particular edge to define the particular route based on the path expansion when the particular edge does not have enough capacity.

### Claim 17 (depends on 14)

The computer readable medium of claim 14, wherein the set of instructions for performing the at least one path search comprises a set of instructions for identifying a plurality of path expansions across the plurality of edges.

### Claim 18 (depends on 15)

The computer readable medium of claim 15, wherein the computer program further comprises a set of instructions for reducing the particular edge's capacity after using the particular edge to define the particular route, in order to account for the edges's use by the particular route.

### Claim 19 (depends on 14)

The computer readable medium of claim 14, wherein each edge is associated with at least one area in the IC layout, wherein the set of instructions for defining the capacity of an edge comprises sets of instructions for:
a) dividing the at least one area into a plurality of sub-regions;
b) generating lines to traverse across the at least one area based on local preferred wiring directions for the sub-regions, wherein the lines start at one set of sub regions; and
c) identifying the capacity of the edge based on a number of generated lines that terminate on another set of sub-regions.

### Claim 20 (depends on 19)

The computer readable medium of claim 19, wherein at least one of the lines cannot traverse across the at least one area because of blockage.

### Claim 21 (depends on 14)

The computer readable medium of claim 14, wherein each edge is associated with at least one area in the IC layout, wherein the set of instructions for defining the capacity of an edge comprises sets of instructions for:
a) determining whether the at least one area associated with the edge covers a boundary between two different regions with two different local preferred directions, wherein the two different regions comprise first and second regions;
b) when the edge covers the boundary between the two different regions, computing an estimated number of wire tracks that are incident on that boundary in the first region and an estimated number of wire tracks that are incident on that boundary in the second region; and
c) using the estimated numbers to define the capacity of the edge.

### Claim 22 (depends on 14)

The computer readable medium of claim 14, wherein each of the plurality of layers comprises at least two regions with different local preferred wiring directions, wherein the set of instructions for defining the capacities of the plurality of edges based on the different local preferred wiring directions of the two regions comprises a set of instructions for defining the capacities of the plurality of edges based on different local preferred wiring directions of different regions on different layers.

### Claim 23 (depends on 14)

The computer readable medium of claim 14, wherein the computer program further comprises a set of intructions for defining, for the first region, a set of edges along the second local preferred direction at a boundary with the second region, wherein the set of edges is for facilitating traversal of the global route between the first and second regions.