Low power realization of finite state machines—a decomposition approach

ABSTRACT

We present in this article a new approach to the synthesis problem for finite state machines with the reduction of power dissipation as a design objective. A finite state machine is decomposed into a number of coupled submachines. Most of the time, only one of the submachines will be activated which, consequently, could lead to substantial savings in power consumption. The key steps in our approach are: (1) decomposition of a finite state machine into submachines so that there is a high probability that state transitions will be confined to the smaller of the submachines most of the time, and (2) synthesis of the coupled submachines to optimize the logic circuits. Experimental results confirmed that our approach produced very good results (in particular, for finite state machines with a large number of states.)

REFERENCES

• 1: Mazhar Alidina , José Monteiro , Srinivas Devadas , Abhijit Ghosh , Marios Papaefthymiou, Precomputation-based sequential logic optimization for low power, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.74-81, November 06-10, 1994, San Jose, California, United States
• 2: BENINI, L. AND DE MICHELI, G. 1995a. State assignment for low power dissipation. IEEE J. Solid State Circuits 30, 3 (March), 258-268.
• 3: Luca Benini , Giovanni De Micheli, Transformation and synthesis of FSMs for low-power gated-clock implementation, Proceedings of the 1995 international symposium on Low power design, p.21-26, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224086]
• 4: CHANDRAKASAN, A. P., SHENG, S., AND BRODERSEN, R.W. 1992. Low-power CMOS digital design. IEEE J. Solid-State Circuits 27, 4 (April), 473-484.
• 5: DEVADAS, S., MA, H., AND NEWTON, R. 1991. MUSTANG: State assignment of finite state machines targeting multilevel logic implementations. IEEE Trans. CAD (Dec.), 1290-1300.
• 6: DRESIG, F., LANCHES, P., RETTIG, O., AND BAITINGER, U.G. 1993. Simulation and reduction of CMOS power dissipation at logic level. In Proceedings of the EDAC'93 EURO-ASIC (Feb.), 341-346.
• 7: 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
• 8: Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
• 9: LIN, B. AND DE MAN, H. 1993. Low-power driven technology mapping under timing constraints. In Proceedings of ICCD'93 (Oct.), 421-427.
• 10: LIN, B. AND NEWTON, A.R. 1989. Synthesis of multiple level logic from symbolic high-level description language. In Proceedings of the IFIP International Conference on VLSI, 187-196.
• 11: PAPOULIS, A. 1984. Probability, Random Variables and Stochastic Processes. McGraw Hill, New York.
• 12: PRASAD, S. C. AND ROY, K. 1993. Circuit activity driven multilevel logic optimization for low power reliable operation. In Proceedings of the EDAC'93 EURO-ASIC (Feb.), 368-372.
• 13: 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
• 14: Ellen Sentovich , Kanwar Jit Singh , Cho W. Moon , Hamid Savoj , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Sequential Circuit Design Using Synthesis and Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.328-333, October 11-14, 1992
• 15: Vivek Tiwari , Pranav Ashar , Sharad Malik, Technology mapping for lower power, Proceedings of the 30th international conference on Design automation, p.74-79, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164581]
• 16: Chi-Ying Tsui , Massoud Pedram , Alvin M. Despain, Technology decomposition and mapping targeting low power dissipation, Proceedings of the 30th international conference on Design automation, p.68-73, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164577]
• 17: Wu, S.-S. 1996. State assignment for low power and high speed. M.S. thesis, Dept. of Computer Science, Tsing Hua University, Taiwan.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits
      B.6.3 Design Aids
          Subjects: Optimization

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

General Terms:
Design, Performance

Keywords:
decomposition of finite state machines, lower power design, state assignment