Analysis of Work Stealing with latency - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Article Dans Une Revue Journal of Parallel and Distributed Computing Année : 2021

Analysis of Work Stealing with latency

Résumé

We study the impact of communication latency on the classical Work Stealing load balancing algorithm. Our paper extends the reference model in which we introduce a latency parameter. By using a theoretical analysis and simulation, we study the overall impact of this latency on the Makespan (maximum completion time). We derive a new expression of the expected running time of a bag of independent tasks scheduled by Work Stealing. This expression enables us to predict under which conditions a given run will yield acceptable performance. For instance, we can easily calibrate the maximal number of processors to use for a given work/platform combination. All our results are validated through simulation on a wide range of parameters.
Fichier principal
Vignette du fichier
WS_JPDC.pdf (553.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03356234 , version 1 (27-09-2021)

Identifiants

Citer

Nicolas Gast, Mohammed Khatiri, Denis Trystram, Frédéric Wagner. Analysis of Work Stealing with latency. Journal of Parallel and Distributed Computing, 2021, 153, pp.119-129. ⟨10.1016/j.jpdc.2021.03.010⟩. ⟨hal-03356234⟩
102 Consultations
235 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More