GEMINI(1.VLSI)

NAME
gemini - Compare two circuit netlists

SYNOPSIS
gemini [options] circuit1 circuit2

DESCRIPTION
Gemini compares the two circuits contained in the files circuit1 and circuit2 and determines whether they are equivalent. If the circuits are different, Gemini reports a set of nets and devices that it thinks are the source of the difference. If the circuits are too different, then this set may be too large to be helpful. In this case, the user may bind corresponding nodes in the two circuits to help Gemini find the source of error. The circuit file format may be of two types: The MIT/Berkeley SIM format that is widely used for NMOS and CMOS circuits, and a general purpose circuit format used by Gemini. This latter format is provided so that users can use Gemini on whatever circuit technology they are interested in. The algorithm used by Gemini is based on general graph isomorphism and thus is technology independent. For a description of this format, refer to the Gemini User's Manual. (While Gemini has been used for other technologies, the user should be aware that Gemini has only been tested using SIM file input.) Gemini first reads the two circuit graphs and prints a summary containing the number of devices and nets in each. It then performs a graph isomorphishm algorithm which matches nodes between the two circuits in a series of passes. Gemini prints a series of digits indicating in thousands the number of nodes that have been matched. Many programs that produce SIM format produce accompanying .al (alias) files containing `=' lines indicating node names that are equivalent. Gemini automatically looks for .al files corresponding to the circuit files specified in the command line. The .al file is ignored if not present. Gemini can also warn the user about nets in the circuit which have no connections. These will probably be extraneous items like a logo but may in fact be something more serious like an input pad that has not been connected. Part of the information produced by Gemini is the number of matches that were deduced. This indicates how successful the local matching algorithm was in matching nodes. If this number is small with respect to the total number of nodes in the circuits, it indicates that the circuits are very symmetrical. The option flags may be specified anywhere in the command line and there need not be a space between the flag and it's argument.

-h  Print a short description of the most commonly used options.

-m  Do NOT use the local matching algorithm, but rely solely on the global partitioning algorithm.

-f  Case-fold names when reading in the two circuit graphs. Case sensitive node names are NOT recommended; however, Gemini runs a bit faster if it does not have to case-fold. Vdd and GND are treated separately so that case is always ignored for these two signal names.

-w  This will cause Gemini to check the sizes of the transistors it matches and print a warning if they are not the same, within a given tolerance (+/- 10%).

-z  Tells Gemini to print all nets with zero connections.

-c  Disable the preprocessing step that Gemini uses to collapse series transistor chains before applying the isomorphism algorithm. The cost of this step varies, typically 0-20%, but in some cases up to 50%.

-cw Enable warnings for those series transistors whose order does not correspond in the two circuits. (Note that -c and -cw are exclusive.) The default is no warning other than a count of the number of series connected transistors out of order.

-nnumber
    This parameter determines how much information is printed for nets. If the nets has fewer than <number> connections, then information is printed out for each connection. Otherwise, only the net name is printed. The default value is 10.

-v  Turn on Verbose mode. This may cause more detailed information to be printed for nets and devices.

-E  filename
    Gemini reads an equivalence file that binds corresponding nodes in the two circuits. Each line in the file begins with a `=' followed by two names, the first from the first circuit and followed a name from the second. These two nodes are bound together before the circuit graphs are matched.

-D  filename
    Gemini produces a dictionary file that indicates the matching nodes in the two circuits. The file format is the same as the equivalence file format. Only nodes with real names (not *) are printed in this file.

-M  symbol[:number]
    Gemini produces an error file in Magic format, highlighting the devices that appear in the error report. The extracted SIM file must given first and symbol is the name of the root symbol of the magic layout. The magic output file is produced with the name "symbol.err.mag" and contains both labels and rectangles on the error layer for each device that appears in the device error list or as a connection in the net error list. The devices from the two lists are distinguished by the label used. A "D" label indicates a non-matching device. A "N" label indicates the device is connected to a non-matching net whose name is also given. (Of course a device may have both a D and N label.) (The -n option can be used to control the devices listed in the net error list.) An optional number after a colon gives the value of lambda in CIF units. The default value is 100 (corresponding to a 2 micron process). If the -cw option is used, transistor chains appearing out of order will be marked. The error label given is "SIZE". If the -w option is used, transistors with sizes outside the tolerance will be marked. The error label indicates the size of the matching transistor in the other circuit.

-G  Use the Gemini input format instead of the default SIM format.

-I  Run Gemini interactively. This allows the user to give Gemini some help when it comes to matching ambiguous nodes.

The following flags can be used to change the parameters used by the graph isomorphism algorithm of Gemini. Users are advised to leave these alone unless they understand what the algorithm is doing.

-t  Trace the progress of the labelling procedure. This will show how much trouble Gemini is having with the circuit.

-o  Do not optimize the labelling procedure. This means that ALL nodes will be relabelled on every pass.

-pnumber
    Specify the number of labelling passes where no progress is detected before trying something drastic. The default value is 2.

-snumber
    Specify the number of times suspect nodes are relabeled where no progress is detected before trying something even more drastic. The default value is 1.

-enumber
    Gemini is allowed to stop when there are less than this many unresolved nodes left in the two circuits. The default value is 0. I don't know why you would want to change this value.

Doublechecking Gemini
Old versions of Gemini have been known to report differing circuits as being the same. The way to ensure that this is not the case is to create a dictionary file using the -D option and then rerun Gemini using the -E option with this file. There have been no reported instances of this type of error with this version of Gemini. PLEASE send a bug report if you suspect that this has happened to you.

ERROR REPORT
Gemini produces error reports as listings of nets and devices it thinks are at fault. The key idea is that the circuits are identical if the given nets and devices are deleted from the circuits. Gemini has 2 different classes of error nodes: those that it thinks are definitely in error and those that may be OK if the nodes in the first class are fixed. In general, it is best to examine all nodes in the error report. Devices and nets are printed in varying detail. Nets are identified by name and the devices to which they are connected. The -n option allows more or less detail to be shown for nets. Devices are identified by name (if any) and the nets to thich they are connected. These connections are listed in the same order as given in the device definitions. For SIM file transistors, the connections are listed in the same order as in the SIM file - gate followed by source and drain. For devices representing series connected transistors, the gates are listed first, in the order in which they appear between the collective source and drain.

SERIES CONNECTED TRANSISTORS
Unless the -c flag is used, series connected transistors are merged into single devices. Gemini checks as these devices are matched to make sure the transistors are in the same order in both circuits and prints a warning (if -cw is used) if they are not. In symmetrical circuits where are there are chains with the same gate sequence, but with a different order, Gemini may arbitrarily match the wrong chains and print a warning. (This will be fixed in a later version of Gemini.)

SYMMETRIC CIRCUITS
When there is symmetry in the circuits being compared, there will be many different ways that some nodes can be matched between the two circuits. For example, in a memory array, the words lines and bit lines can be permuted giving an exponential number of different ways to match the nodes in the two circuits. When Gemini detects that its algorithm is making no progress, it assumes that the problem is one of symmetry. It also assumes that the partitions that it has at that point are automorphism partitions so that any match between nodes in matching partitions is valid. If this assumption is invalid, then Gemini may, in its arbitrary choice of two nodes, pick nodes that do not match and then erroneously conclude that the circuits are different. If this happens, Gemini will throw up its hands and refuse to conclude anything about the circuits. The user must then use the equivalence file to remove the symmetry causing the problem. In the memory example, this can be done by binding the address inputs and the data outputs. Although removing symmetry is not often required, it can speed up the execution time.

FINDING DIFFERENCES
When two circuits are different, Gemini attempts to pinpoint the source of the difference. This is a very hard problem in general, and sometimes Gemini will not give very accurate feedback, especially if there are many differences or if there is a lot of symmetry. Here are some hints on how to proceed in this situation.

1.  Don't try to use Gemini if the size of the two circuits differ by more than a few (~ 1%) nodes.

2.  If node names are easily decipherable, generate a dictionary file to find nodes that have been mis-matched in error. Such nodes can then be bound correctly using the equivalence file.

3.  Use an equivalence file to give Gemini an anchor from which to work. This file can be derived from the dictionary file. The equivalence file is very important when the circuits contain substantial symmetry.

4.  Sometimes it is useful to turn off the local matching algorithm with the -m option and see if a different set of discrepancies are flagged. This may give a hint as to the problem.

SEE ALSO
     The Gemini User's Manual

AUTHOR
     Carl Ebeling (Northwest LIS, University of Washington)

BUGS
     The Gemini file format is not actively supported.
     Gemini will sometimes think that isomorphic circuits are
        different because it does not backtrack on the guess it makes.
     Old versions of Gemini have been known to think that different circuits
        were isomorphic. The -E/-D checking method described above
    can be used to doublecheck.
     Discrepancies between circuits are sometimes not pinpointed well enough.