Scheduling Parallel Iterative Applications on Volatile Resources

Abstract : In this paper we study the execution of iterative applications on volatile processors such as those found on desktop grids. We develop master-worker scheduling schemes that attempt to achieve good trade-offs between worker speed and worker availability. A key feature of our approach is that we consider a communication model where the bandwidth capacity of the master for sending application data to workers is limited. This limitation makes the scheduling problem more difficult both in a theoretical sense and a practical sense. Furthermore, we consider that a processor can be in one of three states: available, down, or temporarily preempted by its owner. This preempted state also makes the design of scheduling algorithms more difficult. In practical settings, e.g., desktop grids, master bandwidth is limited and processors are temporarily reclaimed. Consequently, addressing the aforementioned difficulties is necessary for successfully deploying master-worker applications on volatile platforms. Our first contribution is to determine the complexity of the scheduling problem in its off-line version, i.e., when processor availability behaviors are known in advance. Even with this knowledge, the problem is NP-hard, and cannot be approximated within a factor $8/7$. Our second contribution is a closed-form formula for the expectation of the time needed by a worker to complete a set of tasks. This formula relies on a Markovian assumption for the temporal availability of processors, and is at the heart of some heuristics that aim at favoring ``reliable'' processors in a sensible manner. Our third contribution is a set of heuristics, which we evaluate in simulation. Our results provide insightful guidance to selecting the best strategy as a function of processor state availability versus average task duration.
Type de document :
Rapport
[Research Report] 2010, pp.19
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00524784
Contributeur : Fanny Dufossé <>
Soumis le : mardi 19 octobre 2010 - 15:58:04
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 06:48:12

Fichier

rr2010-31.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00524784, version 2

Collections

Citation

Henri Casanova, Fanny Dufossé, Yves Robert, Frédéric Vivien. Scheduling Parallel Iterative Applications on Volatile Resources. [Research Report] 2010, pp.19. 〈inria-00524784v2〉

Partager

Métriques

Consultations de la notice

423

Téléchargements de fichiers

186