Topological vias route wherein the topological via does not have a coordinate within the region

• US 7,089,524 B1
• Filed: 08/28/2002
• Issued: 08/08/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): DO, THUAN V
• Application Number:
  US10/233,202
• Time in Patent Office: 1,441 Days
• Field of Search: 716/9, 716/1, 716/2, 716/11, 716/12, 716/14, 438/14
• US Class Current: 716/130
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

Some embodiments of the invention provide a method for generating multi-layer topological routes in a region of a design layout. The method selects a net that has routable elements on a several interconnect layers. For the selected net, the method defines a topological route that connects the selected net'"'"'s routable elements. The topological route includes a topological via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, without having a coordinate within the region.

Claims

1. A method for generating multi-layer topological routes in a region of a design layout comprising:

a) selecting a net having routable elements on a plurality of interconnect layers; and

b) for the selected net, defining a topological route that connects the selected net'"'"'s routable elements, wherein the topological route includes a topological via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, wherein the topological via does not have a coordinate within the region.

2. The method of claim 1 further comprising:

a) selecting a second net having routable elements on a plurality of interconnect layers; and

b) for the selected second net, defining a topological route that connects the selected second net'"'"'s routable elements, wherein the topological route includes a topological via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, wherein the topological via does not have a coordinate within the region.

3. The method of claim 1 further comprising:

a) decomposing the region into a tessellated graph with a plurality of faces;

b) defining the topological vias within the interior of the faces.

4. The method of claim 3, wherein a topological via traverses two faces on two different layers.

5. The method of claim 4 further comprising:

defining a topological via that traverses two faces when the overlap of two regions within the two faces is a region that is sufficiently large to contain a via.

6. The method of claim 5, wherein a via can be anywhere within the overlapping region based on which it is defined.

7. The method of claim 1 further comprising:

a) selecting a second net having routable elements on a plurality of interconnect layers; and

b) for the selected second net, defining a second topological route that connects the selected second net'"'"'s routable elements, wherein the second topological route includes a second via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, wherein the second via has a fixed coordinate within the region.

9. The method of claim 1, wherein the topological structure includes a graph for each layer of the region.

10. The method of claim 9, wherein each graph is defined by generating a tessellated graph based on geometries in the graph'"'"'s corresponding layer.

11. The method of claim 10, wherein the geometries represent routable elements in the region.

12. The method of claim 10, wherein the geometries represent obstacles in the region.

13. The method of claim 12, wherein the geometries represent routable elements in the region.

8. A method for generating multi-layer topological routes in a region of a design layout comprising:

a) defining a topological structure to represent a multi-interconnect layer region for routing; and

b) embedding topological routes of nets in the topological structure, wherein some routes use topological vias to traverse between the region'"'"'s interconnect layers;

wherein the topological vias do not have fixed coordinates that specify their location within the structure.

14. A computer readable medium storing a computer program for generating multi-layer topological routes in a region of a design layout, the computer program comprising instructions for:

a) selecting a net having routable elements on a plurality of interconnect layers; and

b) for the selected net, defining a topological route that connects the selected net'"'"'s routable elements, wherein the topological route includes a topological via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, wherein the topological via does not have a coordinate within the region.

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

a) selecting a second net having routable elements on a plurality of interconnect layers; and

b) for the selected second net, defining a topological route that connects the selected second net'"'"'s routable elements, wherein the topological route includes a topological via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, wherein the topological via does not have a coordinate within the region.

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

a) decomposing the region into a tessellated graph with a plurality of faces;

b) defining the topological vias within the interior of the faces.

17. The computer readable medium of claim 16, wherein a topological via traverses two faces on two different layers.

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

defining a topological via that traverses two faces when the overlap of two regions within the two faces is a region that is sufficiently large to contain a via.

19. The computer readable medium of claim 18, wherein a via can be anywhere within the overlapping region based on which it is defined.

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

a) selecting a second net having routable elements on a plurality of interconnect layers; and

b) for the selected second net, defining a second topological route that connects the selected second net'"'"'s routable elements, wherein the second topological route includes a second via that specifies the defined route'"'"'s traversal from one interconnect layer to another interconnect layer, wherein the second via has a fixed coordinate within the region.