US5629861A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Nested maximum space computation and efficient generation of nested shape complementation
Assignee: International Business Machines Corp
•
Filing: 1995-05-19
•
Granted: 1997-05-13
•
Expires: 2015-05-19
Abstract
Abstract A method of nested maximum space computation is used for the processing of shapes in design data for integrated circuits and printed circuit electronic packages. This method determines the complement of a design level without unnecessary flattening or denesting thereby reducing the processing time and the volume of the output data. Native shapes are first expanded by one-half the maximum space ground rule value to get the expanded native shapes. The nested shape complementation method is applied to the expanded native shapes to get the error candidate shapes. The error candidate shapes indicate areas that are possible violations. Next, the expanded native shapes are subtracted from the error candidate shapes to get the real error shapes. The nested shape complementation method finds the regions between shapes in a hierarchical design without denesting. For each cell that does not have transforms of other cells, the nested shape complementation method finds the cell's proper frame and uses that frame and the cell's native shapes to create complemented shapes. For each cell with transforms of other cells, the nested shape complementation method finds the cell's proper frame and uses that frame, the cell's native shapes, and its transformed cell's frames to create complemented shapes. The complemented shapes are added to the cell as native shapes on a new design level.
Inventors
- 👤 Young O. Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 08:54
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
124 words
A computer-implemented method of efficiently generating nested complemented shapes of a physical design for integrated circuit chip or electronic package designs without flattening or denesting hierarchal design data of the physical design comprising the steps of: inputting an original design as nested shapes information in a data file; generating a contents for each cell of the nested shapes information; generating a proper frame bounding the generated contents for each cell of the nested shapes information; determining complemented shapes for each cell as a difference between the generated proper frame and the generated contents for each cell of the nested shapes information; storing the complemented shapes as native shapes in each cell; and removing parts of the complemented shapes that overlap original design level shapes.
Claim 2
Dependent Claim
124 words
A computer-implemented method of efficiently generating nested complemented shapes of a physical design for integrated circuit chip or electronic package designs without flattening or denesting hierarchal design data of the physical design comprising the steps of: inputting an original design as nested shapes information in a data file; generating a contents for each cell of the nested shapes information; generating a proper frame bounding the generated contents for each cell of the nested shapes information; determining complemented shapes for each cell as a difference between the generated proper frame and the generated contents for each cell of the nested shapes information; storing the complemented shapes as native shapes in each cell; and removing parts of the complemented shapes that overlap original design level shapes.
Claim 3
Dependent Claim
25 words
The computer-implemented method of claim 1 further comprising the steps of: generating a frame for each step and repeated cell; and storing the generated frame.
Claim 4
Dependent Claim
58 words
The computer-implemented method of claim 2 wherein the step of generating a proper frame for each cell comprises the steps of: determining for each cell whether the cell is a step and repeated cell; and for a step and repeated cell, updating the stored generated frame by adding a bounding box of the generated contents of the cell.
Claim 5
Dependent Claim
97 words
The computer-implemented method of claim 1 wherein the step of generating the contents of a cell comprises the steps of: for each native shape in a cell, updating the contents of the cell by adding the native shape until all native shapes in the cell have been processed; given a transform to a cell, generating a coordinate transform having a geometric translation; accessing a stored frame for the cell and applying the coordinate transform to the frame to generate a transformed frame; and updating the contents by adding the transformed frame until all transforms have been processed.
Claim 6
Dependent Claim
44 words
The computer-implemented method of claim 4 further comprising the steps of: determining if a cell is a step and repeated cell; if a step and repeated cell, setting the transform to an origin coordinate transform; and calculating a width and height of the frame.
Claim 7
Dependent Claim
106 words
A computer-implemented method of efficiently determining violations of a maximum space restriction for a physical design of integrated circuit chip or electronic package designs without flattening or denesting hierarchial design data of the physical design comprising the steps of: inputting an original design nested shapes information in a data file; generating a contents for each cell of the nested shapes information; generating a proper frame for each cell of the nested shapes information; determining error candidate areas in each cell; storing the error candidate shapes as native shapes in each cell; and removing parts of the error candidate shapes that overlap the original design level shapes.
Claim 8
Dependent Claim
106 words
A computer-implemented method of efficiently determining violations of a maximum space restriction for a physical design of integrated circuit chip or electronic package designs without flattening or denesting hierarchial design data of the physical design comprising the steps of: inputting an original design nested shapes information in a data file; generating a contents for each cell of the nested shapes information; generating a proper frame for each cell of the nested shapes information; determining error candidate areas in each cell; storing the error candidate shapes as native shapes in each cell; and removing parts of the error candidate shapes that overlap the original design level shapes.
Claim 9
Dependent Claim
25 words
The computer-implemented method of claim 6 further comprising the steps of: generating a frame for each step and repeated cell; and storing the generated frame.
Claim 10
Dependent Claim
58 words
The computer-implemented method of claim 7 wherein the step of generating a proper frame for each cell comprises the steps of: determining for each cell whether the cell is a step and repeated cell; and for a step and repeated cell, updating the stored generated frame by adding a bounding box of the generated contents of the cell.
Claim 11
Dependent Claim
97 words
The computer-implemented method of claim 6 wherein the step of generating the conents of a cell comprises the steps of: for each native shape in a cell, updating the contents of the cell by adding the native shape until all native shapes in the cell have been processed; given a transform to a cell, generating a coordinate transform having a geometric translation; accessing a stored frame for the cell and applying the coordinate transform to the frame to generate a transformed frame; and updating the contents by adding the transformed frame until all transforms have been processed.
Claim 12
Dependent Claim
44 words
The computer-implemented method of claim 9 further comprising the steps of: determining if a cell is a step and repeated cell; if a step and repeated cell, setting the transform to an origin coordinate transform; and calculating a width and height of the frame.
Claim 13
Dependent Claim
102 words
A computer-implemented method of efficiently generating nested complemented shapes of a hierarchical design data file without flattening or denesting hierarchal design data comprising the steps of: inputting an original design as nested shapes information in a data file; generating a contents for each cell of the nested shapes information; generating a proper frame bounding the generated contents for each cell of the nested shapes information; determining complemented shapes for each cell as a difference between the generated proper frame and the generated contents for each cell of the nested shapes information; and storing the complemented shapes as native shapes in each cell.
Claim 14
Dependent Claim
102 words
A computer-implemented method of efficiently generating nested complemented shapes of a hierarchical design data file without flattening or denesting hierarchal design data comprising the steps of: inputting an original design as nested shapes information in a data file; generating a contents for each cell of the nested shapes information; generating a proper frame bounding the generated contents for each cell of the nested shapes information; determining complemented shapes for each cell as a difference between the generated proper frame and the generated contents for each cell of the nested shapes information; and storing the complemented shapes as native shapes in each cell.
References Cited (Backward Citations)
US4426584A
Cited
US4949162A
Cited
US4815003A
Cited
US5046012A
Cited
US5206815A
Cited
US5182718A
Cited
US5309371A
Cited
US5159201A
Cited
US5392222A
Cited
US5398195A
Cited
US5519628A
Cited
US5440720A
Cited
US5537648A
Cited
US5526279A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |