Method and apparatus for decomposing a region of an integrated circuit layout

• US 7,020,863 B1
• Filed: 08/28/2002
• Issued: 03/28/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): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US10/231,423
• Time in Patent Office: 1,308 Days
• Field of Search: 716/7, 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 region of an intergrated circuit (“IC”) layout. The method defines several nodes in the region. The method then specifies a plurality of edges in the region. Each edge is between a pair of nodes, and some edges are neither perpendicular nor parallel to some of the edges. The method uses the edges to define routes in the region.

Claims

1. A method of decomposing a region of an integrated circuit (“

IC”

) layout, wherein the region contains a plurality of nets, wherein each net has a set of routable elements, the method comprising;

a) defining a plurality of nodes in the region of the IC layout, wherein defining the nodes comprises using the routable elements to define nodes, wherein using the routable elements to define nodes comprises defining nodes at a boundary of the routable elements; and

b) specifying a plurality of edges in the region, wherein each edge is between a pair of nodes, wherein some of the edges are neither perpendicular nor parallel to some of the other edges, wherein the edges are for use in defining routes that intersect the edges.

2. The method of claim 1, wherein at least some routable elements have vertices and edges between the vertices, wherein defining nodes at the boundary of the routable elements comprises defining nodes at vertices of the routable elements.

3. The method of claim 2, wherein defining nodes at the boundary of the routable elements further comprises defining nodes along edges of the routable elements.

4. The method of claim 1, wherein using the routable elements to define nodes comprises defining nodes within the routable elements.

5. The method of claim 1, wherein the region contains a set of obstacles, wherein defining the nodes comprises using the obstacles to define nodes.

6. The method of claim 5, wherein using the obstacles to define nodes comprises defining nodes at a boundary of the obstacles.

7. The method of claim 6, wherein at least some obstacles have vertices and edges between the vertices, wherein defining nodes at the boundary of the obstacles comprises defining nodes at vertices of the obstacles.

8. The method of claim 7, wherein defining nodes at the boundary of the obstacles further comprises defining nodes along edges of the obstacles.

9. The method of claim 5, wherein using the obstacles to define nodes comprises defining nodes within the obstacles.

10. The method of claim 9, wherein using the obstacles to define nodes further comprises defining nodes at the boundary of the obstacles.

11. The method of claim 1, wherein the region is decomposed in order to route nets in the region, wherein the nets are routes according to a particular wiring model, wherein the method further comprising:

computing a capacity of each edge based on the particular wiring model.

12. The method of claim 1, wherein the edges define a plurality of faces, wherein the method further comprises:

specifying via locations within at least some of the faces.

13. A computer readable medium that stores a computer program for decomposing a region of an integrated circuit (“

IC”

) layout, wherein the region contains a plurality of nets, wherein each net has a set of routable elements, the computer program comprising instructions for;

a) defining a plurality of nodes in the region of the IC layout, wherein defining the nodes comprises using the routable elements to define nodes, wherein using the routable elements to define nodes comprises defining nodes at a boundary of the routable elements; and

b) specifying a plurality of edges in the region, wherein each edge is between a pair of nodes, wherein some of the edges are neither perpendicular nor parallel to some of the other edges, wherein the edges are for use in defining routes that intersect the edges.

14. The computer readable medium of claim 13, wherein the region contains a plurality of nets, wherein each net has a set of obstacles, wherein the instructions for defining the nodes comprises instructions for using the obstacles to define nodes.

15. The computer readable medium of claim 13, wherein the region is decomposed in order to route nets in the region, wherein the nets are routes according to a particular wiring model, wherein the computer program further comprises instructions for computing a capacity of each edge based on the particular wiring model.

16. The computer readable medium of claim 13, wherein the edges define a plurality of faces, wherein the computer program further comprises instructions for specifying via locations within at least some of the faces.

17. A method of decomposing a region of an integrated circuit (“

IC”

) layout, wherein the layout has a pair of coordinate axes, the method comprising;

a) defining a plurality of nodes in the region of the IC layout, wherein the region contains a plurality of nets, wherein each net has a set of routable elements, wherein defining the nodes comprises using the routable elements to define nodes, wherein using the routable elements to define nodes comprises defining nodes at a boundary of the routable elements; and

b) specifying a plurality of edges in the region, wherein each edge is between a pair of nodes, wherein some of the edges are neither perpendicular nor parallel to either of the coordinate axes, wherein the edges are for use in defining routes that intersect the edges.