Genealogy driven IC layout generator and classification method

1. A method performed by a computer system, comprising:

generating an initial set of integrated circuit (IC) design layout clips as a current set of IC design layout clips, wherein an IC design layout clip comprises a building block of a specified size for an IC design;

removing any of the IC design layout clips from the current set of IC design layout clips that do not meet the one or more usefulness criteria, wherein the usefulness criteria include uniqueness such that a given IC design layout clip from the current set of CI deign layout clips cannot be obtained from another IC design layout clip from the current set of IC design layout clips by any combination of rotation or reflection operations, wherein each IC design layout clip includes one or more polygons, and wherein, to determine the any of the IC design layout clips from the current set of IC design layout clips that do not meet the one or more usefulness criteria, the computer system:

determines a Manhattan shape signature (MSS) for each Manhattan polygon in each IC design layout clip in the current set of IC design layout clips;

applies classification criteria to each IC design layout clip in the set of IC design layout clips to produce a fingerprint corresponding to each IC design layout clip in the set of IC design layout clips; and

only compares each pair of clips having a same corresponding fingerprint to identify non-unique IC design layout clips; and

when a size of the IC design layout clips is less than a desired clip size, generating a new set of IC design layout clips from the current set of IC design layout clips according to every combination of pairs of the design layout clips in the current set of IC design layout clips, including all possible rotations or reflections before combination, relabeling the new set of IC design layout clips as the current set of IC design layout clips, and repeating the removing process; and

when the size of the IC design layout clips is not less than the desired clip size, storing the current set of IC design layout clips as a final set of all possible IC design layout clips, or any part of all possible IC design layout clips, satisfying the one or more usefulness criteria and of the desired clip size, and storing clip ancestor data for each of the IC design layout clips in the final set of IC design layout clips.

2. The method of claim 1 , wherein the usefulness criteria further include one or more of satisfaction of design rule checker requirements and engineering or manufacturing practicality.

3. The method of claim 1 , wherein the classification criteria include one or more of a total number of polygons in an IC design layout clip, a number of edges of each polygon, the MSS of each Manhattan polygon, a polygon area of each polygon, a polygon perimeter of each polygon, a ratio of longest edge to shortest edge of each polygon, a minimum distance between each polygon and its clip border, a distance between a center of gravity of each polygon and its IC design layout clip, or a distance between a center of gravity of pairs of polygons in a IC design layout clip.

4. The method of claim 1 , further comprising thereafter manufacturing an IC according to the final set of IC design layout clips.

5. The method of claim 1 , further comprising receiving the desired clip size or receiving the one or more usefulness criteria.

6. A computer system comprising:

a processor; and

an accessible memory, the computer system configured to:

generate an initial set of integrated circuit (IC) design layout clips as a current set of IC design layout clip, wherein an IC design layout clip comprises a building block of a specified size for an IC design;

remove any of the IC design layout clips from the current set of IC design layout clips that do not meet the one or more usefulness criteria, wherein the usefulness criteria include uniqueness such that a given IC design layout clip from the current set of CI deign layout clips cannot be obtained from another IC design layout clip from the current set of IC design layout clips by any combination of rotation or reflection operations, wherein each IC design layout clip includes one or more polygons, and wherein, to determine the any of the IC design layout clips from the current set of IC design layout clips that do not meet the one or more usefulness criteria, the computer system:

determines a Manhattan shape signature (MSS) for each Manhattan polygon in each IC design layout clip in the current set of IC design layout clips;

applies classification criteria to each IC design layout clip in the set of IC design layout clips to produce a fingerprint corresponding to each IC design layout clip in the set of IC design layout clips; and

only compares each pair of clips having a same corresponding fingerprint to identify non-unique IC design layout clips; and

when a size of the IC design layout clips is less than a desired clip size, generate a new set of IC design layout clips from the current set of IC design layout clips according to every combination of pairs of the design layout clips in the current set of IC design layout clips, and repeat the removing process; and

when the size of the IC design layout clips is not less than the desired clip size, store the current set of IC design layout clips as a final set of IC design layout clips.

7. The computer system of claim 6 , wherein the usefulness criteria further include one or more of satisfaction of design rule checker requirements and engineering or manufacturing practicality.

8. The computer system of claim 6 , wherein the classification criteria includes one or more of a total number of polygons in an IC design layout clip, a number of edges of each polygon, the MSS of each polygon, a polygon area of each polygon, a polygon perimeter of each polygon, a ratio of longest edge to shortest edge of each polygon, a minimum distance between each polygon and its clip border, a distance between a center of gravity of each polygon and its IC design layout clip, or a distance between a center of gravity of pairs of polygons in a IC design layout clip.

9. The computer system of claim 6 , wherein the computer system is further configured to thereafter manufacture an IC according to the final set of IC design layout clips.

10. The computer system of claim 6 , wherein the computer system is further configured to receive the desired clip size or receive the one or more usefulness criteria.

11. A non-transitory computer-readable medium storing executable instructions that, when executed, cause one or more computer systems to:

generate an initial set of integrated circuit (IC) design layout clips as a current set of IC design layout clips, wherein an IC design layout clip comprises a building block of a specified size for an IC design;

remove any of the IC design layout clips from the current set of IC design layout clips that do not meet the one or more usefulness criteria, wherein the usefulness criteria include uniqueness such that a given IC design layout clip from the current set of CI deign layout clips cannot be obtained from another IC design layout clip from the current set of IC design layout clips by any combination of rotation or reflection operations, wherein each IC design layout clip includes one or more polygons, and wherein, to determine the any of the IC design layout clips from the current set of IC design layout clips that do not meet the one or more usefulness criteria, the non-transitory computer-readable medium further stores executable instructions that, when executed, cause the one or more computer systems to:

determine a Manhattan shape signature (MSS) for each Manhattan polygon in each IC design layout clip in the current set of IC design layout clips;

apply classification criteria to each IC design layout clip in the set of IC design layout clips to produce a fingerprint corresponding to each IC design layout clip in the set of IC design layout clips; and

compare clips having a same corresponding fingerprint to identify non-unique IC design layout clips; and

when a size of the IC design layout clips is less than a desired clip size, generate a new set of IC design layout clips from the current set of IC design layout clips according to every combination of pairs of the design layout clips in the current set of IC design layout clips, and repeat the removing process; and

when the size of the IC design layout clips is not less than the desired clip size, store the current set of IC design layout clips as a final set of IC design layout clips.

12. The non-transitory computer-readable medium of claim 11 , wherein the usefulness criteria further include one or more of satisfaction of design rule checker requirements and engineering or manufacturing practicality.

13. The non-transitory computer-readable medium of claim 11 , wherein the classification criteria includes one or more of a total number of polygons in an IC design layout clip, a number of edges of each polygon, the MSS of each polygon, a polygon area of each polygon, a polygon perimeter of each polygon, a ratio of longest edge to shortest edge of each polygon, a minimum distance between each polygon and its clip border, a distance between a center of gravity of each polygon and its IC design layout clip, or a distance between a center of gravity of pairs of polygons in a IC design layout clip.

14. The non-transitory computer-readable medium of claim 11 , further storing executable instructions that, when executed, cause the one or more computer systems to thereafter manufacture an IC according to the final set of IC design layout clips.