Method and apparatus for computing capacity of a region for non-manhattan routing

• US 20040103387A1
• Filed: 12/31/2002
• Published: 05/27/2004
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Deretsky, Zachary
• Granted Patent: US 7,080,342 B2
• Time in Patent Office: Days
• US Class Current: 716/13
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

For a router that allows routing in at least one non-Manhattan direction, some embodiments of the invention provide a method of computing a capacity for non-Manhattan routing in a region. The method identifies a polygon about the region, where the polygon has at least one side that is not aligned with either Manhattan direction. It then identifies a set of potential obstacles within the polygon. The method then calculates the capacity of the region for non-Manhattan routing, based on the identified set of potential obstacles.

Claims

1. For a router that allows routing in at least one non-Manhattan direction, a method of computing a capacity for non-Manhattan routing in a region, the method comprising:

a) identifying a polygon about the region, wherein the polygon has at least one side that is not aligned with either Manhattan direction;

b) identifying a set of potential obstacles within the polygon;

c) calculating the capacity of the region for non-Manhattan routing, based on the identified set of potential obstacles.

2. The method of claim 1, wherein the polygon has a plurality of sides that are not aligned with either Manhattan direction.

3. The method of claim 1, wherein the at least one side is parallel to the non-Manhattan routing direction used by the router.

4. The method of claim 3, wherein the polygon has at least a first pair of sides that are parallel to the non-Manhattan routing direction used by the router.

5. The method of claim 4, wherein the polygon is a parallelogram.

6. The method of claim 5, wherein the parallelogram has a second pair of sides that are parallel to a boundary representing the region.

7. The method of claim 6, wherein the boundary is between two Gcells, wherein identifying the polygon comprises:

a) identifying the second pair of sides as translations of the boundary to particular locations of the Gcells;

b) identifying the first pair as sides in the non-Manhattan routing direction that each connects to the each side in the second pair.

8. The method of claim 1, wherein calculating the capacity of the region comprises identifying the portion of the region that each identified obstacle will intersect if it is moved across the region in the non-Manhattan routing direction.

9. The method of claim 8, wherein calculating the capacity further comprises:

a) specifying the intersected portions as blocked portions of the region;

b) identifying an unblocked portion of the region from the blocked portion;

c) specifying the capacity based on the unblocked portion.

10. The method of claim 9, wherein the region is on a particular layer of a design layout, said layer having a particular pitch, wherein specifying the capacity comprises:

a) computing a sum of each unblocked portion that is at least one pitch long;

b) specifying the capacity as the division of the sum by the pitch.

15. The computer readable medium of claim 4, wherein the polygon is a parallelogram.

16. The computer readable medium of claim 5, wherein the parallelogram has a second pair of sides that are parallel to a boundary representing the region.

17. The computer readable medium of claim 6, wherein the boundary is between two Gcells, wherein the set of instructions for identifying the polygon comprises a set of instructions for:

a) identifying the second pair of sides as translations of the boundary to particular locations of the Gcells;

b) identifying the first pair as sides in the non-Manhattan routing direction that each connects to the each side in the second pair.

11. A computer readable medium that stores a computer program that computing a capacity for non-Manhattan routing in a region for a router that allows routing in at least one non-Manhattan direction, the computer program comprising sets of instructions for:

a) identifying a polygon about the region, wherein the polygon has at least one side that is not aligned with either Manhattan direction;

b) identifying a set of potential obstacles within the polygon;

c) calculating the capacity of the region for non-Manhattan routing, based on the identified set of potential obstacles.

12. The computer readable medium of claim 11, wherein the polygon has a plurality of sides that are not aligned with either Manhattan direction.

13. The computer readable medium of claim 11, wherein the at least one side is parallel to the non-Manhattan routing direction used by the router.

14. The computer readable medium of claim 13, wherein the polygon has at least a first pair of sides that are parallel to the non-Manhattan routing direction used by the router.

18. The computer readable medium of claim 11, wherein the set of instructions for calculating the capacity of the region comprises a set of instructions for identifying the portion of the region that each identified obstacle will intersect if it is moved across the region in the non-Manhattan routing direction.

19. The computer readable medium of claim 18, wherein the set of instructions for calculating the capacity further comprises sets of instructions for:

a) specifying the intersected portions as blocked portions of the region;

b) identifying an unblocked portion of the region from the blocked portion;

c) specifying the capacity based on the unblocked portion.

20. The computer readable medium of claim 19, wherein the region is on a particular layer of a design layout, said layer having a particular pitch, wherein the set of instructions for specifying the capacity comprises sets of instructions for:

a) computing a sum of each unblocked portion that is at least one pitch long;

b) specifying the capacity as the division of the sum by the pitch.