Совместное энергосберегающее кодирование состояний последовательных автоматов сети, реализующей параллельный автомат

Цели. Рассматривается задача энергосберегающего кодирования частичных состояний параллельного автомата.  Целью работы является исследование возможности применения приема декомпозиции при кодировании частичных состояний для снижения размерности задачи.

Методы. Заданный параллельный автомат разлагается в сеть последовательных автоматов, состояния которых кодируются затем троичными векторами. Метод кодирования использует поиск максимального разреза во взвешенном графе, представляющем пары состояний, связанных переходами. Весами ребер графа являются величины, связанные с вероятностями переходов.

Результаты. Описан способ построения сети из последовательных автоматов, реализующей заданный параллельный автомат. Вероятности переходов между состояниями вычисляются путем решения системы линейных уравнений согласно методу Чэпмена – Колмогорова. Значения внутренних переменных, кодирующих состояния каждого компонентного последовательного автомата, находятся по двухблочным разбиениям множества его состояний, которые определяются разрезами соответствующего графа переходов.

Заключение. Использование декомпозиции параллельного автомата позволяет снизить размерность трудоемкой задачи кодирования состояний. Предлагаемый метод предназначен для применения в системах автоматизированного проектирования дискретных устройств.

1. Мурога, С. Системное проектирование сверхбольших интегральных схем : в 2-х кн. / С. Мурога. – М. : Мир, 1985. – Кн. 1. – 288 с.

2. Pedram, M. Power minimization in IC design: Principles and applications / M. Pedram // ACM Transactions on Design Automation of Electronic Systems. – 1996. – Vol. 1. – P. 3–56.

3. Kashirova, L. State assignment of finite state machine for decrease of power dissipation / L. Kashirova, A. Keevallik, M. Meshkov // Second Intern. Conf. Computer-Aided Design of Discrete Devices (CAD DD’97), Minsk, Republic of Belarus, 12–14 Nov. 1997. – Minsk : Institute of Engineering Cybernetics of the NASB, 1997. – Vol. 1. – P. 60–67.

4. Sudnitson, A. Partition search for FSM low power synthesis / А. Sudnitson // Fourth Intern. Conf. Computer-Aided Design of Discrete Devices (CAD DD’2001), Minsk, Republic of Belarus, 14–16 Nov. 2001. – Minsk : Institute of Engineering Cybernetics of the NASB, 2001. – Vol. 1. – P. 44–49.

5. Закревский, А. Д. Алгоритмы энергосберегающего кодирования состояний автомата / А. Д. Закревский // Информатика. – 2011. – № 1(29). – С. 68–78.

6. Поттосин, Ю. В. Кодирование состояний дискретного автомата, ориентированное на уменьшение энергопотребления реализующей схемы / Ю. В. Поттосин // Прикладная дискретная математика. – 2011. – № 4(14). – С. 62–71.

7. Поттосин, Ю. В. Энергосберегающее противогоночное кодирование состояний асинхронного автомата / Ю. В. Поттосин // Информатика. – 2015. – № 2(46). – С. 94–101.

8. Pottosin, Yu. Race-free state assignment for low power asynchronous automaton / Yu. Pottosin // Further Improvements in the Boolean Domain / ed. B. Steinbach. – Cambridge Scholars Publishing, 2018. – P. 253–267.

9. Pottosin, Yu. V. Low power assignment of partial states of a parallel automaton / Yu. V. Pottosin // Прикладная дискретная математика. – 2022. – № 56. – С. 113–122.

10. Pottosin, Yu. Optimal state assignment of synchronous parallel automata / Yu. Pottosin // Design of Embedded Control Systems. – N. Y. : Springer, 2005. – P. 111–124.

11. Закревский, А. Д. Параллельные алгоритмы логического управления / А. Д. Закревский. – М. : УРСС, 2003. – 304 с.

12. Питерсон, Дж. Теория сетей Петри и моделирование систем / Дж. Питерсон. – М. : Мир, 1984. – 264 с.

13. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.

14. Закревский, А. Д. Блочное кодирование частичных состояний у автоматов, реализующих параллельные алгоритмы логического управления / А. Д. Закревский // Изв. АН СССР. Техническая кибернетика. – 1983. – № 5. – С. 3–11.

15. Черемисинова, Л. Д. Реализация асинхронными автоматами параллельных алгоритмов логического управления / Л. Д. Черемисинова // Автоматика и вычислительная техника. – 1985. – № 2. – С. 65–69.

16. Поттосин, Ю. В. Декомпозиционный метод кодирования состояний параллельного автомата / Ю. В. Поттосин // Автоматика и вычислительная техника. – 1987. – № 1. – С. 84–91.

17. Поттосин, Ю. В. Комбинаторные задачи в логическом проектировании дискретных устройств / Ю. В. Поттосин. – Минск : Беларус. навука, 2021. – 175 с.

18. Соловьев, В. В. Проектирование цифровых систем на основе программируемых логических интегральных схем / В. В. Соловьев. – М. : Горячая линия – Телеком, 2001. – 636 с.

19. Piguet, C. Low-power and low-voltage CMOS digital design / C. Piguet // Microelectronic Engineering. – 1997. – No. 39. – P. 179–208.

20. Hartmanis, J. Algebraic structure theory of sequential machines / J. Hartmanis, R. E. Stearns. – Englewood Cliffs, N. J. Prentice Hall Inc., 1966. – 208 p.

21. Кээваллик, А. Э. Теорема декомпозиции конечных автоматов / А. Э. Кээваллик // Автоматика и вычислительная техника. – 1974. – № 1. – С. 17–24.

22. Ковалев, А. В. О нахождении отношения параллельности на множестве мест одного подкласса сетей Петри / А. В. Ковалев // Вес. Акад. навук Беларускай ССР. Сер. фiз.-матэм. навук. – 1989. – № 2. – С. 106–110.

23. Закревский, А. Д. Раскраска графов при декомпозиции булевых функций / А. Д. Закревский // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5. – С. 83–97.

24. Macii, E. High-level power modeling, estimation and optimization / E. Macii, M. Pedram, F. Somenzi // IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems. – 1998. – Vol. 17, no. 11. – P. 1061–1079.