Scheduling computational workflows on failure-prone platforms

Résumé : Nous étudions l'ordonnancement de flux de calculs sur des machines sujettes à des pannesqui suivent une loi exponentielle. Quand une faute arrive, la plateforme récupère son état lorsdu dernier point de sauvegarde de données. Le problème est ici de minimiser l'espérance dutemps total d'exécution en choisissant l'ordre d'exécution des tâches ainsi que les tâches dont la sortie est sauvegardée (checkpoint). Nous proposons un algorithme polynomial pour les forkainsi qu'une preuve de NP-complétude pour les joins. Le résultat principal de ce travail est unalgorithme polynomial pour évaluer le temps d'exécution d'un DAG ordonnancé. Cet algorithme permet l'évaluation d'heuristiques pour résoudre le problème d'ordonnancement, nous en proposons et les évaluons sur des flux de calculs représentatifs de configurations actuelles.
Type de document :
Rapport
[Research Report] RR-8609, ENS Lyon; LIP; INRIA; CNRS; Université Lyon 1. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01075100
Contributeur : Equipe Roma <>
Soumis le : jeudi 16 octobre 2014 - 15:55:35
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : samedi 17 janvier 2015 - 10:46:37

Fichier

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

Identifiants

  • HAL Id : hal-01075100, version 1

Collections

Citation

Guillaume Aupy, Anne Benoit, Henri Casanova, Yves Robert. Scheduling computational workflows on failure-prone platforms. [Research Report] RR-8609, ENS Lyon; LIP; INRIA; CNRS; Université Lyon 1. 2014. 〈hal-01075100〉

Partager

Métriques

Consultations de la notice

421

Téléchargements de fichiers

115