Cellular Automata (CA) are extensively utilized for modeling and simulating complex systems due to their simplicity, flexibility, and ability to represent diverse phenomena. However, the computational intensity of CA models, particularly in large-scale applications, demands the development of efficient parallel execution techniques. This is especially critical when targeting shared memory architectures, where resource management and thread coordination play pivotal roles in achieving optimal performance. In this study, we examine a range of parallel execution strategies specifically designed to enhance the efficiency and scalability of CA models. The experimental evaluation highlights good scalability in execution time and resource utilization, making these strategies highly suitable for extensive simulations across various domains. Additionally, the results emphasize that imbalance conditions—often arising during CA computations—can considerably influence the effectiveness of choosing a given strategy.

This work is focused on the transparent execution of Cellular Automata models on a multi-GPU architecture. Although Cellular Automata models can be easily parallelized on a single GPU, the domain size and transition function complexity may require the use of multiple GPUs. Our goal is to allow modellers to be completely unaware of the parallel execution context, i.e., the code implementing the Cellular Automata model remains the same regardless if the execution is performed on CPU, single GPU, or multi-GPU systems. This paper supplies meaningful technical insights on how to ensure both transparency and efficiency in multi-GPU execution of Cellular Automata models. In particular, an object-oriented approach is exploited in which a transparent layer is devised that abstracts the parallelization details and allows a strong “separation of concerns” between the execution parallelism issues and the model implementation. Preliminary experiments have been carried out on the multi-GPU cluster CTE-POWER available at the Barcelona Supercomputing Center (BSC), witnessing good speedups notwithstanding the transparency feature supplied by our approach.

Cellular Automata (CA) models, initially studied by John von Neumann, have been developed by numerous researchers and applied in both academic and scientific fields. Thanks to their local and independent rules, simulations of complex systems can be easily implemented based on CA modelling on parallel machines. However, due to the heterogeneity of the components - from the hardware to the software perspective-the various possible scenarios running parallelism in today's architectures can pose a challenge in such implementations, making it difficult to exploit. This paper presents OpenCAL++, a transparent and efficient object-oriented platform for the parallel execution of cellular automata models. The architecture of OpenCAL++ ensures the modeller a fully transparent parallel execution and a strong “separation of concerns” between the execution parallelism issues and the model implementation. The code implementing the Cellular Automata model remains the same whether the execution performs in a shared-, distributed-memory or a GPGPU context, irrespective of the optimizations adopted. To this aim, the object-oriented paradigm has been intensely exploited. As well as the OpenCAL++ architecture, we present the description of a simple Cellular Automata model implementation for illustrative purposes.

Abstract In this paper, techniques for dynamic load balancing of the cellular automata parallel execution are presented for the case of domain space partitioned along two dimensions. Starting from general closed-form expressions that allow to compute the optimal workload assignment in a dynamic fashion when partitioning takes place along only one dimension, we tailor the procedure to allow partitioning and balancing along both dimensions. Both qualitative and quantitative experiments are carried out that assess performance improvement in applying load balancing for the case of two-dimensional partitioned domain, especially when the load balancing takes place along both dimensions.

The triangular Shepard interpolation method is an extension of the well-known bivariate Shepard’s method for interpolating large sets of scattered data. In particular, the classical point-based weight functions are substituted by basis functions built upon triangulation of the scattered points. As shown in the literature, this method exhibits advantages with respect to other interpolation methods for interpolating scattered bivariate data. Nevertheless, as the size of the data set increases, an efficient implementation of the method becomes more and more necessary. In this paper, we present a parallel implementation of the triangular Shepard interpolation method that beside exploiting benefits due to the parallelization itself, introduces a novel approach for the triangulation of the scattered data.

Load Balancing is generally referred as the technique to properly partition computation among processing elements in order to achieve optimal resource usage and thus reduce computation time. In this paper, we present a dynamic load balancing application in the context of the parallel execution of Cellular Automata where the domain space is partitioned in two dimensional regions that are assigned to different processing elements. Starting from general closed-form expressions that allow to compute the optimal workload assignment in a dynamic fashion when partitioning takes place along only one dimension, we extend the procedure to allow partitioning and balancing along both dimensions. As confirmed by the experimental results, two dimensional partitioning itself enables to speedup the execution, and further improvements are obtained when the load balancing occurs along both dimensions.

The allocation of the computational load across different processing elements is an important issue in parallel computing. Indeed, an unbalanced load distribution can strongly affect the performances of a parallel system caused by an excess of synchronization idle times due to less loaded processes waiting for more loaded ones. In this article, we focus on the load balancing issues in the context of the parallel execution of spatial-related applications where the domain space is partitioned in regions that are assigned to different processing elements. In particular, without loss of generality, we consider the well-known spatial-related Cellular Automata computational paradigm for evaluating the proposed dynamic load balancing approach. The main contribution of this article is the derivation of simple closed-form expressions that allow to compute the optimal workload assignment in a dynamic fashion, with the goal of guaranteeing a fully balanced workload distribution during the parallel execution. Based on these expressions, an algorithm for balanced execution of cellular automata is presented and implemented using the MPI technology. Eventually, an experimental section practically shows the behaviour of the proposed dynamic load balancing approach and proves its performance improvement, compared to the not-balanced version, as witnessed by the appreciable reduction of execution times.

Cellular Automata (CA) are parallel models well-suited for studying complex systems that are based on local rules of evolution. Notable examples of application are found in fluid-dynamics, crowd simulation, flow-simulation and many more. Nevertheless, CA can be fruitfully exploited as a support in numerical approaches, such as finite element and finite volume methods. Though easily parallelizable by domain partitioning among the nodes of a parallel system, the performance and scalability of cellular automata executed on parallel/distributed machines are limited due to the need of synchronizing nodes at each computational step. With the aim of reducing the synchronization burden, we here present a preliminary study on techniques stemmed from the Discrete-Event Simulation field for the optimization of CA on distributed memory architectures. Preliminary results, executed in a distributed memory environment, have shown the usefulness of the considered approach in reducing execution times and therefore in improving the speed up of the parallel execution of the test case.

The Cellular Automata paradigm is an efficient tool to model and study complex systems such as traffic simulation, lava flows and swarm based behaviour. In addition, cellular automata can be profitably used in many mathematical problems such as differential equations and chaos theory. Due to their inherent parallel nature, cellular automata can be efficiently parallelized among a set of computing nodes in order to scale and speed up their execution. This paper presents a preliminary study on different parallelization techniques for structured grid models such as cellular automata on distributed memory architectures. In particular, three strategies are presented and compared in order to evaluate their efficiency in terms of speedup. An experimental section shows the performance achieved by the three strategies when a real-life application, namely the SciddicaT cellular automata model for debris-flows simulation, is adopted.

This paper presents the release fv3 of the Complex Cellular Automata model Sciara for simulating lava flows. It is based on a Bingham-like rheology and both flow velocity and the physical time corresponding to a computational step have been made explicit. The model has been preliminary tested with satisfying results by considering the 2006 lava event at Mt Etna (Italy). A HTML5 based Web application with a WebGL 3D interactive visualization system has also been developed as user interface for Sciara-fv3. Eventually, the numerical code has been parallelised by the CUDA GPGPU paradigm, allowing for a considerable reduction of the execution time, despite the numerical code complexity.