Routing method and apparatus

• US 20030066043A1
• Filed: 01/13/2002
• Published: 04/03/2003
• Est. Priority Date: 08/23/2001
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Caldwell, Andrew, Frankle, Jonathan, Jacques, Etienne, Buset, Oscar
• Granted Patent: US 7,155,697 B2
• Time in Patent Office: Days
• US Class Current: 716/13
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

Some embodiments of the invention provide a method for defining routes for nets in a region of a circuit layout. This method uses a first set of lines to measure length of routes, and uses a second set of lines to measure congestion of routes.

Claims

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

a) using a first set of lines to measure length of routes;

b) using a second set of lines to measure congestion of routes.

2. The method of claim 1, wherein at least some of the lines in the first set are not in the second set

3. The method of claim 1, wherein the second set lines define a plurality of congestion edges, wherein using the second set of lines comprises measuring the congestion of routes across the congestion edges.

4. The method of claim 3, wherein the routes have diagonal edges that intersect the congestion edges, wherein measuring the congestion of routes across the congestion edges comprises measuring the congestion of diagonal route edges across the congestion edges.

5. The method of claim 4, wherein the routes further have horizontal or vertical edges that intersect the congestion edges, wherein measuring the congestion of routes across the congestion edges further comprises measuring the congestion of the horizontal or vertical route edges across the congestion edges.

6. The method of claim 1, wherein each net has a set of pins, the method further comprising:

a) using a third set of lines to partition the region into a first set of sub-regions;

b) for each net, identifying a route that traverse a group of first-set sub-regions that contain the net'"'"'s set of pins.

7. The method of claim 6, wherein the second and third sets of lines are identical.

8. The method of claim 1, wherein each net has a set of pins, wherein the first set of lines defines a first set of sub-regions, the method further comprising:

for each net, identifying a route that traverse a group of first-set sub- regions that contain the net'"'"'s set of pins;

wherein each route has a set of route segments, and each route segment traverses two sub-regions in the first set of sub-regions.

9. The method of claim 8 further comprising measuring the length of each route by summing the length of each route segment in the route'"'"'s set of route segments.

10. The method of claim 9, wherein using the second set of lines comprises measuring the congestion of routes across the second set of lines.

11. The method of claim 10, wherein the second set of lines define a plurality of congestion edges, wherein measuring the congestion of the routes comprises measuring the congestion of routes across the congestion edges.

12. The method of claim 11 further comprising:

once a route is completed, specifying each route only with respect to the route'"'"'s segments that cross the congestion edges.

13. The method of claim 8, wherein identifying the route for each net comprises:

starting at a first-set sub-region that contains a pin of the net, successively specifying a route segment that expands the route into a new first-set sub-region until the route traverses all the group of sub-regions that contain the net'"'"'s pins.

14. The method of claim 13 further comprising:

at each expansion of a route segment, computing a length cost;

for each expansion of a route segment across a second-set line, computing a congestion cost based on the congestion of the second-set line.

15. The method of claim 13,

wherein specifying a first route segment comprises examining a plurality of potential route-segment expansions,

wherein for each potential route-segment expansion, computing a length cost;

wherein if the potential route-segment expansion intersects a second-set line, computing a congestion of the second-set line.