MULTIPROCESS IMPLEMENTATION OF ALGORITHMS FOR ALGEBRAIC SYNTHESIS OF A FINITE STATE MACHINE

Abstract

Context. The problem of the parallel implementation of two algorithms for algebraic synthesis of a finite state machine with datapath of transitions is considered. This type of state machine can be used as an alternative to a finite state machine with a canonical structure in order to reduce hardware expenses in the state machine circuit. The object of the study is algorithms for finding complete and partial solutions to the problem of the algebraic synthesis of a finite state machine, which have a parallel
implementation based on a mechanism if processes. The first of these algorithms is the known algorithm for the complete sequential enumeration of state encoding variants with a fixed set of transition operations. The second algorithm implements an infinite enumeration of state encoding variants based on pseudo-random encoding. The goal of each algorithm is to find a solution to the algebraic synthesis problem with as few uncovered transitions as possible in a given time. This paper proposes an approach to increasing the speed of these algorithms, which consists in their parallel implementation using all processor cores available on the computer. This contributes to finding more efficient solutions to the algebraic synthesis problem in a given time, which can lead to lower hardware expenses in the device circuit.
Objective. Multiprocess implementation and research of algorithms for finding solutions to the algebraic synthesis problem of
finite state machine with datapath of transitions.
Method. The research is based on the structure of a finite state machine with a datapath of transitions. The synthesis of the state machine circuit is preceded by a stage of algebraic synthesis, the result of which is the combination of a certain method of state encoding with the assignment of certain arithmetic-logical operations to individual transitions of the finite state machine. Such a combination is a solution to the problem of algebraic synthesis of a finite state machine with a datapath of transitions. In the general case, for a given finite state machine there are many solutions, each of which can be either complete (each transition is covered by one of the given operations) or partial (when part of the transitions remains uncovered by any of the operations). The more transitions in a partial solution are covered, the less hardware expenses are spent on implementing the state machine circuit and the better the solution found. The search for the best solutions requires an enumeration of a large number of possible variants of state encoding. In this case, it does not matter in principle whether the enumeration of the encoding variants is carried out sequentially or in a pseudorandom manner. In this work, in order to speed up the search for solutions to the algebraic synthesis problem, a parallel implementation of two algorithms is proposed, for which the “multiprocessing” module of the Python language is used. Both algorithms (the sequential search algorithm and the pseudo-random search algorithm) were implemented in programmatic way and investigated on the example of an abstract control algorithm using an i5-13500 processor. The purpose of the experiments was to evaluate the improvement of solutions to the algebraic synthesis problem found in the same running time by single-process and multi-process implementations of the specified algorithms.
Results. Using the example of an abstract control algorithm, it is demonstrated that, in general, multiprocess implementation of
the considered algebraic synthesis algorithms allows finding better solutions to the algebraic synthesis problem in the same time than with a single-process (non-parallel) implementation of these algorithms. The advantage of the parallel implementation of the algorithms is preserved when using different sets of transition operations.
Conclusions. The algebraic synthesis of a finite state machine with a datapath of transitions is based on an algorithm for finding solutions to the algebraic synthesis problem. The paper proposes modified versions of previously known algorithms for finding such solutions, based on the use of the “multiprocessing” module of the Python language. The software implementation of these algorithms has proven that such an approach is generally better than a single-process search for state encoding variants, since it allows finding better solutions (solutions with fewer uncovered transitions) in the same time. The disadvantage of the proposed algorithms can be considered the use of more computer resources, which can negatively affect energy consumption