The problem of a low-power assignment of the partial states of a parallel automaton is considered. A method to solve that problem is suggested that provides minimizing the number of memory elements in the implementing circuit of the automaton and minimization of their switching activity. The problem is reduced to finding a minimal weighted cover of a graph with its complete bipartite sub-graphs (bi-cliques).
Download file
Counter downloads: 43
- Title Low power assignment of partial states of a parallel automaton
- Headline Low power assignment of partial states of a parallel automaton
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 56
- Date:
- DOI 10.17223/20710410/56/7
Keywords
parallel automaton, partial state, state assignment, complete bipartite sub-graph, weighted cover problemAuthors
References
Muroga S. VLSI System Design. When and How to Design Very-Large-Scale Integrated Circuits. N.Y., John Wiley & Sons, 1982.
Pedram M. Power minimization in IC design: Principles and applications. ACM Trans. Design Automat. Electron. Syst., 1996, vol. 6, pp. 3-56.
Kashirova L., Keevallik A., and Meshkov M. State assignment of finite state machine for decrease of power dissipation. Second Intern. Conf. CAD DD’97, Minsk, Republic of Belarus, November 12-14, 1997. Minsk, NASB, Institute of Engineering Cybernetics, 1997, vol. 1, pp. 60-67.
Sudnitson A. Partition search for FSM low power synthesis. Fourth Intern. Conf. CAD DD’2001, Minsk, November 14-16, 2001. Minsk, NASB, Institute of Engineering Cybernetics, 2001, vol. 1, pp. 44-49.
Zakrevskiy A. D. Algoritmy energosberegayushchego kodirovaniya sostoyaniy avtomata [Algorithms for low power state assignment of an automaton]. Informatika, 2011, no. 1(29), pp. 68-78. (in Russian)
Pottosin Yu. V. Kodirovanie sostoyaniy diskretnogo avtomata, orientirovannoe na umen’shenie energopotrebleniya realizuyushchey skhemy [State assignment in a discrete automaton targeting an implementing low power circuit]. Prikladnaya Diskretnaya Matematika, 2011, no.4(14), pp.62-71. (in Russian)
Pottosin Yu. V. Energosberegayushchee protivogonochnoe kodirovanie sostoyaniy asinkhronnogo avtomata [Low power race-free state assignment of an asynchronous automaton]. Informatika, 2015, no. 2(46), pp. 94-101. (in Russian)
Pottosin Yu. Race-free state assignment for low power asynchronous automaton. Further Improvements in the Boolean Domain. Ed. B. Steinbach. Cambridge Scholars Publ., 2018, pp.253-267.
Pottosin Yu. Optimal state assignment of synchronous parallel automata. Design of Embedded Control Systems. Eds. M. A. Adamski, A. Karatkevich, and M. Wegrzyn. N.Y., Springer, 2005, pp.111-124.
Zakrevskiy A. D. Parallel’nye Algoritmy Logicheskogo Upravleniya [Parallel Algorithms for Logical Control]. Moscow, URSS, 2003, 304p. (in Russian)
Peterson J. L. Petri Net Theory and the Modeling of Systems. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981.
Zakrevskiy A. D., Pottosin Yu. V., and Cheremisinova L. D. Design of Logical Control Devices. Tallinn, TUT Press, 2009.
Zakrevskiy A. D., Pottosin Yu. V., and Cheremisinova L. D.Combinatorial Algorithms of Discrete Mathematics. Tallinn, TUT Press, 2008.
Pottosin Yu. V. Kombinatornye Zadachi v Logicheskom Proektirovanii Diskretnykh Ustroystv [Combinatorial Problems in Logical Design of Discrete Devices]. Minsk, Belaruskaja Navuka, 2021, 175 p. (in Russian)
Zakrevskiy A. D. Optimizatsiya pokrytiy mnozhestv [Optimization of set covering]. Logicheskiy Yazyk dlya Predstavleniya Algoritmov Sinteza Releynykh Ustroystv [Logical Language for Representation of Algorithms for Relay Devices Synthesis]. Ed. M. A. Gavrilov. Moscow, Nauka, 1966, pp. 136-148. (in Russian)
Low power assignment of partial states of a parallel automaton | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 56. DOI: 10.17223/20710410/56/7
Download full-text version
Counter downloads: 114