High performance subcircuit recognition using a new probabilistic circuit labeling algorithm
Nikolay Rubanov · 2003
Recognition of subcircuit instances in a larger circuit is widely used in simulation and verification of IC CAD. Subcircuit recognition (SR) can be stated as a problem of finding images of a model bipartite graph (BG) corresponding to a subcircuit in an object BG corresponding to a circuit. The best-known SR algorithms are based on the search-oriented subgraph isomorphism methods. Unfortunately, the search methods may require exponential runtime for large and symmetrical circuits. We develop a high performance SR method based on a new efficient BG labeling algorithm (LA). This algorithm computes probabilistic labels for the vertices corresponding to devices and nets based on the exhaustive analysis of the non-local vertex surroundings. The high discriminative properties of the LA allow combining it with an optimization based graph recognition technique. The experimental results show that the new subcircuit recognition method recognizes all the subcircuit instances about an order of magnitude faster than the search algorithms.