Method and apparatus for pre-computing routes

• US 6,877,149 B2
• Filed: 01/13/2002
• Issued: 04/05/2005
• Est. Priority Date: 08/23/2001
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Chao, Heng-Yi
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US10/047,976
• Publication Number:
  US 20030115566A1
• Time in Patent Office: 1,178 Days
• Field of Search: 716/7, 716 11- 14
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

Some embodiments provide a method of pre-computing routes for nets in a region of a circuit layout. The method initially defines a set of partitioning lines for partitioning the region into a plurality of sub-regions during a routing operation. The method then identifies a primary set of sub-regions that has more than one sub-region. It then determines whether the primary set of sub-regions is an open set that has a sub-region that is not adjacent to any other sub-region in the set. If the primary set of sub-regions is not an open set, the method identifies a route that connects the sub-regions in the primary set, and stores the identified route for the primary set of sub-regions. On the other hand, if the primary set of sub-regions is an open set, the method identifies a connection set of sub-regions that when combined with the primary set forms a closed set of sub-regions that (i) does not have any sub-region that is not adjacent to another sub-region in the closed set, and (ii) can be traversed by a minimum tree route that connects each sub-region in the connection set to at least two other sub-regions in the primary and connection sets of sub-regions. For the primary set of sub-regions, the method then stores at least either the connection set of sub-regions or the closed set of sub-regions.

Claims

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

a) defining a set of partitioning lines for partitioning the region into a plurality of sub-regions during a routing operation;

b) identifying a primary set of sub-regions that has more than one sub-region;

c) determining whether the primary set of sub-regions is an open set that has a sub-region that is not adjacent to any other sub-region in the set; and

d) if the primary set of sub-regions is not an open set,

identifying a route that connects the sub-regions in the primary set; and

storing the identified route for the primary set of sub-regions.

2. The method of claim 1 further comprising:

identifying multiple routes that traverse the sub-regions in the primary set when the primary set of sub-regions is not an open set.

3. The method of claim 2, wherein the routes are minimum trees, where each tree traverses the sub-regions in the primary set.

4. The method of claim 1 further comprising:

if the primary set of sub-regions is an open set,

identifying a connection set of sub-regions that when combined with the primary set forms a closed set of sub-regions that (i) does not have any sub-region that is not adjacent to at least one other sub-region in the closed set, and (ii) can be traversed by a minimum tree route that connects each sub-region in the connection set to at least two other sub-regions in the primary and connection sets of sub-regions; and

storing at least either the connection set of sub-regions or the closed set of sub-regions for the primary set of sub-regions.

5. The method of claim 4 further comprising:

when the primary set of sub-regions is an open set, identifying and storing multiple connection set of sub-regions for the primary set of sub-regions, wherein each connection set when combined with the primary set forms a closed set of sub-regions that (i) does not have any sub-region that is not adjacent to at least one other sub-region in the closed set, and (ii) can be traversed by a minimum tree route that connects each sub-region in the connection set to at least two other sub-regions in the primary and connection sets of sub-regions.

6. The method of claim 1 further comprising:

a) identifying several primary sets of sub-regions, wherein each primary set of sub-regions has more than one sub-region; and

b) for each primary set,

determining whether the primary set is an open set that has a sub-region that is not adjacent to any other sub-region in the set; and

if the primary set of sub-regions is not an open set, (i) identifying a route that connects the sub-regions in the primary set, and (ii) storing the identified route for the primary set of sub-regions.

7. The method of claim 6 further comprising:

for each of a plurality of the primary sets, identifying multiple routes that traverse the sub-regions in the primary set when the primary set of sub-regions is not an open set.

8. The method of claim 7, wherein the routes are minimum trees.

9. The method of claim 6 further comprising:

if a primary set of sub-regions is an open set,

identifying a connection set of sub-regions that when combined with the primary set forms a closed set of sub-regions that (i) does not have any sub-region that is not adjacent to at least one other sub-region in the closed set, and (ii) can be traversed by a minimum tree route that connects each sub-region in the connection set to at least two other sub-regions in the primary and connection sets of sub-regions; and

storing at least either the connection set of sub-regions or the closed set of sub-regions for the primary set of sub-regions.

10. The method of claim 9 further comprising:

when a first primary set of sub-regions is an open set, identifying and storing multiple connection set of sub-regions for the first primary set of sub-regions, wherein each connection set when combined with the first primary set forms a closed set of sub-regions that (i) does not have any sub-region that is not adjacent to at least one other sub-region in the closed set, and (ii) can be traversed by a minimum tree route that connects each sub-region in the connection set to at least two other sub-regions in the primary and connection sets of sub-regions.

11. The method of claim 6, wherein a plurality of paths exist between the sub-regions defined by the set of partitioning lines, wherein the routes are defined with respect to the paths.

12. The method of claim 11, wherein a plurality of the paths are diagonal paths, wherein some of the routes traverse some of the diagonal paths.

13. The method of claim 6, wherein a plurality of edges exist between the sub-regions defined by the set of partitioning lines, wherein the routes are defined with respect to the paths.

14. The method of claim 13, wherein a plurality of the edges between the sub-regions are diagonal edges, wherein some of the routes intersect some of the diagonal edges.

15. A method of pre-computing routes for nets in a layout region that is partitioned into a plurality of sub-regions, the method comprising:

a) identifying a primary set of sub-regions that has more than one sub-region;

b) when the primary set of sub-regions is not an open set that has a sub-region that is not adjacent to any other sub-region in the set, identifying and storing a route that connects the sub-regions in the primary set; and

c) when the primary set of sub-regions is an open set that has a sub-region that is not adjacent to any other sub-region in the set, storing a set of indicia that enables the generation of a route for the primary set during a routing operation.

16. The method of claim 15 further comprising identifying multiple routes that traverse the sub-regions in the primary set when the primary set of sub-regions is not an open set.

17. The method of claim 16, wherein the routes are minimum trees, where each tree traverses the sub-regions in the primary set.

18. The method of claim 15, wherein the set of indicia includes a connection set of sub-regions that when the primary set forms a closed set of sub-regions that does not have any sub-regions that is not adjacent to at least one other sub-region in the closed set.

19. The method of claim 18, wherein during the routing operation, a route for the primary set of sub-regions is identified by combining the primary set of sub-regions with the connection set of sub-regions to obtain the closed set of sub-regions and retrieving a route stored for the closed set of sub-regions.

20. The method of claim 15, wherein the set of indicia is a set of sub-regions that is formed by combing the primary set of sub-regions with a connection set of sub-regions, wherein the closed set of sub-regions does not have any sub-region that is not adjacent to at least one other sub-region in the closed set.

21. The method of claim 20, wherein during the routing operation, a route for the primary set of sub-regions is identified by retrieving a route stored for the closed set of sub-regions.

22. A computer readable medium that stores a computer program for pre-computing routes for nets in a layout region that is partitioned into a plurality of sub-regions, the computer program comprising sets of instructions for:

a) identifying a primary set of sub-regions that has more than one sub-region;

b) when the primary set of sub-regions is not an open set that has a sub-region that is not adjacent to any other sub-region in the set, identifying and storing a route that connects the sub-regions in the primary set; and

c) when the primary set of sub-regions is an open set that has sub-region that is not adjacent to any other sub-region in the set, storing a set of indicia that enables the generation of a route for the primary set during a routing operation.