An efficient subcircuit recognition using the nonlinear graph matching

ABSTRACT

Subcircuit recognition (SR) is a problem of identifying all instances of a small subcircuit in a larger circuit. Despite recent progress toward the linear graph matching based SR algorithms, finding a large set of subcircuits in a multi-million circuit may be still prohibitively long for many IC CAD applications. In this paper we develop a new efficient SR method using a nonlinear graph matching strategy. Namely, our method employs an advanced nonlinear technique to minimize the objective function (OF) associated with the SR problem. Unlike the linear graph matching we don't approximate the OF by the first-order terms in its Taylor series expansion. In contrast, the second-order terms are exploited to form a set of nonlinear equations (SNE) that describe the net and device match probabilities. To solve the obtained SNE we use a nonlinear version of the Kaczmarz method (KM). We improve the KM efficiency by making two modifications in its updating scheme; this leads to fast and stable convergence of the SR process. The experimental results show that the new method is on average three times faster compared to the linear graph matching algorithms.

REFERENCES

• 1: Thomas S Chanak, Netlist Processing for Custom VLSI via Pattern Matching, Stanford University, Stanford, CA, 1995
• 2: Miles Ohlrich , Carl Ebeling , Eka Ginting , Lisa Sather, SubGemini: identifying subcircuits using a fast subgraph isomorphism algorithm, Proceedings of the 30th international conference on Design automation, p.31-37, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164556]
• 3: Pelz, G., Röttcher, U. Pattern Matching and Refinement Hybrid Approach to Circuit Comparison. IEEE Trans., V. CAD-10, N. 2, 1994, 264--276.
• 4: Kim, W., Shin, H. Hierarchical LVS based on hierarchy rebuilding. Proceedings of the ASP-DAC Conference, 1998, 379-384.
• 5: Rangarajan, A., Yuille, A., Mjolsness, E. A Convergence Proof for the Softassign Quadratic Assignment Algorithm. Advances in NIP Systems 9, 1997, MIT Press, Cambridge, MA, 620--626.
• 6: Rubanov, N. SubIslands: The Probabilistic Match Assignment Algorithm for Subcircuit Recognition. IEEE Trans., V. CAD-22, N. 1, 2003, 26--38.
• 7: Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
• 8: Natterer, F., Numerical Solution of Bilinear Inverse Problems. Preprint, Numeric Department, Westfalische-Wilhelms University Muenster, Germany, 1996.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Verification

Keywords:
design verification, graph matching, subcircuit recognition