Abstract
Cellular Automata play an important role in the simulation of complex systems where non-linear dynamical behaviors emerge from local interactions of their constituent parts. The spatial nature of cellular automata permits an efficient and straightforward parallelization by domain space partitioning among computing nodes. Nevertheless, load balancing issues can easily arise due to differences in computation times of the different portions of the domain space. This paper is focused on the load balancing technique applied to the parallel execution of cellular automata in the case of multi-dimensional space partitioning, i.e., when the domain space is partitioned along more than one dimension. In particular, a hierarchical approach is introduced that maximizes performances thanks to domain partitioning not constrained to a rigid grid structure. The advantages of avoiding a rigid grid structure for partitioning are due to the resulting greater degree of freedom in workload balancing and are proved by an extensive experimental evaluation.

This publication has 24 references indexed in Scilit: