Рассматривается задача кодирования частичных состояний параллельного автомата. Предложен метод решения, который обеспечивает минимизацию числа элементов памяти в схеме, реализующей автомат, и минимизацию интенсивности их переключений. Задача сводится к нахождению минимального взвешенного покрытия графа его полными двудольными подграфами (бикликами).
Скачать электронную версию публикации
Загружен, раз: 42
- Title Энергосберегающее кодирование частичных состояний параллельного автомата
- Headline Энергосберегающее кодирование частичных состояний параллельного автомата
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 56
- Date:
- DOI 10.17223/20710410/56/7
Ключевые слова
параллельный автомат, частичное состояние, кодирование состояний, полный двудольный подграф, задача о взвешенном покрытииАвторы
Ссылки
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)
Энергосберегающее кодирование частичных состояний параллельного автомата | Прикладная дискретная математика. 2022. № 56. DOI: 10.17223/20710410/56/7
Скачать полнотекстовую версию
Загружен, раз: 113