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

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

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

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

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

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.