Method and apparatus for generating routes for groups of related node configurations

• US 6,795,958 B2
• Filed: 01/04/2002
• Issued: 09/21/2004
• 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, Ganley, Joseph L.
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): LIN, SUN J
• Application Number:
  US10/039,618
• Publication Number:
  US 20030064559A1
• Time in Patent Office: 991 Days
• Field of Search: 716/14, 716/12, 716/13, 716/8
• 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 of the invention provide a method that identifies a set of routes for a net that has a set of pins in a region of a design layout. The method initially partitions the region into a number of sub-regions. It then identifies a first set of sub-regions that contains the net'"'"'s pins. Based on the first set of sub-regions, the method identifies a first route that traverses a second set of sub-regions. The first and second sets of sub-regions have a particular relationship. Based on this particular relationship, the method identifies a second route from the first route, where the second route traverses the first set of sub-regions.

Claims

1. A method of identifying a set of routes for a net having a set of pins in a region of a design layout, the method comprising:

a) partitioning the region into a plurality of sub-regions,

b) identifying a first set of sub-regions containing the net'"'"'s pins;

c) based on the first set of sub-regions, identifying a first route that traverses a second set of sub-regions, wherein the first and second set of sub-regions have a particular relationship; and

d) based on the particular relationship, identifying a second route from the first route, wherein the second route traverses the first set of sub-regions.

2. The method of claim 1 further comprising identifying the particular relationship between the first and second sets of sub-regions.

3. The method of claim 2, wherein identifying the particular relationship comprises retrieving an indicia that specifies the particular relationship from a storage structure.

4. The method of claim 2, wherein the first and second sets of sub-regions have a symmetrical relationship.

5. The method of claim 4, wherein identifying the second route comprises transforming the first route into the second route based on the symmetrical relationship.

6. The method of claim 5, wherein transforming the first route comprises rotating the first route about an origin by a particular angle.

7. The method of claim 5, wherein transforming the first route comprises flipping the first route about an axis.

8. The method of claim 5, wherein transforming the first route comprises rotating the first route about an origin by a particular angle and flipping the rotated first route about an axis.

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

a) partitioning the region into a plurality of sub-regions, and

b) for each particular net,

i) identifying a set of sub-regions containing the net'"'"'s pins;

ii) retrieving a first set of routes for the identified set of sub-regions from a storage structure, wherein each route in the retrieved set of routes traverses a base set of sub-regions that has a particular relationship to the identified set of sub-regions;

iii) identifying a second set of routes from the first set of routes based on the particular relationship between the base set of sub-regions and the identified set of sub-regions, wherein the second set of routes are routes for the particular net.

10. The method of claim 9 further comprising for each particular net identifying the particular relationship between the identified set of sub-regions for the net and the base set of sub-regions traversed by each retrieved route in the first set of routes.

11. The method of claim 9, wherein a first net'"'"'s identified set of sub-regions is identical to the base set of sub-regions traversed by the first set of routes for the first net, wherein identifying the second set of routes for the first net comprises specifying the first set of routes as the second set of routes.

12. The method of claim 9, wherein identifying a second set of routes for a first net comprises rotating each of the routes in the first set of routes retrieved for the first net.

13. The method of claim 9, wherein identifying a second set of routes for a first net comprises flipping each route in the first set of routes about an axis.

14. The method of claim 9, wherein identifying a second set of routes for a first net comprises rotating each route in the first set of routes about an origin by a particular angle and then flipping each rotated route about an axis.

15. A computer readable medium that includes a computer program for identifying a route for a net in a region of a design layout, the computer program comprising:

a) a first set of instructions for partitioning the region into a plurality of sub-regions,

b) a second set of instructions for identifying a first set of sub-regions containing the net'"'"'s pins;

c) a third set of instructions for identifying, based on the first set of sub-regions, a first route that traverses a second set of sub-regions, wherein the first and second set of sub-regions have a particular relationship; and

d) a third set of instructions for identifying, based on the particular relationship, a second route from the first route, wherein the second route traverses the first set of sub-regions.

16. The computer readable medium of claim 15 wherein the computer program further comprises a fourth set of instructions for identifying the particular relationship between the first and second sets of sub-regions.

17. The computer readable medium of claim 16, wherein the first and second sets of sub-regions have a symmetrical relationship.

18. The computer readable medium of claim 15, wherein the third set of instructions comprises a fourth set of instructions for transforming the first route into the second route based on the symmetrical relationship.

19. The computer readable medium of claim 18, wherein the fourth set of instructions comprises a fifth set of instructions for rotating the first route about an origin by a particular angle.

20. The computer readable medium of claim 18, wherein the fourth set of instructions comprises a fifth set of instructions for flipping the first route about an axis.

21. The computer readable medium of claim 18, wherein the fourth set of instructions comprises a fifth set of instructions for rotating the first route about an origin by a particular angle and flipping the rotated first route about an axis.