Parallel implementation of cellular automata algorithms for simulation of spatial dynamics

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.