Removal of relatively unimportant shapes from a set of shapes

• US 7,289,658 B2
• Filed: 06/24/2003
• Issued: 10/30/2007
• Est. Priority Date: 06/24/2003
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dunham, Timothy G., Shanmugam, Valarmathi C., Allen, Joseph B.
• Primary Examiner(s): Mancuso; Joseph
• Assistant Examiner(s): LIEW, ALEX KOK SOON
• Application Number:
  US10/604,063
• Publication Number:
  US 20040268290A1
• Time in Patent Office: 1,589 Days
• Field of Search: None
• US Class Current: 382/144
• 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:

providing a base geometry in a two-dimensional rectangular coordinate system, said base geometry having at least one initial geometric shape;

adding at least one anchor to the at least one initial geometric shape to form a first shape pattern, wherein the formed first shape pattern includes the at least one initial geometric shape and the at least one anchor so added, wherein a first anchor of the at least one anchor of the first shape pattern comprises a first extension, a first flare, and a second flare, wherein the first extension extends a first portion of the at least one initial geometric shape in a first direction, wherein the first flare and the second flare are disposed on opposite sides of the first portion, wherein the first flare extends the first portion in a second direction that is perpendicular to the first direction, wherein the second flare extends the first portion in a third direction that is opposite the second direction and perpendicular to the first direction, wherein a second anchor of the at least one anchor of the first shape pattern consists of a second extension and a third flare, wherein the second extension extends a second portion of the at least one initial geometric shape in the first direction, and wherein the third flare extends the second portion in the third direction, wherein a third anchor of the at least one anchor of the first shape pattern consists of a fourth flare disposed on a third portion of the at least one initial geometric shape;

forming a second shape pattern, wherein the second shape pattern consists of all of the first shape pattern and error shapes, wherein said forming the second shape pattern comprises forming a first error shape by moving the second portion in the second direction, wherein said forming the second shape pattern further comprises simultaneously forming a second error shape and a third error shape of the error shapes by shifting the third portion together with the fourth flare in a fourth direction that is opposite the first direction, wherein the second error shape and the third error shape have a same thickness in the fourth direction, wherein the second error shape is an additive error shape that physically exists in the second shape pattern, and wherein the third error shape is a subtractive error shape that logically exists in the second shape pattern;

extracting the error shapes from the second shape pattern;

deriving from a subset of the extracted 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;

deleting a subset of the environment shapes such that only a plurality of unique environment shapes satisfying a selection criterion remain subject to the remaining unique environment shapes differing from each other with respect to a geometrical characteristic of their respective geometric shapes, wherein each error shape in the subset has a polygonal shape;

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;

wherein expanding the first error shape to form a corresponding first expanded shape comprises outwardly projecting each bounding side of the first error shape by a distance in a direction perpendicular to the bounding side;

wherein said forming the at least one environment shape comprises forming a first environment shape and a second environment shape corresponding to the first expanded shape by removing all portions of the first expanded shape which are common to the second shape pattern, wherein the formed first environmental shape is a polygon of 12 sides and is in direct mechanical contact with the second extension and the third flare, wherein the formed second environmental shape is a rectangle and is in direct mechanical contact with the third flare, and wherein the third flare is disposed between the first and second environmental shapes and separates the first and second environmental shapes from each other.