Skip to Main content Skip to Navigation
Journal articles

Analysis of Work Stealing with latency

Nicolas Gast 1 Mohammed Khatiri 2, 3 Denis Trystram 2 Frédéric Wagner 2 
1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : 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.
Complete list of metadata
Contributor : Nicolas Gast Connect in order to contact the contributor
Submitted on : Monday, September 27, 2021 - 6:02:16 PM
Last modification on : Friday, July 8, 2022 - 10:07:24 AM
Long-term archiving on: : Tuesday, December 28, 2021 - 7:18:36 PM


Files produced by the author(s)



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



Record views


Files downloads