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

Olivier Beaumont 1 Henri Casanova 2 Arnaud Legrand Yves Robert 3, 4 Yang Yang 2
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
3 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.
Document type :
Reports
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071663
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:26:26 PM
Last modification on : Wednesday, August 7, 2019 - 12:18:05 PM

Identifiers

  • HAL Id : inria-00071663, version 1

Citation

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, LIP. 2003, pp.LIP RR-2003-41. ⟨inria-00071663⟩

Share

Metrics

Record views

352

Files downloads

533