SubGemini: Identifying SubCircuits using a Fast Subgraph Isomorphism Algorithm

The problem of finding subcircuits in a larger circuit arises in many contexts in computer-aided design. This is a problem currently solved using ad hoc techniques that rely on the circuit technology and implementation details. For example, channel graphs and signal flow are often used to extract simple gates from a transistor layout. Such techniques, however, do not generalize to different subcircuit structures and do not transfer to other technologies. We present a technology-independent algorithm for this problem based on a solution to the subgraph isomorphism problem. Although this problem is known to be NP-complete, our solution is very fast in practice for real circuits. We describe the algorithm, which uses an extension of the graph partitioning algorithm used by Gemini [3] for graph isomorphism, and present experimental results that show that the typical running time for large CMOS circuits is approximately linear in the total number of devices within the subcircuits being matched.