Kazachanskyy A. V. The Abstract

Now in many spheres of manufacture management of technological processes by means of digital electronic systems is applied. Thus various demands are made to functioning and construction of these systems. In one branches of manufacture high speed of management of technological processes, and in others – low hardware expenses is required at construction of control systems.

In this work attempt to create structure of the finite state machines which would be optimum on hardware expenses and speed has been made. The traditional structure of the finite state machines with "rigid" logic has the highest speed among all known structures of synchronous finite state machines. But finite state machine with "rigid" logic have one big lack – an irregularity of their structure that complicates their realisation on the LSI. Finite state machines with programmed logic have more regular structure, but have thus a few of lacks: the multidirected conditional transitions in these finite state machines are performed for some steps of work; in a format of microcommands of these finite state machines it is necessary to set at least transition one address that increases word length of microcommands and, hence, capacity of operating memory.

All listed lacks of two kinds of finite state machines leave in a compositional microprogram control units (CMCU) which structure is an association of structures of the finite state machine with "rigid" logic and the finite state machine with programmed logic. Structure of CMCU is represented on fig. 1. In such structure of the finite state machine the multidirected conditional transitions are performed for one step of work of the finite state machine, the format of microcommands of such finite state machines has only an operational part and thus the structure of such finite state machine has regular character.

Figure 1. Structure of a compositional microprogram control units

Minimisation of hardware expenses at construction of finite state machines is a classical research problem in the computer science and mathematics. Researchers of Computers department in DonNTU already it is a lot of years actively are engaged in minimisation methods studying of hardware expenses at construction of finite state machines. I had been offered a method of compatible microoperations fields coding in operational part of CMCU and realisation of the Mealy finite state machine in structure of CMCU in the form of two-level MPL scheme of the finite state machine. The methods of hardware expenses minimisation offered in work in CMCU reach a task in view at insignificant fall of speed in CMCU.

The purpose of the work is synthesis and research CMCU with use of compatible microoperations fields coding in an operational part of the finite state machine and with application of two-level scheme MPL of the finite state machine in structure of CMCU. Synthesis and research of CMCU are carried out in basis of LSI. For achievement of this purpose following local problems are solved: studying of CMCU synthesis existing methods; the analysis of existing element basis of LSI; consideration of existing methods of compatible microoperations fields coding; working out of synthesis algorithms and optimisation CMCU; program realisation of the developed algorithms.

Scientific novelty of the work consists in a finding of optimum CMCU structure from the point of view of hardware expenses and speed for realisation of management algorithms with certain parameters. Law between parameters of concrete algorithms and CMCU structure on which these algorithms are realised has been found.

Practical value of the work consists in construction of CMCU in which such combination of optimisation methods of the finite state machine which was not applied earlier in relation to CMCU is applied and which allows to reach maximum optimisation of CMCU from the point of view of a parity "hardware expenses + speed". Also the computer program of CMCU synthesis and optimisation on the set entrance parameters of management algorithms has been developed.

Now there is a considerable quantity of finite state machines with various structures optimisation methods. From domestic scientists who are engaged in researches in the given area, the professor of DonNTU Computers department Barkalov A. A. is most known. Among methods of finite state machines with "rigid" logic optimisation there are synthesis methods of two-level, three-level and multilevel structures of Mealy and Moore finite state machines. Also there are methods of finite state machines realisation on counters. The set of optimisation methods of finite state machines with programmed logic and in particular optimisation methods of an operational part of these finite state machines has been developed. Several of minimisation algorithms of word length of operating memory has been developed at compatible microoperations fields coding: Schwarz's algorithm, algorithm Grasselli-Montanary, Das algorithm, algorithm of branches and borders, etc. All listed algorithms, except Schwarz's algorithm, demand a lot of time for distribution of microoperations on separate fields. But Schwarz's algorithm though is the most high-speed, does not guarantee optimum distribution of microoperations.

As a result of work performance the algorithm of definition of operational linear chains (OLC) in management algorithms has been developed. The example of OLC allocation in algorithm is represented on fig. 2.

Figure 2. An order of OLC allocation in management algorithm
(animation in volume of 230409 bytes, consists of 10 slides, frequency of shots change – 1 Hz, has a continuous cycle of repetition)

As a result of OLC allocation and synthesis of the finite state machine with programmed logic in CMCU structure the management algorithm will be transformed to a kind represented on fig. 3. In work the algorithm of management algorithm transformation has been developed.

Figure 3. Transformed an algorithm flow graph

The transformed management algorithm is realised in the form of MPL finite state machine in CMCU structure which block diagramme is represented on fig. 4.

Figure 4. Block diagramme of the MPL finite state machine

Figure 5. Developed CMCU structure

Also in work creation of the program realising all developed algorithms for synthesis of CMCU is planned.

As a result of work performance existing optimisation methods of finite state machines structures and element basis of LSI in which realisation of developed CMCU structure is planned have been analysed. Also synthesis algorithms and CMCU structure optimisation have been developed. Further software working out in which the developed methods and algorithms are realised is planned.

The Abstract

for the master qualifying work on a theme:

"Synthesis and research of compositional microprogram control units with use of a compatible microoperations fields coding method"

Introduction

Work urgency

The purposes and work problems

Prospective scientific novelty

Practical value of work

The review of existing decisions and methods

The description of the received and planned results

Conclusion

References