Method and apparatus for pre-computing attributes of routes

• US 6,907,593 B2
• Filed: 01/13/2002
• Issued: 06/14/2005
• Est. Priority Date: 12/06/2000
• Status: Expired due to Term

• 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): Thompson, A. M.
• Assistant Examiner(s): LIN, SUN J
• Application Number:
  US10/046,864
• Publication Number:
  US 20020199165A1
• Time in Patent Office: 1,248 Days
• Field of Search: 716/13, 716/12, 716/14
• US Class Current: 716/129
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: G06F 30/3953 detailed
• CPC Class Codes: G11B 7/08582 Sled-type positioners

Abstract

Some embodiments provide a method of pre-computing attributes of routes for nets in a region of a design layout. The pre-computed attributes are used by an electronic design automation application that partitions a design-layout region into a plurality of sub-region.

Claims

1. For an electronic design automation application that partitions a region of a design layout into a plurality of sub-regions, wherein a plurality of edges exist between said sub-regions, a method of pre-computing attributes of routes for nets in the region, the method comprising:

a) for a first set of sub-regions, wherein each sub-region of the first set includes only one contact point, identifying a first set of potential routes, wherein each route in the first set of potential routes traverses the first set of sub-regions through the contact point of each sub-region of the first set;

wherein the contact points are located at the same location in each sub-region and each of a plurality of sets of potential routes has at least two routes;

b) for each particular edge, identifying an edge-intersect cost that is dependent on the number of routes in the first set of potential routes that intersect the particular edge; and

c) storing the identified edge-intersect costs for the first set of sub-regions.

2. The method of claim 1, wherein the edge-intersect cost of a particular edge equals the number of potential routes that intersect the particular edge.

3. The method of claim 1 further comprising:

a) for a second set of sub-regions, identifying a second set of potential routes, wherein each route in the second set of potential routes traverses the second set of sub-regions;

b) for each particular edge, identifying an edge-intersect cost that is dependent on the number of routes in the second set of potential routes that intersect the particular edge; and

c) storing the identified edge-intersect costs for the second set of sub-regions.

4. For an electronic design automation application that partitions a region of a design layout into a plurality of sub-regions, wherein a plurality of edges exist between said sub-regions, a method of pre-computing attributes of routes for nets in the region, the method comprising:

a) for a first set of sub-regions, wherein each sub-region of the first set includes a contact point, identifying a first set of potential routes, wherein each route in the first set of potential routes traverses the first set of sub-regions through the contact point of each sub-region of the first set;

b) for each particular edge, identifying an edge-intersect cost that is dependent on the number of routes in the first set of potential routes that intersect the particular edge; and

c) storing the identified edge-intersect costs for the first set of sub-regions;

wherein identifying the edge-intersect cost for each particular edge comprises identifying an edge-intersect probability for each particular edge, wherein the edge-intersect probability for each particular edge equals the number of potential routes of the first set of potential routes that intersect the particular edge divided by the number of potential routes in the first set of potential routes.

5. The method of claim 4, wherein the cost for each particular edge equals the edge-intersect probability for the particular edge.

6. The method of claim 4, wherein identifying the cost for each particular edge further comprises deriving the cost for each particular edge from the edge-intersect probability of the particular edge.

7. For an electronic design automation application that partitions a region of a design layout into a plurality of sub-regions, wherein a plurality of paths exist between said sub-regions, a method of pre-computing attributes of routes for nets in the region, the method comprising:

a) for a first set of sub-regions, wherein each sub-region of the first set includes only one contact point, identifying a first set of potential routes that traverse the first set of sub-regions through the contact point of each sub-region of the first set;

wherein the contact points are located at the same location in each sub-region and each of a plurality of sets of potential routes has at least two routes;

b) for each particular path, identifying a path-use cost that is dependent on the number of routes in the first set of potential routes that use the particular path; and

c) storing the identified path-use costs for the first set of sub-regions.

8. The method of claim 7, wherein the path-use cost of a particular path equals the number of potential routes that use the particular path.

9. The method of claim 7 further comprising:

a) for a second set of sub-regions, identifying a second set of potential routes that traverse the second set of sub-regions;

b) for each particular path, identifying a path-use cost that is dependent on the number of routes in the second set of potential routes that use the particular path; and

c) storing the identified path-use costs for the second set of sub-regions.

10. For an electronic design automation application that partitions a region of a design layout into a plurality of sub-regions, wherein a plurality of paths exist between said sub-regions, a method of pre-computing attributes of routes for nets in the region, the method comprising:

a) for a first set of sub-regions, wherein each sub-region of the first set includes a contact point, identifying a first set of potential routes that traverse the first set of sub-regions through the contact point of each sub-region of the first set;

b) for each particular path, identifying a path-use cost that is dependent on the number of routes in the first set of potential routes that use the particular path; and

c) storing the identified path-use costs for the first set of sub-regions;

wherein identifying the path-use cost for each particular path comprises identifying an path-use probability for each particular path, wherein the path-use probability for each particular path equals the number of potential routes of the first set of potential routes that use the particular path divided by the number of potential routes in the first set of potential routes.

11. The method of claim 10, wherein the cost for each particular path equals the path-use probability for the particular path.

12. The method of claim 10, wherein identifying the cost for each particular path further comprises deriving the cost for each particular path from the path-use probability of the particular path.