US6009252A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods, apparatus and computer program products for determining equivalencies between integrated circuit schematics and layouts using color symmetrizing matrices
Assignee: Synopsys Inc
•
Filing: 1998-03-05
•
Granted: 1999-12-28
•
Expires: 2018-03-05
Abstract
Abstract A layout versus schematic (LVS) comparison tool determines one-to-one equivalency between an integrated circuit schematic and an integrated circuit layout by performing operations to generate color symmetrizing matrices corresponding to respective child cells in the integrated circuit schematic. Here, the child cells are characterized as having a number of symmetrical configurations which at a port level are electrically equivalent. Operations are also performed to generate a first color symmetry vector for a child cell in the integrated circuit schematic and a second color symmetry vector for the corresponding child cell in the integrated circuit layout. A vector equivalency is also preferably determined by comparing a product of the color symmetrizing matrix and the first color symmetry vector against a product of the color symmetrizing matrix and the second color symmetry vector. Notwithstanding the presence of a vector equivalency, a possibility may still exist that with respect to the corresponding symmetric child cells in the schematic and layout, isomorphism between the schematic and layout is not present. To address this possibility, an operation is preferably performed to detect the absence of a spurious symmetry in the color symmetrizing matrix. If an absence is detected, the presence of the vector equivalency will unequivocally establish the one-to-one correspondence with respect to the child cells being analyzed. Thus, the need to perform a computationally expensive membership test to determine whether a selected permutation can be derived from valid symmetries, can be successfully eliminated. The preferred comparison tool also infers symmetries, where available, so that symmetries of a child cell may be propagated to a parent cell when the tool is evaluating a grandparent cell containing the parent cell.
Inventors
- 👤 Gary Bruce Lipton
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 14:53
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
222 words
A method of determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising the steps of: representing the integrated circuit schematic as a hierarchical schematic netlist having a child cell and a parent cell containing the child cell; extracting the integrated circuit layout as a hierarchical layout netlist having a child cell and a parent cell containing the child cell; generating a color symmetrizing matrix corresponding to one of the child cells in the hierarchical schematic netlist and the hierarchical layout netlist; generating a schematic graph of the parent cell in the hierarchical schematic netlist; generating a layout graph of the parent cell in the hierarchical layout netlist; coloring the vertices in the schematic graph and generating a first color symmetry vector for the child cell therein; coloring the vertices in the layout graph and generating a second color symmetry vector for the child cell therein; determining an equivalency between the colors of the vertices in the schematic graph and the colors of the vertices in the layout graph; determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 2
Independent Claim
222 words
A method of determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising the steps of: representing the integrated circuit schematic as a hierarchical schematic netlist having a child cell and a parent cell containing the child cell; extracting the integrated circuit layout as a hierarchical layout netlist having a child cell and a parent cell containing the child cell; generating a color symmetrizing matrix corresponding to one of the child cells in the hierarchical schematic netlist and the hierarchical layout netlist; generating a schematic graph of the parent cell in the hierarchical schematic netlist; generating a layout graph of the parent cell in the hierarchical layout netlist; coloring the vertices in the schematic graph and generating a first color symmetry vector for the child cell therein; coloring the vertices in the layout graph and generating a second color symmetry vector for the child cell therein; determining an equivalency between the colors of the vertices in the schematic graph and the colors of the vertices in the layout graph; determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 3
Dependent Claim
46 words
The method of claim 1, wherein said step of determining a vector equivalency comprises determining a vector equivalency if and only if an equivalency between the colors of the vertices in the circuit schematic graph and the colors of the vertices in the layout graph exists.
Claim 4
Dependent Claim
30 words
The method of claim 1, wherein said step of generating a color symmetrizing matrix comprises generating a color symmetrizing matrix corresponding to the child cell in the hierarchical schematic netlist.
Claim 5
Dependent Claim
68 words
The method of claim 3, wherein said representing step comprises representing the integrated circuit schematic as a hierarchical schematic netlist having a plurality of child cells and a parent cell containing the plurality of child cells; and wherein said extracting step comprises extracting the integrated circuit layout as a hierarchical layout netlist having a plurality of child cells and a parent cell containing the plurality of child cells.
Claim 6
Dependent Claim
98 words
The method of claim 4, wherein said step of coloring the vertices in the schematic graph comprises coloring the vertices in the schematic graph and generating a respective first color symmetry vector for each of the child cells in the schematic graph of the parent cell in the hierarchical schematic netlist; and wherein said step of coloring the vertices in the layout graph comprises coloring the vertices in the layout graph and generating a respective second color symmetry vector for each of the child cells in the layout graph of the parent cell in the hierarchical layout netlist.
Claim 7
Dependent Claim
51 words
The method of claim 1, wherein said step of detecting absence of a spurious symmetry comprises the steps of: determining a number of actual symmetries of the color symmetrizing matrix; and determining whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 8
Dependent Claim
39 words
The method of claim 6, wherein said step of detecting absence of a spurious symmetry comprises performing a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 9
Dependent Claim
37 words
The method of claim 7, wherein said step of performing a membership test comprises performing a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 10
Dependent Claim
118 words
The method of claim 1, wherein said step of determining a vector equivalency comprises determining a vector equivalency if and only if an equivalency between the colors of the vertices in the circuit schematic graph and the colors of the vertices in the layout graph exists; wherein said step of generating a color symmetrizing matrix comprises generating a color symmetrizing matrix corresponding to the child cell in the hierarchical schematic netlist; and wherein said step of detecting absence of a spurious symmetry comprises the steps of determining a number of actual symmetries of the color symmetrizing matrix; and determining whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 11
Dependent Claim
39 words
The method of claim 9, wherein said step of detecting absence of a spurious symmetry comprises performing a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 12
Dependent Claim
37 words
The method of claim 10, wherein said step of performing a membership test comprises performing a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 13
Independent Claim
114 words
A method of determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising the steps of: generating a color symmetrizing matrix corresponding to a child cell in the integrated circuit schematic; generating a first color symmetry vector for the child cell in the integrated circuit schematic; generating a second color symmetry vector for a child cell in the integrated circuit layout; determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 14
Independent Claim
114 words
A method of determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising the steps of: generating a color symmetrizing matrix corresponding to a child cell in the integrated circuit schematic; generating a first color symmetry vector for the child cell in the integrated circuit schematic; generating a second color symmetry vector for a child cell in the integrated circuit layout; determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 15
Dependent Claim
51 words
The method of claim 12, wherein said step of detecting absence of a spurious symmetry comprises the steps of: determining a number of actual symmetries of the color symmetrizing matrix; and determining whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 16
Dependent Claim
39 words
The method of claim 13, wherein said step of detecting absence of a spurious symmetry comprises performing a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 17
Dependent Claim
37 words
The method of claim 14, wherein said step of performing a membership test comprises performing a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 18
Independent Claim
228 words
A method of determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising the steps of: representing the integrated circuit schematic as a hierarchical schematic netlist having a child cell, a parent cell containing the child cell and a grandparent cell containing the parent cell; extracting the integrated circuit layout as a hierarchical layout netlist having a child cell, a parent cell containing the child cell and a grandparent cell containing the parent cell; propagating a symmetry of the child cell to the parent cell in the hierarchical schematic netlist; generating a color symmetrizing matrix corresponding to the parent cell in the hierarchical schematic netlist; generating a schematic graph of the grandparent cell in the hierarchical schematic netlist; generating a layout graph of the grandparent cell in the hierarchical layout netlist; coloring the vertices in the schematic graph and generating a first color symmetry vector for the parent cell therein; coloring the vertices in the layout graph and generating a second color symmetry vector for the parent cell therein; determining an equivalency between the colors of the vertices in the schematic graph and the colors of the vertices in the layout graph; and determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector.
Claim 19
Independent Claim
228 words
A method of determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising the steps of: representing the integrated circuit schematic as a hierarchical schematic netlist having a child cell, a parent cell containing the child cell and a grandparent cell containing the parent cell; extracting the integrated circuit layout as a hierarchical layout netlist having a child cell, a parent cell containing the child cell and a grandparent cell containing the parent cell; propagating a symmetry of the child cell to the parent cell in the hierarchical schematic netlist; generating a color symmetrizing matrix corresponding to the parent cell in the hierarchical schematic netlist; generating a schematic graph of the grandparent cell in the hierarchical schematic netlist; generating a layout graph of the grandparent cell in the hierarchical layout netlist; coloring the vertices in the schematic graph and generating a first color symmetry vector for the parent cell therein; coloring the vertices in the layout graph and generating a second color symmetry vector for the parent cell therein; determining an equivalency between the colors of the vertices in the schematic graph and the colors of the vertices in the layout graph; and determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector.
Claim 20
Dependent Claim
27 words
The method of claim 16, further comprising the step of detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 21
Dependent Claim
51 words
The method of claim 17, wherein said step of detecting absence of a spurious symmetry comprises the steps of: determining a number of actual symmetries of the color symmetrizing matrix; and determining whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 22
Dependent Claim
39 words
The method of claim 18, wherein said step of detecting absence of a spurious symmetry comprises performing a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 23
Dependent Claim
37 words
The method of claim 19, wherein said step of performing a membership test comprises performing a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 24
Dependent Claim
290 words
A computer program product for determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising a computer readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising: computer-readable program code means for representing the integrated circuit schematic as a hierarchical schematic netlist having a child cell and a parent cell containing the child cell; computer-readable program code means for extracting the integrated circuit layout as a hierarchical layout netlist having a child cell and a parent cell containing the child cell; computer-readable program code means for generating a color symmetrizing matrix corresponding to one of the child cells in the hierarchical schematic netlist and the hierarchical layout netlist; computer-readable program code means for generating a schematic graph of the parent cell in the hierarchical schematic netlist; computer-readable program code means for generating a layout graph of the parent cell in the hierarchical layout netlist; computer-readable program code means for coloring the vertices in the schematic graph and generating a first color symmetry vector for the child cell therein; computer-readable program code means for coloring the vertices in the layout graph and generating a second color symmetry vector for the child cell therein; computer-readable program code means for determining an equivalency between the colors of the vertices in the schematic graph and the colors of the vertices in the layout graph; computer-readable program code means for determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and computer-readable program code means detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 25
Dependent Claim
290 words
A computer program product for determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising a computer readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising: computer-readable program code means for representing the integrated circuit schematic as a hierarchical schematic netlist having a child cell and a parent cell containing the child cell; computer-readable program code means for extracting the integrated circuit layout as a hierarchical layout netlist having a child cell and a parent cell containing the child cell; computer-readable program code means for generating a color symmetrizing matrix corresponding to one of the child cells in the hierarchical schematic netlist and the hierarchical layout netlist; computer-readable program code means for generating a schematic graph of the parent cell in the hierarchical schematic netlist; computer-readable program code means for generating a layout graph of the parent cell in the hierarchical layout netlist; computer-readable program code means for coloring the vertices in the schematic graph and generating a first color symmetry vector for the child cell therein; computer-readable program code means for coloring the vertices in the layout graph and generating a second color symmetry vector for the child cell therein; computer-readable program code means for determining an equivalency between the colors of the vertices in the schematic graph and the colors of the vertices in the layout graph; computer-readable program code means for determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and computer-readable program code means detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 26
Dependent Claim
56 words
The computer program product of claim 21, wherein said computer-program product code means for determining a vector equivalency comprises computer-program product code means for determining a vector equivalency if and only if an equivalency between the colors of the vertices in the circuit schematic graph and the colors of the vertices in the layout graph exists.
Claim 27
Dependent Claim
58 words
The computer program product of claim 21, wherein said computer-program product code means for detecting absence of a spurious symmetry comprises computer-program product code means for determining a number of actual symmetries of the color symmetrizing matrix and determining whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 28
Dependent Claim
49 words
The computer program product of claim 23, wherein said computer-program product code means for detecting absence of a spurious symmetry comprises computer-program product code means for performing a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 29
Dependent Claim
47 words
The computer program product of claim 24, wherein said computer-program product code means for performing a membership test comprises computer-program product code means for performing a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 30
Independent Claim
121 words
An apparatus for determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising: means for generating a color symmetrizing matrix corresponding to a child cell in the integrated circuit schematic; means for generating a first color symmetry vector for the child cell in the integrated circuit schematic; means for generating a second color symmetry vector for a child cell in the integrated circuit layout; means for determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and means for detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 31
Independent Claim
121 words
An apparatus for determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising: means for generating a color symmetrizing matrix corresponding to a child cell in the integrated circuit schematic; means for generating a first color symmetry vector for the child cell in the integrated circuit schematic; means for generating a second color symmetry vector for a child cell in the integrated circuit layout; means for determining a vector equivalency between a product of the color symmetrizing matrix and the first color symmetry vector and a product of the color symmetrizing matrix and the second color symmetry vector; and means for detecting absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 32
Dependent Claim
50 words
The apparatus of claim 26, wherein said means for detecting absence of a spurious symmetry comprises means for determining a number of actual symmetries of the color symmetrizing matrix and determining whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 33
Dependent Claim
41 words
The apparatus of claim 27, wherein said means for detecting absence of a spurious symmetry comprises means for performing a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 34
Dependent Claim
39 words
The apparatus of claim 28, wherein said means for performing a membership test comprises means for performing a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 35
Dependent Claim
130 words
A computer program product for determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising: computer-readable program code that generates a color symmetrizing matrix corresponding to a child cell in the integrated circuit schematic; computer-readable program code that determines a vector equivalency between a product of the color symmetrizing matrix and a first color symmetry vector for the child cell in the integrated circuit schematic and a product of the color symmetrizing matrix and a second color symmetry vector for a child cell in the integrated circuit layout; and computer-readable program code that detects absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 36
Dependent Claim
130 words
A computer program product for determining equivalency between an integrated circuit schematic and an integrated circuit layout, comprising a computer-readable storage medium having computer-readable program code embodied in said medium, said computer-readable program code comprising: computer-readable program code that generates a color symmetrizing matrix corresponding to a child cell in the integrated circuit schematic; computer-readable program code that determines a vector equivalency between a product of the color symmetrizing matrix and a first color symmetry vector for the child cell in the integrated circuit schematic and a product of the color symmetrizing matrix and a second color symmetry vector for a child cell in the integrated circuit layout; and computer-readable program code that detects absence of a spurious symmetry in the color symmetrizing matrix if a vector equivalency is determined.
Claim 37
Dependent Claim
60 words
The computer program product of claim 30, wherein said computer-readable program code that detects absence of a spurious symmetry comprises: computer-readable program code that determines a number of actual symmetries of the color symmetrizing matrix; and computer-readable program code that determines whether the number of actual symmetries of the color symmetrizing matrix is equivalent to a number of desired symmetries.
Claim 38
Dependent Claim
47 words
The computer program product of claim 31, wherein said computer-readable program code that detects absence of a spurious symmetry comprises: computer-readable program code that performs a membership test if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
Claim 39
Dependent Claim
45 words
The computer program product of claim 32, wherein said computer-readable program code that performs a membership test comprises computer-readable program code that performs a Schreier-Simms operation if the number of actual symmetries of the color symmetrizing matrix is greater than the number of desired symmetries.
References Cited (Backward Citations)
US5249134A
Cited
US5301318A
Cited
US5095454A
Cited
US5243538A
Cited
US5243538B1
Cited
US5555201A
Cited
US5801958A
Cited
US5541849A
Cited
US5249133A
Cited
US5490095A
Cited
US5349659A
Cited
US5648910A
Cited
US5281558A
Cited
US5513313A
Cited
US5497334A
Cited
US5528508A
Cited
US5475695A
Cited
US5606698A
Cited
US5550750A
Cited
US5455928A
Cited
US5463561A
Cited
US5461576A
Cited
US5469366A
Cited
US5634115A
Cited
US5568396A
Cited
US5581474A
Cited
US5548524A
Cited
US5623419A
Cited
US5559718A
Cited
US5475605A
Cited
US5604680A
Cited
US5590049A
Cited
US5625565A
Cited
US5903469A
Cited
US5592392A
Cited
US5610832A
Cited
US5636132A
Cited
US5625564A
Cited
US5689432A
Cited
US5694481A
Cited
US5649166A
Cited
US5574388A
Cited
US5691910A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-27 | 2003-06-28 | 2003-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-27 | 2007-06-28 | 2007-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-27 | 2011-06-28 | 2011-12-28 | $7700.00 | Window Closed / Lapsed |