Method and apparatus for decomposing a design layout

• US 7,114,141 B1
• Filed: 08/14/2002
• Issued: 09/26/2006
• Est. Priority Date: 01/22/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew
• Primary Examiner(s): Thompson, A. M.
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US10/222,088
• Time in Patent Office: 1,504 Days
• Field of Search: 716/12, 716/13, 716/14
• 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 decomposing a design layout. The method decomposes the layout into a tessellated graph with several edges. It then computes the capacity of the edges based on a interconnect line model that is used to connect elements in the design layout. The layout has two orthogonal coordinate axes. At least one interconnect line specified by the model is neither parallel nor perpendicular to the coordinate axes. Also, in some embodiments, some of the edges are neither parallel nor perpendicular to the coordinate axes.

Claims

1. A method of decomposing a design layout, wherein the layout has a plurality of wiring layers, the method comprising:

a) decomposing the layout into a tessellated graph with a plurality of edges, said edges for defining routes within the design layout;

b) selecting a wiring model from a set of at least two wiring models, wherein each wiring model specifies a set of wiring directions in the layout, wherein at least one of the wiring models specifies a wiring direction that is not specified a wiring direction on any wiring layer of at least one other wiring model; and

c) computing the capacity of the edges based on the selected wiring model, wherein routes are defined based on the selected wiring model in order to connect elements in the design layout, and wherein a plurality of the edges are neither parallel nor perpendicular to a plurality of the other edges.

2. The method of claim 1, wherein the layout has two orthogonal coordinate axes, and wherein at least one wiring direction specified by the selected wiring model is neither parallel nor perpendicular to either coordinate axis.

3. The method of claim 2 further comprising:

identifying a capacity vector for a particular edge;

computing the capacity of the particular edge based on the selected wiring model and the capacity vector.

4. The method of claim 3, wherein the capacity vector is the particular edge.

5. The method of claim 4, wherein the particular edge connects to a virtual pin in the design layout.

6. The method of claim 3, wherein the particular edge is between two nodes each of which is associated with a particular geometry in the layout, wherein the capacity vector is a vector that traverses the shortest distance between the sides of the two geometries associated with the two nodes.

7. The method of claim 3, wherein computing the capacity of the particular edge comprises projecting the capacity vector on to the closest wiring direction specified by the selected wiring model for the layer containing the particular edge.

8. The method of claim 3, further comprising:

identifying a plurality of sectors each of which specifies a range of angles, and each of which is associated with a wiring direction specified by the selected wiring model;

identifying the sector in which the capacity vector'"'"'s angle with respect to the coordinate system of the layout falls;

projecting the capacity vector on to the wiring direction associated with the identified sector.

9. The method of claim 8, wherein the sectors specify identical ranges of angles.

10. The method of claim 8, wherein at least one sector specifies a different range of angles than at least one other sector.

11. The method of claim 10, wherein the different ranges are due to different line widths in different directions.

12. The method of claim 11, wherein the line widths are different in different directions on the same layer for one particular type of element in the design layout.

13. The method of claim 1, wherein the layout represents the design of a portion of an integrated circuit.

14. The method of claim 1, wherein the layout represents the design of an entire integrated circuit.

15. A computer readable medium that stores a computer program for decomposing a design layout, wherein the layout has a plurality of wiring layers, the computer program comprising instructions for:

a) decomposing the layout into a tessellated graph with a plurality of edges, said edges for defining routes within the design layout;

b) selecting a wiring model from a set of at least two wiring models, wherein each wiring model specifies a set of wiring directions in the layout, wherein at least one of the wiring models specifies a wiring direction that is not specified as a wiring direction on any wiring layer of at least one other wiring model; and

c) computing the capacity of the edges based on the selected wiring model, wherein routes are defined based on the selected wiring model in order to connect elements in the design layout, and wherein a plurality of the edges are neither parallel nor perpendicular to a plurality of the other edges.

16. The computer readable medium of claim 15, wherein the layout has two orthogonal coordinate axes, wherein at least one wiring direction specified by the selected wiring model is neither parallel nor perpendicular to either coordinate axis.

17. The computer readable medium of claim 16, wherein the computer program further comprises instructions for:

identifying a capacity vector for a particular edge;

computing the capacity of the particular edge based on the selected wiring model and the capacity vector.

18. The computer readable medium of claim 17, wherein the capacity vector is the particular edge.

19. The computer readable medium of claim 17, wherein the particular edge is between two nodes each of which is associated with a particular geometry in the layout, wherein the capacity vector is a vector that traverses the shortest distance between the sides of the two geometries associated with the two nodes.

20. The computer readable medium of claim 17, wherein the instructions for computing the capacity of the particular edge comprises instructions for projecting the capacity vector on to the closest wiring direction specified by the selected wiring model for the layer containing the particular edge.

21. The computer readable medium of claim 17, wherein the computer program further comprises instructions for:

identifying a plurality of sectors each of which specifies a range of angles, and each of which is associated with a wiring direction specified by the selected wiring model;

identifying the sector in which the capacity vector'"'"'s angle with respect to the coordinate system of the layout falls;

projecting the capacity vector on to the wiring direction associated with the identified sector.

22. The computer readable medium of claim 21, wherein the sectors specify identical ranges of angles.

23. The computer readable medium of claim 21, wherein at least one sector specifies a different range of angles than at least one other sector.