Method and apparatus for routing with independent goals on different layers

• US 8,112,733 B2
• Filed: 12/01/2008
• Issued: 02/07/2012
• Est. Priority Date: 11/18/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Frankle, Jonathan, Caldwell, Andrew
• Primary Examiner(s): Rossoshek, Helen
• Application Number:
  US12/326,100
• Publication Number:
  US 20090077522A1
• Time in Patent Office: 1,163 Days
• Field of Search: 716/126, 716/129, 716/130, 716/132, 716/135, 716/136, 716/137, 716/138, 716/139
• US Class Current: 716/126
• 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:

selecting a particular net with a set of routable elements in an integrated circuit (“

IC”

) design layout region comprising multiple wiring layers and;

based on at least two different via congestion goals between at least two different pairs of wiring layers, using a computer generate a route for the particular net without referencing any previously generated route for the particular net, wherein the generated route traverses at least two sub-regions of the IC design layout region.

2. The method of claim 1, wherein generating the route comprises computing a cost for the route by using different via congestion goals for different pairs of wiring layers.

3. The method of claim 2, wherein the route cost is further based on a via capacity between at least a particular pair of wiring layers and based on at least one usage value of the particular pair of wiring layers.

4. The method of claim 1, wherein generating the route comprises computing a cost based on an exponential expression having an exponent that includes a capacity value, a usage value, and a particular congestion goal for a particular pair of wiring layers.

5. The method of claim 4, wherein the capacity value between the particular pair of wiring layers is multiplied by the particular congestion goal for the particular pair of wiring layers.

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

7. The method of claim 1, wherein a particular congestion goal between a particular pair of wiring layers is a desired target congestion for at least one particular sub-region of the particular pair of wiring layers.

8. The method of claim 1, wherein the generated route is further based on a capacity value that relates to a number of possible vias for at least one particular sub-region of a particular pair of wiring layers.

9. The method of claim 1, wherein the generated route is further based on a usage value that relates to a number of vias for at least one particular sub-region of a particular pair of wiring layers.

10. The method of claim 1, wherein generating the route comprises identifying a set of sub-regions that contain at least one routable element of the particular net.

11. The method of claim 1, wherein the two sub-regions of the IC design layout region are two sub-regions on one layer of the IC design layout region.

12. The method of claim 1, wherein the two sub-regions of the IC design layout region are two sub-regions on two different layers of the IC design layout region.

13. A method of routing comprising:

receiving a first via congestion goal for a first pair of adjacent wiring layers of a multi-layer integrated circuit (“

IC”

) design layout region;

receiving a second via congestion goal for a second pair of adjacent wiring layers of the multi-layer IC design layout region, wherein each via congestion goal is related to a number of vias between a pair of adjacent wiring layers, wherein the second via congestion goal is different the first via congestion goal; and

with a computer, generating a route for a net based on the first and second via congestion goals.

14. The method of claim 13, wherein generating the route comprises computing a cost for the route by using different via congestion goals for different pairs of adjacent wiring layers.

15. The method of claim 14, wherein the route cost is based on a plurality of capacity values of different sub-regions between each pair of adjacent wiring layers and based on a plurality of usage values of the different sub-regions.

16. The method of claim 13, wherein generating the routes-route for the nets net based on the first and second via congestion goals comprises generating the route for the net based on different via congestion goals for different adjacent wiring layers of the multi-layer IC design layout region.

17. The method of claim 13, wherein generating the route for the net based on the first and second via congestion goals comprises computing a cost for the route by using different via congestion goals for different adjacent wiring layers.

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

19. The method of claim 13, wherein the generated route is further based on a via scaling factor.

20. The method of claim 13, wherein generating the route comprises identifying sub-regions of the multi-layer IC design layout region that contain at least one routable element of the net.

21. The method of claim 13, wherein each via congestion goal is further related to a target maximum number of vias between a pair of adjacent wiring layers.

22. A system comprising:

a memory for storing a computer program comprising sets of instructions; and

at least one processor for executing sets of instructions for;

selecting a particular net with a set of routable elements in an integrated circuit “

IC”

design layout region having multiple wiring layers, the IC design layout region comprising a set of sub-regions;

receiving a first via congestion goal for a first pair of wiring layers of the multi-layer IC design layout region;

receiving a second via congestion goal for a second pair of wiring layers of the multi-layer IC design layout region, wherein the second via congestion goal is different the first via congestion goal; and

generating a route for the particular net that connects the set of sub-regions that contain the set of routable elements of the particular net based on the first and second congestion goals.

23. The system of claim 22, wherein a particular congestion goal for a particular pair of wiring layers relates to a desired number of vias for at least one particular sub-region of the particular pair of wiring layers.

24. The system of claim of claim 22, wherein the generated route is further based on a via capacity value that relates to a number of possible vias for at least one particular sub-region of a particular pair of wiring layers.

25. The system of claim 22, wherein said generating the route does not rely on any previously generated route for the particular net.

26. The system of claim 22, wherein said receiving of the first and second via congestion goals is before said generating.