TEST GRAPH-SCHEMES OF THE ALGORITHMS OF FINITE STATE MACHINES WORK FOR ASSESSING THE EFFICIENCY OF AUTOMATED SYNTHESIS IN XILINX VIVADO CAD
Authors: Barkalov A. A. , Titarenko L. A. , Babakov R. M. 
Published: October 2023

Context. The problem of evaluating the effectiveness of the automated design of a microprogram finite state machine with the operational transformation of state codes using Xilinx Vivado CAD is considered. The object of the research was graph-schemes of control algorithms implemented by finite state machine and able to prove the effectiveness of the principle of operational transformation of state codes in comparison with standard synthesis methods built into the CAD, in the context of hardware expenses optimization.

Objective. Development and research of graph-schemes of control algorithms in order to substantiate the effectiveness of the application of structure of the finite state machine with datapath of transitions in comparison with the built-in methods of synthesizing finite state machines in Xilinx Vivado CAD in the basis of programmable logic devices.

Method. The research is based on the hypothetical assumption that the Xilinx Vivado CAD has built-in methods of automated design of the circuit of a finite state machine, the effectiveness of which, according to the criterion of hardware expenses, exceeds other known methods of optimizing hardware expenses in the finite state machine circuit. In order to refute this hypothesis, it is proposed to prove that in some cases known methods of hardware expenses optimization in the finite state machine circuit are more effective in comparison with the methods built into CAD. In this work, as a well-known optimization method, the method of operational transformation of state codes, which corresponds to the structure of a finite state machine with datapath of transitions, is chosen. The effectiveness of this method is demonstrated on the example of several test graph-schemes of algorithms, the structure of which is abstract and artificially adapted to the chosen optimization method. The adaptation of the selected graph-schemes of the algorithms consists in the fact that a relatively small number of transition operations is required for their implementation with the help of a finite state machine with datapath of transitions. This contributes to the simplification of the circuit of the finite state machine and the reduction of hardware costs for its implementation. At the same time, the test graph-schemes of the algorithms have the possibility of scaling, which allows to automate the construction of VHDL models of the corresponding finite state machines for graph-schemes of different sizes and to evaluate the optimization of hardware expenses for finite state machines of different complexity.

Results. Using the example of several graph-schemes of algorithms, it is demonstrated that in some cases none of the finite state machine synthesis methods built into the Xilinx Vivado CAD is able to surpass the method of operational transformation of state codes according to the criterion of hardware expenses for the implementation of a finite state machine circuit. At the same time, a several-fold gain in hardware expenses can be achieved, which indicates the expediency of using this method under certain conditions. The formal definition of such conditions for the considered and other known optimization methods is a separate unsolved scientific problem.

Conclusions. The conducted experiments confirmed that in some cases, the known methods of synthesis of finite state machines allow to obtain circuits with lower hardware expenses than when using the methods of synthesis of finite state machines contained in Xilinx Vivado CAD. This testifies to the general expediency of using existing and developing new methods of hardware expenses optimization in the circuit of the finite state machines and the current relevance of the theory of the synthesis of digital automata as a scientific direction.