2023, issue 3, p. 88-100
Received 20.07.2023; Revised 12.08.2023; Accepted 26.09.2023
Published 29.09.2023; First Online 19.10.2023
https://doi.org/10.34229/2707-451X.23.3.8
Previous | FULL TEXT (in Ukrainian) | Next
Optimization of a Mealy Automaton Circuit in a Mixed Element Basis
Alexander Barkalov 1 
, Larysa Titarenko 1, 2 , Oleksandr Golovin 3 , Oleksandr Matvienko 3 *
1 University of Zielona Gora, Poland
2 Kharkiv National University of Radio Electronics, 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. The control device is one of the most important blocks of any digital system. The main function of the control device is to coordinate the interaction of the remaining units of the system. Therefore, the characteristics of the control device circuit have a significant impact on the quality of the overall system.
To represent the law of functioning of the control device, the models of the microprogrammed automaton (MPA) by Moore and Mealy are used. When synthesizing MPA circuits, it is necessary to solve a number of optimization problems: reducing hardware costs, increasing performance, minimizing power consumption, and jointly optimizing hardware-time characteristics. Methods for solving these problems largely depend on the elemental basis used. Currently, one of the main bases in which modern digital systems are implemented is the FPGA.
The main blocks in the FPGA are configurable logic blocks, a programmable interconnect matrix, a timing tree, and programmable inputs and outputs. To implement MPA schemes, two types of configurable logic blocks can be used: tabular logic elements (TLE) and built-in memory blocks (VBP), which have the property of reconfiguration. However, VBPs are widely used to implement various operating blocks of digital systems. Therefore, the controller circuit designer can use a limited number of such memory blocks.
Purpose of the article. The article deals with the issues of MPA synthesis when there are a limited number of "free" blocks of EBP. In this case, the microprogram automaton circuit is represented by a network consisting of VBP and TLE blocks. A method for the synthesis of a microprogram automaton with optimization of the number of TLEs is proposed when only one VBP can be used in the microprogram automaton circuit.
The proposed method is based on the use of a built-in memory block that performs the replacement of input variables and the coding of the automaton outputs.
Results. Studies of the effectiveness of the proposed method were carried out on standard machines. FPGAs of the Virtex-7 family from Xilinx were used as the elemental basis. To implement the proposed MPA, the Vivado package was used. The results of the research showed that the use of the VBP block made it possible to reduce the number of SLE blocks by an average of 14 % – 18 % compared to schemes consisting only of SLE. For the Virtex-7 family FPGA, the number of TLE inputs Io= 6 was sufficient for a single-level implementation of the output system.
Conclusions. The effectiveness of the proposed method makes it possible to recommend it for use in the synthesis of microprogram automata under conditions of an extremely limited number of BVPs.
Keywords: Mealy automaton, synthesis, coding of inputs, coding of sets of outputs.
Cite as: Barkalov A., Titarenko L., Golovin O., Matvienko O. Optimization of a Mealy Automaton Circuit in a Mixed Element Basis. Cybernetics and Computer Technologies. 2023. 3. P. 88–100. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.3.8
References
1. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p. https://doi.org/10.1007/978-1-4615-2692-6
2. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
3. 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
4. Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Berlin: Springer, 2013. 172 p. https://doi.org/10.1007/978-3-642-36166-1
5. Wiśniewski R., Bazydło G., Szcześniak P., Wojnakowski M. Petri net-based specification of cyber-physical systems oriented to control direct matrix converters with space vector modulation. IEEE Access, 2019. Vol. 7. 23407–23420.
6. 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.
7. Tiwari A., Tomko K. 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.
8. Rawski M., Tomaszewicz P., Borowski G., Luba T. Logic synthesis method of digital circuits designed for implementation with embedded memory blocks on FPGAs. In: Design of Digital Systems and Devises. Lecture Notes in Electrical Engineering. Adamski M., Barkalov A., Wegrzyn M. (Eds.). Vol. 79. Berlin: Springer, 2011. P. 121–144. https://doi.org/10.1007/978-3-642-17545-9_5
9. Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press, 2004. 542 p.
10. Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier, 2008. 784 p. https://doi.org/10.1016/B978-0-7506-8397-5.X0001-3.
11. 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
12. 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. 34 (5). P. 867–871. https://doi.org/10.1109/TCAD.2015.2406859
13. Sklyarov V. Synthesis and Implementation of RAM-based Finite States Maсhines in FPGAs. in Proceeding of Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing. Villach: Springer-Verlag, 2000. P. 718–728. https://doi.org/10.1007/3-540-44614-1_76
14. Kuon I., Tessier R., Rose J. FPGA Architecture: Survey and Challenges. Foundations and Trends in Electronic Design Automation. 2008. 2 (2). P. 135–253. https://doi.org/10.1561/1000000005
15. Kubica M., Opara A., Kania D.. Technology Mapping for LUT- based. FPGA. Berlin: Springer, 2021. https://doi.org/10.1007/978-3-030-60488-2
16. Barkalov A.A., Titarenko L.A., Barkalov A.A.(jr). A Structural Decomposition as a tool for the optimization of an FPGA–based implementation of a Mealy FSM. Cybernetics and Systems Analysis. 2012. 48 (2). P. 313–322. https://doi.org/10.1007/s10559-012-9410-2
17. Barkalov A., Titarenko L., Mielcarek K. Hardware reduction for LUT–based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. P. 595–607. https://doi.org/10.2478/amcs-2018-0046
18. Barkalov A., Titarenko L., Mielcarek K. Improving characteristics of LUT–based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2020. 30 (4). P. 745–759.
19. Vivado Design Suite. https://www.xilinx.com/products/design-tools/vivado.html (accessed: 15.01.2023)
20. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.
21. 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. https://doi.org/10.15407/usim.2016.03.016
22. 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. https://doi.org/10.15407/usim.2017.04.043
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next