2023, issue 4, p. 84-96
Received 30.09.2023; Revised 17.10.2023; Accepted 28.11.2023
Published 04.12.2023; First Online 05.12.2023
https://doi.org/10.34229/2707-451X.23.4.10
Previous | FULL TEXT (in Ukrainian) | Next
Separation of Input Variables for Optimization of the Mealy FSM Circuit
Alexandr Barkalov 1 
, Larysa Titarenko 1, 2 , Oleksandr Golovin 3 , Oleksandr Matvienko 3 , Svitlana Saburova 2
1 University of Zielona Gora, Poland
2 Kharkiv National University of Radio Electronics, Kharkiv, Ukraine
3 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. One of the most important blocks of almost any digital system is the control device (CU), since the characteristics of the CU largely determine the characteristics of the system as a whole.
In the practice of engineering design, the behavior of the CU is often specified using the Mealy finite state machine (FSM) model. A feature of Mealy FSM is the dependence of systems of Boolean functions that define the circuit on FSM inputs and states. In this article, this feature is taken into account when optimizing the characteristics of FSM circuit in the basis of FPGA chips.
When developing FSM circuits, it is necessary to optimize its characteristics, such as performance and hardware costs.
FPGAs are one of the most common logic bases for implementing digital systems. FPGA components such as look-up table (LUT) elements, programmable flip-flops, embedded memory blocks (EMBs), and programmable interconnects are sufficient to implement the CU circuit.
The purpose of the article. In this paper, we propose a method for reducing hardware costs in the Mealy FSM cirucit implemented in the FPGA basis. In this case, the problem of implementing a circuit in a mixed elemental basis is considered. A mixed basis is understood as the joint use of LUTs and EMBs. The situation is considered when the number of available EMBs is extremely limited, which is quite possible, since EMBs are widely used to implement various operating blocks of digital systems.
The main disadvantage of LUTs is the small number of inputs. Modern digital systems can generate signals of logical conditions entering the CU, the number of which is tens of times greater than the number of LUT inputs. This discrepancy between the characteristics of the control algorithm and the number of inputs of the LUTs leads to multilevel CU circuits with an irregular structure of programmable interconnections. To optimize multilevel schemes, the method of replacing input variables is used with the joint use of LUTs and EMB blocks.
Results. The analysis of the effectiveness of the proposed method was carried out using the libraries of standard benchmarks FSMs and the Vivado CAD platform. Studies have shown that the proposed method makes it possible to reduce the number of LUTs in the range from 100% to 82%. For 37% of automata, the method of replacing input variables can be applied only in conjunction with the separation of input variables.
Conclusions. The proposed method makes it possible to reduce hardware costs (the number of LUTs and their interconnections), delay time, and power consumption. The article shows the conditions for applying the proposed method. The results of studies of the effectiveness of the proposed method for standard automata using chips of the Virtex-7 family and the Vivado industrial package are presented.
Keywords: finite state machine, synthesis, FPGA, EMB, LUT, input replacement.
Cite as: Barkalov A., Titarenko L., Golovin O., Matvienko O., Saburova S. Separation of Input Variables for Optimization of the Mealy FSM Circuit. Cybernetics and Computer Technologies. 2023. 4. P. 84–96. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.4.10
References
1. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state machines. Tallinn: TUT Press, 2012. 240 p. https://doi.org/10.1109/IranianCEE.2013.6599683
2. Baranov S. Logic and System Design of Digital Systems. Tallinn: TUT Press, 2008.
3. Baranov S. Finite State Machines and Algorithmic State Machines. Amazon, 01 2018.
4. DeMicheli G. Synthesis and Optimization of Digital Circuits. McGraw–Hill, 1994. 576 p.
5. Wolf W. FPGA-Based System Design. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2004. 548 p.
6. Maxfield C. FPGAs: Instant access. Newnes, 2008. 204 p.
7. Trimberger S. Three ages of FPGA: A retrospective on the first thirty years of FPGA technology. IEEE Proceedings Solid-State Circuits Magazine. 2018. Vol. 10, No. 2. P. 16–29. http://dx.doi.org/10.1109/mssc.2018.2822862
8. Ruiz-Rosero J., Ramirez-Gonzalez G., Khanna R. Field programmable gate array applications – a scientometric review. Computation. 2019. 7 (4). 63. https://doi.org/10.3390/computation7040063
9. Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and optimization of FPGA-based systems. Berlin: Springer, 2014. 432 p. https://doi.org/10.1007/978-3-319-04708-9_6.
10. Barkalov A., Titarenko L. Logic synthesis for FSM-based control units. Berlin: Springer, 2009. 233 p. https://doi.org/10.1007/978-3-642-04309-3
11. Barkalov A., Titarenko L., Mielcarek K., Chmielewski S. Logic Synthesis for FPGA-Based Control Units - Structural Decomposition in Logic Design. Lecture Notes in Electrical Engineering. Berlin: Springer. 2020. https://doi.org/10.1007/978-3-030-38295-7
12. Marwedel P. Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things. 3rd ed. Springer International Publishing, 2018. https://doi.org/10.1007/978-3-030-60910-8
13. Garcia-Vargas I., Senhadji-Navarro R., Jim Бnez-Moreno G., Civit-Balcells A., Guerra-Gutierrezz P. ROM-based finite state machines implementation in low cost FPGAs. IEEE Intern. Simp. on Industrial Electronics (ISIE’07) (Vigo, 2007). 2007. P. 2342–2347. https://doi.org/10.1109/ISIE.2007.4374972
14. Garcia-Vargas L., Senhaji-Navarro R. Finite state machines with input multiplexing: A performance study. IEEE Transactions on CAD of Integrated Circuits and Systems. 2015. Vol. 34, Iss. 5. P. 867–871. https://doi.org/10.1109/TCAD.2015.2406859
15. Xilinx. https://www.xilinx.com/products/silicon-devices.html (accessed: 01.01.2023)
16. Xilinx. Virtex-7 Family Overview. PDF, Xilinx Corporation. 2021. http://www.xilinx.com/support/documentation/ data_ sheets/ds183_Virtex_7_Data_Sheet.pdf (accessed: 01.01.2023)
17. Chapman K. Multiplexer Design Techniques for Datapath Performance with Minimized Routing Resources. Xilinx All Programmable, 2014. https://api.semanticscholar.org/CorpusID:61416418 (accessed: 01.01.2023)
18. Feng W., Greene J., Mishchenko A. Improving FPGA Performance with a S44 LUT Structure. In Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (NewYork: NY, USA, 02 2018), FPGA’18, Association for Computing Machinery. 2018. P. 61–66. http://dx.doi.org/10.1145/3174243.3174272
19. Islam M.M., Hossain M.S., Shahjalal M., Hasan M.K., Jang Y.M. Area-time e_cient hardware implementation of modular multiplication for elliptic curve cryptography. IEEE Access. 2020. Vol. 8. P. 73898–73906. http://dx.doi.org/10.1109/ACCESS.2020.2988379
20. Machado L., Cortadella J. Support-Reducing Decomposition for FPGA Mapping. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Vol. 39, No. 1. P. 213–224. http://dx.doi.org/10.1109/TCAD.2018.2878187
21. Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Bulletin of the polish academy of sciences technical sciences. 2010. Vol. 58, No. 4. 172 p. http://dx.doi.org/10.2478/v10175-010-0067-6
22. Kolopienczyk M., Titarenko L., Barkalov A. Design of EMB-based Moore FSMs. Journal of Circuits, Systems and Computers. 2017. Vol. 26, No. 7. P. 1–23. https://doi.org/10.1142/S0218126617501250
23. Tiwari A., Tomko K.A. Saving power by mapping finite state machines into embedded memory blocks in FPGAs. Proc. Design, Automation and Test in Europe Conference and Exhibition. (Paris, France, 6–20 Feb. 2004). 2004. Vol. 2. P. 916–921. https://doi.org/10.1109/DATE.2004.1269007
24. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.
25. Vivado. https://www.xilinx.com/products/design-tools/vivado.html (accessed: 01.01.2023)
26. Xilinx. Vitis Platform. https://www.xilinx.com/products/design-tools/vitis/vitis-platform.html (accessed: 01.01.2023)
27. Barkalov A.A., Titarenko L.A., Vizor Ya.Ye., Matvienko A.V., Gorina V.V. Reducing the number of LUT elements in the combined automaton circuit. Control Systems and Computers. 2016. No. 3. P. 16–22. (in Russian) https://doi.org/10.15407/usim.2016.03.016
28. Barkalov A.A., Titarenko L.A., Vizor Ya.Ye., Matvienko A.V. Reducing the Hardware Amount for the Combined Automata. Control Systems and Computers. 2017. No. 4. P. 43–50. (in Russian) https://doi.org/10.15407/usim.2017.04.043
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next