Joint low power state assignment of sequential automata of a net implementing a parallel automaton
https://doi.org/10.37661/1816-0301-2023-20-1-75-90
Abstract
Objectives. The problem of low power state assignment of partial states of a parallel automaton is considered. The objective of the paper is to investigate the possibilities of using the decomposition in state assignment of partial states in order to decrease the task dimension.
Methods. Parallel automaton is decomposed into a net of sequential automata whose states are assigned then with ternary vectors. The method for assignment uses searching for a maximal cut in a weighted graph that represents pairs of states connected by transitions. The edge weights of the graph are the values related to the probabilities of transitions.
Results. A method to construct a net of sequential automata that realizes the given parallel automaton is described. The probabilities of transitions between sets are calculated by means of solving a system of linear equations according to the Chapmann – Kolmogorov method. The values of inner variables assigned to the states of every component sequential automaton are obtained from two-block partitions of its set of states that are determined by the cuts of corresponding transition graph.
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. Muroga S. VLSI System Design: When and How to Design Very-Large-Scale Integrated Circuits, 1st edition. Wiley, 1982, 496 р.
2. Pedram M. Power minimization in IC design: Principles and applications. ACM Transactions on Design Automation of Electronic Systems, 1996, vol. 1, pp. 3–56.
3. 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.
4. Sudnitson A. Partition search for FSM low power synthesis. Fourth International Conference ComputerAided Design of Discrete Devices (CAD DD’2001), Minsk, Republic of Belarus, 14–16 November 2001. Minsk, Institute of Engineering Cybernetics of the National Academy of Sciences of Belarus, 2001, vol. 1, pp. 44–49.
5. Zakrevskij A. D. Algorithms for low power state assignment of an automaton. Informatika [Informatics], 2011, no. 1(29), pp. 68–78 (In Russ.).
6. 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.).
7. Pottosin Yu. V. Low power race-free state assignment of an asynchronous automaton. Informatika [Informatics], 2015, no. 2(46), pp. 94–101 (In Russ.).
8. Pottosin Yu. Race-free state assignment for low power asynchronous automaton. Further Improvements in the Boolean Domain. In B. Steinbach (ed.). Cambridge Scholars Publishing, 2018, pp. 253–267.
9. 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.
10. Pottosin Yu. Optimal state assignment of synchronous parallel automata. Design of Embedded Control Systems. New York, Springer, 2005, pp. 111–124.
11. Zakrevskij A. D. Parallel’nye algoritmy logicheskogo upravleniya. Parallel Algorithms for Logical Control. Moscow, URSS, 2003, 304 p. (In Russ.).
12. Peterson J. L. Petri Net Theory and the Modeling of Systems, 1st edition. Prentice Hall, 1981, 290 р.
13. 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.).
14. Zakrevskij A. D. Block partial state assignment of automata that implement parallel algorithms for logical control. Izvestija Akademii nauk Sojuza Sovetskih Socialisticheskih Respublik. Tehnicheskaja kibernetika [Proceedings of the Academy of Sciences of the Union of Soviet Socialist Republics. Technical Cybernetics], 1983, no. 5, pp. 3–11 (In Russ.).
15. 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.).
16. 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.).
17. 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.).
18. Solov’yov V. V. Proektirovanie cifrovyh sistem na osnove programmiruemyh logicheskih integral’nyh shem. The Design of Digital Systems Based on Programmable Logical Integrated Circuits. Moscow, Goryachaya linia – Telekom, 2001, 636 p. (In Russ.).
19. Piguet C. Low-power and low-voltage CMOS digital design. Microelectronic Engineering, 1997, no. 39, pp. 179–208.
20. Hartmanis J., Stearns R.E. Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N. J. Prentice Hall Inc., 1966, 208 p.
21. Keevallik A. Decomposition theorem of finite automata. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1974, no. 1, pp. 17–24 (In Russ.).
22. Kovalyov A. V. About finding parallelism relation on the set of positions of a subclass of Petri nets. Vesci Akadjemii navuk Belaruskaj Saveckaj Sacyjalіstychnaj Rjespublіkі. Seryja fizika-matjematychnyh navuk [Proceedings of the Academy of Sciences of the Belarusian Soviet Socialist Republic. Physics and Mathematics Series], 1989, no. 2, pp. 106–110 (In Russ.).
23. Zakrevskij A. D. Graph coloring during the decomposition of Boolean functions. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 2000, iss. 5, pp. 83–97 (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.
Review
For citations:
Pottosin Yu.V. Joint low power state assignment of sequential automata of a net implementing a parallel automaton. Informatics. 2023;20(1):75-90. (In Russ.) https://doi.org/10.37661/1816-0301-2023-20-1-75-90
Views: 273
Email this article 