Skip to Main content Skip to Navigation
New interface
Journal articles

The impact of heterogeneity on master-slave scheduling

Jean-François Pineau 1, 2 Yves Robert 1, 2 Frédéric Vivien 1, 2 
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we assess the impact of heterogeneity on scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time. We target both on-line and off-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such on-line problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal deterministic algorithm for heterogeneous platforms. Whether the source of heterogeneity comes from computation speeds, or from communication bandwidths, or from both, we establish lower bounds on the competitive ratio of any deterministic algorithm. We provide such bounds for the most important objective functions: the minimization of the makespan (or total execution time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of all response times. Altogether, we obtain nine theorems which nicely assess the impact of heterogeneity on on-line scheduling. For off-line scheduling, we prove several result for problems with release dates, either optimality or NP-hardness. These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, November 13, 2018 - 2:39:29 PM
Last modification on : Tuesday, October 25, 2022 - 4:16:56 PM
Long-term archiving on: : Thursday, February 14, 2019 - 12:21:59 PM


Files produced by the author(s)



Jean-François Pineau, Yves Robert, Frédéric Vivien. The impact of heterogeneity on master-slave scheduling. Parallel Computing, 2008, 34 (3), pp.158-176. ⟨10.1016/j.parco.2007.12.006⟩. ⟨hal-00803473⟩



Record views


Files downloads