On the complexity of scheduling checkpoints for computational workflows

Yves Robert 1, 2 Frédéric Vivien 1, 2 Dounia Zaidouni 1, 2, *
* Auteur correspondant
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper deals with the complexity of scheduling computational workflows in the presence of Exponentially distributed failures. When such a failure occurs, rollback and recovery is used so that the execution can resume from the last checkpointed state. The goal is to minimize the expected execution time, and we have to decide in which order to execute the tasks, and whether to checkpoint or not after the completion of each given task. We show that this scheduling problem is strongly NP-complete, and propose a (polynomial-time) dynamic programming algorithm for the case where the application graph is a linear chain. These results lay the theoretical foundations of the problem, and constitute a prerequisite before discussing scheduling strategies for arbitrary DAGS of moldable tasks subject to general failure distributions.
Type de document :
Communication dans un congrès
FTXS'2012, the Workshop on Fault-Tolerance for HPC at Extreme Scale, in conjunction with the 42nd Annual IEEE/IFIP Int. Conf. on Dependable Systems and Networks (DSN 2012), 2012, Boston, United States. IEEE Computer Society Press, 2012, 〈10.1109/DSNW.2012.6264675〉
Liste complète des métadonnées

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

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

Fichier

Complexity-Scheduling-Zaidouni...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Yves Robert, Frédéric Vivien, Dounia Zaidouni. On the complexity of scheduling checkpoints for computational workflows. FTXS'2012, the Workshop on Fault-Tolerance for HPC at Extreme Scale, in conjunction with the 42nd Annual IEEE/IFIP Int. Conf. on Dependable Systems and Networks (DSN 2012), 2012, Boston, United States. IEEE Computer Society Press, 2012, 〈10.1109/DSNW.2012.6264675〉. 〈hal-00763382〉

Partager

Métriques

Consultations de la notice

360

Téléchargements de fichiers

124