Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-12-22
2003-01-07
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06505323
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the design, layout, testing and manufacture of microelectronic circuits and systems, and more particularly to apparatus and methods for verifying microelectronic circuits and systems prior to manufacture.
BACKGROUND OF THE INVENTION
Present day ultra-large-scale integration (ULSI) circuits may include hundreds of thousands or millions of interconnected active electronic devices on an integrated circuit chip. The large capital investment required to fabricate and test large scale integrated circuits prior to sale to a customer and the difficulty, expense and loss of goodwill associated with reworking and replacing integrated circuits which fail to operate as planned, have increased the need to accurately characterize the electrical behavior of integrated circuits prior to their manufacture.
Moreover, now that submicron and deep-submicron (0.5 &mgr;m and below) technologies have begun to dominate silicon chip manufacturing and the prospect of million-plus-gate chips operating at clock rates of 100 MHZ has become a reality, fundamental changes have had to be made to conventional integrated circuit design methodologies and the electronic design automation (EDA) tools based thereon. To meet the challenges posed by such large-scale circuits, techniques have been developed to represent integrated circuit designs at various levels of abstraction. According to these techniques, an integrated circuit design may be represented by an electrical schematic containing devices and nets interconnecting the devices and by geometric layout data that describes patterns of regions or elements to be formed in and/or on an integrated circuit substrate (e.g., wafer).
Techniques for managing highly integrated circuit designs include hierarchical design techniques. Using such techniques, a particular design is partitioned into functional cells and cells-within-cells, etc., so that at a given level of hierarchy the design may be analyzed as a set of cells and their respective interconnections, without being concerned with all the details of the contents of the cells (e.g., subcells within each cell).
These hierarchical techniques can be essential to the efficient performance of computer-assisted integrated circuit design verification. Such verification may include operations to perform layout versus schematic comparison (LVS) using computer-based design tools. As will be understood by those skilled in the art, tools to perform layout versus schematic comparison may include extraction software to extract a layout netlist from geometric layout data. An extracted layout netlist is then compared to an electrical schematic netlist to determine functional equivalence between the original integrated circuit schematic and the integrated circuit layout. One difficulty associated with the performance of these operations may be caused by a dissimilarity in the labeling of nets and devices in the extracted layout netlist relative to the electrical schematic netlist.
Conventional methods for determining correspondence between an electrical schematic netlist and a layout netlist are described in U.S. Pat. Nos. 5,249,133 to Batra entitled “Method for the Hierarchical Comparison of Schematics and Layouts of Electronic Components”; U.S. Pat. No. 5,463,561 to Razdan entitled “High Capacity Netlist Comparison”; and U.S. Pat. No. 5,243,538 to Okuzawa et al. entitled “Comparison and Verification System for Logic Circuits and Method Thereof.” Another conventional method for determining correspondence includes operations to represent the electrical schematic netlist and the layout netlist as a schematic graph and a layout graph, respectively. Each of these graphs may be represented as bipartite graphs having vertices (also referred to herein as “nodes”) that represent devices and nets within their respective netlists. LVS software is then used to determine an isomorphism between the bipartite graphs.
The unambiguous determination of isomorphism between two arbitrary graphs may be a computationally intractable problem. To address this problem, heuristic methods for identifying graph isomorphisms with acceptable reliability and efficiency for ULSI designs have been developed. One generally established heuristic method is an iterative graph-coloring method described in articles by C. Ebeling and O. Zajicek entitled “Validating VLSI Circuit Layout By Wirelist Comparison,” Proceedings of ICCAD, pp. 172-173 (1983); and by C. Ebeling entitled “
Gemini II: A Second Generation Layout Validation Program
,” IEEE ICCAD-88, Digest of Technical Papers, pp. 322-325, Nov. 7-10, (1988), the disclosures of which are hereby incorporated herein by reference. As described in these articles, an integer node value (color) is assigned to each node of a bipartite graph of the electrical schematic netlist and the extracted layout netlist, based on a graph invariant such as “number of nearest neighbors” (i.e., number of adjacent nodes/vertices). Each node is iteratively recolored as a function of the colors of its neighbors, until the maximum number of unique colors is achieved (i.e., an equilibrium state is achieved). Because these operations are independent of labeling, equivalent schematic and layout netlists generally will be represented by the same set of colors. A one-to-one correspondence may then be achieved by simply matching up each node in the schematic graph with a node in the layout graph that has the same color.
Unfortunately, some circuits may exhibit symmetry that may cause different nodes to receive the same color because the “neighborhoods” associated with these nodes are similar. When two or more nodes have the same color, ambiguities in selecting matching nodes may arise. Typically, this situation is handled by making a guess as to which ones of the nodes in the schematic graph correspond to the same colored nodes in the layout graph, then assigning new colors to the matched nodes and then recoloring. If the guess was incorrect, a number of nodes may fail to match when the matching is applied at the next level of hierarchy, even though an alternate guess might have resulted in a complete one-to-one mapping.
For example, the AND-OR-INVERT (AOI) cell of
FIG. 1
exhibits a number of symmetries with respect to input A because input A may be independently swapped with input B or input A may be swapped with input C if and only if input B is also swapped with input D. Similar symmetries also exist with respect to inputs B, C and D.
FIG. 2
illustrates an original electrical schematic (S
1
) of the AOI cell and an extracted layout schematic (L
1
) of the AOI cell.
FIG. 3
illustrates an original electrical schematic (S
2
) which contains the AOI cell S
1
of
FIG. 2
as a child cell and an extracted layout schematic (L
2
) which contains the AOI cell L
1
of
FIG. 2
as a child cell. As will be understood by those skilled in the art, verification of the schematics of
FIG. 3
will only be concerned with the mapping of ports (W,X,Y,Z) of the AOI cell L
1
of
FIG. 2
to the ports (Q,R,S,T) of the schematic S
2
of FIG.
2
. However, because the symmetry of the design may cause the ports of each AOI child cell in
FIG. 2
to acquire the same color when the schematic and layout graphs of the AOI child cells have been colored to an equilibrium state, a conventional LVS tool may make an arbitrary mapping which may be incorrect (e.g., Q→W, R→Y, S→X, T→Z). A consequence of this arbitrary mapping may be manifested at the next level of hierarchy.
For example, as illustrated by
FIG. 3
, an incorrect choice in the mapping of S
1
to L
1
(i.e., the child cells) may cause S
2
and L
2
(i.e., the parent cells) to be reported as nonequivalent after a coloring algorithm has been performed on the schematic and layout graphs at the parent level. Here, devices D
1
-D
4
are distinct devices that are connected between the ports of the AOI “child” cell and the ports of the “parent” cell. Thus, LVS software may report a mismatch between an original electrical schematic netlist and an ext
Johnson, IV Harry Clarkson
Lipton Gary Bruce
White Jonathan Calvin
Avant! Corporation
Dimyan Magid Y
Myers Bigel & Sibley & Sajovec
Smith Matthew
LandOfFree
Methods, apparatus and computer program products that... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, apparatus and computer program products that..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, apparatus and computer program products that... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3016983