Decomposition of a parallel automaton into a net of sequential automata and low power state assignment of them at asynchronous implementation
https://doi.org/10.37661/1816-0301-2024-21-3-7-22
Abstract
Objectives. The problems of decomposition of a parallel automaton into a net of sequential automata at synchronous realization and low power race free state assignment of them are considered. The objective of the paper is to investigate the possibilities of applying decomposition in state assignment of partial states in order to decrease the problem dimension taking into account the peculiar properties of the asynchronous realization.
Methods. The given parallel automaton is decomposed into a net of sequential asynchronous automata whose states are assigned then with ternary vectors. The power consumption lowering of the designed device is achieved by lowering the intensity of its memory elements switching that is appreciated by probabilities of transitions between the states of the automaton. The state assignment is reduced to the problem of minimal weighted cover. The probabilities of transitions between sets are calculated by means of solving a system of linear equations according to the Chapmann – Kolmogorov method.
Results. A method to construct a net of sequential asynchronous automata that realizes the given parallel automaton is described. The paper touches upon the problem of minimization of interconnections in the net.
Conclusion. Applying parallel automaton decomposition allows decreasing the dimension of the laborious problem of state assignment. The proposed method is intended for application in computer aided systems for design of discrete devices.
About the Author
Yu. V. Pottosin
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Yuri V. Pottosin, Ph. D. (Phys.-Math.), Leading Researcher
st. Surganova, 6, Minsk, 220012
References
1. Zakrevskij A. D. Parallel’nye algoritmy logicheskogo upravleniya. Parallel Algorithms for Logical Control. Moscow, URSS, 2003, 304 p. (In Russ.).
2. Peterson J. Petri Net Theory and the Modeling of Systems; first edition. Prentice Hall, 1981, 290 р.
3. Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals of Discrete Devices Design. Moscow, Fizmatlit, 2007, 592 p. (In Russ.).
4. Zakrevskij A. D. Block partial state assignment of automata that implement parallel algorithms for logical control. Izvestija Akademii nauk SSSR. Tehnicheskaja kibernetika [Proceedings of the Academy of Sciences of the USSR. Engineering Cybernetics], 1983, no. 5, pp. 3–11 (In Russ.).
5. Cheremisinova L. D. Implementation of parallel algorithms for logical control by asynchronous automata. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1985, no. 2, pp. 65–69 (In Russ.).
6. Pottosin Yu. V. A decomposition method for state assignment of a parallel automaton. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1987, no. 1, pp. 84–91 (In Russ.).
7. Muroga C. Sistemnoye proektirovanie sverhbol’shih integral’nyh shem : v dvuh knigah. System Design of Super Large Integrated Circuits : In 2 Issues. Moscow, Mir, 1985, iss. 1, 288 p. (In Russ.).
8. Pedram M. Power minimization in IC design: Principles and applications. ACM Transactions on Design Automation of Electronic Systems, 1996, vol. 1, pp. 3–56.
9. Kashirova L., Keevallik A., Meshkov A. M. State assignment of finite state machine for decrease of power dissipation. Second International Conference Computer-Aided Design of Discrete Devices, CAD DD’97, Minsk, Republic of Belarus, 12–14 November 1997. Minsk, Institute of Engineering Cybernetics of the National Academy of Sciences of Belarus, 1997, vol. 1, pp. 60–67.
10. Sudnitson A. Partition search for FSM low power synthesis. Fourth International Conference Computer-Aided Design of Discrete Devices, CAD DD’2001, Minsk, 14–16 November 2001. Minsk, Institute of Engineering Cybernetics of the National Academy of Sciences of Belarus, 2001, vol. 1, pp. 44–49.
11. Zakrevskij A. D. Algorithms for low power state assignment of an automaton. Informatika [Informatics], 2011, no. 1(29), pp. 68–78 (In Russ.).
12. Pottosin Yu. V. State assignment of a discrete automaton to decrease power consumption of the implementing circuit. Prikladnaya diskretnaya matematika [Discrete Applied Mathematics], 2011, no. 4(14), pp. 62–71 (In Russ.).
13. Pottosin Yu. V. Low power race-free state assignment of an asynchronous automaton. Informatika [Informatics], 2015, no. 2(46), pp. 94–101 (In Russ.).
14. Pottosin Yu. Race-free state assignment for low power asynchronous automaton. Further Improvements in the Boolean Domain. Ed. B. Steinbach. Cambridge Scholars Publishing, 2018, pp. 253–267.
15. Pottosin Yu. V. Low power assignment of partial states of a parallel automaton. Prikladnaya diskretnaya matematika [Discrete Applied Mathematics], 2022, no. 56, pp. 113–122.
16. Pottosin Yu. Optimal state assignment of synchronous parallel automata. Design of Embedded Control Systems. New York, Springer, 2005, pp. 111–124.
17. Pottosin Yu. V. Joint low power state assignment of sequential automata that form a net implementing a parallel automaton. Informatika [Informatics], 2023, vol. 20, no. 1, pp. 75−90 (In Russ.).
18. Pottosin Yu. V. Kombinatornye zadachi v logicheskom proektirovanii diskretnyh ustrojstv. Combinatorial Problems in Logical Design of Discrete Devices. Minsk, Belaruskaya navuka, 2021, 175 p. (In Russ.).
19. Piguet C. Low-power and low-voltage CMOS digital design. Microelectronic Engineering, 1997, no. 39, pp. 179–208.
20. Yakubajtis E. A. Asinhronnye logicheskie avtomaty. Asynchronous Logical Automata. Riga, Zinatne, 1966, 380 p. (In Russ.).
21. Hartmanis J., Stearns R. E. Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, New Jersey, Prentice Hall Inc., 1966, 208 p.
22. Keevallik A. Decomposition theorem of finite automata. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1974, no. 1, pp. 17–24 (In Russ.).
23. Kovalyov A. V. About finding parallelism relation on the set of positions of a subclass of Petri nets. Vesci Akademii nauk Belaruskaj SSR. Seria fizika-matematichnyh navuk [Proceedings of the Academy of Sciences of Byelorussian SSR. Series of Physico-Mathematical Sciences], 1989, no. 2, pp. 106–110 (In Russ.).
24. Macii E., Pedram M., Somenzi F. High-level power modeling, estimation and optimization. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, 1998, vol. 17, no. 11, pp. 1061–1079.
25. Zakrevskij A. D. Optimization of set covers. Logicheskij yazyk dlya predstavlenia algoritmov sinteza relejnyh ustrojstv [Logical Language for Presenting Algorithms for Synthesis of Relay Devices], Moscow, Nauka, 1966, pp. 136–148 (In Russ.).
26. Pottosin Yu. V., Toropov N. R., Shestakov E. A. A method for minimizing a system of completely specified Boolean functions. Informatika [Informatics], 2008, no. 2(18), pp. 102–110 (In Russ.).
Review
For citations:
Pottosin Yu.V. Decomposition of a parallel automaton into a net of sequential automata and low power state assignment of them at asynchronous implementation. Informatics. 2024;21(3):7-22. (In Russ.) https://doi.org/10.37661/1816-0301-2024-21-3-7-22
Views: 236
Email this article 