Improving Hardware in LUT-Based Mealy FSMs
Source abstract
Abstract
The main contribution of this paper is a novel design method reducing the number of look-up table (LUT) elements in the circuits of three-block Mealy finite-state machines (FSMs). The proposed method is based on using codes of collections of outputs (COs) for representing both FSM state variables and outputs. The interstate transitions are represented by output collections generated during two adjacent cycles of FSM operation. To avoid doubling the number of variables encoding of COs, two registers are used. The first register keeps a code of CO produced in the current cycle of operation; the code of a CO produced in the previous cycle is kept in the second register. There is given a synthesis example with applying the proposed method. The results of the research are shown. The research is conducted using the CAD tool Vivado by Xilinx. The experiments prove that the proposed approach allows reducing the hardware compared with such known methods as auto and one-hot of Vivado, and JEDI. Additionally, the proposed approach gives better results than a method based on the simultaneous replacement of inputs and encoding of COs. Compared to circuits of the three-block FSMs, the LUT counts are reduced by an average of 7.21% without significant reduction in the performance. Our approach loses in terms of power consumption (on average 9.62%) and power–time products (on average 10.44%). The gain in LUT counts and area–time products increases with the increase in the numbers of FSM states and inputs.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Radiation Effects in Electronics · Embedded Systems Design Techniques · VLSI and Analog Circuit Testing
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 Computer Science and Information Technology, Vasyl Stus’ Donetsk National University, 600-Richya Str. 21, 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 Gorzow Wielkopolski, Poland
References (62)
Show source-provided references
1. Grout, I. (2011). Digital Systems Design with FPGAs and CPLDs, Elsevier Science.
2. Ruiz-Rosero, J., Ramirez-Gonzalez, G., and Khanna, R. (2019). Field Programmable Gate Array Applications—A Scientometric Review. Computation, 7.10.3390/computation7040063 ↗
3. Gajski, D.D., Abdi, S., Gerstlauer, A., and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, Springer Science & Business Media.10.1007/978-1-4419-0504-8 ↗
4. Baranov, S. (2018). Finite State Machines and Algorithmic State Machines: Fast and Simple Design of Complex Finite State Machines, Amazon.
5. Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer Academic Publishers.10.1007/978-1-4615-2692-6 ↗
6. Czerwinski, R., and Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer. Volume 231 of Lecture Notes in Electrical Engineering.10.1007/978-3-642-36166-1 ↗
7. Gazi, O., and Arli, A. (2021). State Machines Using VHDL: FPGA Implementation of Serial Communication and Display Protocols, Springer.10.1007/978-3-030-61698-4 ↗
8. Koo, B., Bae, J., Kim, S., Park, K., and Kim, H. (2020). Test case generation method for increasing software reliability in Safety-Critical Embedded Systems. Electronics, 9.10.3390/electronics9050797 ↗
9. Baranov, S. (2018). High-Level Synthesis of Digital Systems: For Data-Path and Control Dominated Systems, Amazon.
10. Zhao, X., He, Y., Chen, X., and Liu, Z. (2021). Human-Robot collaborative Assembly Based on Eye-Hand and a Finite State Machine in a Virtual Environment. Appl. Sci., 11.10.3390/app11125754 ↗
11. Fast and compact sequential circuits for the FPGA-based reconfigurable systems10.1016/S1383-7621(03)00070-5 ↗
12. Area-time efficient hardware implementation of modular multiplication for elliptic curve cryptography10.1109/ACCESS.2020.2988379 ↗
13. Barkalov, A., Titarenko, L., and Krzywicki, K. (2021). Structural Decomposition in FSM Design: Roots, Evolution, Current State—A Review. Electronics, 10.10.3390/electronics10101174 ↗
14. Barkalov, A., Titarenko, L., Krzywicki, K., and Saburova, S. (2020). Improving the Characteristics of Multi-Level LUT-Based Mealy FSMs. Electronics, 9.10.3390/electronics9111859 ↗
15. Barkalov, A., Titarenko, L., and Krzywicki, K. (2020). Reducing LUT Count for FPGA-Based Mealy FSMs. Appl. Sci., 10.10.3390/app10155115 ↗
16. Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill.
17. A technology mapping of fsms based on a graph of excitations and outputs10.1109/ACCESS.2019.2895206 ↗
18. Sklarova, D., Sklarov, V.A., and Sudnitson, A. (2012). Design of FPGA-Based Circuits Using Hierarchical Finite State Machines, TUT Press.
19. (2022, May 25). AMD Xilinx FPGAs. Available online: https://www.xilinx.com/products/silicon-devices/fpga.html.
20. Trimberger, S.M. (2012). Field-Programmable Gate Array Technology, Springer Science & Business Media.
21. Scalable don’t-care-based logic optimization and resynthesis10.1145/2068716.2068720 ↗
22. Kubica, M., Opara, A., and Kania, D. (2021). Logic Synthesis Strategy Oriented to Low Power Optimization. Appl. Sci., 11.10.3390/app11198797 ↗
23. Nguyen, T.T., Kim, S., Eom, Y., and Lee, H. (2022). Area-Time Efficient Hardware Architecture for CRYSTALS-Kyber. Appl. Sci., 12.10.3390/app12115305 ↗
24. Ney, J., Hammoud, B., Dörner, S., Herrmann, M., Clausius, J., ten Brink, S., and Wehn, N. (2022). Efficient FPGA Implementation of an ANN-Based Demapper Using Cross-Layer Analysis. Electronics, 11.10.3390/electronics11071138 ↗
25. High-Performance Implementation of Power Components on FPGA Platform10.1007/s42835-022-01005-6 ↗
26. Nikolic, S., Zgheib, G., and Ienne, P. (2022). Detailed Placement for Dedicated LUT-Level FPGA Interconnect. ACM Trans. Reconfig. Technol. Syst. (TRETS).10.1145/3501802 ↗
27. Skliarova, I. (2022). A Survey of Network-Based Hardware Accelerators. Electronics, 11.10.3390/electronics11071029 ↗
28. Senhadji-Navarro, R., and Garcia-Vargas, I. (2022). Mapping Arbitrary Logic Functions onto Carry Chains in FPGAs. Electronics, 11.10.3390/electronics11010027 ↗
29. Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers.10.1007/978-1-4757-3393-8 ↗
30. Technology mapping oriented to adaptive logic modules
31. Improvements to technology mapping for LUT-based FPGAs
32. Touili, T., Cook, B., and Jackson, P. (2010). ABC: An Academic Industrial-Strength Verification Tool. Computer Aided Verification: Berlin/Heidelberg, Germany, 2010, Springer.
33. Soloviev, V.V. (2016). Architetures Xilinx FPGA: Family CPLD and FPGA 7, Hot-line-Telecom. (In Russian).
34. Altera (2022, May 25). Cyclone IV Device Handbook. Available online: http://www.altera.com/literature/hb/cyclone-iv/cyclone4-handbook.pdf.
35. A Probabilistic Tabu Search State Assignment Algorithm for Area and Power Optimization of Sequential Circuits10.1007/s13369-020-04697-y ↗
36. 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, Monterey, CA, USA.10.1145/3174243.3174272 ↗
37. Barkalov, A., Titarenko, L., Krzywicki, K., and Saburova, S. (2021). Improving Characteristics of LUT-Based Mealy FSMs with Twofold State Assignment. Electronics, 10.10.3390/electronics10080901 ↗
38. Methodology for Distributed-ROM-based Implementation of Finite State Machines
39. Kubica, M., Opara, A., and Kania, D. (2021). Technology Maping for LUT-Based FPGA, Springer.10.1007/978-3-030-60488-2 ↗
40. Barkalov, A., Titarenko, L., Mielcarek, K., and Chmielewski, S. (2020). Logic Synthesis for FPGA-Based Control Units—Structural Decomposition in Logic Design, Springer. Volume 636 of Lecture Notes in Electrical Engineering.10.1007/978-3-030-38295-7 ↗
41. State Assignment of Finite-State Machines by Using the Values of Output Variables
42. Implementation of finite-state machines based on programmable logic ICs with the help of the merged model of Mealy and Moore machines10.1134/S106422691302006X ↗
43. Park, J., and Yoo, H. (2020). Area-efficient fault tolerance encoding for Finite State Machines. Electronics, 9.10.3390/electronics9071110 ↗
44. Sentovich, E.M., Singh, K.J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., and Sangiovanni-Vincentelli, A. (1992). SIS: A System for Sequential Circuit Synthesis, University of California.
45. (2022, May 25). ABC System. Available online: https://people.eecs.berkeley.edu/~alanmi/abc/.
46. Baranov, S. (2020). From Algorithm to Digital System: HSL and RTL tool Sinthagate in Digital System Design, Amazon.
47. Vivado Design Suite User Guide: Synthesis, Available online: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2019_1/ug901-vivado-synthesis.pdf.
48. (2022, May 25). Xilinx Vitis. Available online: https://www.xilinx.com/products/design-tools/vitis/vitis-platform.html.
49. (2022, May 25). Quartus Prime. Available online: https://www.intel.pl/content/www/pl/pl/software/programmable/quartus-prime/overview.html.
50. Khatri, S.P., and Gulati, K. (2011). Advanced Techniques in Logic Synthesis, Optimizations and Applications, Springer.
51. 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 ↗
52. Saving power by mapping finite-state machines into embedded memory blocks in FPGAs10.1109/DATE.2004.1269007 ↗
53. Micro-programming and the design of the control circuits in an electronic digital computer10.1017/S0305004100028322 ↗
54. Chapman, K. (2014). Multiplexer Design Techniques for Data-Path Performance with Minimized Routing Resources, Xilinx Inc.. Version 1.2.
55. Achasova, S. (1987). Synthesis Algorithms for Automata with PLAs, M: Soviet Radio. (In Russian).
56. McElvain, K. (1993). LGSynth93 Benchmark, Mentor Graphics.
57. A survey of design techniques for system-level dynamic power management10.1109/92.845896 ↗
58. Optimal state assignment for finite state machines
59. A probabilistic pairwise swap search state assignment algorithm for sequential circuit optimization10.1016/j.vlsi.2016.08.001 ↗
60. (2019). VC709 Evaluation Board for the Virtex-7 FPGA User Guide, Xilinx, Inc.. UG887 (v1.6).
61. Barkalov, A., Titarenko, L., Krzywicki, K., and Saburova, S. (2022). Improving Characteristics of LUT-Based Three-Block Mealy FSMs’ Circuits. Electronics, 11.10.3390/electronics11060950 ↗
62. The power-delay product and its implication to CMOS Inverter10.1088/1742-6596/1754/1/012131 ↗