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

https://hal.inria.fr/hal-03356234
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

File

WS_JPDC.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

77

Files downloads

119