Realistic Models and Efficient Algorithms for Fault Tolerant Scheduling on Heterogeneous Platforms

Abstract : Most list scheduling heuristics rely on a simple platform model where communication contention is not taken into account. In addition, it is generally assumed that processors in the systems are completely safe. To schedule precedence graphs in a more realistic framework, we introduce an efficient fault tolerant scheduling algorithm that is both contention-aware and capable of supporting $\varepsilon$ arbitrary fail-silent (fail-stop) processor failures. We focus on a bi-criteria approach, where we aim at minimizing the total execution time, or latency, given a fixed number of failures supported in the system. Our algorithm has a low time complexity, and drastically reduces the number of additional communications induced by the replication mechanism. Experimental results fully demonstrate the usefulness of the proposed algorithm, which leads to efficient execution schemes while guaranteeing a prescribed level of fault tolerance.
Type de document :
Rapport
[Research Report] RR-6606, INRIA. 2008, pp.28
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-00308775
Contributeur : Mourad Hakem <>
Soumis le : vendredi 1 août 2008 - 15:35:02
Dernière modification le : mardi 16 janvier 2018 - 15:34:05
Document(s) archivé(s) le : mardi 28 juin 2011 - 12:22:50

Fichier

RR-6606.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00308775, version 1

Collections

Citation

Anne Benoit, Mourad Hakem, Yves Robert. Realistic Models and Efficient Algorithms for Fault Tolerant Scheduling on Heterogeneous Platforms. [Research Report] RR-6606, INRIA. 2008, pp.28. 〈inria-00308775〉

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

48