A High-Performance Subcircuit Recognition Method Based on the Nonlinear Graph Optimization

Subcircuit recognition (SR) is a problem of identifying instances of a small subcircuit in a larger circuit. Despite recent progress toward linear optimization-based SR algorithms, finding a large set of subcircuits in a multimillion transistor or gate-level netlist may still be too slow for many integrated-circuit computer-aided design applications. This paper describes a new high-performance method to identify subcircuits using a nonlinear graph optimization strategy. The method uses an advanced nonlinear technique to find a global minimum of the objective function associated with the SR problem. Unlike linear graph optimization, this method does not approximate the objective function by the first-order terms in its Taylor series expansion. In contrast, to increase the recognition rate, the second-order terms are exploited to form a set of nonlinear equations that describe the net and device match probabilities. Consequently, computing the match probabilities in the new approach is based on the nonlocal structure of connections between nets and devices. An iterative nonlinear version of the Kaczmarz method (KM) is used to solve the obtained set of nonlinear equations. The KM efficiency is improved by making an important modification in its updating scheme, which leads to fast and stable convergence of the recognition process. The experimental results show that the new method is on average three times faster than linear graph optimization algorithms such as the probabilistic match assignment algorithm