Introducing Guardian -
LVS Verification for PC-based Platforms


Introduction

Guardian is a (state-of-the-art) hierarchical netlist comparison system, which eliminates many of the disadvantages of existing programs. Running on PCs under Windows NT, it easily compares circuits with a large number of devices. The advanced algorithms implemented in Guardian allow a substantial reduction of execution time and also detect discrepancies between two netlists more precisely. Guardian generates a comprehensive hierarchical report, which is easy to read. An embedded tool, called the Spice Netlist Rover, links report files with source netlists to make inspecting correct matches and errors simple.



Guardian Functionality

Guardian is used for comparing two circuits described by their netlists. Most often one of these netlists corresponds to the schematic of a circuit produced by a schematic editor. It represents the logic of the circuit. The other one is extracted from mask layout by Maverick netlist extractor. It represents the actual physical layout of the circuit as produced by Expert layout editor. This kind of circuit verification is called LVS (layout versus schematic comparison). It is not uncommon to compare two schematic netlists (SVS, or schematic versus schematic) or two layout netlists (LVL, or layout versus layout).



Figure 1. Running LVS for open spice file.



Guardian compares circuits, which may contain both primitive devices (flat circuits) and cell or hierarchical blocks of different kinds (hierarchical circuits).

Guardian does not require any identification marks in both netlists to start comparison. However, it takes advantage of such marks if present, allowing comparison with initial correspondence node pairs defined in the prematch file.

Guardian uses Spice netlist format for comparison. Spice netlists describe circuits at the device level i.e. in terms of transistors, diodes, resistors and capacitors.

If a spice netlist contains only subcircuit definitions but neither subcircuit calls nor element statements, one of these subcircuits serves as a main subcircuit. In fact, this subcircuit will contain other subcircuit calls and/or element statements. In this case, the main subcircuit will be treated as the top-level subcircuit.

If there are subcircuit calls and/or element statements in the spice netlist, they will be considered as elements of the top level subcircuit. The default subcircuit name "top" will be used for it.

The basic flow of the netlist comparison is as follows.

First of all, Guardian performs netlist transformation. At this stage, series and parallel devices are merged and unused devices are filtered out.

After that Guardian performs logic gate recognition and reduces groups of transistors into "boxes" with permutable (interchangeable) groups of terminals.

Finally, the actual comparison takes place, during which Guardian attempts to match elements of the two netlists against each other.

Both preprocessing and comparison are controlled by various options and conditions. Some options may be specified through the user interface, others are specified by control files. An example of the latter case is the list of prematched nets, devices, or subcircuits.

The results of netlist comparison (filtered, merged and reduced devices, matched pairs, and discrepancies) are stored in report files. While reporting unmatched nodes Guardian gives suggestions about node pairs that could be correct matches if discrepancies between netlists were fixed.


Running Guardian

Using Guardian is very simple and convenient. There is an embedded text editor, which allows viewing of netlists and reports. You can start netlist comparison while viewing an open spice file by selecting the Run LVS menu command. A dialog box prompting the user to choose the second spice file for the comparison will appear.

The second way to start comparison is to use Run LVS menu command when there is no open spice file. The Guardian Settings panel will open for selecting input files and options.




Figure 2. Main page of Guardian Settings



All options for running LVS are set through the user interface. The only exception is for defining any initial corresponding node pairs in the prematch file.

There is an option to save all current settings into the context file. Saved settings can be restored at any time from the file for use in comparison.



Netlist Transformation

While preprocessing Guardian can optimize input netlists in order to reduce the number of devices and to replace groups of primitive devices by logical gates. Netlist transformation has the following steps:

  • All unused devices such as MOS transistors with shortened drain and source, devices with floating pins, MOS transistors with gate connected to ground or power nets are filtered out.


  • Devices of the same type connected in parallel or in series are merged into a single element. MOS transistors connected in series must have a common gate.


  • Groups of transistors which represent most common logic gates (inverter, NAND, NOR, etc.) are recognized and replaced with "black boxes" with permutable terminals.


  • Groups of transistors, which do not form common logic gates, are combined together into a single element with permutable terminals as well.


  • Two terminal devices (resistors, capacitors, etc.) connected in parallel or in series but found in different cells (even at different levels of hierarchy) are across-hierarchically reduced into a single device.



All components of netlist transformation listed above are optional and can be switched off by the user.


Advanced Guardian Comparison Algorithm.


The mathematical aspects of the netlist comparison problem have been extensively studied, and many different algorithms have been developed. Most of them are based on classical graph isomorphism (GI) techniques. These techniques require flattening compared netlists, assigning labels to nodes (devices and nets) and then refining the labels according to the node neighborhood. As a result, GI-based algorithms compare successfully only simple circuits (netlists) with little or no symmetry. On the other hand, they have several serious disadvantages when applied to realistically large circuits with high symmetry. In particular, the loss of information about circuit hierarchy as well as circuit symmetry may tremendously increase execution time. Furthermore, algorithms using GI methods cannot prevent single error propagation, which results in the generation of many spurious errors far from the original one.

The power of Guardian is a result of using advanced, fast search?oriented subgraph isomorphism techniques. It helps overcome drawbacks associated with standard GI?based algorithms. In other words, the Guardian comparison algorithm combines both the graph isomorphism and the special subgraph isomorphism methods and dynamically switches between them depending on an analysis of the validation process. Briefly, the Guardian algorithm can be presented as follows. The partitioning techniques are used as the primary basis of the algorithm. Compared circuits are represented by bipartite graphs with devices and nets as graph nodes. These nodes are partitioned into classes based on assigning labels according to node invariants. Obtained labels are repeatedly refined using the principles of local and global matching and some kinds of heuristics. This avoids avoiding label collisions and leads to singular partitions with high probability.

However, the basic refinement algorithm has some disadvantages. For example, in the presence of symmetry the relabeling process requires too many iterations to obtain unique labels. Further, in some cases there is no sufficient information available for label recalculation. It leads to creating non-singular partitions. Combination of the above GI ? based algorithm with special fast search ? oriented subgraph isomorphism (SGI) techniques helps avoid such problems. First of all, these SGI techniques are used to form original patterns of gate level subcircuits and then quickly find and match these patterns in both netlists anywhere it is possible. If the matching of whole patterns is impossible owing to errors, we dynamically form pseudo gates and match them to the most appropriate original gate patterns. Such a pseudo matching procedure avoids label collisions and error spreading, enhancing error classification. Moreover, the more detailed analysis with pseudo matched gates often allows matching nodes in a graph "region" neighboring error node. If pseudo matching was erroneous, it does not lead to extra errors due to analysis of netlist hierarchy.

Thus, the advanced Guardian comparison algorithm yields comparison results that are superior comparing with other algorithms.


Flatten Function

Sometimes a user may need to work with a flat rather than hierarchical netlist. One of the features of Guardian is a possibility to convert hierarchical netlists into flat ones. The flatten function performs this task. The resulting netlist is stored in a spice format file with comments, which explain the conversion details. Device and net names in the resulting flat netlist contain information about the whole path from the top level of circuit hierarchy to the node.


Integrated Spice Netlist Rover

One of the advanced features of Guardian is the Spice Netlist Rover that is seamlessly integrated within it. Spice Netlist Rover is a tool for navigating through the hierarchy of the netlist represented in the form of a tree. In addition to hierarchy tree navigation, Spice Netlist Rover provides a convenient visual supplement for other operations that are somehow related to netlist hierarchy. It highlights selected cell instances, visualizes the results of the LVS verification (e.g. coloring matched and unmatched instances). It also allows the user to specify and show instances placed anywhere in the netlist?s hierarchy, and to find and select a branch of any instance from the spice netlist.





Figure 3. Spice Netlist Rover in action.


Depending on the Spice Rover actions the netlist hierarchy is shown in two different forms: Basic Tree View and Branch Tree View.

Having two forms of view is essential in case of "cell hierarchy", when a circuit consists of hierarchically nested cell instances. When hierarchy becomes deeper and more instances of the same cell appear, the hierarchical tree becomes enormous and incomprehensible.

For this reason Basic Tree View branches out only along cells. The instances of the same cell in a common parent cell are grouped together and do not branch further.

Spice Rover performs the following operations between the hierarchy tree and the spice netlist:

  • If you double click on a cell item you switch to the window containing the spice netlist at the place where this cell is defined.


  • If you double click on a cell instance you switch to the window with the spice netlist and highlights the place where this cell is called.


  • Double clicking on a device highlights a device statement in the spice netlist.

Spice Netlist Rover may show several trees:

  • Active Cell Tree shows the hierarchy of the cell in the current active window.
  • Project Tree shows the hierarchy of the whole netlist.
  • Branch Tree allows Spice Rover to access cell instances laying deep in the hierarchy of the active cell.



Advanced Hierarchical Report

When hierarchical netlists are being compared, the output files are desired in hierarchical form as well. It is also very important not only to have a list of unmatched nodes, but to also point out causes of these discrepancies. Unlike other LVS systems, Guardian performs both tasks.

Guardian reports matched node pairs and unmatched nodes starting from the top-level subcircuit, which corresponds to the zero hierarchy level. After that nodes from the most complex subcircuit, which belongs to the top level, are reported, and so on. As a result all reported nodes will be composed of a hierarchical tree. Increasing level numbers reflects a moving down in the hierarchy. Since the netlists being compared may have a different hierarchy structure, the level number is defined according to the first netlist hierarchy structure.

In most cases netlists differ from each other. In this case Guardian tries to match elements of one netlist to elements of the other as often as possible. An advanced approach is used to classify discrepancies and locate the errors. Information about the node environment is collected during the comparison. It is used in an attempt to find node pairs that could have matched.

As a part of the Guardian report, a file will list all nodes that have not been matched. This file contains three sections:

Unmatched nodes and possible matches
This section contains unmatched nets and devices from the first netlist that have unique neighborhoods. However no corresponding net/device is found in the second netlist. Wherever it is possible the matching algorithm gives a reference to a node (or nodes) from second netlists that did not match because of having different features (different device type or net degree). If a net from the first netlist has more than one possible match in many cases it may indicate a broken connection in the second netlist. For some nodes no references may be found. Missing devices in the second netlist might cause such an outcome.

Following group(s) of unmatched nodes might have appeared in the case of missing corresponding node(s) in either netlist
In this section, groups with the same feature nodes in both netlists are listed. Node features are defined by node environment. Nodes inside a group are similar and can not be distinguished from one another (e.g. resistors connected in parallel or nets with similar connections). The number of nodes in corresponding groups is always different because of discrepancies between two netlists. For this reason the algorithm is not able to match nodes from one group to nodes from the other. In many cases such groups might result from missing devices or nets in either netlist.

For following nodes from the second netlist no references have been found
This section reports all unmatched nets and devices from the second netlist that have not been listed in the previous two sections. No references from the first netlist were found by the matching algorithm. In many cases these nodes are missing in the first netlist. An example of the unmatched report file is given for two input multiplexer:


    * * * * * * * * * * * * * * * * * * * * *
    * GUARDIAN UNMATCHED NODES REPORT *
    * * * * * * * * * * * * * * * * * * * * *
    first netlist: "mux2m"

    number of unmatched nets : 3
    number of unmatched devices : 0
    second netlist: "mux2m_e"

    number of unmatched nets : 4
    number of unmatched devices : 1

    UNMATCHED NODES AND POSSIBLE MATCHES:

    L0: N: top:VSS[4] . . . . . >> top:VSS[5]
    L0: N: top:MOUT[3] . . . . . >> top:MOUT[4]
    L1: N: top:XMUX2:XINV_OUT[4] >> top:XMUX2:#10[2]
    top:XMUX2:XINV_OUT[2]

    FOR FOLLOWING NODES FROM SECOND NETLIST NO REFERENCES HAVE BEEN FOUND:

    L?: R: No reference found . >> top:RLOAD

    * * * * * * * * * * * * * * * * * * * * *

All three sections may not appear in every the unmatched file as it depends on discrepancies between the two netlists. However the first section is generated whenever any errors have been detected.





Figure 4. Two input multiplexer.







Figure 5. Layout display for
two-input multiplexer.





Guardian Report Browsing

Guardian has an efficient viewer which links output files to netlists and makes easy to browse reports.

If one double clicks on a (hierarchical) name of an instance or a net in the Guardian match or discrepancy file, this name will become highlighted and the Element View panel will appear as shown at Figure 6.





Figure 6. Report browsing.



Depending on where a node is located in the netlist (top level or subcircuit) a corresponding viewer option will be available. Two ways of browsing are available:

  • If you select Top level or Subcircuit level option and press OK button, the corresponding spice netlist will be opened and the location of first appearance for this node name will be highlighted. This place will be either at the top level of netlist or in the subcircuit.


  • If you select Environment option and press the OK button, all node neighbors can be inspected. The panel Element Environment pop-up will appear.







Figure 7. Sequential viewing elements neighbors.

This panel shows the name, type, full path of the selected node and the list of its neighbors in the hierarchical netlist. All neighbors of a device are nets. All neighbors of a net are devices.

Now you can "travel" through the entire netlist by double clicking on one of the element neighbors. Each time a similar panel will appear for that neighbor.