REMOVAL OF RELATIVELY UNIMPORTANT SHAPES FROM A SET OF SHAPES

• US 20040268290A1
• Filed: 06/24/2003
• Published: 12/30/2004
• Est. Priority Date: 06/24/2003
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Shanmugam, Valarmathi C., Allen, Joseph B., Dunham, Timothy G.
• Granted Patent: US 7,289,658 B2
• Time in Patent Office: Days
• US Class Current: 716/52
• CPC Class Codes: G03F 1/68 Preparation processes not covered by groups G03F1/20 - G03F1/50
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

A method for reducing a number of shapes, and a computer readable program code adapted to perform said method. The method forms first and second shape patterns. The second shape pattern includes the first shape pattern and error shapes. The error shapes are extracted from the second shape pattern. At least one environment shape corresponding to each error shape is derived from a subset of the error shapes. For example, each error shape in the subset may be expanded to form a corresponding expanded shape, and at least one environment shape corresponding to each expanded shape may be formed by removing all portions of the expanded shape common to the second shape pattern. The environment shape reflects a local geometric environment of its corresponding error shape. A subset of the environment shapes are deleted such that only unique environment shapes satisfying a selection criterion remain.

Claims

1. A method for reducing a number of shapes, said method comprising the steps of:

forming a first shape pattern;

forming a second shape pattern, said second shape pattern including the first shape pattern and error shapes;

extracting the error shapes from the second shape pattern;

deriving from a subset of the error shapes at least one environment shape corresponding to each error shape in the subset of the error shapes, said environment shape reflecting a local geometric environment of its corresponding error shape; and

deleting a subset of the environment shapes such that only unique environment shapes satisfying a selection criterion remain.

2. The method of claim 1, said method further comprising distributing the error shapes into at least one group such that the at least one group is defined by a grouping criterion, wherein the subset of the error shapes is a first group of the at least one group.

3. The method of claim 2, wherein the at least one group consists of a plurality of groups.

4. The method of claim 3, wherein the grouping criterion relates to a combination of an area of the error shape and a smallest linear dimension of the error shape.

5. The method of claim 1, wherein the deriving step comprises:

expanding each error shape in the subset to form a corresponding expanded shape; and

forming the at least one environment shape corresponding to each expanded shape by removing all portions of the expanded shape which are common to the second shape pattern.

6. The method of claim 5, wherein each error shape in the subset has a polygonal shape, and wherein expanding the first error shape comprises outwardly projecting each bounding side of the error shape by a distance in a direction perpendicular to the bounding side.

7. The method of claim 6, wherein the distance is a same distance for each bounding side of a first error shape of the error shapes in the subset.

8. The method of claim 7, wherein the same distance is identical for each error shape in the subset.

9. The method of claim 6, wherein the distance is a same first distance for each bounding side oriented in a first direction for a first error shape of the error shapes in the subset, wherein the distance is a same second distance for each bounding side oriented in a second direction for the first error shape, wherein the second direction is orthogonal to the first direction, and wherein the same first distance is unequal to the same second distance.

10. The method of claim 9, wherein the same first distance is identical for each error shape in the subset, and wherein the same second distance is identical for each error shape in the subset.

11. The method of claim 1, wherein the selection criterion relates to N independent characteristics of each environment shape such that N is at least 1, and wherein the deleting step includes sorting the environment shapes in accordance with N sort keys such that the N sort keys are the N independent characteristics.

12. The method of claim 11, wherein each environment shape is polygonal, wherein N is at least 2, and wherein the N independent characteristics comprise at least two of:

the vertex count of the environment shape, the area of the environment shape, and a perimeter of the environmental shape.

13. The method of claim 1, wherein the extracting step comprises performing:

(first shape pattern) XOR (second shape pattern).

14. The method of claim 1, wherein the error shapes comprises a plurality of additive shapes and a plurality of subtractive shapes.

15. The method of claim 1, wherein prior to the step of forming a first shape pattern the method further comprises providing a base geometry having at least one initial geometric shape, and wherein the step of forming a first shape pattern comprises adding at least one anchor to the at least one initial geometric shape such that the first shape pattern so formed includes the at least one initial shape and the at least one anchor so added.

16. A computer program product, comprising a computer usable medium having a computer readable program code embodied therein, said computer readable program code adapted to perform a method for reducing a number of shapes, said method comprising the steps of:

forming a first shape pattern;

forming a second shape pattern, said second shape pattern including the first shape pattern and error shapes;

extracting the error shapes from the second shape pattern;

deriving from a subset of the error shapes at least one environment shape corresponding to each error shape in the subset of the error shapes, said environment shape reflecting a local geometric environment of its corresponding error shape; and

deleting a subset of the environment shapes such that only unique environment shapes satisfying a selection criterion remain.

17. The computer program product of claim 16, said method further comprising distributing the error shapes into at least one group such that the at least one group is defined by a grouping criterion, wherein the subset of the error shapes is a first group of the at least one group.

18. The computer program product of claim 17, wherein the at least one group consists of a plurality of groups.

19. The computer program product of claim 18, wherein the grouping criterion relates to a combination of an area of the error shape and a smallest linear dimension of the error shape.

20. The computer program product of claim 16, wherein the deriving step comprises:

expanding each error shape in the subset to form a corresponding expanded shape; and

forming the at least one environment shape corresponding to each expanded shape by removing all portions of the expanded shape which are common to the second shape pattern.

21. The computer program product of claim 20, wherein each error shape in the subset has a polygonal shape, and wherein expanding the first error shape comprises outwardly projecting each bounding side of the error shape by a distance in a direction perpendicular to the bounding side.

22. The computer program product of claim 21, wherein the distance is a same distance for each bounding side of a first error shape of the error shapes in the subset.

23. The computer program product of claim 22, wherein the same distance is identical for each error shape in the subset.

24. The computer program product of claim 21, wherein the distance is a same first distance for each bounding side oriented in a first direction for a first error shape of the error shapes in the subset, wherein the distance is a same second distance for each bounding side oriented in a second direction for the first error shape, wherein the second direction is orthogonal to the first direction, and wherein the same first distance is unequal to the same second distance.

25. The computer program product of claim 24, wherein the same first distance is identical for each error shape in the subset, and wherein the same second distance is identical for each error shape in the subset.

26. The computer program product of claim 16, wherein the selection criterion relates to N independent characteristics of each environment shape such that N is at least 1, and wherein the deleting step includes sorting the environment shapes in accordance with N sort keys such that the N sort keys are the N independent characteristics.

27. The computer program product of claim 26, wherein each environment shape is polygonal, wherein N is at least 2, and wherein the N independent characteristics comprise at least two of:

the vertex count of the environment shape, the area of the environment shape, and a perimeter of the environmental shape.

28. The computer program product of claim 16, wherein the extracting step comprises performing:

(first shape pattern) XOR (second shape pattern).

29. The computer program product of claim 16, wherein the error shapes comprises a plurality of additive shapes and a plurality of subtractive shapes.

30. The computer program product of claim 16, wherein the prior to the step of forming a first shape pattern the method further comprises providing a base geometry having at least one initial geometric shape, and wherein the step of forming a first shape pattern comprises adding at least one anchor to the at least one initial geometric shape such that the first shape pattern so formed includes the at least one initial shape and the at least one anchor so added.