Reducing LUT Count for FPGA-Based Mealy FSMs
Source abstract
Abstract
Very often, digital systems include sequential blocks which can be represented using a model of Mealy finite state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and power consumption. The paper proposes a novel design method optimizing LUT counts of LUT-based Mealy FSMs. The method is based on simultaneous use of such methods of structural decomposition as the replacement of FSM inputs and encoding of the collections of outputs. The proposed method results in three-level logic circuits of Mealy FSMs. These circuits have regular systems of interconnections. An example of FSM synthesis with the proposed method is given. The experiments with standard benchmarks were conducted. The results of experiments show that the proposed approach leads to reducing the LUT counts from 12% to 59% in average compared with known methods of synthesis of single-level FSMs. Furthermore, our approach provides better LUT counts as compared to methods of synthesis of two-level FSMs (from 9% to 20%). This gain is accompanied by a small loss of FSM performance.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: VLSI and Analog Circuit Testing · Advanced Memory and Neural Computing · Radiation Effects in Electronics
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. Licealna 9, 65-417 Zielona Góra, Poland
Department of Mathematics and Information Technology, Vasyl’ Stus Donetsk National University, 21, 600-richya str., 21021 Vinnytsia, Ukraine
Department of Infocommunication Engineering, Faculty of Infocommunications, Kharkiv National University of Radio Electronics, Nauky avenue 14, 61166 Kharkiv, Ukraine
Department of Technology, The Jacob of Paradies University, ul. Teatralna 25, 66-400 Gorzów Wielkopolski, Poland
References (66)
Show source-provided references
1. Marwedel, P. (2018). Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things, Springer. [3rd ed.].10.1007/978-3-319-56045-8 ↗
2. Fault detection variants of the CloudBus protocol for IoT distributed embedded systems10.4316/AECE.2017.02001 ↗
3. Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw–Hill.
4. Bailliul, J., and Samad, T. (2015). Encyclopaedia of Systems and Control, Springer.10.1007/978-1-4471-5058-9 ↗
5. Baranov, S. (2008). Logic and System Design of Digital Systems, TUTPress.
6. Minns, P., and Elliot, I. (2008). FSM-Based Digital Design Using Verilog HDL, John Wiley and Sons.10.1002/9780470987629 ↗
7. Jiminez, J.J., Trojman, L., and Procel, L.-M. (2019, January 12–15). Power and area reduction of MD5 based on cryptoprocessors using novel approach of internal counters on the finite state machine. Proceedings of the IEEE Fourth Ecuador Technical Chapter Meeting (ETCM), Guayaquil, Ecuador.10.1109/ETCM48019.2019.9014878 ↗
8. Czerwinski, R., and Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer.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.10.1007/978-3-319-04708-9 ↗
10. (2020, July 24). Intel FPGAs and Programmable Devices. Available online: https://www.intel.pl/content/www/pl/pl/products/programmable.html.
11. Altera (2020, July 24). Cyclone IV Device Handbook. Available online: http://www.altera.com/literature/hb/cyclone-iv/cyclone4-handbook.pdf.
12. (2020, July 24). Xilinx FPGAs. Available online: https://www.xilinx.com/products/silicon-devices/fpga.html.
13. Vázquez-Castillo, J., Castillo-Atoche, A., Carrasco-Alvarez, R., Longoria-Gandara, O., and Ortegón-Aguilar, J. (2020). FPGA-Based Hardware Matrix Inversion Architecture Using Hybrid Piecewise Polynomial Approximation Systolic Cells. Electronics, 9.10.3390/electronics9010182 ↗
14. Walters, E.G. (2017). Reduced-Area Constant-Coefficient and Multiple-Constant Multipliers for Xilinx FPGAs with 6-Input LUTs. Electronics, 6.10.3390/electronics6040101 ↗
15. Agrawal, R., Ahuja, K., Hau Hoo, C., Duy Anh Nguyen, T., and Kumar, A. (2019). ParaLarPD: Parallel FPGA Router Using Primal-Dual Sub-Gradient Method. Electronics, 8.10.3390/electronics8121439 ↗
16. Grout, I. (2011). Digital Systems Design with FPGAs and CPLDs, Elsevier.
17. Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers.10.1007/978-1-4757-3393-8 ↗
18. Rawski, M., Łuba, T., Jachna, Z., and Tomaszewicz, P. (2005). Design of Embedded Control Systems, Springer. The Influence of Functional Decomposition Onmodern Digital Design Process.
19. Technology Mapping Oriented to Adaptive Logic Modules
20. Decomposition of multi-level functions oriented to configurability of logic blocks
21. Improvements to technology mapping for LUT-based FPGAs
22. A technology mapping of fsms based on a graph of excitations and outputs10.1109/ACCESS.2019.2895206 ↗
23. Area-oriented technologymapping for lut-based logic blocks10.1515/amcs-2017-0015 ↗
24. Support-Reducing Decomposition for FPGA Mapping10.1109/TCAD.2018.2878187 ↗
25. Scalable don’t-care-based logic optimization and resynthesis10.1145/2068716.2068720 ↗
26. 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 (FPGA’18), Monterey, CA, USA.10.1145/3174243.3174272 ↗
27. Kilts, S. (2007). Advanced FPGA Design: Architecture, Implementation, and Optimization, John Wiley & Sons, Inc.10.1002/9780470127896 ↗
28. FPGA architecture: Survey and challenges—Found trends
29. McElvain, K. (1993). LGSynth93 Benchmark, Mentor Graphics.
30. SoC research and development platform for distributed embedded systems
31. Strategy of Logic Synthesis using MTBDD dedicated to FPGA10.1016/j.vlsi.2018.02.009 ↗
32. Logic synthesis for FPGAs based on cutting of BDD10.1016/j.micpro.2017.06.010 ↗
33. Touili, T., Cook, B., and Jackson, P. (2010). ABC: An Academic Industrial-Strength Verification Tool. Computer Aided Verification, Springer.10.1007/978-3-642-14295-6 ↗
34. Sentovich, E.M., Singh, K.J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P.R., Brayton, R.K., and Sangiovanni-Vincentelli, A. (1992). SIS: A System for Sequential Circuit Synthesis, University of California. Tech. Rep.
35. Barkalov, A., Titarenko, L., Mielcarek, K., and Chmielewski, S. (2020). Logic Synthesis for FPGA-Based Control Units—Structural Decomposition in Logic Design, Springer.10.1007/978-3-030-38295-7 ↗
36. Finite State Machine Based Modelling of Discrete Control Algorithm in LAD Diagram Language With Use of New Generation Engineering Software10.1016/j.procs.2019.09.431 ↗
37. State Assignment of Finite-State Machines by Using the Values of Output Variables
38. Optimal state assignment for finite statemachines
39. A probabilistic pairwise swap search state assignment algorithm for sequential circuit optimization10.1016/j.vlsi.2016.08.001 ↗
40. Structural models of finite-state machines for their implementation on programmable logic devices and systems on chip10.1134/S1064230715010074 ↗
41. Synchronous FSM design methodology for Low-Power Smart Sensors and RFID Devices
42. Sklyarov, V. (2000). Synthesis and implementation of RAM-based finite state machines in FPGAs. International Workshop on Field Programmable Logic and Applications, Springer.10.1007/3-540-44614-1_76 ↗
43. Hardware reduction for lut-based mealy fsms10.2478/amcs-2018-0046 ↗
44. An application of functional decomposition in ROM-based FSM implementation in FPGA devices10.1016/j.sysarc.2004.07.004 ↗
45. Design of emb-based moore fsms
46. 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 ↗
47. ROM based FSM implementation using input multiplexing in FPGA devices10.1049/el:20046007 ↗
48. 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 ↗
49. High-Speed and Area-Efficient Reconfigurable Multiplexer Bank for RAM-Based Finite State Machine Implementations10.1142/S0218126615501017 ↗
50. Minimization of mealy finite-state machines by internal states gluing10.1134/S1064230712010091 ↗
51. Barkalov, A., Titarenko, L., Mazurkiewicz, M., and Krzywicki, K. (2020). Encoding of terms in EMB-based Mealy FSMs. Appl. Sci., 10.10.3390/app10082762 ↗
52. Structural decomposition as a tool for the optimization of an FPGA-based implementation of a Mealy FSM10.1007/s10559-012-9410-2 ↗
53. Testa, E., Amaru, L., Soeken, M., Mishchenko, A., Vuillod, P., Luo, J., Casares, C., Gaillardon, P., and Micheli, G.D. (2019, January 25–29). Scalable boolean methods in a modern synthesis flow. Proceedings of the 2019 Design, Automation Test in Europe Conference Exhibition (DATE), Florence, Italy.10.23919/DATE.2019.8714776 ↗
54. Selvaraj, H., Nowicka, M., and Luba, T. (1998, January 9–11). Non-Disjoint Decomposition Strategy in Decomposition-Based Algorithms & Tools. Proceedings of the International Conference on Computational Intelligence and Multimedia Application, Melbourne, Australia.
55. Functional decomposition of combinational logic circuits with PKmin
56. Xilinx (2020, July 24). XST UserGuide.V. 11.3. Available online: https://www.xilinx.com/support/documentation/sw_manuals/xilinx11/xst.pdf.
57. (2020, July 24). Vivado. Available online: https://www.xilinx.com/products/design-tools/vivado.html.
58. (2020, July 24). Quartus Prime. Available online: https://www.intel.pl/content/www/pl/pl/software/programmable/quartus-prime/overview.html.
59. High-Performance Architecture for Binary-Tree-Based Finite State Machines10.1109/TCAD.2017.2731678 ↗
60. Finite state machines with input multiplexing: A performance study10.1109/TCAD.2015.2406859 ↗
61. Sass, R., and Schmidt, A. (2010). Embedded System Design with platform FPGAs: Principles and Practices, Morgan Kaufmann Publishers.
62. Dahl, O., Dijkstra, E., and Hoare, C. (1972). Structured Programming, Academic Press.
63. Microprogramming and the design of the control circuits in an electronic digital computer10.1017/S0305004100028322 ↗
64. Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer Academic Publishers.10.1007/978-1-4615-2692-6 ↗
65. (2019). Vivado Design Suite User Guide: Synthesis, Xilinx, Inc.. UG901 (v2019.1).
66. (2019). VC709 Evaluation Board for the Virtex-7 FPGA User Guide, Xilinx, Inc.. UG887 (v1.6).