Fault Tolerant Scheduling of Precedence Task Graphs on Heterogeneous Platforms

Anne Benoit 1 Mourad Hakem 1 Yves Robert 1
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Fault tolerance and latency are important requirements in several applications which are time critical in nature: such applications require guaranties in terms of latency, even when processors are subject to failures. In this paper, we propose a fault tolerant scheduling heuristic for mapping precedence task graphs on heterogeneous systems. Our approach is based on an active replication scheme, capable of supporting $\varepsilon$ arbitrary fail-silent (fail-stop) processor failures, hence valid results will be provided even if $\varepsilon$ processors fail. We focus on a bi-criteria approach, where we aim at minimizing the latency given a fixed number of failures supported in the system, or the other way round. Major achievements include a low complexity, and a drastic reduction of the number of additional communications induced by the replication mechanism. Experimental results demonstrate that our heuristics, despite their lower complexity, outperform their direct competitor, the FTBAR scheduling algorithm[8].
Type de document :
[Research Report] RR-6418, INRIA. 2008
Liste complète des métadonnées

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

Contributeur : Mourad Hakem <>
Soumis le : mardi 22 janvier 2008 - 14:41:10
Dernière modification le : vendredi 20 avril 2018 - 15:44:23
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 19:58:00


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00207593, version 3



Anne Benoit, Mourad Hakem, Yves Robert. Fault Tolerant Scheduling of Precedence Task Graphs on Heterogeneous Platforms. [Research Report] RR-6418, INRIA. 2008. 〈inria-00207593v3〉



Consultations de la notice


Téléchargements de fichiers