Method and apparatus for computing capacity of a region for non-Manhattan routing
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.
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.