Theoretical bounds for switching activity analysis in finite-state machines

ABSTRACT

The objective of this paper is to provide lower and upper bounds for the switching activity on the state lines in Finite State Machines (FSMs). Using a Markov chain model for the behavior of the states of the FSM, we derive theoretical bounds for the average Hamming distance on the state lines which are valid irrespective of the state encoding used in the final implementation. Such lower and upper bounds, in addition to providing a target for any state assignment algorithm, can also be used as parameters in a high-level model of power, and thus provide an early indication about the performance limits of the target FSM. Experimental results obtained for the mcnc'91 benchmark suite show that our bounds are tighter than the bounds reported previously by other researchers and can be effectively used in a high-level power estimation framework.

REFERENCES

• 1: Massoud Pedram, Power minimization in IC design: principles and applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.3-56, Jan. 1996 [doi>10.1145/225871.225877]
• 2: Kaushik Roy , Sharat Prasad, SYCLOP: Synthesis of CMOS Logic for Low Power Applications, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.464-467, October 11-14, 1992
• 3: Chi-Ying Tsui , Massoud Pedram , Chih-Ang Chen , Alvin M. Despain, Low power state assignment targeting two-and multi-level logic implementations, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.82-87, November 06-10, 1994, San Jose, California, United States
• 4: L. Benini and G. De Micheli, 'State Assignment for Low Power Dissipation', in IEEE Journal of Solid State Circuits, vol.30, no.3, 1995.
• 5: Gary D. Hachtel , Mariano Hermida , Abelardo Pardo , Massimo Poncino , Fabio Somenzi, Re-encoding sequential circuits to reduce power dissipation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.70-73, November 06-10, 1994, San Jose, California, United States
• 6: Balakrishna Kumthekar , In-Ho Moon , Fabio Somenzi, A symbolic algorithm for low-power sequential synthesis, Proceedings of the 1997 international symposium on Low power electronics and design, p.56-61, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263283]
• 7: Mircea R. Stan , Wayne P. Burleson, Bus-invert coding for low-power I/O, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.1, p.49-58, March 1995 [doi>10.1109/92.365453]
• 8: Ching-Long Su , Chi-Ying Tsui , Alvin M. Despain, Saving Power in the Control Path of Embedded Processors, IEEE Design & Test, v.11 n.4, p.24-30, October 1994 [doi>10.1109/54.329448]
• 9: Akhilesh Tyagi, Entropic bounds on FSM switching, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.456-464, Dec. 1997 [doi>10.1109/92.645072]
• 10: Sumant Ramprasad , Naresh R. Shanbhag , Ibrahim N. Hajj, Achievable bounds on signal transition activity, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.126-129, November 09-13, 1997, San Jose, California, United States
• 11: G. Hachtel, E. Macii, A. Pardo, and E Somenzi, 'Markovian Analysis of Large Finite State Machines,' in IEEE Trans. on CAD of Integrated Circuits, vol. 15, no. 12, Dec. 1996.
• 12: D. Marculescu , R. Marculescu , M. Pedram, Trace-driven steady-state probability estimation in FSMs with application to power estimation, Proceedings of the conference on Design, automation and test in Europe, p.774-781, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 13: D. Marculescu, R. Marculescu, and M. Pedram, 'Information Theoretic Measures for Power Analysis,' in IEEE Trans. on CAD of Integrated Circuits, vol. 15, no.6, June 1996.
• 14: Paul E. Landman , Jan M. Rabaey, Activity-sensitive architectural power analysis for the control path, Proceedings of the 1995 international symposium on Low power design, p.93-98, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224098]
• 15: Mahadevamurty Nemani , Farid N. Najm, High-level area and power estimation for VLSI circuits, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.114-119, November 09-13, 1997, San Jose, California, United States
• 16: F. Ferrandi , F. Fummi , E. Macii , M. Poncino , D. Sciuto, Power estimation of behavioral descriptions, Proceedings of the conference on Design, automation and test in Europe, p.762-766, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 17: G. De Micheli, R.K. Brayton, and A. Sangiovanni-Vincentelli, 'Optimal State Assignment for Finite State Machines,' in IEEE Trans. on CAD of Integrated Circuits, vol.4, no.7, July 1985.
• 18: T. Villa and A. Sangiovanni-Vincentelli, 'NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementation,' in IEEE Trans. on CAD of Integrated Circuits, vol.9, no.9, Sept. 1990.
• 19: A. Tyagi, Personal communication, Feb. 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

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

General Terms:
Design, Experimentation, Measurement, Performance, Theory