Checkpointing strategies for parallel jobs

Résumé : Nous présentons dans ce travail une analyse rigoureuse des stratégies de checkpoint, pour les applications séquentielles et parallèles. L'objectif est de minimiser l'espérance du temps de complétion d'une application s'exécutant sur des processeurs pouvant être de victimes de pannes. Dans le cas séquentiel, une résolution exacte est proposée lorsque les intervalles inter-pannes sont distribués selon une loi exponentielle. Il semble que ce résultat soit la première preuve rigoureuse de l'optimalité des stratégies périodiques de checkpoint dans ce cadre. Dans le cas général (c'est-à-dire pour des lois quelconques), nous fournissons une programmation dynamique permettant des calculs optimaux, à un quantum de temps fixé près. Dans le cas des applications parallèles, nous étendons le résultat exact (pour le cas exponentiel), et ce pour différents modèles d'applications et de coûts de checkpoints. Pour le cas général, nous proposons une deuxième programmation dynamique (plus rapide) dont l'objectif est de maximiser l'espérance du travail fait avant la prochaine panne, qui s'avère fournir de bonnes approximations pour le problème initial. Nous validons nos résultats grâce à de nombreuses simulations, réalisées pour des lois inter-pannes de distribution exponentielles et de Weibull (cette dernière distribution étant selon de nombreuses études plus appropriée pour modéliser des durées inter-pannes). Ces simulations confirment nos résultats théoriques. De plus, ils apparaît que notre algorithme de programmation dynamique fournit de bien meilleures performances que les solutions existantes pour le cas des lois de Weibull.
Type de document :
Rapport
[Research Report] RR-7520, INRIA. 2011, pp.45
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00560582
Contributeur : Marin Bougeret <>
Soumis le : vendredi 22 avril 2011 - 15:16:41
Dernière modification le : jeudi 11 janvier 2018 - 06:21:36
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 02:25:32

Fichier

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

Identifiants

  • HAL Id : inria-00560582, version 3

Collections

Citation

Marin Bougeret, Henri Casanova, Mikael Rabie, Yves Robert, Frédéric Vivien. Checkpointing strategies for parallel jobs. [Research Report] RR-7520, INRIA. 2011, pp.45. 〈inria-00560582v3〉

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

192