informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2023-20-1-75-90inform-1230Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNСовместное энергосберегающее кодирование состояний последовательных автоматов сети, реализующей параллельный автоматJoint low power state assignment of sequential automata of a net implementing a parallel automatonПоттосинЮ. В.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 Belarus2023290320232017590Copyright © Поттосин Ю.В., 20232023Поттосин Ю.В.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/1230Цели

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

Методы

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

Результаты

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

Заключение

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

Objectives

Objectives. The problem of low power state assignment of partial states of a parallel automaton is considered. The objective of the paper is to investigate the possibilities of using the decomposition in state assignment of partial states in order to decrease the task dimension.

Methods

Methods. Parallel automaton is decomposed into a net of sequential automata whose states are  assigned then with ternary vectors. The method for assignment uses searching for a maximal cut in a weighted graph that represents pairs of states connected by transitions. The edge weights of the graph are the values  related to the probabilities of transitions.

Results

Results. A method to construct a net of sequential automata that realizes the given parallel automaton is  described. The probabilities of transitions between sets are calculated by means of solving a system of linear equations according to the Chapmann – Kolmogorov method. The values of inner variables assigned to the states of every component sequential automaton are obtained from two-block partitions of its set of states that are determined by the cuts of corresponding transition graph.

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 automatatransition graphprobability of transition between statesReferencesМурога, С. Системное проектирование сверхбольших интегральных схем : в 2-х кн. / С. Мурога. – М. : Мир, 1985. – Кн. 1. – 288 с.Muroga S. VLSI System Design: When and How to Design Very-Large-Scale Integrated Circuits, 1st edition. Wiley, 1982, 496 р.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.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 NASB, 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, Republic of Belarus, 14–16 Nov. 2001. – Minsk : Institute of Engineering Cybernetics of the NASB, 2001. – Vol. 1. – P. 44–49.Sudnitson A. Partition search for FSM low power synthesis. Fourth International Conference ComputerAided Design of Discrete Devices (CAD DD’2001), Minsk, Republic of Belarus, 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. In B. Steinbach (ed.). 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.Закревский, А. Д. Параллельные алгоритмы логического управления / А. Д. Закревский. – М. : УРСС, 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. L. Petri Net Theory and the Modeling of Systems, 1st 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 Sojuza Sovetskih Socialisticheskih Respublik. Tehnicheskaja kibernetika [Proceedings of the Academy of Sciences of the Union of Soviet Socialist Republics. Technical 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.).Поттосин, Ю. В. Комбинаторные задачи в логическом проектировании дискретных устройств / Ю. В. Поттосин. – Минск : Беларус. навука, 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.).Соловьев, В. В. Проектирование цифровых систем на основе программируемых логических интегральных схем / В. В. Соловьев. – М. : Горячая линия – Телеком, 2001. – 636 с.Solov’yov V. V. Proektirovanie cifrovyh sistem na osnove programmiruemyh logicheskih integral’nyh shem. The Design of Digital Systems Based on Programmable Logical Integrated Circuits. Moscow, Goryachaya linia – Telekom, 2001, 636 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.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, N. J. 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 Akadjemii navuk Belaruskaj Saveckaj Sacyjalіstychnaj Rjespublіkі. Seryja fizika-matjematychnyh navuk [Proceedings of the Academy of Sciences of the Belarusian Soviet Socialist Republic. Physics and Mathematics Series], 1989, no. 2, pp. 106–110 (In Russ.).Закревский, А. Д. Раскраска графов при декомпозиции булевых функций / А. Д. Закревский // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5. – С. 83–97.Zakrevskij A. D. Graph coloring during the decomposition of Boolean functions. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 2000, iss. 5, pp. 83–97 (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.

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