Coarse-grained parallelization of cellular-automata simulation algorithms
Pages 370 - 384
Abstract
Simulating spatial dynamics in physics by Cellular Automata (CA) requires very large computation power, and, hence, CA simulation algorithms are to be implemented on multiprocessors. The preconceived opinion, that no much effort is required to obtain highly efficient coarse grained parallel CA algorithm, is not always true. In fact, a great variety of CA modifications coming into practical use need appropriate, sometimes sophisticated, methods of CA algorithms parallel implementation. Proceeding from the above a general approach to CA parallelization, based on domain decomposition correctness conditions, is formulated. Starting from the correctness conditions particular parallelization methods are developed for the main classes of CA simulation models: synchronous CA with multi-cell updating rules, asynchronous probabilistic CA, and CA compositions. Examples and experimental results are given for each case.
References
[1]
Toffolli, T.: Cellular Automata as an Alternative to (rather than Approximation of) Differential Equations in Modeling Physics. Physica D 10, 117-127 (1984)
[2]
Wolfram, S.: A new kind of science. Wolfram Media Inc., Champaign, Ill., USA (2002)
[3]
Toffolli, T., Margolus, N.: Cellular Automata Machines. MIT Press, Cambridge (1987)
[4]
Rothman, B.H., Zaleski, S.: Lattice-Gas Cellular Automata. Cambridge Univ. Press, Complex Hydrodynamics. London (1997)
[5]
Latkin, E.I., Elokhin, V.I., Gorodetskii, V.V.: Spiral concentration waves in the Monte-Carlo model of CO oxidation over Pd(110) caused by synchronization via COads diffusion between separate parts of catalytic surface. Chemical Engineering Journal 91, 123-131 (2003)
[6]
Neizvestny, I.G., Shwartz, N.L., Yanovitskaya, Z.S., Zverev, A.V.: 3D-model of epitaxial growth on porous {111} and {100} Si surfaces. Computer Physics Communications 147, 272-275 (2002)
[7]
Sipper, M.: Evolution of Parallel Cellular Machines: The Cellular Programming Approach. Springer, Heidelberg (1997)
[8]
Bandini, S., Erbacci, G., Mauri, G.: Implementing Cellular Automata Based Models on Parallel Architectures: The CAPP Project. In: Malyshkin, V. (ed.) Parallel Computing Technologies. LNCS, vol. 1662, pp. 167-179. Springer, Heidelberg (1999)
[9]
Carotenuto, L., Mele, F., Furnari, M.M., Napolitano, R.: Pecans: A parallel environment for cellular automata modeling. Complex Systems 10, 23-41 (1996)
[10]
Malinetski, G.G., Stepantsov, M.E.: Modeling Diuffusive Processes by Cellular Automata with Margolus Neighborhood. Zhurnal Vychislitelnoy Matematiki i Matematicheskoy Phiziki (in Russian) 36(6), 1017-1021 (1998)
[11]
Bandman, O.: Simulation Spatial Dynamics by Probabilistic Cellular Automata. In: Bandini, S., Chopard, B., Tomassini, M. (eds.) ACRI 2002. LNCS, vol. 2493, pp. 10-19. Springer, Heidelberg (2002)
[12]
Achasova, S., Bandman, O., Markova, V., Piskunov, S.: Parallel Substitution Algorithm. In: Theory and Application, World Scientific, Singapore (1994)
[13]
Park, J.K., Steiglitz, K., Thurston, W.P.: Soliton-like behavior in automata. Physica D 19, 423-432 (1986)
[14]
Medvedev, Y.G.: Experimental study of Computational characteristic of parallel implementation of 3D cellular Automata model of viscous flow. In: Proceedings of Scientific Confernce Parallel Programming Technology, pp. 79-82. Moscow Univ. Press (2006)
[15]
Bandman, O.: Parallel Implementation of Asynchronous Cellular Automata Algorithm. In: El Yacoubi, S., Chopard, B., Bandini, S. (eds.) ACRI 2006. LNCS, vol. 4173, pp. 41-47. Springer, Heidelberg (2006)
[16]
Nedea, S.V., Lukkien, J.J., Jansen, A.P.J., Hilbers, P.A.J.: Methods for parallel simulation of surface reaction. In: Werner, B. (ed.) 4th Int. Workshop on Parallel and Distributrd Scientific and Engineering Computing with Applications, pp. 7-16. IEEE Comp. Society, Nice, France (2003)
[17]
Chen, N., Glazier, J.A., Alber, M.S.A: A Parallel Implementation of the Cellular Potts Model for Simulation of Cell-Based Morphogenesis. In: El Yacoubi, S., Chopard, B., Bandini, S. (eds.) ACRI 2006. LNCS, vol. 4173, pp. 58-67. Springer, Heidelberg (2006)
[18]
Bandman, O.: Composing Fine-graned Parallel Algorithms for Spatial Dynamics Simulation. In: Malyshkin, V. (ed.) PaCT 2005. LNCS, vol. 3606, pp. 99-113. Springer, Heidelberg (2005)
- Coarse-grained parallelization of cellular-automata simulation algorithms
Recommendations
Cellular Automata: Elementary Cellular Automata
Cellular automata CA are discrete dynamical systems consist of a regular finite grid of cell; each cell encapsulating an equal portion of the state, and arranged spatially in a regular fashion to form an n-dimensional lattice. A cellular automata is ...
Closure properties of cellular automata
Concerning the power of one-dimensional cellular automata recognizers, Ibarra and Jiang have proved that real time cellular automata (CA) and linear time CA are equivalent if and only if real time CA is closed under reverse. In this paper we investigate ...
Cellular automata between sofic tree shifts
We study the sofic tree shifts of A^@S^^^@?, where @S^@? is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if X@?A^@S^^^@? is a sofic tree shift, then the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- National Scientific Council: National Scientific Council (Taiwan)
- Microsoft: Microsoft
- The Russian Fund for Basic Research: The Russian Fund for Basic Research
- IBM: IBM
- The Russian Academy of Sciences: The Russian Academy of Sciences
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 03 September 2007
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025