Test graph-schemes of the algorithms of finite state machines work for assessing the efficiency of automated synthesis in Xilinx Vivado CAD

Abstract

EN: 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. UK: Актуальність. Розглянуто задачу оцінки ефективності автоматизованого проєктування мікропрограмного автомата з операційним перетворенням кодів станів із використанням САПР Xilinx Vivado. Об’єктом дослідження були граф-схеми алгоритмів керування, що імплементуються мікропрограмним автоматом та здатні довести ефективність принципу операційного перетворення кодів станів у порівнянні зі стандартними методами синтезу, вбудованими в САПР, в контексті оптимізації апаратурних витрат. Мета. Розробка і дослідження граф-схем алгоритмів керування з метою обґрунтування ефективності застосування структури мікропрограмного автомата з операційним автоматом переходів у порівнянні із вбудованими методами синтезу автоматів в САПР Xilinx Vivado в базисі програмувальних логічних пристроїв. Метод. В основу дослідження покладено гіпотетичне припущення про те, що САПР Xilinx Vivado має вбудовані методи автоматизованого проектування схеми мікропрограмного автомата, ефективність яких за критерієм апаратурних витрат перевершує інші відомих методи оптимізації апаратурних витрат в схемі автомата. З метою спростування даної гіпотези запропоновано довести, що в окремих випадках відомі методи оптимізації апаратурних витрат в схемі автомата є більш ефективними у порівняні з методами, вбудованими в САПР. В даній роботі в якості відомого методу оптимізації обраний метод операційного перетворення кодів станів, що породжує структуру мікропрограмного автомата з операційним автоматом переходів. Ефективність цього методу доводиться на прикладі кількох тестових граф-схем алгоритмів, структура яких є абстрактною і штучно адаптована до обраного методу оптимізації. Адаптація обраних граф-схем алгоритмів полягає в тому, що для їх реалізації за допомогою мікропрограмного автомата з операційним автоматом переходів потрібна відносно мала кількість операцій переходів. Це сприяє спрощенню схеми автомата і зменшенню апаратурних витрат на її реалізацію. Разом з тим тестові граф-схеми алгоритмів мають можливість масштабування, що дозволяє автоматизувати побудову VHDL-моделей відповідного автомата для граф-схем різного розміру і оцінити оптимізацію апаратурних витрат для автоматів різної складності. Результати. На прикладі декількох граф-схем алгоритмів продемонстровано, що в окремих випадках жоден із методів синтезу кінцевих автоматів, вбудованих в САПР Xilinx Vivado, не здатен перевершити метод операційного перетворення кодів станів за критерієм апаратурних витрат на реалізацію схеми мікропрограмного автомата. При цьому може досягатись кількаразовий виграш у витратах апаратури, що свідчить про доцільність використання даного методу за певних умов. Формальне визначення таких умов для розглянутого та інших відомих методів оптимізації є окремою невирішеною науковою проблемою. Висновки. Проведені експерименти підтвердили, що в окремих випадках відомі методи синтезу мікропрограмних автоматів дозволяють отримати схеми автоматів із меншими витратами апаратури, ніж при використанні методів синтезу автоматів, вбудованих в САПР Xilinx Vivado. Це свідчить про загальну доцільність використання існуючих і розробки нових методів оптимізації апаратурних витрат в схемі автомата та про сьогоденну актуальність теорії синтезу цифрових автоматів як наукового напрямку.