Method and apparatus for generating topological routes for IC layouts using perturbations

• US 6,957,409 B1
• Filed: 08/14/2002
• Issued: 10/18/2005
• 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): DO, THUAN V
• Application Number:
  US10/219,675
• Time in Patent Office: 1,161 Days
• Field of Search: 716/1, 716/7, 716/12, 716/14, 716/13
• US Class Current: 716/130
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method for identifying topological routes in a region of an integrated circuit (“IC”) design layout. The method receives a set of nets. Each net in the set has a set of routable elements in the IC design-layout region. For each net, the method then specifies a topological route that connects the net'"'"'s routable elements. Each topological route is a route that represents a set of diffeomorphic geometric routes.

Claims

1. A method of identifying topological routes in a region of an integrated circuit (“

IC”

) design layout, the method comprising;

a) receiving a set of nets, wherein each net has a set of routable elements in the IC design-layout region;

b) generating a tessellated graph, wherein the tessellated graph is a decomposition of the design layout into a plurality of polygons; and

c) for each net, embedding in the tessellated graph a topological route that connects the net'"'"'s routable elements, wherein each topological route is a route that represents a set of geometric routes that are morphable into one another through a continuous sequence of perturbations, each geometric route being one geometric realization of the topological route.

2. The method of claim 1 wherein the tessellated graph

includes a plurality of topological items for defining topological routes, said topological items including a set of items for each net that represent the net'"'"'s routable elements;

wherein embedding a topological route for a net comprises specifying an associated set of items in the tessellated graph for the net.

3. The method of claim 2, wherein the associated set of items for at least one of the nets includes at least one item that represents a via.

4. The method of claim 2, wherein the tessellated graph includes a plurality of nodes and a plurality of edges, wherein each edge is between a pair of nodes.

5. The method of claim 4, wherein the layout has a coordinate system with at least two coordinate axes, and the tessellated graph comprises a triangulated graph that includes a plurality of edges, wherein at least some of the edges are not aligned with either coordinate axis.

6. The method of claim 4, wherein the associated set of items for at least one net includes items along edges of the tessellated graph.

7. The method of claim 6, wherein the associated set of items for at least one net includes nodes in the tessellated graph.

8. The method of claim 7, wherein certain items in the tessellated graph are vias, wherein specifying the associated sets of items for a net in the set of nets comprises identifying regions inside the polygons that are suitable for containing vias.

9. The method of claim 8, wherein identifying regions inside the polygons that are suitable for containing vias comprises:

identifying at least two regions within at least two polygons on two different layers of the tessellated graph;

identifying the intersection of the two regions;

determining that the intersection of the two regions is sufficiently large for containing a via; and

specifying the via in the identified intersection.

10. The method of claim 9, wherein the method identifies and intersects the two regions and specifies the via within the identified intersection before embedding the topological route for a net that uses the via.

11. The method of claim 9, wherein the method identifies and intersects the two regions and specifies the via within the identified intersection while embedding the topological route that uses the via.

12. The method of claim 1, wherein the topological route for each net includes a set of topological paths, wherein embedding a topological route for a net comprises using a depth first, iterative deepening path search to identify each topological path of the topological route for the net.

13. The method of claim 1, wherein the topological route for each net includes a set of topological paths, wherein the tessellated graph

includes a plurality of topological items for defining topological routes, said topological items including a first set of items for a net that represent the net'"'"'s routable elements;

and

wherein embedding a topological route comprises;

identifying each topological path of a topological route for a net by using a best first search that expresses the cost of a path that reaches a topological item in the graph in terms of a function that is defined over the topological item.

14. A computer readable medium comprising a computer program having executable code, the computer program for identifying topological routes in a region of an integrated circuit (“

IC”

) design layout, the computer program comprising sets of instructions for;

a) receiving a set of nets, wherein each net has a set of routable elements in the IC design-layout region;

b) generating a tessellated graph, wherein the tessellated graph is a decomposition of the design layout into a plurality of polygons; and

c) for each net, embedding in the tessellated graph a topological route that connects the net'"'"'s routable elements, wherein each topological route is a route that represents a set of geometric routes that are morphable into one another through a continuous sequence of perturbations, each geometric route being one geometric realization of the topological route.

15. The computer readable medium of claim 14,

wherein the tessellated graph includes a plurality of topological items for defining, topological routes, said topological items including a set of items for each net that represent the net'"'"'s routable elements;

wherein the set of instructions for embedding a topological route for a net comprises a set of instructions for specifying an associated set of items in the tessellated graph for the net.

16. The computer readable medium of claim 15, wherein the associated set of items for at least one of the nets includes at least one item that represents a via.

17. The computer readable medium of claim 15, wherein the tessellated graph includes a plurality of nodes and a plurality of edges, wherein each edge is between a pair of nodes.

18. The computer readable medium of claim 17, wherein the layout has a coordinate system with at least two coordinate axes, and the tessellated graph is a triangulated graph that includes a plurality of edges, wherein at least some of the edges are not aligned with either coordinate axis.

19. The computer readable medium of claim 14, wherein the topological route for each net includes a set of topological paths, wherein the set or instructions for embedding a topological route for a net comprises a set of instructions for using a depth first, iterative deepening path search to identify each topological path of the topological route for the net.

20. The computer readable medium of claim 14, wherein the

tessellated graph includes a plurality of topological items for defining topological routes, said topological items including a first set of items for a net that represent the net'"'"'s routable elements;

and

wherein the set of instructions for embedding a topological route comprises a set of instructions for identifying each topological path of a topological route for a net by using a best first search that expresses the cost of a path that reaches a topological item in the graph in terms of a function that is defined over the topological item.