The Gemini Netlist Comparison Project

Gemini

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: The Gemini program is available via anonymous ftp. For details, contact larry@cs.washington.edu

SubGemini

SubGemini is a program that uses a general subgraph isomorphism algorithm to find subcircuits in a larger circuit. While the subgraph isomorphism problem is known to be NP-complete in general, the SubGemini algorithm can efficiently solve this problem for most circuits encountered in practice by making use of their inherent structure. The SubGemini program exists only as a prototype proof-of-concept and thus is not generally available. Please contact us (ebeling@cs.washington.edu) if you have interest in obtaining the source code.

Gemini Publications

Any documents contained in this page are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
The Original Gemini Paper
Carl Ebeling and Ofer Zajicek. "Validating VLSI Circuit Layout by Wirelist Comparison," In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD-83) , pp. 172-173, September 1983.
An Extended Algorithm for Gemini Based on Local Matching
Carl Ebeling. "Gemini II: A Second Generation Layout Validation Tool," In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD-88), pp. 322-325, November 1988.
Abstract
Gemini is a circuit comparison program that is widely used to compare circuit layout against a specification. In this paper we describe recent extensions made to Gemini that make it faster, enable it to isolate errors better, and extend its domain of application. This has been done by changes to the labeling algorithm, extensions to the local matching algorithm, better handling of symmetrical circuits and the accommodation of series-connected transistors. GeminiII's algorithm is separated into global labeling and local matching phases. GeminiII dynamically switches between the two depending on the amount of local structure contained in the circuit, taking advantage of the speed of the local matching algorithm when possible and relying on the power of the more general algorithm when the simple algorithm fails. This blending of algorithms also allows differences between two circuits to be better contained so that defects can be pinpointed.
Postscript of document without figures is available.
An Algorithm for Finding Subcircuits in Large Circuits.
Miles Ohlrich, Carl Ebeling, Eka Ginting and Lisa Sather. "SubGemini: Identifying Subcircuits Using a Fast Subgraph Isomorphism Algorithm," In Proceedings of the 30th IEEE/ACM Design Automation Conference, June 1993.
Abstract
The task of identifying circuit components in large circuit graphs arises naturally in several contexts. The most common example is the extraction of gates from transistor netlists for gate-level simulation, but it is also used in comparing netlists hierarchically, and checking for questionable circuit structures in layout. This paper presents an efficient, technology-independent algorithm for performing this task. Efficiency is important because this task is typically used in a larger context such as a preprocessing step for simulation. Technology-independence allows the same algorithm to be used in many different contexts, including digital and analog circuits, MOS and bipolar technologies, and for circuit using varying levels of abstraction.

We have approached the general problem by treating it as an instance of the subgraph isomorphism problem. By solving the problem using a true subgraph isomorphism algorithm that assumes nothing about the underlying circuits, we achieve a true technology-independent solution. While the subgraph isomorphism problem is known to be NP-complete in general, the algorithm presented in this paper can efficiently solve this problem for most circuits encountered in practice by making use of the structure found in circuits.

This algorithm has been implemented in a program called SubGemini and has been applied to a wide variety of interesting subcircuit problems. We present results that give the running time for a range of different circuit types and sizes. We show that for most circuits the running time is linear in the size of the circuit graphs and the number of component instances to be found. As an example, all the RAM cells in a 16K bit static RAM can be identified in less than a minute on a Sparcstation 2.

[go back] RETURN TO UW CS&E HOMEPAGE

larry@cs.washington.edu