Method and apparatus for routing

• US 6,889,372 B1
• Filed: 10/31/2002
• Issued: 05/03/2005
• Est. Priority Date: 07/15/2000
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew
• Primary Examiner(s): WHITMORE, STACY
• Application Number:
  US10/286,598
• Time in Patent Office: 915 Days
• Field of Search: 716 12- 14
• 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 of identifying routes for net in a region of a design layout. The method identifies a first route for a first net without using a routing grid. It then updates at least one previously defined route for another net to account for spacing constraints relating to the first route. In some embodiments, the method further (1) identifies previously defined routes that might need to be modified to account for spacing constraints relating to the first route; (2) examines the identified routes to determine whether the identified routes need to be modified to account for spacing constraints relating to the first route; and (3) updates several previously defined routes to account for spacing constraints relating to the first route.

Claims

1. A method of identifying routes for nets in a region of a design layout, the method comprising:

a) identifying a first route for a first net without using a routing grid, and

b) shoving at least one previously defined route for another net within the region of the design layout by updating said at least one previously defined route for the other net to account for spacing constraints relating to the first route, without removing any segment of the previously defined route.

2. The method of claim 1 further comprising:

a) identifying previously defined routes that might need to be modified to account for spacing constraints relating to the first route;

b) examining the identified routes to determine whether the identified routes need to be modified to account for spacing constraints relating to the first route; and

c) shoving a plurality of previously defined routes within the region of the design layout by updating the plurality of previously defined routes to account for spacing constraints relating to the first route.

3. The method of claim 2 further comprising defining a tessellated graph of the region, wherein the tessellated graph has a plurality of edges, wherein the routes are defined with respect to the edges.

4. The method of claim 3, wherein the routes are topological routes.

5. The method of claim 4, wherein a topological particle is specified for each route at an intersection of the route and each edge that the route intersects, wherein identifying previously defined routes that might need to be modified comprises identifying the routes that have topological particles on edges that the first route intersects.

6. The method of claim 5, wherein the topological particles have an assigned coordinate in the layout, wherein updating a previously defined route comprises modifying the coordinate of at least one particular topological particle for the route to account for a required spacing between the previously defined route and the first route along the edge on which the particular topological particle exists.

7. The method of claim 6, wherein the first route is a portion of a larger route for the first net.

8. A method of defining topological routes for nets in a region of a design layout, wherein the topological routes are optimized for a particular interconnect-line model that specifies a plurality of interconnect line directions, the method comprising:

a) specifying a first topological route for a first net;

b) specifying a temporary geometrical embedding for the first topological route, wherein the temporary geometric embedding specifies a series of connected topological particles, wherein the series of connected topological particles includes at least two particles that are along a line that is not aligned with any of the interconnect-line directions specified by the wiring model;

c) specifying a second topological route for a second net; and

d) updating the temporary geometric embedding of the first topological route to account for spacing constraints related to the second topological route.

9. A computer readable medium that stores a computer program having executable code, the computer program for identifying routes for nets in a region of a design layout, the computer program comprising sets of instructions for:

a) identifying a first route for a first net without using a routing grid, and

b) shoving at least one previously defined route for another net within the region of the design layout by updating said at least one previously defined route for the other net to account for spacing constraints relating to the first route, without removing any segment of the previously defined route.

10. The computer readable medium of claim 9, wherein the computer program further comprises sets of instructions for:

a) identifying previously defined routes that might need to be modified to account for spacing constraints relating to the first route;

b) examining the identified routes to determine whether the identified routes need to be modified to account for spacing constraints relating to the first route; and

c) shoving a plurality of previously defined routes within the region of the design layout by updating the plurality of previously defined routes to account for spacing constraints relating to the first route.

11. The computer readable medium of claim 10, wherein the computer program further comprises a set of instructions for defining a tessellated graph of the region, wherein the tessellated graph has a plurality of edges, wherein the routes are defined with respect to the edges.

12. The computer readable medium of claim 11, wherein the routes are topological routes.

13. The computer readable medium of claim 12, wherein a topological particle is specified for each route at an intersection of the route and each edge that the route intersects, wherein the set of instructions for identifying previously defined routes that might need to be modified comprises a set of instructions for identifying the routes that have topological particles on edges that the first route intersects.

14. The computer readable medium of claim 13, wherein the topological particles have an assigned coordinate in the layout, wherein the set of instructions for updating a previously defined route comprises a set of instructions for modifying the coordinate of at least one particular topological particle for the route to account for a required spacing between the previously defined route and the first route along the edge on which the particular topological particle exists.

15. The computer readable medium of claim 14, wherein the first route is a portion of a larger route for the first net.

16. A method of identifying routes for nets in a region of a design layout, the method comprising:

a) identifying a first route for a first net without using a routing grid, and

b) shoving at least one previously defined route for another net within the region of the design layout by modifying said at least one previously defined route for the other net to account for spacing constraints relating to the first route, without ripping out and re-routing any portion of the previously defined route.

17. A method of defining routes for nets in a region of a design layout, the method comprising:

a) identifying a first route for a first net;

b) based on the first route, identifying a second route for the first net;

c) identifying a third route for a second net; and

d) shoving the second route within the region of the design layout by modifying the second route to account for spacing constraints related to the third route, without removing any segment of the second route.

18. The method of claim 17, wherein the modifying does not re-route the second route.