Interdependent latch setup/hold time characterization via Euler-Newton curve tracing on state-transition equations

ABSTRACT

Interdependent characterization of latch setup/hold times is a core component of techniques for pessimism reduction via Setup/Hold Interdependence Aware Static Timing Analysis (SHIA-STA) [1], [2]. We present an efficient and novel method for such characterization, by formulating the interdependent setup-hold time problem as an underdetermined nonlinear equation h(τs, τh) = 0, which we derive from the latch's state-transition function. We solve this equation numerically using a Moore-Penrose Newton method. Further, we use null-space information from the Newton's Jacobian matrix to efficiently find constant-clock-to-Q contours (in the setup/hold time plane), via an Euler-Newton curve tracing procedure. We validate the method on TSPC and C²MOS registers, obtaining speedups of more than 20 x over prior approaches while achieving superior accuracy. This speedup increases linearly with the precision with which curve tracing is desired. In view of the importance and large computational expense of latch characterization in industry today, the new technique represents a significant enabling technology for dramatically speeding up industrial timing closure flows.

REFERENCES

• 1: Emre Salman , Eby G. Friedman , Ali Dasdan , Feroze Taraporevala , Kayhan Kucukcakar, Pessimism Reduction In Static Timing Analysis Using Interdependent Setup and Hold Times, Proceedings of the 7th International Symposium on Quality Electronic Design, p.159-164, March 27-29, 2006 [doi>10.1109/ISQED.2006.100]
• 2: C. Amin C. Kashyap, K. Killpack. Personal Communications, 2006, 2007.
• 3: W. Rothig. Library Characterization and Modeling for 130 nm and 90 nm SOC Design. Proceedings of the IEEE International SOC Conference, pages 383--386, September 2003.
• 4: D. Patel. CHARMS: Characterization and Modeling System for Accurate Delay Prediction of ASIC Designs. Proceedings of the IEEE Custom Integrated Circuits Conference, pages 9.5.1--9.5.6, May 1990.
• 5: R. W. Phelps. Advanced Library Characterization for High-Performance ASIC. Proceedings of the IEEE Custom International ASIC conference, pages 15--3.1 - 15--3.4, September 1991.
• 6: Shweta Srivastava , Jaijeet Roychowdhury, Rapid and accurate latch characterization via direct Newton solution of setup/hold times, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 7: T. J. Aprille and T. N. Trick. Steady-State Analysis of Nonlinear Circuits with Periodic Inputs. Proc. IEEE, 60(1):108--114, January 1972.
• 8: S. Skelboe. Computation of The Periodic Steady-State Response of Nonlinear Networks by Extrapolation Methods. IEEE Trans. Ckts. Syst., CAS-27(3):161--175, March 1980.
• 9: Ricardo Telichevesky , Ken Kundert , Jacob White, Efficient AC and noise analysis of two-tone RF circuits, Proceedings of the 33rd annual conference on Design automation, p.292-297, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240572]
• 10: Eugene L. Allgower , Kurt Georg, Numerical continuation methods: an introduction, Springer-Verlag New York, Inc., New York, NY, 1990
• 11: K. Yamamura and M. Kiyoi. A Piecewise Linear Homotopy Method With the Use of the Newton Homotopy and Polyhedral Subdivision. Trans. IEICE, 73:140--148, 1990.
• 12: C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice Hall PTR, Upper Saddle River, NJ, 1971
• 13: Leon O. Chua , Paul Y. Lin, Computer-Aided Analysis of Electronic Circuits: Algorithms and Computational Techniques, Prentice Hall Professional Technical Reference, 1975
• 14: William H. Press , William T. Vetterling, Numerical Recipes in Pascal: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1989
• 15: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 16: Thomas L. Quarles. SPICE 3C.1 User's Guide. University of California, Berkeley, EECS Industrial Liaison Program, University of California, Berkeley California, 94720, April 1989.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

General Terms:
Algorithms

Keywords:
characterization, euler-newton, hold time, interdependence, setup time