Cellular-automata models of natural processes, implementation on supercomputers

O. L. Bandman

Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 102-121.

Résumé

Conventional mathematical models based on differential calculus are sometimes not capable to simulate nonlinear dissipative processes on micro- or nano-level of resolution. This fact stimulates the development of new approaches to spatial dynamics simulation. Among them, cellular automata (CA) modeling is one of the promising methodologies, due to CA large simulation capability and compatibility with modern trends in supercomputer architecture. Although CA simulation is intensively studied and used in different fields, a few attention is paid to studying the parallel implementation peculiarities of large scale CA-models on supercomputers. Just this aspect of CA-simulation is the subject of the paper aiming to analyse CA-simulation methods adaptiveness to supercomputing implementation based on validity conditions requirements for different modes of CA operation. For this purpose, the concept of the operation mode well known for simple CA (having only one transition rule) is expanded for composed CA (containing many transition rules). The new concept determines a CA-transition rules execution order, which in turn determines the behavioral properties of CA-model and their influence on the simulation performance. The obtained results are illustrated by some examples, which show CA methods at work by simulating essentially nonlinear and dissipative processes: superposition of asynchronous CAs for simulation of water permeating through porous medium and parallel composition of two CAs simulating pattern formation on a heated plate. Basically, the paper generalizes CA computer simulation theoretical results and experience obtained by researchers from the Institute of Computational Mathematics and Mathematical Geophysics of Siberian Branch of Russian Academy of Sciences.

Détail

Keywords: mathematical modeling, parallel computing, cellular automata models, lattice-gas hydrodynamics
Mots-clés : reaction-diffusion processes.

Bibliographie

[1] Von Neumann J., The Theory of Self-Reproducing Automata, Mir Publ., Moscow, 1971, 384 pp. (in Russian)

[2] Wolfram S., “Computation theory of cellular automata”, Commun. Math. Phys., 96 (1984), 15–57 | DOI | MR | Zbl

[3] Sandefur J. T., Discrete Dynamical Systems: Theory and Applications, University Press, Oxford, 1990, 445 pp. | MR

[4] Donienunzio A., Formenti E., Kurka P., “Cellular automata dynamical systems”, Handbook of Natural Computing, v. 1, eds. G. Rozenberg, T. Bäck, J. N. Kok, Springer, Berlin, 2012, 24–76

[5] Wolfram S., “Statistical mechanics of cellular automata”, Rev. Mod. Phys., 35 (1983), 601–643 | DOI | MR

[6] Toffolli T., Margolus N., Cellular Automata Machines: A New Environment for Modeling, MIT-Press, USA, 1987, 260 pp.

[7] Frish U., Hasslacher B., Pomeau Y., “Lattice-gas automata for Navier–Stokes equation”, Phys. Rev. Let., 56 (1986), 1505–1508 | DOI

[8] Wolfram S., A New Kind of Science, Wolfram Media Inc., Champaign, Ill., USA, 2002, 1197 pp. | MR | Zbl

[9] Weimar J., “Cellular automata for reaction-diffusion systems”, Parallel Computing, 23:11 (1997), 1699–1715 | DOI | MR

[10] Vanag V. K., Dissipative Structures in Reaction-Diffusion Systems, Institute of Computer Science Publ., Izhevsk, 2008, 300 pp. (in Russian)

[11] Madore B., Freedman W., “Computer simulation of the Belousov–Zhabotinski reaction”, Science, 222 (1983), 615–618 | DOI

[12] Park J. K., Steiglitz K., Thurston W. P., “Soliton-like behavior in automata”, Physica D, 19 (1986), 423–432 | DOI | MR | Zbl

[13] Achasova S., Bandman O., Markova V., Piskunov S., Parallel Substitution Algorithm. Theory and Application, World Scientific, Singapore, 1994, 198 pp. | Zbl

[14] Bandman O. L., “Cellular automata models of spatial dynamics”, System Informatics, 2006, no. 10, 59–111 (in Russian)

[15] Achasova S. M., Bandman O. L., The Correctness of Parallel Computing Processes, Nauka Publ., Novosibirsk, 1990, 256 pp. (in Russian) | MR

[16] Bandman O., “Parallel simulation of asynchronous cellular automata evolution”, ACRI-2006, LNCS, 4173, 2006, 41–47 | MR | Zbl

[17] Sharifulina A., Elokhin V., “Simulation of heterogeneous catalytic reaction by asynchronous cellular automata on multicomputer”, PaCT-2011, LNCS, 6873, 2011, 210–216

[18] Sharifulina A. E., “Parallel implementation of the catalytic reaction $(\mathrm{CO}+ \mathrm O_2\to\mathrm{CO}_2)$ using an asynchronous cellular automaton”, Proc. PaVT-2012, SUSU Publ., Chelyabinsk, 2012, 325–335 (in Russian)

[19] Bandman O., “Cellular automata composition techniques for spatial dynamics simulation”, Simulating Complex Systems by Cellular Automata, eds. A. G. Hoekstra, J. Kroc, P. M. A. Sloot, Springer, Berlin, 2010, 81–116 | DOI

[20] Bandman O., “Using multi core computers for implementing cellular automata systems”, PaCT-2011, LNCS, 6873, 2011, 45–58

[21] Medvedev Yu. G., “An extension of the cellular-automaton FHP-I flow model to the FHP-MP multi- particle model”, Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika, 2009, no. 1(6), 33–40 (in Russian)

[22] Medvedev Yu. G., “The 3D fluid flow simulation”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2002, no. 1(II), 236–240 (in Russian)

[23] Medvedev Yu. G., “Many-cellular automata models of diffusion process”, Novye inf. tekhnologii v issled. slozhnykh struktur, Tez. dokl., NTL Publ., Tomsk, 2010, 21–22 (in Russian)

[24] Bandman O., “Cellular automata diffusion models for multicomputer implementation”, Bull. Nov. Comp. Center. Ser. Comp. Sci., 36 (2014), 21–31 | Zbl

[25] Medvedev Yu. G., “Applying the cellular automaton model of a viscous fluid flow in investigating 3D porous media”, Avtometriya, 42:3 (2006), 21–31 (in Russian)

[26] Medvedev Yu. G., “The software package for cellular automata modeling of gas-powder flow”, Proc. PaVT-2012, SUSU Publ., Chelyabinsk, 2012, 732 (in Russian)

[27] Wolf-Gladrow D., Lattice-Gas Cellular Automata and Lattice Boltzmann Models, Springer, Berlin, 2000, 310 pp. | MR | Zbl

[28] Chetverushkin B. N., Kinetically consistent schemes in gas dynamics: the new model of a viscous gas, algorithms, parallel implementation, application, MSU Publ., Moscow, 1999, 232 pp. (in Russian)

[29] Numerical Algorithms and Round-off Errors, http://www.sml.ee.upatras.gr/uploadedfiles/roundofferror.pdf

[30] Kireeva A., “Two-layer CA model for simulating catalytic reaction at dynamically varying temperature”, ACRI-2014, LNCS, 8751, 2014, 166–175

[31] Bandman O. L., Kireeva A. E., “Stochastic cellular automata simulation of oscillations and autowaves in reaction-diffusion systems.”, Numerical Analysis and Applications, 8:3 (2015), 208–222 | DOI | DOI | MR | Zbl

[32] Bandman O., “Cellular automata model of fluid permeation through porous material”, PaCT-2013, LNCS, 7979, 2013, 295–316

[33] Bandman O., “Parallel composition of asynchronous cellular automata simulating reaction diffusion processes”, ACRI-2010, LNCS, 6350, 2010, 395–398 | Zbl

[34] Vitvitsky A. A., “Cellular automata with dynamic structure to simulate the growth of biological tissues”, Numerical Analysis and Applications, 7:4 (2014), 263–273 | DOI | MR