2018/05/02 by Nicolas Gast, Gast, Nicolas, Mohammed Khatiri +6 · 1 citation
Computer Science · #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1805.00857
arxiv created 2018/05/02 · openalex publication_date 2018/05/02 · arxiv updated 2018/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study in this paper 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 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.