2022, issue 2, p. 83-94
Received 14.08.2022; Revised 14.09.2022; Accepted 29.09.2022
Published 30.09.2022; First Online 05.10.2022
https://doi.org/10.34229/2707-451X.22.2.9
Previous | FULL TEXT (in Ukrainian) | Next
Optimization of a Moore 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 unit is one of the most important building blocks of any digital system. The main function of the control unit is to coordinate the interaction between all system blocks. Therefore, the characteristics of a control unit circuit have a significant impact on the quality of the system as a whole.
To represent the law of functioning of a control unit, the models of the Moore and Mealy finite state machines (FSM) are used. When synthesizing circuits of FSMs, it is necessary to solve a number of optimization problems, such as the reducing hardware amount, increasing performance, minimizing power consumption, joint optimization of hardware-temporal characteristics. Methods for solving these problems largely depend on the used logical elements.
Currently, FPGA microchips are one of the main platforms in which modern digital systems are implemented. The main blocks in the FPGA, which are used in the implementation of FSM circuits, are embedded memory blocks (EMBs), logical blocks LUT (look-up table) and a system of programmable interconnections. The best characteristics are possessed by FSM circuits implemented with EMBs. However, EMBs are widely used to implement various operational blocks of digital systems. Therefore, the designer of a control unit circuitry can use a rather limited number of EMBs.
Purpose of the article. The article deals with the extreme case when there is only a single "free" EMB available. In this case, the FSM circuit is represented by a network consisting of this EMB and LUTs. There is proposed a method for the synthesis of an FSM with the optimization of the number of LUTs, when only one EMB block is available for implementing some part of the circuit.
The proposed method is based on the using classes of pseudoequivalent states of Moore FSMs. The states are coded in such a way that the state code consists of the code of the class of pseudoequivalent states and the code of a collection of microoperations.
Results. Studies of the effectiveness of the proposed method were carried out on standard FSMs. FPGAs of the Virtex-7 family from Xilinx were used as an implementation platform. The research results showed that the proposed method allows reducing the number of LUTs in FSM circuits by 12 % – 19 % in comparison with the known methods. In all cases, only a single EMB was used.
Conclusions. The effectiveness of the proposed method allows us to recommend it for use in the synthesis of FSMs if there is of an extreme shortage of EMBs.
Keywords: Moore FSM, FPGA, LUT, EMB, pseudoequivalent states, synthesis.
Cite as: Barkalov A., Titarenko L., Golovin O., Matvienko O. Optimization of a Moore Automaton Circuit in a Mixed Element Basis. Cybernetics and Computer Technologies. 2022. 2. P. 83–94. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.2.9
References
1. Solov'yev V. V. Designing digital circuits based on programmable logic integrated circuits M.: Goryachaya liniya TELEKOM, 2001. 636 p. (in Russian)
2. 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
3. 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
4. Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier, 2008. 784 p.
5. Glushkov VM Synthesis of digital machines. M.: Fizmatgiz, 1962.476 p. (in Russian)
6. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p. https://doi.org/10.1007/978-1-4615-2692-6
7. Barkalov A., Titarenko L., Mielcarek K., and Chmielewski S.. Logic Synthesis for FPGA–Based Control Units. – Structural Decomposition in Logic Design. Vol. 636 of Lecture Notes in Electrical Egineering. Springer, 2020. https://doi.org/10.1007/978-3-030-38295-7
8. Barkalov A.A., Titarenko L.A. Code transformation in compositional microprogram control units. Cybernetics and Systems Analysis. 2011. 47 (5). P. 763–772. https://doi.org/10.1007/s10559-011-9355-x
9. Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press. 2004. 542 p.
10. 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
11. UG473 (v1.14. July 3. 2019). https://www.xilinx.com/ (accessed: 14.08.2022)
12. 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
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–727. https://doi.org/10.1007/3-540-44614-1_76
14. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.
15. Achasova S. M. Algorithms for the synthesis of automata on programmable matrices. M.: Radio i svyaz', 1987. 136 p. (in Russian)
16. Vivado Design Suite. https://www.xilinx.com/products/design-tools/vivado.html (accessed: 01.01.2020)
17. VC709 Evaluation Board for the Virtex-7 FPGA. User Guide; UG887 (v1.6); Xilinx, Inc.: San Jose, CA, USA, 2019.
18. Barkalov A.A., Tytarenko L.A., Vyzor YA.E., Matvyenko A.V. Realization of combined finite state machine with FPGAs. Kompyuterni zasoby, merezhi ta systemy. 2016. P. 10–19. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/122858
19. Barkalov A.A., Tytarenko L.A., Vyzor YA.E., Matvyenko A.V. Encoding of output variables in combined automation. Kompyuterni zasoby, merezhi ta systemy. 2018 P. 73–80. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/150610
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next