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

• US 7,080,342 B2
• Filed: 12/31/2002
• Issued: 07/18/2006
• Est. Priority Date: 11/18/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Deretsky, Zachary, Teig, Steven
• Primary Examiner(s): WHITMORE, STACY
• Application Number:
  US10/335,064
• Publication Number:
  US 20040103387A1
• Time in Patent Office: 1,295 Days
• Field of Search: 716 12- 14, 716/7
• US Class Current: 716/129
• 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, said router partitioning a region of a layout into a plurality of sub-regions, said router defining routes that traverse said sub-regions, a method of computing a capacity for non-Manhattan routing in the region, the method comprising:

a) identifying a polygon within the region, wherein the polygon has at least one side that is not aligned with a Manhattan direction, wherein the polygon is not one of the sub-regions;

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

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 a 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 is 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; and

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; and

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; and

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

11. A computer readable medium that stores a computer program that computes a capacity for non-Manhattan routing in a region of a layout for a router that allows routing in at least one non-Manhattan direction, said router partitioning the region of the layout into a plurality of sub-regions, said router defining routes that traverse said sub-regions, the computer program comprising sets of instructions for:

a) identifying a polygon within the region, wherein the polygon has at least one side that is not aligned with a Manhattan direction, wherein the polygon is not one of the sub-regions;

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

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 a 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.

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

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

17. The computer readable medium of claim 16, 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; and

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

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; and

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; and

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