The impact of heterogeneity on master-slave on-line scheduling

Abstract : In this paper, we assess the impact of heterogeneity for 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-step. We target on-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal de-terministic 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 determin-istic 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. These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our (prelim-inary) results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.
Type de document :
Communication dans un congrès
HCW'2006, the 15th Heterogeneous Computing Workshop, 2006, Rhodes Island, Greece. IEEE Computer Society Press, 2006
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00804401
Contributeur : Equipe Roma <>
Soumis le : mardi 20 novembre 2018 - 17:16:58
Dernière modification le : mercredi 21 novembre 2018 - 09:23:23

Fichier

camera_ready.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00804401, version 1

Collections

Citation

Jean-François Pineau, Yves Robert, Frédéric Vivien. The impact of heterogeneity on master-slave on-line scheduling. HCW'2006, the 15th Heterogeneous Computing Workshop, 2006, Rhodes Island, Greece. IEEE Computer Society Press, 2006. 〈hal-00804401〉

Partager

Métriques

Consultations de la notice

306

Téléchargements de fichiers

3