Methods, apparatus and computer program products for determining equivalencies between integrated circuit schematics and layouts using color symmetrizing matrices
First Claim
1. 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.
2 Assignments
0 Petitions
Accused Products
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.
85 Citations
33 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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. - View Dependent Claims (13, 14, 15)
-
-
16. 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. - View Dependent Claims (17, 18, 19, 20)
-
-
21. 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. - View Dependent Claims (22, 23, 24, 25)
-
-
26. 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. - View Dependent Claims (27, 28, 29)
-
-
30. 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. - View Dependent Claims (31, 32, 33)
-
Specification