Presentation
Cost-Based Partial Subgraph Matching for Circuit Pattern Recognition
DescriptionIdentifying recurring sub-circuits within large transistor-level designs is a common requirement in circuit analysis and verification. Traditional approaches rely on exact subgraph isomorphism, requiring identical structure and attributes between a pattern and a design. However, real designs often include small structural variations introduced by incremental changes, optimizations, or renaming, causing exact matching methods to miss relevant instances and increasing manual analysis effort.
This work presents a scalable framework for partial subgraph matching that quantifies structural similarity rather than enforcing exact equivalence. Circuits are represented as attributed graphs, and matching is formulated as an injective optimization problem using a cost-based graph edit distance. The cost function captures label mismatches, unmatched nodes, and missing or extra edges, enabling fine-grained assessment of near-miss matches. To address the computational complexity of partial matching, the framework combines biased candidate subgraph sampling with an efficient approximation strategy based on greedy initialization and iterative refinement.
The approach produces ranked candidate matches along with detailed, interpretable difference reports that highlight structural deviations between circuits. Experimental results demonstrate predictable runtime scaling with candidate budget and consistent behavior across a range of circuit patterns. The framework also establishes a foundation for automated tuning of cost parameters and learning-based candidate filtering.
This work presents a scalable framework for partial subgraph matching that quantifies structural similarity rather than enforcing exact equivalence. Circuits are represented as attributed graphs, and matching is formulated as an injective optimization problem using a cost-based graph edit distance. The cost function captures label mismatches, unmatched nodes, and missing or extra edges, enabling fine-grained assessment of near-miss matches. To address the computational complexity of partial matching, the framework combines biased candidate subgraph sampling with an efficient approximation strategy based on greedy initialization and iterative refinement.
The approach produces ranked candidate matches along with detailed, interpretable difference reports that highlight structural deviations between circuits. Experimental results demonstrate predictable runtime scaling with candidate budget and consistent behavior across a range of circuit patterns. The framework also establishes a foundation for automated tuning of cost parameters and learning-based candidate filtering.
Event Type
Engineering Poster Gladiator
TimeMonday, July 275:22pm - 5:30pm PDT
LocationDAC Pavilion, Exhibit Floor