Mapping tightly-coupled applications on volatile resources

Abstract : Platforms that comprise volatile processors, such as desktop grids, have been traditionally used for executing independent-task applications. In this work we study the scheduling of tightly-coupled iterative master-worker applications onto volatile processors. The main challenge is that workers must be simultaneously available for the application to make progress. We consider two additional complications: one should take into account that workers can become temporarily reclaimed and, for data-intensive applications, one should account for the limited bandwidth between the master and the workers. In this context, our first contribution is a theoretical study of the scheduling problem in its off-line version, i.e., when processor availability is known in advance. Even in this case the problem is NP-hard. Our second contribution is an analytical approximation of the expectation of the time needed by a set of workers to complete a set of tasks and of the probability of success of this computation. This approximation relies on a Markovian assumption for the temporal availability of processors. Our third contribution is a set of heuristics, some of which use the above approximation to favor reliable processors in a sensible manner. We evaluate these heuristics in simulation. We identify some heuristics that significantly outperform their competitors and derive heuristic design guidelines.
Type de document :
Communication dans un congrès
PDP'2013, the 21st Euromicro Int. Conf. on Parallel, Distributed, and Network-Based Processing, Feb 2013, Belfast, United Kingdom. IEEE Computer Society Press, 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00763376
Contributeur : Equipe Roma <>
Soumis le : lundi 10 décembre 2012 - 16:10:55
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : samedi 17 décembre 2016 - 23:46:36

Fichier

paper100-pdp13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00763376, version 1

Collections

Citation

Henri Casanova, Fanny Dufossé, Yves Robert, Frédéric Vivien. Mapping tightly-coupled applications on volatile resources. PDP'2013, the 21st Euromicro Int. Conf. on Parallel, Distributed, and Network-Based Processing, Feb 2013, Belfast, United Kingdom. IEEE Computer Society Press, 2013. 〈hal-00763376〉

Partager

Métriques

Consultations de la notice

397

Téléchargements de fichiers

71