informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2024-21-3-7-22inform-1297Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNДекомпозиция параллельного автомата в сеть последовательных автоматов и энергосберегающее кодирование их состояний при асинхронной реализацииDecomposition of a parallel automaton into a net of sequential automata and low power state assignment of them at asynchronous implementationПоттосинЮ. В.PottosinYu. V.

Поттосин Юрий Васильевич, кандидат физико-математических наук, ведущий научный сотрудник

ул. Сурганова, 6, Минск, 220012

Yuri V. Pottosin, Ph. D. (Phys.-Math.), Leading Researcher

st. Surganova, 6, Minsk, 220012

pott@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus202430092024213722Copyright © Поттосин Ю.В., 20242024Поттосин Ю.В.Pottosin Y.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1297Цели

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

Методы

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

Результаты

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

Заключение

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

Objectives

Objectives. The problems of decomposition of a parallel automaton into a net of sequential automata at synchronous realization and low power race free state assignment of them are considered. The objective of the paper is to investigate the possibilities of applying decomposition in state assignment of partial states in order to decrease the problem dimension taking into account the peculiar properties of the asynchronous realization.

Methods

Methods. The given parallel automaton is decomposed into a net of sequential asynchronous automata whose states are assigned then with ternary vectors. The power consumption lowering of the designed device is achieved by lowering the intensity of its memory elements switching that is appreciated by probabilities of transitions between the states of the automaton. The state assignment is reduced to the problem of minimal weighted cover. The probabilities of transitions between sets are calculated by means of solving a system of linear equations according to the Chapmann – Kolmogorov method.

Results

Results. A method to construct a net of sequential asynchronous automata that realizes the given parallel automaton is described. The paper touches upon the problem of minimization of interconnections in the net.

Conclusion

Conclusion. Applying parallel automaton decomposition allows decreasing the dimension of the laborious problem of state assignment. The proposed method is intended for application in computer aided systems for design of discrete devices.

параллельный автоматчастичное состояниедекомпозиция автоматовкодирование состояний автоматавероятность перехода между состояниямивзвешенное покрытиеparallel automatonpartial statedecomposition of automatastate assignment of automataprobability of transition between statesweighted coverReferencesЗакревский, А. Д. Параллельные алгоритмы логического управления / А. Д. Закревский. – М. : УРСС, 2003. – 304 с.Zakrevskij A. D. Parallel’nye algoritmy logicheskogo upravleniya. Parallel Algorithms for Logical Control. Moscow, URSS, 2003, 304 p. (In Russ.).Питерсон, Дж. Теория сетей Петри и моделирование систем : пер. с англ. / Дж. Питерсон. – М. : Мир, 1984. – 264 с.Peterson J. Petri Net Theory and the Modeling of Systems; first edition. Prentice Hall, 1981, 290 р.Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals of Discrete Devices Design. Moscow, Fizmatlit, 2007, 592 p. (In Russ.).Закревский, А. Д. Блочное кодирование частичных состояний у автоматов, реализующих параллельные алгоритмы логического управления / А. Д. Закревский // Изв. АН СССР. Техническая кибернетика. – 1983. – № 5. – С. 3–11.Zakrevskij A. D. Block partial state assignment of automata that implement parallel algorithms for logical control. Izvestija Akademii nauk SSSR. Tehnicheskaja kibernetika [Proceedings of the Academy of Sciences of the USSR. Engineering Cybernetics], 1983, no. 5, pp. 3–11 (In Russ.).Черемисинова, Л. Д. Реализация асинхронными автоматами параллельных алгоритмов логического управления / Л. Д. Черемисинова // Автоматика и вычислительная техника. – 1985. – № 2. – С. 65–69.Cheremisinova L. D. Implementation of parallel algorithms for logical control by asynchronous automata. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1985, no. 2, pp. 65–69 (In Russ.).Поттосин, Ю. В. Декомпозиционный метод кодирования состояний параллельного автомата / Ю. В. Поттосин // Автоматика и вычислительная техника. – 1987. – № 1. – С. 84–91.Pottosin Yu. V. A decomposition method for state assignment of a parallel automaton. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1987, no. 1, pp. 84–91 (In Russ.).Мурога, С. Системное проектирование сверхбольших интегральных схем : в 2 кн. / С. Мурога. – М. : Мир, 1985. – Кн. 1. – 288 с.Muroga C. Sistemnoye proektirovanie sverhbol’shih integral’nyh shem : v dvuh knigah. System Design of Super Large Integrated Circuits : In 2 Issues. Moscow, Mir, 1985, iss. 1, 288 p. (In Russ.).Pedram, M. Power minimization in IC design: Principles and applications / M. Pedram // ACM Trans. Design Automat. Electron. Syst. – 1996. – Vol. 1. – P. 3–56.Pedram M. Power minimization in IC design: Principles and applications. ACM Transactions on Design Automation of Electronic Systems, 1996, vol. 1, pp. 3–56.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.Kashirova L., Keevallik A., Meshkov A. M. State assignment of finite state machine for decrease of power dissipation. Second International Conference Computer-Aided Design of Discrete Devices, CAD DD’97, Minsk, Republic of Belarus, 12–14 November 1997. Minsk, Institute of Engineering Cybernetics of the National Academy of Sciences of Belarus, 1997, vol. 1, pp. 60–67.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.Sudnitson A. Partition search for FSM low power synthesis. Fourth International Conference Computer-Aided Design of Discrete Devices, CAD DD’2001, Minsk, 14–16 November 2001. Minsk, Institute of Engineering Cybernetics of the National Academy of Sciences of Belarus, 2001, vol. 1, pp. 44–49.Закревский, А. Д. Алгоритмы энергосберегающего кодирования состояний автомата / А. Д. Закревский // Информатика. – 2011. – № 1(29). – С. 68–78.Zakrevskij A. D. Algorithms for low power state assignment of an automaton. Informatika [Informatics], 2011, no. 1(29), pp. 68–78 (In Russ.).Поттосин, Ю. В. Кодирование состояний дискретного автомата, ориентированное на уменьшение энергопотребления реализующей схемы / Ю. В. Поттосин // Прикладная дискретная математика. – 2011. – № 4(14). – С. 62–71.Pottosin Yu. V. State assignment of a discrete automaton to decrease power consumption of the implementing circuit. Prikladnaya diskretnaya matematika [Discrete Applied Mathematics], 2011, no. 4(14), pp. 62–71 (In Russ.).Поттосин, Ю. В. Энергосберегающее противогоночное кодирование состояний асинхронного автомата / Ю. В. Поттосин // Информатика. – 2015. – № 2(46). – С. 94–101.Pottosin Yu. V. Low power race-free state assignment of an asynchronous automaton. Informatika [Informatics], 2015, no. 2(46), pp. 94–101 (In Russ.).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.Pottosin Yu. Race-free state assignment for low power asynchronous automaton. Further Improvements in the Boolean Domain. Ed. B. Steinbach. Cambridge Scholars Publishing, 2018, pp. 253–267.Pottosin, Yu. V. Low power assignment of partial states of a parallel automaton / Yu. V. Pottosin // Прикладная дискретная математика. – 2022. – № 56. – С. 113–122.Pottosin Yu. V. Low power assignment of partial states of a parallel automaton. Prikladnaya diskretnaya matematika [Discrete Applied Mathematics], 2022, no. 56, pp. 113–122.Pottosin, Yu. Optimal state assignment of synchronous parallel automata / Yu. Pottosin // Design of Embedded Control Systems. – N. Y. : Springer, 2005. – P. 111–124.Pottosin Yu. Optimal state assignment of synchronous parallel automata. Design of Embedded Control Systems. New York, Springer, 2005, pp. 111–124.Поттосин, Ю. В. Совместное энергосберегающее кодирование состояний последовательных автоматов сети, реализующей параллельный автомат / Ю. В. Поттосин // Информатика. – 2023. − Т. 20, № 1. – С. 75–90.Pottosin Yu. V. Joint low power state assignment of sequential automata that form a net implementing a parallel automaton. Informatika [Informatics], 2023, vol. 20, no. 1, pp. 75−90 (In Russ.).Поттосин, Ю. В. Комбинаторные задачи в логическом проектировании дискретных устройств / Ю. В. Поттосин. – Минск : Беларуская навука, 2021. – 175 с.Pottosin Yu. V. Kombinatornye zadachi v logicheskom proektirovanii diskretnyh ustrojstv. Combinatorial Problems in Logical Design of Discrete Devices. Minsk, Belaruskaya navuka, 2021, 175 p. (In Russ.).Piguet, C. Low-power and low-voltage CMOS digital design / C. Piguet // Microelectronic Engineering. – 1997. – No. 39. – P. 179–208.Piguet C. Low-power and low-voltage CMOS digital design. Microelectronic Engineering, 1997, no. 39, pp. 179–208.Якубайтис, Э. А. Асинхронные логические автоматы / Э. А. Якубайтис. – Рига : Зинатне, 1966. – 380 с.Yakubajtis E. A. Asinhronnye logicheskie avtomaty. Asynchronous Logical Automata. Riga, Zinatne, 1966, 380 p. (In Russ.).Hartmanis, J. Algebraic structure theory of sequential machines / J. Hartmanis, R.E. Stearns. – Englewood Cliffs, N. J. : Prentice Hall Inc., 1966. – 208 p.Hartmanis J., Stearns R. E. Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, New Jersey, Prentice Hall Inc., 1966, 208 p.Кээваллик, А. Э. Теорема декомпозиции конечных автоматов / А. Э. Кээваллик // Автоматика и вычислительная техника. – 1974. – № 1. – С. 17–24.Keevallik A. Decomposition theorem of finite automata. Avtomatika i vychislinel’naya tehnika [Automation and Computer Engineering], 1974, no. 1, pp. 17–24 (In Russ.).Ковалев, А. В. О нахождении отношения параллельности на множестве мест одного подкласса сетей Петри / А. В. Ковалев // Вес. Акад. навук Беларускай ССР. Сер. фiз.-мат. навук. – 1989. – № 2. – С. 106–110.Kovalyov A. V. About finding parallelism relation on the set of positions of a subclass of Petri nets. Vesci Akademii nauk Belaruskaj SSR. Seria fizika-matematichnyh navuk [Proceedings of the Academy of Sciences of Byelorussian SSR. Series of Physico-Mathematical Sciences], 1989, no. 2, pp. 106–110 (In Russ.).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.Macii E., Pedram M., Somenzi F. High-level power modeling, estimation and optimization. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, 1998, vol. 17, no. 11, pp. 1061–1079.Закревский, А. Д. Оптимизация покрытий множеств / А. Д. Закревский // Логический язык для представления алгоритмов синтеза релейных устройств. – М. : Наука, 1966. – С. 136–148.Zakrevskij A. D. Optimization of set covers. Logicheskij yazyk dlya predstavlenia algoritmov sinteza relejnyh ustrojstv [Logical Language for Presenting Algorithms for Synthesis of Relay Devices], Moscow, Nauka, 1966, pp. 136–148 (In Russ.).Поттосин, Ю. В. Метод минимизации системы полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2008. − № 2(18). – С. 102–110.Pottosin Yu. V., Toropov N. R., Shestakov E. A. A method for minimizing a system of completely specified Boolean functions. Informatika [Informatics], 2008, no. 2(18), pp. 102–110 (In Russ.).

The authors declare that there are no conflicts of interest present.