US6011911A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Layout overlap detection with selective flattening in computer implemented integrated circuit design
Assignee: Synopsys Inc
•
Filing: 1997-09-30
•
Granted: 2000-01-04
•
Expires: 2017-09-30
Abstract
Abstract The present invention relates to a method for efficiently performing hierarchical design rules checks (DRC) and layout versus schematic comparison (LVS) on layout areas of an integrated circuit where cells overlap or where a cell and local geometry overlap. With the present invention, a hierarchical tree describes the integrated circuit's layout data including cells having parent-child relationships and including local geometry. The present invention performs efficient layout verification by performing LVS and DRC checking on the new portions of an integrated circuit design and layout areas containing overlapping cells. When instances of cells overlap, the present invention determines the overlap area using predefined data structures that divide each cell into an array of spatial bins. Each bin of a parent is examined to determine if two or more cell instances reside therein or if a cell instance and local geometry reside therein. Once overlap is detected, the areas of the layout data corresponding to the overlap areas are selectively flattened prior to proceeding to DRC and LVS processing. During selective flattening of the overlap areas, the hierarchical tree is traversed from the top cell down through intermediate nodes to the leaf nodes. Each time geometry data is located during the traversal, it is pushes directly to the top cell without being stored in intermediate locations. This provides an effective mechanism for selective flattening.
Inventors
- 👤 Wai-Yan Ho
- 👤 Hongbo Tang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 08:45
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
166 words
A computer implemented method for verifying a portion of layout data of an integrated circuit device where said layout data comprises a plurality of cells having parent-child relationships and organized according to a hierarchical tree, said method comprising the steps of: a) defining an array of top level bins corresponding to the surface area of a top level cell of said integrated circuit wherein a parent cell can include multiple top level bins; b) constructing a linked list for each top level bin wherein said linked list contains a listing of bins of all instances within said top level bin and any local geometry within said top level bin; and c) identifying overlap areas within said integrated circuit by searching through all link lists of said top level bins and recording top level bins having bins of two or more cell instances indicated in their corresponding linked lists; and d) performing layout verification only on layout geometries associated with said overlap areas identified in step c).
Claim 2
Dependent Claim
166 words
A computer implemented method for verifying a portion of layout data of an integrated circuit device where said layout data comprises a plurality of cells having parent-child relationships and organized according to a hierarchical tree, said method comprising the steps of: a) defining an array of top level bins corresponding to the surface area of a top level cell of said integrated circuit wherein a parent cell can include multiple top level bins; b) constructing a linked list for each top level bin wherein said linked list contains a listing of bins of all instances within said top level bin and any local geometry within said top level bin; and c) identifying overlap areas within said integrated circuit by searching through all link lists of said top level bins and recording top level bins having bins of two or more cell instances indicated in their corresponding linked lists; and d) performing layout verification only on layout geometries associated with said overlap areas identified in step c).
Claim 3
Dependent Claim
55 words
The method of claim 1 wherein step c) further comprises the step of identifying overlap areas within said integrated circuit by searching through all said link lists of said top level bins and recording top level bins having local geometry and a bin of at least one cell instance indicated in their corresponding linked lists.
Claim 4
Dependent Claim
33 words
The method of claim 1 wherein step d) comprises the steps of: d1) flattening said overlap areas into an overlap database; and d2) performing layout verification on the geometries of said overlap database.
Claim 5
Dependent Claim
36 words
The method of claim 3 wherein step d2) comprises the steps of: performing design rule checking on said geometries of said overlap database; and performing layout versus schematic checking on said geometries of said overlap database.
Claim 6
Dependent Claim
94 words
The method of claim 1 wherein said step b) comprising the steps of: b1) defining an array of local bins for each cell instance of said hierarchical tree; b2) identifying the coordinates of each of said local bins of each of said cell instances with respect to coordinates of said top level bins; b3) using said coordinates to record, in a linked list for a given top level bin, those local bins located within said given top level bin; and b4) repeating step b3) for each top level bin of said top level cell.
Claim 7
Dependent Claim
69 words
The method of claim 5 wherein said step b) further comprises the steps of: b5) identifying the coordinates of each local geometry of said top level cell; and b6) using said coordinates to record, in a linked list for a given top level bin, those local geometry located within said given top level bin; and b7) repeating step b6) for each top level bin of said top level cell.
Claim 8
Dependent Claim
197 words
A computer implemented method for verifying a portion of the layout data defining an integrated circuit, said method comprising the computer implemented steps of: a) creating a polygon database having a plurality of cells containing geometry of said layout data; b) creating a hierarchical tree defining parent-child relationships of said plurality of cells wherein said hierarchical tree and said plurality of cells fully describe the layout data of said integrated circuit; c) defining an array of top level bins corresponding to the surface area of a top level cell of said integrated circuit wherein a parent cell can include multiple top level bins; d) constructing a linked list for each top level bin wherein said linked list contains a listing of bins of all cell instances within said top level bin and any local geometry within said top level bin; e) identifying overlap areas within said integrated circuit by searching through all link lists of said top level bins and recording top level bins having bins of two or more cell instances indicated in their corresponding linked lists; and f) performing layout verification only on layout geometries associated with said overlap areas as identified in step e).
Claim 9
Dependent Claim
197 words
A computer implemented method for verifying a portion of the layout data defining an integrated circuit, said method comprising the computer implemented steps of: a) creating a polygon database having a plurality of cells containing geometry of said layout data; b) creating a hierarchical tree defining parent-child relationships of said plurality of cells wherein said hierarchical tree and said plurality of cells fully describe the layout data of said integrated circuit; c) defining an array of top level bins corresponding to the surface area of a top level cell of said integrated circuit wherein a parent cell can include multiple top level bins; d) constructing a linked list for each top level bin wherein said linked list contains a listing of bins of all cell instances within said top level bin and any local geometry within said top level bin; e) identifying overlap areas within said integrated circuit by searching through all link lists of said top level bins and recording top level bins having bins of two or more cell instances indicated in their corresponding linked lists; and f) performing layout verification only on layout geometries associated with said overlap areas as identified in step e).
Claim 10
Dependent Claim
55 words
The method of claim 7 wherein step e) further comprises the step of identifying overlap areas within said integrated circuit by searching through all said link lists of said top level bins and recording top level bins having local geometry and a bin of at least one cell instance indicated in their corresponding linked lists.
Claim 11
Dependent Claim
33 words
The method of claim 7 wherein step f) comprises the steps of: f1) flattening said overlap areas into an overlap database; and f2) performing layout verification on the geometries of said overlap database.
Claim 12
Dependent Claim
36 words
The method of claim 9 wherein step f2) comprises the steps of: performing design rule checking on said geometries of said overlap database; and performing layout versus schematic checking on said geometries of said overlap database.
Claim 13
Dependent Claim
94 words
The method of claim 7 wherein said step d) comprising the steps of: d1) defining an array of local bins for each cell instance of said hierarchical tree; d2) identifying the coordinates of each of said local bins of each of said cell instances with respect to coordinates of said top level bins; d3) using said coordinates to record, in a linked list for a given top level bin, those local bins located within said given top level bin; and d4) repeating step d3) for each top level bin of said top level cell.
Claim 14
Dependent Claim
69 words
The method of claim 11 wherein said step d) further comprises the steps of: d5) identifying the coordinates of each local geometry of said top level cell; and d6) using said coordinates to record, in a linked list for a given top level bin, those local geometry located within said given top level bin; and d7) repeating step d6) for each top level bin of said top level cell.
Claim 15
Dependent Claim
228 words
A computer system having a processor coupled to a bus and a memory unit coupled to said bus, said memory unit containing instructions that when executed implement a method for verifying a portion of the layout data defining an integrated circuit, said method comprising the steps of: a) creating a polygon database within said memory unit having a plurality of cells each for containing geometry of said layout data; b) creating a hierarchical tree defining parent-child relationships of each of said plurality of cells wherein said hierarchical tree and said plurality of cells fully describe the layout data of said integrated circuit; c) defining an array of top level bins corresponding to the surface area of a top level cell of said integrated circuit wherein a parent cell can include multiple top level bins; d) constructing a linked list for each top level bin wherein said linked list contains a listing of bins of all instances within said top level bin and any local geometry within said top level bin; and e) identifying overlap areas within said integrated circuit by searching through all link lists of said top level bins and recording top level bins having bins of two or more cell instances indicated in their corresponding linked lists; and f) performing layout verification only on layout geometries associated with said overlap areas as identified in step e).
Claim 16
Dependent Claim
228 words
A computer system having a processor coupled to a bus and a memory unit coupled to said bus, said memory unit containing instructions that when executed implement a method for verifying a portion of the layout data defining an integrated circuit, said method comprising the steps of: a) creating a polygon database within said memory unit having a plurality of cells each for containing geometry of said layout data; b) creating a hierarchical tree defining parent-child relationships of each of said plurality of cells wherein said hierarchical tree and said plurality of cells fully describe the layout data of said integrated circuit; c) defining an array of top level bins corresponding to the surface area of a top level cell of said integrated circuit wherein a parent cell can include multiple top level bins; d) constructing a linked list for each top level bin wherein said linked list contains a listing of bins of all instances within said top level bin and any local geometry within said top level bin; and e) identifying overlap areas within said integrated circuit by searching through all link lists of said top level bins and recording top level bins having bins of two or more cell instances indicated in their corresponding linked lists; and f) performing layout verification only on layout geometries associated with said overlap areas as identified in step e).
Claim 17
Dependent Claim
56 words
The computer system of claim 13 wherein step e) further comprises the step of identifying overlap areas within said integrated circuit by searching through all said link lists of said top level bins and recording top level bins having local geometry and a bin of at least one cell instance indicated in their corresponding linked lists.
Claim 18
Dependent Claim
39 words
The computer system of claim 13 wherein step f) comprises the steps of: f1) flattening said overlap areas into an overlap database stored within said memory unit; and f2) performing layout verification only the geometries of said overlap database.
Claim 19
Dependent Claim
37 words
The computer system of claim 15 wherein step f2) comprises the steps of: performing design rule checking on said geometries of said overlap database; and performing layout versus schematic checking on said geometries of said overlap database.
Claim 20
Dependent Claim
96 words
The computer system of claim 13 wherein said step d) comprising the steps of: d1) defining an array of local bins for each cell instance; d2) identifying the coordinates of each of said local bins of each of said cell instances with respect to coordinates of said top level bins of said top level cell; d3) using said coordinates to record, in a linked list for a given top level bin, those local bins located within said given top level bin; and d4) repeating step d3) for each top level bin of said top level cell.
Claim 21
Dependent Claim
69 words
The computer system of claim 17 wherein said step d) further comprises the steps of: d5) identifying the coordinates of each local geometry of said top level cell; d6) using said coordinates to record, in a linked list for a given top level bin, those local geometries located within said given top level bin; and d7) repeating step d6) for each top level bin of said top level cell.
References Cited (Backward Citations)
US5050091A
Cited
US5544067A
Cited
US5281558A
Cited
US5528508A
Cited
US5604680A
Cited
US5625564A
Cited
US5629861A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-03 | 2003-07-05 | 2004-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-03 | 2007-07-05 | 2008-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-03 | 2011-07-05 | 2012-01-04 | $7700.00 | Window Closed / Lapsed |