2024, issue 2, p. 87-100
Received 10.04.2024; Revised 04.05.2024; Accepted 28.05.2024
Published 09.06.2024; First Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.9
Previous | FULL TEXT (in Ukrainian) | Next
Optimization of the Microprogram Mealy Machine Circuit Based on LUT and EMB
Alexandr 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. A digital system is a collection of combinational and sequential blocks. Sequential blocks can be divided into library and non-standard classes. The first class includes, for example, counters or shift registers. To implement the circuits of such blocks, standard CAD programs are used. And for the second class, which is the control unit (CU), there are no standard library solutions. This explains the relevance of methods for synthesis and optimization of circuits of non-standard sequential blocks, such as CU.
When synthesizing a finite state machine (FSM) circuit, a number of optimization problems arise that are aimed at improving CU characteristics. Methods for solving these problems depend on elemental base characteristics. This paper discusses the implementation of the FSM circuit on a FPGA (field-programmable logic array) basis.
The main FPGA blocks that are used for FSM circuit implementation are LUT (look-up table) elements and EMB (embedded memory blocks) elements. Therefore, to solve optimization problems while developing an FSM circuit, it is necessary to reduce the number of these elements.
The purpose of the article. This work presents an approach to lower hardware costs in the FSM Mealy technique, which uses FPGA for implementation.
The method is based on the extended coding of micro-operation sets, in which the set code also includes the transition state code. The state code is partial since it is determined for a set of states upon transition, from which this set is formed. To implement part of the FSM circuit, the built-in memory block EMB is used. If EMB capabilities are not enough to implement the circuit, then part of the circuit is implemented on LUT elements. It is proposed to implement part of the output signals (micro-operations) on EMB. An example of the synthesis of an FSM circuit using the proposed method is given.
Results. To study the effectiveness of the proposed method, a comparison was made between the control unit of the known structure (U5) and the control unit obtained using the proposed method (U7). In this case, standard benchmarks from a well-known library were used. Research has shown that U7 can reduce the number of LUTs by 28 % of all benchmarks, and U5 only by 9 %. It is important to note that when implementing the entire 64 % standard MPA circuit, one EMB block is sufficient.
Conclusions. The proposed method allows for a reduction in hardware costs (the number of LUT elements). The article shows the conditions for applying the proposed method. Results of experiments examining the effectiveness of the suggested approach to automata implementation with Virtex-7 family chips and the Vivado industrial package are given
Keywords: Mealy FSM, synthesis, FPGA, EMB, LUT, extended codes of micro-operation sets.
Cite as: Barkalov A., Titarenko L., Golovin O., Matvienko O. Optimization of the Microprogram Mealy Machine Circuit Based on LUT and EMB. Cybernetics and Computer Technologies. 2024. 2. P. 87–100. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.2.9
References
1. 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
2. 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. Springer, 2020. Vol. 636. https://doi.org/10.1007/978-3-030-38295-7
3. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p. https://doi.org/10.1007/978-1-4615-2692-6
4. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
5. Barkalov A., Titarenko L., Kolopienczyk M., Mielcarek K., Bazydlo G. Logic synthesis for FPGA-based Finite State Machine. Studies in Systems, Decision and Control. Vol. 38. Springer International Publishing, Cham Heidelberg, 2015. https://doi.org/10.1007/978-3-319-24202-6
6. Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press, 2004. 542 p.
7. 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
8. 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. https://doi.org/10.3390/electronics10080901
9. Bacchetta P., Daldos L., Sciuto D., Silvano C. Low-power state assignment techniques for finite state machines. In Proceedings of the 2000 IEEE International Symposium on Circuits and Systems (ISCAS’2000) (Geneva, 2000), vol. 2, IEEE, P. 641–644. https://doi.org/10.1109/ISCAS.2000.856410
10. 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
11. 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
12. 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
13. Barkalov A. Microprogramcontrol unit as composition of automate with programmable and hardwired logic. Automatics and Computer Science. 1983. 17 (4). P. 36–41.
14. Amann R., Baitinger U. Optimal state chains and states codes in finite state machines. IEEE Transactions on Computer-Aided Design. 1989. 8 (2). P. 153–170. https://doi.org/10.1109/43.21834
15. Barkalov A., Shwec A. Synthesis of compositional microprogram control unit with modified microinstruction addressing. Automatic Control and Computer Sciences. 1994. 28 (5). P. 22–30.
16. Barkalov A.A. Multilevel programmable logic array schemes for microprogrammed automata. Cybern Syst Anal. 1994. 30. P. 489–495. https://doi.org/10.1007/BF02366558
17. 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. Springer,Berlin, 2020. Vol. 636. https://doi.org/10.1007/978-3-030-38295-7
18. Xilinx. http://www.xilinx.com (https://www.amd.com/en.html) (accessed: 01.01.2024)
19. Virtex‐7 T and XT FPGAs Data Sheet. https://docs.xilinx.com/v/u/en-US/ds183_Virtex_7_Data_Sheet (accessed: 01.01.2024)
20. Barkalov O., Titarenko L., Mielcarek K. Hardware reduction for LUT based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. Vol. 28. No. 3. P. 595–607. https://doi.org/10.2478/amcs-2018-0046
21. Barkalov, O., Titarenko, L., and Mielcarek, K. Improving characteristics of LUT-basedMealy FSMs. International Journal of Applied Mathematics and Computer Science. 2020. Vol. 30. No. 4. P. 745–759. https://doi.org/10.34768/amcs-2020-0055
22. Vivado Design Suite. https://www.xilinx.com/products/design-tools/vivado.html (accessed: 01.01.2024)
23. McElvain, Kenneth. IWLS’93 Benchmark Set: Version 4.0. https://www.researchgate.net/publication/238195666_Benchmark_set_Version_40 (accessed: 01.01.2024)
24. Machado L., Cortadella J. Support-Reducing Decomposition for FPGA Mapping. IEEE transactions on Computer-Aided Design of Integrated Circuits and Systems. 2020. 39 (1). P. 213–224. https://doi.org/10.1109/TCAD.2018.2878187
25. Barkalov A.A., Titarenko L.A. Code conversion in compositional microprogram control units. Cybern Syst Anal. 2011. 47. P. 763–772. https://doi.org/10.1007/s10559-011-9355-x
26. www.altera.com (accessed: 01.01.2024)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next