Smart Heuristics for Maximum Common Subgraph Sub-Estimation in Large Digital Circuits

Identifying shared sub-circuits in digital designs is fundamental to synthesis, similarity analysis, simulation, and verification. This paper presents a novel heuristic algorithm for the search of sub-estimation of the Maximum Common Subgraph (MCS) in large, sparse graphs derived from circuits. We represent circuits by converting logic gates and net wires into labeled nodes and their interconnections into directed edges, resulting in typically massive but very sparse graphs. Our algorithm refines the acclaimed McSplit-DAL framework by incorporating neighborhood information to improve the initial assessment of node similarity. This proactive measure reduces the necessity for extensive Domain Action Learning (DAL) feedback, enhancing both computational efficiency and precision. Furthermore, a more compact graph representation allows us to tackle larger circuit analyses. We validate these techniques on random and on contemporary circuit designs, such as RISC-V cores. Extensive experiments confirm our algorithm's effectiveness in pinpointing significant common substructures, showcasing its practical value for real-world digital circuit design and validation tasks on large-scale graphs.