Control Systems and Computers

https://doi.org/10.15407/csc.2022.02.021

Control Systems and Computers, 2022, Issue 2 (298), pp. 21-32

UDC 004.274

Barkalov Olexandr O., Doctor of Technical Sciences, professor, Computer Science and Telecommunications University of Zielona Gora (Poland), ul. Podgorna, 50, Zielona Gora, 65-246, POLAND, ORCID: https://orcid.org/0000-0002-4941-3979,  e-mail: A.Barkalov@iie.uz.zgora.pl

Titarenko Larysa O., Doctor of Technical Sciences, professor, Computer Science and Telecommunications University of Zielona Gora (Poland), ul. Podgorna, 50, Zielona Gora, 65-246, POLAND; professor; Kharkov National University of Radio Electronics, Ukraine, 61000, Kharkov, 14, Science Ave, https://orcid.org/0000-0001-9558-3322, e-mail: L.Titarenko@iie.uz.zgora.pl

Golovin Oleksandr M., PhD (Eng.), Senior Researcher, V.Glushkov Institute of Cybernetics of NAS of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, https://orcid.org/0000-0002-0279-812X,  e-mail: o.m.golovin.1@gmail.com

Matvienko Olexandr V., Researcher, V.Glushkov Institute of Cybernetics of NAS of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, https://orcid.org/0000-0003-1838-1422,  e-mail: matv@online.ua

Optimization of the Mealy Automaton Circuit in the FPGA Basis

Introduction. The ubiquitous penetration of digital systems into all spheres of human activity has made obvious the desire to reduce hardware costs. If for the implementation of combinational circuits there are standard solutions used in various CAD systems, then for many types of accumulating blocks, which include control devices (CU), there are no standard library solutions. CU circuits, which are a sequential circuit, must be designed first each time because, as a rule, these circuits differ in an irregular structure and a complex interconnection system. The characteristics of the control device have a significant impact on the quality of the digital system, and therefore the issue of designing a control device is a responsible process that, as a rule, requires solving the problem of reducing hardware costs. Methods for solving this problem depend on the features of both the architecture of the control device and the elemental basis.

Purpose. The main goal of this work is to reduce hardware costs and power consumption of control devices of digital systems by taking into account features of an element base of the control device and rational organization of micro-command addressing. FPGA (field-programmable logic array) microcircuits, widely used for the implementation of modern digital systems, were chosen as an elementary basis.

Methods. To evaluate the effectiveness of solving the problem, we used the methods of set theory, synthesis of automata, and software simulation using Xilinx Vivado CAD.

Results. The paper proposes a method for reducing hardware costs in the microprogram Mealy automaton (MPA) scheme implemented on an EMB and LUT basis. The method is based on the use of EMB to implement the logical condition replacement block. It is proposed to implement a part of the output signals (micro-operations) on EMB. The applicability conditions for this approach are shown. An example of the synthesis of MPA using the proposed method is given. All stages of the synthesis are analyzed in detail. Some alternative solutions are proposed and the conditions for their use are shown.

Conclusion. Studies have shown that when using one EMB block, our method gives a gain in the number of LUT elements. Comparisons were made with schemes obtained using the Auto, One-hot, and Sequential methods of the Vivado system.

 Download full text! (On Ukrainian)

Keywords: Mealy machine, FPGA, EMB, LUT, structural decomposition, synthesis.

1. Sklyarov, V., Skliarova, I., Barkalov, A., Titarenko, L., 2014. “Synthesis and optimization of FPGA-based systems”. Berlin: Springer, 432 p. https://doi.org/10.1007/978-3-319-04708-9
2. Czerwinski, R., Kania, D., 2013. Finite state machines logic synthesis for complex programmable logic devices. Berlin: Springer, 172 p. https://doi.org/10.1007/978-3-642-36166-1
3. Soloviev, V.V., 2001. Proyektirovaniye tsifrovykh skhem na osnove programmiruyemykh logicheskikh integralnykh skhem. [Design of digital circuits based on programmable logic inte-grated circuits], Hotline – TELECOM, Moscow, 636 p. (In Russian).
4. Maxfield, C., 2004. The design warrior’s guide to FPGAs. Orlando: Academic Press, 542 p.
5. Skliarova, I., Sklyarov, V., Sudnitson, A., 2012. Design of FPGA-based circuits using hierar-chical finite state machines. Tallinn: TUT Press, 240 p.
6. Baranov, S., 1994. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publish-ers, 312 p. 
   https://doi.org/10.1007/978-1-4615-2692-6_6
7. DeMicheli, G., 1994. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 576 p.
8. Kuon, I., Tessier, R., Rose, J., 2008. “FPGA Architecture: Survey and Challenges. Foundations and Trends”. Electronic Design Automation. vol. 2. No 2, pp. 135-253. 
   https://doi.org/10.1561/1000000005
9. Sass, R., Schmidt, A., 2010. Embedded System Design with platform FPGAs: Principles and Practices. Amsterdam: Morgan Kaufmann Publishers, 409 p.
10. UG473 (v1.14) July 3, 2019. [Online] Available at: <www.xilinx.com> [Accessed 2 May. 2021].
11. Rafla, N.I., Gauba, I.A., 2010. “Reconfigurable Pattern Matching Hardware Implementation using On-Chip RAM-Based FSM”. 53rd IEEE International Midwest Symposium on Circuits and Systems. IEEE, August 2010, pp. 49-52. https://doi.org/10.1109/MWSCAS.2010.5548558
12. Tiwari, A., Tomko, K., 2004. “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). Vol. 2, pp. 916-921. https://doi.org/10.1109/DATE.2004.1269007
13. Glushkov, V.M., 1962. Cintez tsifrovykh avtomatov. M.: Fizmatgiz, 476 p. (In Russian).
14. Kubica, M., Opara, A., Kania, D., 2021. Technology Mapping for LUT-based. FPGA. Berlin: Springer, 2021 
    https://doi.org/10.1007/978-3-030-60488-2_1
15. Intel® FPGAs and Programmable Devices. [Online] Available at: <https://www.intel.com/content/www/us/en/ products/programmable.html> [Accessed 2 May. 2021].
16. Yang, S., 1991. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 43 p.
17. Sklyarov, V., 2000. “Synthesis and Implementation of RAM-based Finite States Maсhines in FPGAs”. Proceeding of Field-Programmable Logic and Applications: The Roadmap to Reconfig-urable Computing. Villach: Springer-Verlag, pp 718-727.
    https://doi.org/10.1007/3-540-44614-1_76
18. R. Senhaji-Navarro, I.Garcia-Vargas, G. Jimenes-Moreno, A. Civit-Balcells, and P. Guerra-Gutierres, “ROM-based FSM implementation using input multiplexing in FPGA devices”, Elec-tronics Letters, vol. 40, N 20, pp. 1249-1251, 2004. https://doi.org/10.1049/el:20046007
19. Senhaji-Navarro, R. Garcia-Vargas, I. Guisado, L.J., 2012. “Performance evaluation of RAM-based implementation of Finite States Machines in FPGAs “, 19th IEEE International Confer-ence on Electronics, Circuits, and Systems (ICECS 2012), Seville, Spain, Dec 2012, pp. 225-228.
    https://doi.org/10.1109/ICECS.2012.6463760
20. Yang, S., 1991. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 43 p.
21. Barkalov, A., Titarenko, L., Mielcarek, K., 2018. “Hardware reduction for LUT-based Mealy FSMs”. International Journal of Applied Mathematics and Computer Science, pp. 595-607.
    https://doi.org/10.2478/amcs-2018-0046
22. Barkalov, A., Titarenko, L., Mielcarek, K., 2020. “Improving characteristics of LUT-based Mealy FSMs”. International Journal of Applied Mathematics and Computer Science, 30(4), pp. 745-759.
23. Ruiz-Rosero, J., Ramirez-Gonzalez, G. Khanna, R., 2019. Field Programmable Gate Array Ap-plications-A Scientometric Review. Computation, 7(4), p. 63.
    https://doi.org/10.3390/computation7040063
24. Barkalov, O., Titarenko, L., Barkalov, Jr., 2012. “A Structural Decomposition as a tool for the optimization of an FPGA-based implementation of a Mealy FSM”. Cybernetics and Systems Analysis, Vol. 48, N 2, pp. 313-322. https://doi.org/10.1007/s10559-012-9410-2
25. Vivado Design Suite. [Online] Available at: <https://www.xilinx.com/products/design-tools/vivado.html> [Accessed 2 Jan. 2020].
26. Barkalov, A.A., Titarenko, L.A., Vizor, Ya.E., Matviienko, A.V., 2016. “Optimalnoye kodiro-vaniye sostoyaniy v sovmeshchennom avtomate” [“Optimal coding of states in a combined au-tomaton”], Upravlyayushchiye sistemy i mashiny, 6, pp. 34-39. https://doi.org/10.15407/usim.2016.06.034  (In Russian).
27. Barkalov, A.A., Titarenko, L.A., Vizor, Ya.E., Matvienko, A.V., 2017. “Umensheniye appa-raturnykh zatrat v sovmeshchennykh avtomatakh” [“Reduction of hardware costs in combined machines”], Upravlyayushchiye sistemy i mashiny, 4, pp. 43-50.  https://doi.org/10.15407/usim.2017.04.043 (In Russian).

Received 14. 01.2022