Gemini is a program that compares two circuit netlists and reports whether they are exactly the same, pinpointing differences if there are any. Gemini is typically used to determine whether a VLSI circuit layout is correct by comparing the wirelist extracted from the layout to the specification wirelist. This is also know as LVS - layout vs. schematic. Gemini is a program based on a well-known graph isomorphism algorithm that is very efficient for comparing circuits encountered in practice. Gemini's running time is almost linear in the size of the circuits: about K*(N/1000)^1.07 seconds, where N is the number of transistors, and only slightly worse for very symmetric circuits. (K depends on your processor, but is substantially less than 1 for current workstations.) The latest version of Gemini has the following features:
- Circuit input is in standard sim format with an extension that allows user-defined devices. This allows Gemini to accomodate 4-terminal devices and technologies other than digital CMOS.
- Collapses series (chains) and parallel (fingers) transistors.
- Creates a Magic feedback file that marks differences in the layout itself.
Gemini is still widely used - a copy is available on request. Email gemini-netlist (at) cs.washington.edu
SubGemini was a follow-on project to Gemini that attacked the subgraph isomorphism problem for circuits. A pre-alpha version is available on request.