Dynamic Load Balancing in Parallel Execution of Cellular Automata

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.