Method and apparatus for routing with independent goals on different layers

• US 20040098697A1
• Filed: 12/31/2002
• Published: 05/20/2004
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group), Cadence Design Systems Limited (Cadence Group)
• Original Assignee: Cadence Design Systems Limited (Cadence Group)
• Inventors: Caldwell, Andrew, Frankle, Jonathan
• Granted Patent: US 7,480,885 B2
• Time in Patent Office: Days
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method of routing. The method selects a net with a set of routable elements in a multi-layer layout region. In some embodiments, the method identifies a route for the net based on different congestion goals on different layers. In other embodiments, the method identifies a route for the net based on different congestion goals between different layer pairs. In some embodiments, the method identifies a route for the net based on both the different congestion goals on different layers and between different layer pairs.

Claims

1. A method of routing comprising:

a) selecting a net with a set of routable elements in a multi-layer layout region;

b) identifying a route for the net based on different congestion goals on different layers.

2. The method of claim 1, wherein identifying a route comprises computing a cost for the route by using different congestion factors for different layers.

3. The method of claim 2, wherein the route cost is also based on routing capacity of different areas on each layer and based on usage of the different areas.

4. The method of claim 3, wherein computing the cost comprises using an exponential expression having an exponent that includes a capacity value, a usage value, and a goal factor.

5. The method of claim 4, wherein the capacity of an area on a particular is multiplied by the congestion goal of the particular layer in the exponent.

6. The method of claim 5, wherein the exponent includes the usage value divided by the result of the multiplication.

7. The method of claim 2, wherein the route is a portion of a potential route for the net, wherein the computed cost is the cost of the potential route.

8. The method of claim 7 further comprising:

a) performing a path search to identify a path for the net, wherein the potential route is a path identified through the path search;

b) wherein the computed cost is the cost of defining the potential path by expanding about a previously defined path.

15. The method of claim 2 further comprising:

a) performing a path search to identify a path for the net, wherein the route is a path identified through the path search;

b) wherein the computed cost is the cost of defining the potential path by expanding about a previously defined path.

9. A method of routing comprising:

a) selecting a net with a set of routable elements in a multi-layer layout region;

b) identifying a route for the net based on different congestion goals between different layers.

10. The method of claim 9, wherein identifying a route comprises computing a cost for the route by using different congestion factors for different pairs of layers.

11. The method of claim 10, wherein the route cost is also based on routing capacity between at least a particular pair of layers and based on at least one usage value of the particular pair of layers.

12. The method of claim 11, wherein computing the cost comprises using an exponential expression having an exponent that includes a capacity value, a usage value, and a goal factor.

13. The method of claim 12, wherein, in the exponent, the capacity between the particular pair of layers is multiplied by the congestion goal of the particular pair of layers.

14. The method of claim 13, wherein the exponent includes the usage value divided by the result of the multiplication.