High Performance Subcircut Recognition Using a New Ptobabilistic Circuit Labeling Algorithm
Nikolay Rubanov · International Conference on Artificial Intelligence · 2002
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. In this paper 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 discriminate properties of the LA allow combining it with an optimization based graph recognition technique. The experimental results show that hte new subcircuit recognition method recognizes all the subcircuit instances about an order of magnitude faster than the search algorithms.