SubIslands: the probabilistic match assignment algorithm for subcircuit recognition

The recognition of subcircuit instances in a larger circuit is widely used in the simulation, verification, and testing of integrated circuit computer-aided designs. Subcircuit recognition (SR) can be stated as a problem of finding images of a small model bipartite graph (BG) corresponding to a subcircuit in a large object BG corresponding to a circuit. The best-known SR algorithms are based on the search-oriented subgraph isomorphism methods. Unfortunately, these methods may require a long runtime for large and highly symmetrical circuits. The authors develop a new high-performance probabilistic recognition method for solving the SR problem. This method combines: 1) the graduated assignment matching technique; 2) two well-known concepts from pattern recognition theory, namely, the error propagation and the delayed decision making; and 3) an efficient probabilistic BG labeling algorithm. In contrast to the search-based algorithms, the new recognition method solves the SR problem as an optimization task and, as a consequence, allows extremely fast simultaneous finding of subcircuit images. The experimental results show that this approach recognizes all the subcircuit instances orders of magnitude faster than the search-oriented algorithms.