Method and apparatus for routing with independent goals on different layers

• US 7,480,885 B2
• Filed: 12/31/2002
• Issued: 01/20/2009
• Est. Priority Date: 11/18/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group), Cadence Design Systems Limited (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Caldwell, Andrew, Frankle, Jonathan
• Primary Examiner(s): ROSSOSHEK, YELENA
• Application Number:
  US10/335,180
• Publication Number:
  US 20040098697A1
• Time in Patent Office: 2,212 Days
• Field of Search: 716/2, 716/5, 716 8- 10, 716/12, 716/13, 716/18, 700/121, 257/40, 257/401, 257/659, 257/700, 257/758
• 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 integrated circuit (“

IC”

) design layout region, wherein the multi-layer region comprises a set of sub-regions; and

b) identifying a route for the net based on (i) different congestion goals on different layers of the multi-layer layout region, (ii) a routing capacity value, and (iii) a usage value, wherein the identified route connects at least two sub-regions, wherein a particular congestion goal for a layer is a desired target congestion for a particular area of the layer, wherein the routing capacity value for the layer relates to a number of possible routes in the particular area of the layer, wherein the usage value for the layer relates to a number of routes in the particular area of the layer

wherein selecting the net and identifying the route are performed during a routing operation.

2. The method of claim 1, wherein identifying the route comprises computing a cost based on an exponential expression having an exponent that includes the routing capacity value, the usage value, and the particular congestion goal.

3. The method of claim 2, wherein the routing capacity of value the area of the layer is multiplied by the congestion goal of the layer in the exponent.

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

5. A computer readable medium storing a computer program for routing nets in a multi-layer integrated circuit (“

IC”

) design layout region, wherein the computer program is executable by at least one processor, wherein the computer program comprises sets of instructions for;

a) selecting a net with a set of routable elements in a multi-layer IC design layout region, wherein the multi-layer layout region comprises a set of sub-regions; and

b) identifying a route for the net based on (i) different congestion goals on different layers of the multi-layer layout region, (ii) a routing capacity value, and (iii) a usage value, wherein the identified route connects at least two sub-regions, wherein a particular congestion goal for a layer is a desired target congestion for a particular area of the layer, wherein the routing capacity value for the layer relates to a number of possible routes in the particular area of the layer, wherein the usage value for the layer relates to a number of routes in the particular area of the layer,

wherein selecting the net and identifying the route are performed during a routing operation.

6. The computer readable medium of claim 5, wherein the set of instructions for identifying the route for the net comprises a set of instructions for identifying the route for the net based on different congestion goals between different pairs of layers of the multi-layer layout region.

7. The computer readable medium of claim 6, wherein the set of instructions for identifying the route for the net based on different congestion goals between different pairs of layers of the multi-layer layout region comprises a set of instructions for computing a cost for the route by using different congestion goals for different pairs of layers.

8. A method for routing comprising:

a) identifying a first congestion goal for a first layer of a multi-layer layout integrated circuit (“

IC”

) design region;

b) identifying a second congestion goal for a second layer of the multi-layer IC design layout region, wherein the second congestion goal is different than the first congestion goal; and

c) identifying routes for nets based on (i) the first and second congestion goals, (ii) a routing capacity value, and (iii) a usage value, wherein a particular congestion goal for a particular layer relates to a desired number of routes in a particular area of the particular layer, wherein the routing capacity value for the particular layer relates to a number of possible routes in the particular area of the particular layer, wherein the usage value for the particular layer relates to a number of routes in the particular area of the particular layer.

9. The method of claim 8, wherein identifying the routes comprises computing a cost for a route by using different congestion goals for different layers.

10. The method of claim 9, wherein the route cost is based on routing capacity values of different areas on each layer and based on usage values of the different areas.

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

12. The method of claim 11 further comprising:

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

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

13. The method of claim 8, wherein identifying the routes for the nets based on the first and second congestion goals comprises identifying a route for the net based on different congestion goals between different pairs of layers of the multi-layer layout region.

14. The method of claim 13, wherein identifying the route for the net based on different congestion goals between different pairs of layers of the multi-layer layout region comprises computing a cost for the route by using different congestion goals for different pairs of layers.

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

16. The method of claim 8, wherein identifying routes comprises computing a cost for a route based on an exponential expression having an exponent that includes the capacity value, the usage value, and the particular congestion goal.

17. The method of claim 16, wherein the cost for the route is further based on a routing capacity value between a particular pair of layers that is multiplied by a congestion goal of the particular pair of layers.

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

19. The method of claim 16 wherein the route is a portion of a potential route for a net, wherein the computed cost is the cost of the potential route, the method further comprising:

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

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

20. A computer readable medium storing a computer program for routing, the computer program is executable by at least one processor, the computer program comprising sets of instructions for:

a) identifying a first congestion goal for a first layer of a multi-layer layout integrated circuit (“

IC”

) design region;

b) identifying a second congestion goal for a second layer of the multi-layer IC design layout region, wherein the second congestion goal is different than the first congestion goal; and

c) identifying routes for nets based on (i) the first and second congestion goals, (ii) a routing capacity value, and (iii) a usage value, wherein a particular congestion goal for a particular layer relates to a desired number of routes in a particular area of the particular layer, wherein the routing capacity value for the particular layer relates to a number of possible routes in the particular area of the particular layer, wherein the usage value for the particular layer relates to a number of routes in the particular area of the particular layer.

21. The computer readable medium of claim 20, wherein the sets of instructions for identifying a routes comprises a set of instructions for computing a cost for the route by using different congestion goals for different layers.

22. The computer readable medium of claim 21, wherein the route cost is based on routing capacity values of different areas on each layer and based on usage values of the different areas.