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.

Dynamic Load Balancing in Parallel Execution of Cellular Automata

De Rango A.;Rongo R.;D'Ambrosio D.;Spataro W.
2021-01-01

Abstract

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.
2021
cellular automata
load balancing
Parallel computing
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/313510
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 9
social impact