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

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

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

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

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

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

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

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

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

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

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

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

8. Pedram, M. Power minimization in IC design: Principles and applications / M. Pedram // ACM Trans. Design Automat. Electron. Syst. – 1996. – Vol. 1. – P. 3–56.

9. 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 National Academy of Sciences of Belarus, 1997. – Vol. 1. – P. 60–67.

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

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

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

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

14. 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.

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

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

17. Поттосин, Ю. В. Совместное энергосберегающее кодирование состояний последовательных автоматов сети, реализующей параллельный автомат / Ю. В. Поттосин // Информатика. – 2023. − Т. 20, № 1. – С. 75–90.

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

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

20. Якубайтис, Э. А. Асинхронные логические автоматы / Э. А. Якубайтис. – Рига : Зинатне, 1966. – 380 с.

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

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

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

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.

25. Закревский, А. Д. Оптимизация покрытий множеств / А. Д. Закревский // Логический язык для представления алгоритмов синтеза релейных устройств. – М. : Наука, 1966. – С. 136–148.

26. Поттосин, Ю. В. Метод минимизации системы полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2008. − № 2(18). – С. 102–110.