Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70232510.17587/it.30.571-578ArticlesСтатьиConference Report, Theses of ReportMatrix model of deterministic synchronous cellular automataМоделирование синхронных детерминированных клеточных автоматов матрицамиMatolyginaN. A.МатолыгинаН. А.
Russian Federation

Laboratory Assistant

лаборант

nat.shalyapina@gmail.comGromovM. L.ГромовМ. Л.
Russian Federation

PhD, Associate Professor

канд. физ.-мат. наук, доц.

gromov@mail.tsu.ruTomsk State UniversityНациональный исследовательский Томский государственный университет151120243011Информационные технологии5715780702202607022026Copyright ©; 2024, Informacionnye TehnologiiCopyright ©; 2024, Информационные технологии2024Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702325

The paper presents an approach for modeling deterministic synchronous cellular automata by matrices and operations on them. It is proposed to renumber the states of the automaton and write down a matrix, the elements of which are the current states (numbers associated with them) of the cells of the automaton. It is proposed to calculate the matrix of cell states in the next cycle in two stages: find the convolution of the current matrix with a special core, and map the resulting convolution matrix into the matrix of cell states in the next cycle. The convolution core is determined by the cell neighborhood pattern, and the convolution mapping to the matrix of the following states is based on the transition function of the automaton.

Представлен подход для моделирования детерминированных синхронных автоматов матрицами и операциями над ними. Предлагается перенумеровать состояния автомата и записать матрицу, элементы которой — текущие состояния (привязанные к ним числа) клеток автомата. Вычисление матрицы состояний клеток на следующем такте предлагается выполнять в два этапа: найти свертку текущей матрицы со специальным ядром и отобразить полученную матрицу-свертку в матрицу состояний клеток на следующем такте. Ядро свертки определяется шаблоном соседства клеток, а отображение свертки в матрицу следующих состояний строится по функции переходов автомата.

cellular automatonmatrixmatrix convolutionmathematical modelingклеточный автоматматрицасвертка матрицматематическое моделированиеThe work was carried out with the financial support of the Russian Foundation for Basic Research within the framework of the scientific project No. 20-31-90070 Graduate Students.Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 20-31-90070 Аспиранты.Von Neumann J. Theory of Self-reproducing Automata, Urbana and London, University of Illinois Press, 1966, 403 p.Von Neumann J. Theory of Self-reproducing Automata. Urbana and London: University of Illinois Press, 1966, 403 p.Toffolli T. Cellular Automata Machines, Cambridge, Massachusetts and London, The MIT Press, 1987, 279 p.Toffolli T., Margolus N. Cellular Automata Machines. Cambridge, Massachusetts and London: The MIT Press, 1987, 279 p.Hardy J., Pomeau Y., de Pazzis O. 2D Lattice-Gas model, J. Math. Phys., 1973, no. 14, pp. 1746.Hardy J., Pomeau Y., de Pazzis O. 2D Lattice-Gas model // J. Math. Phys. 1973. N. 14. P. 1746.Bandman O. L. The method of constructing cellular automaton models of the processes of formation of stable structures, Priklandaya diskretnaya matematika, 2010, no. 4, pp. 91—99 (in Russian).Бандман О. Л. Метод построения клеточно-автоматных моделей процессов формирования устойчивых структур // Прикладная дискретная математика. 2010. № 4. С. 91—99.Medvedev Yu. G. Application of a cellular automaton model of viscous fluid flow in the study of three-dimensional porous media, Avtometriya, 2006, vol. 42, no. 3, pp. 21—31 (in Russian).Медведев Ю. Г. Применение клеточно-автоматной модели потока вязкой жидкости в исследовании трехмерных пористых сред // Автометрия. 2006. Т. 42, № 3. С. 21—31.Malinetskii G. G., Stepantsov M. E. Simulation of diffusion processes using cellular automata with Margolus neighborhood, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 1999, vol. 38, no. 6, pp. 1017—1020 (in Russian).Малинецкий Г. Г., Степанцов М. Е. Моделирование диффузионных процессов с помощью клеточных автоматов с окрестностью // Журнал вычислительной математики и математической физики. 1999. Т. 38, № 6. С. 1017—1020.Ochoa Bique A. O., Goryunov A. G., Manenti F. A comparison of simulation techniques for uranium crystallization process, Chemical engineering transactions, 2015, vol. 43, pp. 793—798.Ochoa Bique A. O., Goryunov A. G., Manenti F. A comparison of simulation techniques for uranium crystallization process // Chemical engineering transactions. 2015. Vol. 43. P. 793—798.Batani D., Biava S., Bittanti S., Previdi F. A cellular automaton model of laser—plasma interactions, Laser and Particle Beams, 2001, vol. 19, iss. 04, pp. 631—642.Batani D., Biava S., Bittanti S., Previdi F. A cellular automaton model of laser—plasma interactions // Laser and Particle Beams. 2001. Vol. 19, Iss. 04. P. 631—642.Zhang L., Shiri S., Garoni T. M. A Study of Aggregated Speed in Road Networks Using Cellular Automata, Lecture Notes in Computer Science, 2014, vol. 8751, pp. 596—605.Zhang L., Shiri S., Garoni T. M. A Study of Aggregated Speed in Road Networks Using Cellular Automata // ACRI 2014. Lecture Notes in Computer Science. 2014. Vol. 8751. P. 596—605.Sabelfeld K. K., Kireeva A. A. Parallel implementation of a stochastic cellular automaton model of electron and hole recombination in 2D and 3D inhomogeneous semiconductors, Vestnik YuUrGU. Seriya: Vychislitelnaya matematika i informatika, 2017, vol. 6, no 1, pp. 87—103.Сабельфельд К. К., Киреева А. Е. Параллельная реализация стохастической клеточно-автоматной модели рекомбинации электронов и дырок в 2D и 3D неоднородных полупроводниках // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2017. Т. 6, № 1. С. 87—103.Gibson M., Keedwell Ed., Savic D. An investigation of the efficient implementation of Cellular Automata on multi-core CPU and GPU hardware, Journal of Parallel and Distributed Computing, 2015, vol. 77, pp. 11—25.Gibson M., Keedwell Ed., Savic D. An investigation of the efficient implementation of Cellular Automata on multi-core CPU and GPU hardware // Journal of Parallel and Distributed Computing. 2015. Vol. 77. P. 11—25.Szkoda S., Koza Z., Tykierko M. Accelerating cellular automata simulations using AVX and CUDA, ARXIV, 2012, URL: https://arxiv.org/abs/1208.2428 (access date: 02.08.2024).Szkoda S., Koza Z., Tykierko M. Accelerating cellular automata simulations using AVX and CUDA // ARXIV. 2012. [Электронный ресурс]. URL: https://arxiv.org/abs/1208.2428 (дата обращения: 02.08.2024).Shalyapina N. A., Gromov M. L. "LIFE" in tensors: modeling cellular automata using video cards, Trudy ISP RAN, 2019, vol. 31, iss. 3, pp. 217—228, doi: 10.15514/ISPRAS-2019-31(3)-17 (in Russian).Шаляпина Н. А., Громов М. Л. "ЖИЗНЬ" в тензорах: моделирование клеточных автоматов с помощью видеокарт // Труды ИСП РАН. 2019. Т. 31, Вып. 3. С. 217—228. DOI: 10.15514/ISPRAS-2019-31(3)-17.14. Subbotina A. Yu., Khokhlov N. I. Implementation of cellular automata "the game of Life" and the Kohomoto—Oono cellular automaton using technology MPI, Komputirnye issledovania i modelirovanie, 2010, vol. 2, no. 3, pp. 319—322 (in Russian).Субботина А. Ю., Хохлов Н. И. Реализация клеточных автоматов "игра "Жизнь"" и клеточного автомата Кохомото—Ооно с применением технологии MPI // Компьютерные исследования и моделирование. 2010. Т. 2, № 3. С. 319—322Kalgin K. V. Parallel implementation of asynchronous cellular automata on a 32-core computer system, Sibirskii zhurnal vychislitelnoi matematiki, 2012, vol. 15, no. 1, pp. 55—65 (in Russian).Калгин К. В. Параллельная реализация асинхронных клеточных автоматов на 32-ядерной вычислительной системе // Сибирский журнал вычислительной математики. 2012. Т. 15, № 1. С. 55—65.Szkoda S., Koza Z., Tykierko M. Multi-GPGPU Cellular Automata Simulations using OpenACC, Zenodo, 2014, pp. 1—6.Szkoda S., Koza Z., Tykierko M. Multi-GPGPU Cellular Automata Simulations using OpenACC // Zenodo. 2014. P.1—6.Malyshkin V. Active Knowledge, LuNA and Literacy for Oncoming Centuries, Lecture Notes in Computer Science, 2015, vol. 9465, pp. 292—303.Malyshkin V. Active Knowledge, LuNA and Literacy for Oncoming Centuries // LNCS. 2015. Vol. 9465. P. 292—303.Perepelkin V. A. LuNA system for automatic construction of numerical parallel programs for multicomputers, Problems of Informatics, 2022, no 1, pp. 1—9.Perepelkin V. A. LuNA system for automatic construction of numerical parallel programs for multicomputers // Problems of Informatics. 2022. N. 1. P. 1—9.Markova V. P., Ostapkevich M. B. The comparison of MPI and LuNA capabilities using the implementation of cellular automata wave interference, Problems of Informatics, 2017, no. 2, pp. 53—64.Markova V. P., Ostapkevich M. B. The comparison of mpi and LuNA capabilities using the implementation of cellular automata wave interference // Problems of Informatics. 2017. N. 2. P. 53—64.Matolygina N. A., Gromov M. L., Matolygin A. K. Application of the tensor approach to the software implementation of the cellular automaton flow model, Problemy informatiki, 2023, no. 2, pp. 74—85 (in Russian).20. Матолыгина Н. А., Громов М. Л., Матолыгин А. К. Применение тензорного подхода к программной реализации клеточно-автоматной модели потока // Проблемы информатики. 2023. № 2. С. 74—85.Gromov M., Shalyapina N., Matolygin A. Representation of Particle Shift in the FHP Model by TensorFlow Operations, Proceedings of International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), 2019, pp. 90—92.Gromov M., Shalyapina N., Matolygin A. Representation of Particle Shift in the FHP Model by TensorFlow Operations // Proceedings of International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). 2019. P. 90—92.Matolygin A. K., Shalyapina N. A., Gromov M. L., Torgaev S. N. Tensor approach to software implementation of cellular automata model of diffusion, J. Phys.: Conf. Ser., 2020, vol. 1680, pp. 1—6.Matolygin A. K., Shalyapina N. A., Gromov M. L., Torgaev S. N. Tensor approach to software implementation of cellular automata model of diffusion // J. Phys.: Conf. Ser. 2020. Vol. 1680. P. 1—6.TensorFlow, URL: https://www.tensorflow.org (access date: 01.08.2024).TensorFlow [Электронный ресурс]. URL: https://www. tensorflow.org (дата обращения: 01.08.2024).Moore E. F. Gedanken-experiments on sequential machines, Automata Studies, ed. C. Shannon and J. McCarthy, Princeton, Princeton University Press, 1956, vol. 34, pp. 129—153.Moore E. F. Gedanken-experiments on sequential machines, in C. Shannon and J. McCarthy ed // Automata Studies. 1956. Vol. 34. P. 129—153.Gardner M. The fantastic combinations of John Conway’s new solitaire game "Life", Scientific American, 1970, vol. 223, no. 4, pp. 120—123.Gardner M. The fantastic combinations of John Conway’s new solitaire game "Life" // Scientific American. 1970. Vol. 223, N. 4. P. 120—123.Domasevich M. A., Rubtsov S. E., Pavlova A. V. Implementation of KA models of physical processes on triangulation grids, Ekologicheskii vestnik nauchnykh tsentrov ChES, 2020, vol. 17, no. 3, pp. 13—21 (in Russian).М. А., Рубцов С. Е., Павлова А. В. Реализация КА-моделей физических процессов на триангуляционных сетках // Экологический вестник научных центров ЧЭС. 2020. Т. 17, № 3. С. 13—21.Frisch U., Hasslacher B., Pomeau Y. Lattice-Gas automata for Navier-Stokes equations, Phys. Rev. Lett., 1986, vol. 56, no. 14, pp. 1505—1508.Frisch U., Hasslacher B., Pomeau Y. Lattice-Gas automata for Navier-Stokes equations // Phys. Rev. Lett. 1986. Vol. 56, N. 14. P. 1505—1508.