Parallel Execution of Cellular Automata through Space Partitioning: The Landslide Simulation Sciddicas3-Hex Case Study

The performance and scalability of cellular automata, when executed on parallel/distributed machines, are limited by the necessity of synchronizing all the nodes at each time step, i.e., a node can execute its code only after all the other nodes have executed the previous step. However, if the code is parallelized by partitioning the space of the automata, these synchronization requirements can be relaxed: indeed, a node that manages a given portion of the cellular automata can execute a new step after synchronizing only with the nodes that manage the adjacent portions, while the remaining nodes can execute different time steps. This can be a notable advantage in many novel and increasingly popular applications of cellular automata, such as smart city applications, simulation of natural phenomena, etc., in which the execution times can be different and variable, due to the heterogeneity of machines and/or of the data and/or of the different functions. Indeed, a longer execution time at a node does not slow down the execution at all the other nodes but only at the neighboring nodes. This is particularly advantageous when the nodes that act as a bottleneck can vary during the execution. The goal of the paper is to analyze the benefits that can be achieved with the described approach when different space partitioning strategies are taken into account: i.e., the mono-and the two-dimensional partitioning. Experiments referred to a well-known cellular automata, namely the SciddicaS3-hex model for landslide simulation, exhibit good scalability and prove that the partitioning scheme adopted can result crucial for improving the overall computational performances.