ILP-based optimization of sequential circuits for low power

ABSTRACT

The power consumption of a sequential circuit can be reduced by decomposing it into subcircuits which can be turned off when inactive. Power can also be reduced by careful state encoding. Modeling a given circuit as a finite-state machine, we formulate its decomposition into submachines as an integer linear programming (ILP) problem, and automatically generate the ILP model with power minimization as the objective. A simple, but powerful state encoding method is used for the submachines to further reduce power consumption. We present experimental results which show that circuits designed by our approach consume 30% to 90% less power than conventional circuits.

REFERENCES

• 1: L. Benini, G. De Micheli, and F. Vermulen, "Finite State Machine Partitioning for Low Power ", Proc. International Symposium on Circuits and Systems, 1998, pp. 5--8.
• 2: Sue-Hong Chow , Yi-Cheng Ho , TingTing Hwang , C. L. Liu, Low power realization of finite state machines—a decomposition approach, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.3, p.315-340, July 1996 [doi>10.1145/234860.234862]
• 3: Collaborative Benchmarking Lab., North Carolina State Univ., http://www.cbl.ncsu.edu/benchmarks.
• 4: S. Devadas, et al., "MUSTANG: State Assignment of Finite State Machines Targeting Multilevel Logic Implementations ", IEEE Trans. on CAD, vol. 7, 1988, pp. 1290--1300.
• 5: ILOG cplex webpage. http://www.ilog.com/products/cplex/.
• 6: Harry R. Lewis , Christos H. Papadimitriou , Christos Papadimitriou, Elements of the Theory of Computation, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 7: E. Macii, M. Pedram, and F. Somenzi, "High-Level Power Modeling, Estimation, and Optimization ", IEEE Trans. on CAD, vol. 17, 1998, pp. 1061--1079.
• 8: José C. Monteiro , Arlindo L. Oliveira, Finite state machine decomposition for low power, Proceedings of the 35th annual conference on Design automation, p.758-763, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277235]
• 9: José C. Monteiro , Arlindo L. Oliveira, FSM decomposition by direct circuit manipulation applied to low power design, Proceedings of the 2000 conference on Asia South Pacific design automation, p.351-358, January 2000, Yokohama, Japan [doi>10.1145/368434.368678]
• 10: E. Olson and S. Kang, "Low-Power State Assignment for Finite State Machines ", Proc. International Symposium on Low Power Design, 1994, pp. 63--68.
• 11: A. Papoulis, Probability, Random Variables, and Stochastic Processes, 2 nd Edition, New York: McGraw-Hill, 1984.
• 12: 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]
• 13: K. Roy and S. Prasad, "Circuit Activity Based Logic Synthesis for Low Power Reliable Operations ", IEEE Trans. on VLSI, vol. 1, 1993, pp. 503--513.
• 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: Synopsys, Design Analyzer data sheet, http://www.synopsys.com/products/logic/design_compiler.html.
• 16: C. Y. Tsui, M. Pedram, and A. Despain, "Low-Power State Assignment Targeting Two and Multilevel Implementations ", IEEE Trans. on CAD, vol. 17, 1998, pp. 1281--1291.
• 17: T. Villa and A. Sangiovanni-Vincentelli, "NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementation ", IEEE Trans. on CAD, vol. 9, 1990, pp. 905--924.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Experimentation

Keywords:
decomposition, finite-state machine, integer linear programming, low power