Scheduling Divisible Loads on Star and Tree Networks: Results and Open Problems

Olivier Beaumont 1 Henri Casanova Arnaud Legrand Yves Robert 2, 3 Yang Yang 4
1 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
INRIA Futurs, Université Bordeaux Segalen - Bordeaux 2, Université Sciences et Technologies - Bordeaux 1, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
2 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Applications in many scientific and engineering domains are structured in large numbers of independent tasks with low granularity. These applications can thus be naturally parallelized, typically in master-worker fashion, provided that efficient scheduling strategies are available. Such applications have been called divisible loads because a scheduler may divide the computation among worker processes arbitrarily, both in terms of number of tasks and of task sizes. Divisible load scheduling has been an active area of research for the last twenty years. A vast literature offers results and scheduling algorithms for various models for the underlying distributed computing platform. Broad surveys are available that report on accomplishments in the field. By contrast, in this paper we propose a unified theoretical perspective that synthesizes previously published results, several novel results, and open questions, in a view to foster novel divisible load scheduling research. Specifically, we discuss both one-round and multi-round algorithms, and we restrict our scope to the popular star and tree network topologies, which we study with both linear and affine cost models for communication and computation.
Type de document :
[Research Report] RR-4916, INRIA. 2003
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 18:26:26
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:32:02



  • HAL Id : inria-00071663, version 1


Olivier Beaumont, Henri Casanova, Arnaud Legrand, Yves Robert, Yang Yang. Scheduling Divisible Loads on Star and Tree Networks: Results and Open Problems. [Research Report] RR-4916, INRIA. 2003. 〈inria-00071663〉



Consultations de la notice


Téléchargements de fichiers