Geodesic
Parallel implementation of cellular automata algorithms for simulation of spatial dynamics
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 10 (2007) no. 4, pp. 335-348.

Voir la notice de l'article provenant de la source Math-Net.Ru

Cellular Automaton (CA) is a mathematical model for the spatial dynamics which is mainly used to simulate phenomena with a strong nonlinearity and discontinuity. Since the CA simulation problems size is usually very large, highly efficient methods, algorithms, and software for coarse grained parallelization are urgently needed. The engrained opinion that the fine-grained parallelism of CA eliminates the problem of coarse-grained parallelization is shown to be incorrect. The problems need to be solved. So, a general approach to the CA coarse-grained parallelization based on the CA-correctness conditions is presented. First, the formal model used for the CA representation (Parallel Substitution Algorithm) and the CA correctness conditions are given. Then parallelization methods are considered for synchronous and asynchronous CA. To achieve an acceptable efficiency for asynchronous CA, a method of its approximation with a block-synchronous CA is proposed. All the methods presented are illustrated by computer simulation results. 
@article{SJVM_2007_10_4_a1,
     author = {O. L. Bandman},
     title = {Parallel implementation of cellular automata algorithms for simulation of spatial dynamics},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {335--348},
     publisher = {mathdoc},
     volume = {10},
     number = {4},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2007_10_4_a1/}
}
TY  - JOUR
AU  - O. L. Bandman
TI  - Parallel implementation of cellular automata algorithms for simulation of spatial dynamics
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2007
SP  - 335
EP  - 348
VL  - 10
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2007_10_4_a1/
LA  - ru
ID  - SJVM_2007_10_4_a1
ER  - 
%0 Journal Article
%A O. L. Bandman
%T Parallel implementation of cellular automata algorithms for simulation of spatial dynamics
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2007
%P 335-348
%V 10
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2007_10_4_a1/
%G ru
%F SJVM_2007_10_4_a1
O. L. Bandman. Parallel implementation of cellular automata algorithms for simulation of spatial dynamics. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 10 (2007) no. 4, pp. 335-348. http://geodesic.mathdoc.fr/item/SJVM_2007_10_4_a1/

[1] Von Neumann J., Theory of self reproducing automata, University of Illinois, USA, 1966

[2] Toffolli T., “Cellular Automata as an Alternative to (rather than Approximation of) Differential Equations in Modeling Physics”, Physica D, 10 (1884), 117–127 | DOI | MR

[3] Wolfram S., “Statistical mechanics of Cellular Automata”, Review of Modern Physics, 55 (1993), 607–640 | MR

[4] Bandman O. L., “Kletochno-avtomatnye modeli prostranstvennoi dinamiki”, Sistemnaya informatika, Vyp. 10, Izd-vo SO RAN, Novosirsk, 2006, 58–16

[5] Toffolli T., Margolus N., Cellular Automata Machines, MIT Press, USA, 1987

[6] Madore B. Freedman W., “Computer simulations of the Belousov–Zhabotinsky reaction”, Science, 222 (1983), 615–619 | DOI

[7] Packard N., “Lattice models for solidification and aggregation”, Theory and application of Cellular Automata, ed. S. Wolfram, World Scientific, Singapore, 1986, 305–310 | MR

[8] Wolfram S., A new kind of science, Wolfram Media Inc., USA, Champaign, Ill., 2002 | MR | Zbl

[9] Rothman B. H., Zaleski S., Lattice-Gas Cellular Automata. Simple Models of Complex Hydrodynamics, Cambridge Univ. Press, London, 1997 | MR

[10] Elokhin V. I, Latkin E. I., Matveev A. V., Gorodetskii V. V., “Application of Statistical Lattice Models to the Analysis of Oscillatory and Autowave Processes in the Reaction of Carbom Monoxide Oxidation over Platinum and Palladium Surfaces”, Kinetics and Catalysis, 44:5 (2003), 692–700 | DOI

[11] Neizvestny I. G., Shwartz N. L., Yanovitskaya Z. Sh., “3D-model of epitazial growth on porous 111 and 100 Si surfaces”, Computer Physics Communications, 147 (2002), 272–275 | DOI | Zbl

[12] Chen N., Glazier J. A., Alber M. A., “A Parallel Implementation of the Cellular Potts Model for Simulation of Cell-Based Morphogenesis”, Lecture Notes in Computer Science, 4173, Springer, Berlin, 2006, 58–67 | MR | Zbl

[13] Bandman O. L., “Synchronous versus Asynchronous Cellular Automata for Simulating Nano-System Kinetics”, Bull. Novosibirsk Comp. Center. Ser. Computer Science, 23, Novosibirsk, 2006, 1–12

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

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

[16] Achasova S. M., Bandman O. L., Korrektnost parallelnykh protsessov, Nauka, Novosibirsk, 1999

[17] Golze U., “(A-)synchronous (Non-)deterministic Cell Spaces Simulating Each Other”, J. of Comp. and System Science, 17 (1978), 176–188 | DOI | MR

[18] Malinetskii G. G., Stepantsov M. E., “Modelirovanie diffuzionnykh protsessov kletochnymi avtomatami s okrestnostyu Margoldusa”, Zhurn. vychisl. matem. i mat. fiziki, 36:6 (1998), 1017–1021 | MR

[19] Medvedev Yu. G., “Issledovanie vychislitelnykh kharakteristik programmnoi realizatsii trekhmernoi kletochno-avtomatnoi modeli vyazkoi zhidkosti”, Tr. Vseross. nauch. konf. “Nauchnyi servis v seti INTERNET: tekhnologii parallelnogo programmirovaniya”, Novorossiisk, 2006, 79–85

[20] Marchenko M. A., “Kompleks programm MONC dlya raspredelennykh vychislenii metodom Monte-Karlo”, Sib. zhurn. vychisl. matem. / RAN. Sib. otd-nie, 7:1 (2004), 43–55

[21] Bandman O., “Parallel Simulation of Asynchronous Cellular Automata Evolution”, Lect. Notes in Comp. Sci., 4173, Springer, Berlin, 2006, 41–48 | MR