A statistical static timing analysis considering correlations between delays

ABSTRACT

In this paper, we present a new algorithm for the statistical static timing analysis of a CMOS combinatorial circuit, which can treat correlations of arrival times of input signals to a logic gate and correlations of switching delays in a logic gate. We model each switching delay by a normal distribution, and use a normal distribution of two stochastic variables with a coefficient of correlation for computing the distribution of output delay of a logic gate. Since the algorithm takes the correlation into account, the time complexity is O(n*m) in the worst-case, where n and m are the numbers of vertices and edges of the acyclic graph representing a given combinatorial circuit.

REFERENCES

• 1: H.-F. Jyu, S. Malik, S. Devadas, K.W. Keutzer, "Statistical timing analysis of combinatorial logic circuits," IEEE Trans. VLSI Systems, vol.1, no.2, pp.126-137, 1993
• 2: Rung-Bin Lin , Meng-Chiou Wu, A New Statistical Approach to Timing Analysis of VLSI Circuits, Proceedings of the Eleventh International Conference on VLSI Design: VLSI for Signal Processing, p.507, January 04-07, 1998
• 3: M.Berkelaar, "Statistical delay calculation, a linear time method," Proc. Int. Workshop on Timing Issues in the Specification and Synthesis of Digital Systems (TAU97), pp.15-24, 1997.
• 4: H. Matsunaga, D. Mizoguchi, H. Yasuura, "Estimation of combinatorial circuit delays using the distribution of CMOS gate delays," Proc. DA Symp. '99, pp.77-82, 1999. (in Japanese)
• 5: S. Tsukiyama, M. Tanaka, M. Fukui, "An estimation algorithm of the critical path delay for a combinatorial circuits," Proc. the 13th Workshop on Circuits and Systems in Karuizawa, pp.131-136, 2000. (in Japanese)
• 6: M.Hashimoto and H.Onodera, "A performance optimization method by gate resizing based on statistical static timing analysis," Proc. Workshop on Synthesis And System Integration of MIxed Technology (SASIMI 2000), pp.77-82, 1999.
• 7: E. T. A. F. Jacobs , M. R. C. M. Berkelaar, Gate sizing using a statistical delay model, Proceedings of the conference on Design, automation and test in Europe, p.283-291, March 27-30, 2000, Paris, France [doi>10.1145/343647.343782]
• 8: T. Tamai, S. Nishimoto, S. Tsukiyama, M. Tanaka, M. Fukui, "A layout optimization system of macrocells," Tech. Report of IEICE, VLD 99-128, pp.85-91, 2000. (in Japanese)
• 9: C.E. Clark, "The greatest of a finite set of random variables" Operations Research, vol.9, pp.145-152, 1961.
• 10: M. Kondo, H. Onodera, K. Tamaru, "MOSFET statistical modeling method using an intermediate model," Trans. of IEICE A, vol.J81-A, no.11, pp.1555-1563, 1998. (in Japanese)
• 11: Rony Kay , Lawrence Pileggi, PRIMO: probability interpretation of moments for delay calculation, Proceedings of the 35th annual conference on Design automation, p.463-468, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277172]
• 12: H.C. Chen and D.H. Du, "Path sensitization in critical path problem," IEEE Trans. Computer-Aided Design of ICs and Systems, vol.12, no.2, pp.196-207, 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Performance, Theory