Estimation of state line statistics in sequential circuits

ABSTRACT

In this article, we present a simulation-based technique for estimation of signal statistics (switching activity and signal probability) at the flip-flop output nodes (state signals) of a general sequential circuit. Apart from providing an estimate of the power consumed by the flip-flops, this information is needed for calculating power in the combinational portion of the circuit. The statistics are computed by collecting samples obtained from fast RTL simulation of the circuit under input sequences that are either randomly generated or independently selected from user-specified pattern sets. An important advantage of this approach is that the desired accuracy can be specified up front by the user; with some approximation, the algorithm iterates until the specified accuracy is achieved. This approach has been implemented and tested on a number of sequential circuits and has been shown to handle very large sequential circuits that can not be handled by other existing methods, while using a reasonable amount of CPU time and memory (the circuit s38584.1, with 1426 flip-flops, can be analyzed in about 10 minutes).

REFERENCES

• 1: Brglez, F., Bryan, D., and Kozminski, K. 1989. Combinational profiles of sequential benchmark circuits. In Proceedings of the IEEE International Symposium on Circuits and Systems, 1929--1934.
• 2: Brodersen, R. W., Chandrakasan, A., and Sheng, S. 1991. Technologies for personal communications. In Proceedings of the 1991 Symposium on VLSI Circuits (Tokyo), 5--9.
• 3: Chi-Tsong Chen, One-Dimensional Digital Signal Processing, Marcel Dekker, Inc., New York, NY, 1979
• 4: Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Probabilistic analysis of large finite state machines, Proceedings of the 31st annual conference on Design automation, p.270-275, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196374]
• 5: Asad A. Ismaeel , Melvin A. Breuer, The probability of error detection in sequential circuits using random test vectors, Journal of Electronic Testing: Theory and Applications, v.1 n.4, p.245-256, Jan. 1991 [doi>10.1007/BF00136314]
• 6: Miller, I. R. and Johnson, R. 1990. Probability and Statistics for Engineers, 4th ed., Prentice-Hall, Englewood Cliffs, N.J.
• 7: José Monteiro , Srinivas Devadas , Bill Lin, A methodology for efficient estimation of switching activity in sequential logic circuits, Proceedings of the 31st annual conference on Design automation, p.12-17, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196252]
• 8: Najm, F. 1993a. Statistical estimation of the signal probability in VLSI circuits. Tech. Rep. #UILU-ENG-93-2211, DAC-37, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign.
• 9: Najm, F. 1993b. Transition density : A new measure of activity in digital circuits. IEEE Trans. Comput. Aided Des. 12, 2 (Feb.), 310--323.
• 10: Farid N. Najm, A survey of power estimation techniques in VLSI circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.446-455, Dec. 1994 [doi>10.1109/92.335013]
• 11: Farid N. Najm , Shashank Goel , Ibrahim N. Hajj, Power estimation in sequential circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.635-640, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217602]
• 12: Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 13: Papoulis, A. 1984. Probability, Random Variables, and Stochastic Processes, 2nd ed., McGraw-Hill, New York.
• 14: Chi-Ying Tsui , Massoud Pedram , Alvin M. Despain, Exact and approximate methods for calculating signal and transition probabilities in FSMs, Proceedings of the 31st annual conference on Design automation, p.18-23, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196255]
• 15: Michael G. Xakellis , Farid N. Najm, Statistical estimation of the switching activity in digital circuits, Proceedings of the 31st annual conference on Design automation, p.728-733, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196628]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
Power estimation, finite-state machine, sequential circuit, signal probability, signal statistics, switching activity, transition density