Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits—A Review
Source abstract
Abstract
Methods for reducing power consumption in circuits of finite state machines (FSMs) are discussed in this review. The review outlines the main approaches to solving this problem that have been developed over the last 40 years. The main sources of power dissipation in CMOS circuits are shown; the static and dynamic components of this phenomenon are analyzed. The power consumption saving can be achieved by using coarse-grained methods common to all digital systems. These methods are based on voltage or/and clock frequency scaling. The review shows the main structural diagrams generated by the use of these methods when optimizing the power characteristics of FSM circuits. Also, there are various known fine-grained methods taking into account the specifics of both FSMs and logic elements used. Three groups of the fine-grained methods targeting FPGA-based FSM circuits are analyzed. These groups include clock gating, state assignment, and replacing look-up table (LUT) elements by embedded memory blocks (EMBs). The clock gating involves a separate or joint use of such approaches as the (1) decomposition of FSM inputs and (2) disabling FSM inputs. The aim of the power-saving state assignment is to reduce the switching activity of a resulting FSM circuit. The replacement of LUTs by EMBs allows a reduction in the power consumption due to a decrease in the number of FSM circuit elements and their interconnections. We hope that the review will help experts to use known methods and develop new ones for reducing power consumption. We think that a good knowledge and understanding of existing methods of reducing power consumption is a prerequisite for the development of new, more effective methods to solve this very important problem. Although the methods considered are mainly aimed at FPGA-based FSMs, they can be modified, if necessary, and used for the power consumption optimization of FSM circuits implemented with other logic elements.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Low-power high-performance VLSI design · Parallel Computing and Optimization Techniques · VLSI and FPGA Design Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Institute of Metrology, Electronics and Computer Science, University of Zielona Gora, ul. Licealna 9, 65-417 Zielona Gora, Poland
Department of Infocommunications, Kharkov National University of Radio Electronics, 61000 Kharkov, Ukraine
Department of Technology, The Jacob of Paradies University, ul. Teatralna 25, 66-400 Gorzow Wielkopolski, Poland
References (100+)
Show source-provided references
1. Kharchenko, V., Kondratenko, Y., and Kacprzyk, J. (2019). Green IT Engineering: Social, Business and Industrial Applications, Springer International Publishing.10.1007/978-3-030-00253-4 ↗
2. Microprogram control unit as composition of automate with programmable and hardwired logic
3. Monteiro, J.C. (1999, January 2). Power Optimization Using Dynamic Power Management. Proceedings of the XIIth Conference on Integrated Circuits and Systems Design, Natal, Brazil.
4. De Micheli, G. (1994). Synthesis and Optimization of Digital Circuits, McGraw–Hill.
5. Baillieul, J., and Samad, T. (2015). Encyclopedia of Systems and Control, Springer.10.1007/978-1-4471-5058-9 ↗
6. Baranov, S. (2008). Logic and System Design of Digital Systems, TUT Press.
7. Minns, P., and Elliot, I. (2008). FSM-Based Digital Design Using Verilog HDL, John Wiley and Sons.10.1002/9780470987629 ↗
8. Czerwinski, R., and Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer. Lecture notes in electrical engineering.10.1007/978-3-642-36166-1 ↗
9. Sklyarov, V., Skliarova, I., Barkalov, A., and Titarenko, L. (2014). Synthesis and Optimization of FPGA-Based Systems, Springer International Publishing. Lecture notes in electrical engineering.10.1007/978-3-319-04708-9 ↗
10. Logic Synthesis for FPGAs Based on Cutting of BDD10.1016/j.micpro.2017.06.010 ↗
11. A Technology Mapping of FSMs Based on a Graph of Excitations and Outputs10.1109/ACCESS.2019.2895206 ↗
12. Methods of Improving Time Efficiency of Decomposition Dedicated at FPGA Structures and Using BDD in the Process of Cyber-Physical Synthesis10.1109/ACCESS.2019.2898230 ↗
13. Area-oriented technology mapping for LUT-based logic blocks10.1515/amcs-2017-0015 ↗
14. Barkalov, O., Titarenko, L., and Mazurkiewicz, M. (2019). Foundations of Embedded Systems, Springer International Publishing. Studies in Systems, Decision and Control.10.1007/978-3-030-11961-4 ↗
15. Arora, M. (2016). Embedded System Design: Introduction to SoC System Architecture, Learning Bytes Publishing.
16. Jimenez, J.J., Trojman, L., and Procel, L.M. (2019, January 11–15). Power and Area Reduction of MD5 based on Cryptoprocessor Using novel approach of Internal Counters on the Finite State Machine. Proceedings of the 2019 IEEE Fourth Ecuador Technical Chapters Meeting (ETCM), Guayaquil, Ecuador.10.1109/ETCM48019.2019.9014878 ↗
17. Stochastic neural computation. I. Computational elements10.1109/12.954505 ↗
18. VLSI Implementation of Deep Neural Network Using Integral Stochastic Computing10.1109/TVLSI.2017.2654298 ↗
19. Logical Computation on Stochastic Bit Streams with Linear Finite-State Machines10.1109/TC.2012.231 ↗
20. Fully-Parallel Area-Efficient Deep Neural Network Design Using Stochastic Computing
21. TR-FSM: Transition-Based Reconfigurable Finite State Machine10.1145/2000832.2000835 ↗
22. FPGA Implementation of Reconfigurable Finite State Machine with Input Multiplexing Architecture Using Hungarian Method10.1155/2018/6831901 ↗
23. (2024, January 01). Altera. Available online: http://www.altera.com.
24. (2024, January 01). Atmel. Available online: http://www.atmel.com.
25. (2024, January 01). Xilinx. Available online: http://www.xilinx.com.
26. Advanced Features and Industrial Applications of FPGAs—A Review10.1109/TII.2015.2431223 ↗
27. FPGA Design Methodology for Industrial Control Systems—A Review10.1109/TIE.2007.898281 ↗
28. Rabaey, J. (2009). Low Power Design Essentials, Springer. Integrated Circuits and Systems.10.1007/978-0-387-71713-5 ↗
29. Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer Academic Publishers.10.1007/978-1-4615-2692-6 ↗
30. Gajski, D. (1997). Principles of Digital Design, Prentice-Hall International. Prentice-Hall International Editions.
31. Strategy of logic synthesis using MTBDD dedicated to FPGA10.1016/j.vlsi.2018.02.009 ↗
32. Brayton, R., and Mishchenko, A. (2010, January 15–19). ABC: An academic industrial-strength verification tool. Proceedings of the Computer Aided Verification, Edinburgh, UK.10.1007/978-3-642-14295-6_5 ↗
33. A method for synthesizing sequential circuits10.1002/j.1538-7305.1955.tb03788.x ↗
34. Moore, E.F. (1956). Automata Studies. (AM-34), Princeton University Press.
35. Glushkov, V. (1965). Synthesis of Digital Automata, Fizmatgiz. FTD-MT, Translation Division, Foreign Technology Division.
36. Sentowich, E., Singh, K., Lavango, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., P, P.S., Bryton, R., and Sangiovanni-Vincentelli, A. (1992). SIS: A System for Sequential Circuit Synthesis, University of California. Technical report.
37. (2024, January 01). ABC System. Available online: https://people.eecs.berkeley.edu/~alanmi/abc/.
38. Baranov, S., and Skliarov, V. (1986). Digital Devices with Programmable LSIs with Matrix Structure, Radio and Sviaz. (In Russian).
39. Skliarov, V. (1984). Synthesis of Automata with Matrix LSIs, Nauka i Technika. (In Russian).
40. Grout, I. (2011). Digital Systems Design with FPGAs and CPLDs, Elsevier Science.
41. Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers.10.1007/978-1-4757-3393-8 ↗
42. Dahl, O.J., Dijkstra, E.W., and Hoare, C.A.R. (1972). Structured Programming, Academic Press Ltd.
43. Feng, W., Greene, J., and Mishchenko, A. (2018, January 25–27). Improving FPGA Performance with a S44 LUT Structure. Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, New York, NY, USA. FPGA ’18.10.1145/3174243.3174272 ↗
44. Kilts, S. (2007). Advanced FPGA Design: Architecture, Implementation, and Optimization, Wiley-IEEE Press.10.1002/9780470127896 ↗
45. Barkalov, A., Titarenko, L., Kołopieńczyk, M., Mielcarek, K., and Bazydło, G. (2015). Logic Synthesis for FPGA-Based Finite State Machines; Studies in Systems, Decision and Control, Springer International Publishing.10.1007/978-3-319-24202-6 ↗
46. Tiwari, A., and Tomko, K. (2004, January 16–20). Saving power by mapping finite-state machines into Embedded Memory Blocks in FPGAs. Proceedings of the Conference on Design, Automation and Test in Europe, Paris, France.
47. Kołopieńczyk, M., Barkalov, A., and Titarenko, L. (2014, January 16–18). Hardware reduction for RAM-based Moore FSMs. Proceedings of the 7th International Conference on Human System Interactions—HSI 2014, Costa da Caparica, Portugal.10.1109/HSI.2014.6860485 ↗
48. Design of EMB-Based Moore FSMs
49. Finite State Machines With Input Multiplexing: A Performance Study10.1109/TCAD.2015.2406859 ↗
50. Garcia-Vargas, I., Senhadji-Navarro, R., Jiménez-Moreno, G., Civit-Balcells, A., and Guerra-Gutierrez, P. (2007, January 4–7). ROM-based finite state machine implementation in low cost FPGAs. Proceedings of the IEEE International Symposium on Industrial Electronics ISIE 2007, Vigo, Spain.10.1109/ISIE.2007.4374972 ↗
51. High-Speed and Area-Efficient Reconfigurable Multiplexer Bank for RAM-Based Finite State Machine Implementations10.1142/S0218126615501017 ↗
52. High-Performance Architecture for Binary-Tree-Based Finite State Machines10.1109/TCAD.2017.2731678 ↗
53. ROM-based FSM implementation using input multiplexing in FPGA devices10.1049/el:20046007 ↗
54. Sklyarov, V. (2000, January 27–30). Synthesis and Implementation of RAM-based Finite State Machines in FPGAs. Proceedings of the Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing, Villach, Austria.10.1007/3-540-44614-1_76 ↗
55. An application of functional decomposition in ROM-based FSM implementation in FPGA devices10.1016/j.sysarc.2004.07.004 ↗
56. Adamski, M., Barkalov, A., and Węgrzyn, M. (2011). Design of Digital Systems and Devices. LNEE 79, Springer.10.1007/978-3-642-17545-9 ↗
57. Rafla, N.I., and Gauba, I. (2010, January 1–4). A reconfigurable pattern matching hardware implementation using on-chip RAM-based FSM. Proceedings of the 2010 53rd IEEE International Midwest Symposium on Circuits and Systems, Seattle, WA, USA.10.1109/MWSCAS.2010.5548558 ↗
58. Maxfield, C. (2004). The Design Warrior’s Guide to FPGAs, Academic Press, Inc.
59. Maxfield, C. (2008). FPGAs: Instant Access, Elsevier.
60. Smith, M. (1997). Application-Specific Integrated Circuits, Addison-Wesley.
61. Short-circuit dissipation of static CMOS circuitry and its impact on the design of buffer circuits10.1109/JSSC.1984.1052168 ↗
62. Butts, J.A., and Sohi, G.S. (2000, January 1). A static power model for architects. Proceedings of the 33rd Annual ACM/IEEE International Symposium on Microarchitecture. Association for Computing Machinery, Monterey, CA, USA.10.1145/360128.360148 ↗
63. Power Estimation Methods for Sequential Logic Circuits10.1109/92.406998 ↗
64. Gajski, D.D., Abdi, S., Gerstlauer, A., and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, Springer Publishing Company, Incorporated. [1st ed.].10.1007/978-1-4419-0504-8 ↗
65. Project GreenLight: Optimizing Cyber-infrastructure for a Carbon-Constrained World10.1109/MC.2010.20 ↗
66. (2011). 2011 International Technology Roadmap for Semiconductors (ITRS), Semiconductor Industry Association. Technical report.
67. Ashford, L., and Sanjit Arunkumar, S. (2016). Introduction to Embedded Systems: A Cyber-Physical Systems Approach, The MIT Press. [2nd ed.].
68. Marwedel, P. (2018). Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things, Springer International Publishing. [3rd ed.].
69. A survey of techniques for improving energy efficiency in embedded computing systems10.1504/IJCAET.2014.065419 ↗
70. Automatic FSM Synthesis for Low-power Mixed Synchronous/Asynchronous Implementation10.1155/2001/27496 ↗
71. Synchronous FSM Design Methodology for Low Power Smart Sensors and RFID Devices
72. Shabel, J. (2005). Analysis of Clock Trees, SNUG. Technical report.
73. Monteiro, J.C., and Oliveira, A.L. (1998, January 15–19). Finite State Machine Decomposition for Low Power. Proceedings of the 35th Annual Design Automation Conference, San Francisco, CA, USA.10.1145/277044.277235 ↗
74. Precomputation-based sequential logic optimization for low power10.1109/92.335011 ↗
75. Knuth, D.E. (1969). The Art of Computer Programming, Volume II: Seminumerical Algorithms, Addison-Wesley.
76. Automatic synthesis of low-power gated-clock finite-state machines10.1109/43.503933 ↗
77. Low Power Realization of Finite State Machines—a Decomposition Approach10.1145/234860.234862 ↗
78. Symbolic analysis of a decomposition of information processing machines10.1016/S0019-9958(60)90744-0 ↗
79. Decomposition and factorization of sequential finite state machines10.1109/43.41505 ↗
80. Decompositional Design of Automata Based on PLA with Memory
81. A Hierarchical Model of the Interaction of Microprogrammed Automata
82. McElvain, K. (2018, February 01). LGSynth93 Benchmark Set. Version 4.0. Available online: https://people.engr.ncsu.edu/brglez/CBL/benchmarks/LGSynth93/LGSynth93.tar.
83. Bacchetta, P., Daldos, L., Sciuto, D., and Silvano, C. (2000, January 28–31). Low-power state assignment techniques for finite state machines. Proceedings of the 2000 IEEE International Symposium on Circuits and Systems (ISCAS’2000), Geneva, Switzerland.
84. Agrawal, R., Borowczak, M., and Vemuri, R. (2019, January 5–9). A State Encoding Methodology for Side-Channel Security vs. Power Trade-off Exploration. Proceedings of the 2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID), Delhi, India.10.1109/VLSID.2019.00031 ↗
85. State assignment for low power dissipation10.1109/4.364440 ↗
86. Designing low-power circuits: Practical recipes10.1109/7384.928306 ↗
87. Area conscious state assignment with flip-flop and output polarity selection for finite state machines synthesis—A genetic algorithm10.1093/comjnl/bxh099 ↗
88. Chattopadhyay, S., and Chaudhuri, P. (1998, January 4–7). Genetic algorithm based approach for integrated state assignment and flipflop selection in finite state machines synthesis. Proceedings of the IEEE International Conference on VLSI Design, Chennai, India.
89. Chen, C., Zhao, J., and Ahmadi, M. (2003, January 25–28). A semi-Gray encoding algorithm for low-power state assignment. Proceedings of the 2003 International Symposium on Circuits and Systems, IEEE, Bangkok, Thailand.
90. MUSTANG: State assignment of finite state machines targeting multilevel logic implementation10.1109/43.16807 ↗
91. MUSE: A multilevel symbolic encoding algorithm for state assignment10.1109/43.62789 ↗
92. A Finite State Machine-based Fault Tolerance Technique with Enhanced Area and Power of Synthesized Sequential Circuits10.1049/iet-cdt.2016.0085 ↗
93. El-Maleh, A., Sait, S., and Khan, F. (2006, January 21–24). Finite state machine state assignment for area and power minimization. Proceedings of the 2006 IEEE International Symposium on Circuits and Systems, IEEE, Kos, Greece.
94. A probabilistic pairwise swap search state assignment algorithm for sequential circuit optimization10.1016/j.vlsi.2016.08.001 ↗
95. Minimization of power consumption of finite state machines by splitting their internal states10.1134/S1064230715030090 ↗
96. Gupta, B., Narayanan, H., and Desai, M. (1999, January 7–10). A state assignment scheme targeting performance and area. Proceedings of the 12th International Conference on VLSI Design, Goa, India.10.1109/ICVD.1999.745185 ↗
97. Hu, H., Xue, H., and Bian, J. (2003, January 21–24). A heuristic state assignment algorithm targeting area. Proceedings of the 5th International Conference on ASIC, Beijing, China.
98. ALTO: An Iterative Area/Performance Algorithms for LUT-based FPGA Technology Mapping10.1109/92.863618 ↗
99. Iranli, A., Rezvani, P., and Pedram, M. (2003, January 21–24). Low power synthesis of finite state machines with mixed D and T flip-flops. Proceedings of the Asia and South Pacific–DAC, Kitakyushu, Japan.10.1145/1119772.1119950 ↗
100. Kubatova, H., and Becvar, M. (2002, January 19–20). FEL–Code: FSM Internal State Encoding Method. Proceedings of the 5th International Workshop on Boolean Problems, Freiberg, Germany.