Offline and Online Scheduling of Concurrent Bags-of-Tasks on Heterogeneous Platforms

Anne Benoit 1 Loris Marchal 1, * Jean-François Pineau 1 Yves Robert 1 Frédéric Vivien 1
* Auteur correspondant
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Scheduling problems are already difficult on traditional parallel machines. They become extremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. In this paper we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, which means that there is no a priori (static) knowledge of the workload distribution at the beginning of the execution. The objective is to minimize the maximum stretch, i.e. the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from the literature, thereby fully assessing the usefulness of our approach.
Type de document :
[Research Report] RR-6401, INRIA. 2007, pp.49
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 20 décembre 2007 - 16:43:12
Dernière modification le : mardi 11 décembre 2018 - 10:58:05
Document(s) archivé(s) le : mardi 21 septembre 2010 - 15:04:56


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00200261, version 2



Anne Benoit, Loris Marchal, Jean-François Pineau, Yves Robert, Frédéric Vivien. Offline and Online Scheduling of Concurrent Bags-of-Tasks on Heterogeneous Platforms. [Research Report] RR-6401, INRIA. 2007, pp.49. 〈inria-00200261v2〉



Consultations de la notice


Téléchargements de fichiers