Checkpointing Workflows for Fail-Stop Errors

Abstract : We consider the problem of orchestrating the execution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. For general DAGs this problem is hopelessly intractable. In fact, given a solution, computing its expected makespan is still a difficult problem. To address this challenge, we consider a restricted class of graphs, Minimal Series-Parallel Graphs (\GSPGs). It turns out that many real-world workflow applications are naturally structured as \GSPGs. For this class of graphs, we propose a recursive list-scheduling algorithm that exploits the \GSPG structure to assign sub-graphs to individual processors, and uses dynamic programming to decide which tasks in these sub-gaphs should be checkpointed. Furthermore, it is possible to efficiently compute the expected makespan for the solutionproduced by this algorithm, using a first-order approximation of task weights and existing evaluation algorithms for 2-state probabilistic DAGs. We assess the performance of our algorithm for production workflow configurations, comparing it to (i)~an approach in which all application data is checkpointed, which corresponds to the standard way in which most production workflows are executed today; and (ii)~an approach in which no application data is checkpointed. Our results demonstrate that our algorithm strikes a good compromise between these two approaches, leading to lower checkpointing overhead than the former and to better resilience to failure than the latter. To the best of our knowledge, this is the first scheduling/checkpointing algorithm for workflow applications with fail-stop failures that considers workflow structures more general than mere linear chains of tasks.
Type de document :
Rapport
[Research Report] RR-9068, Inria. 2017, pp.33
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01525378
Contributeur : Equipe Roma <>
Soumis le : jeudi 9 novembre 2017 - 18:01:29
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09
Document(s) archivé(s) le : samedi 10 février 2018 - 13:57:54

Fichier

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

Identifiants

  • HAL Id : hal-01525378, version 3

Citation

Li Han, Louis-Claude Canon, Henri Casanova, Yves Robert, Frédéric Vivien. Checkpointing Workflows for Fail-Stop Errors. [Research Report] RR-9068, Inria. 2017, pp.33. 〈hal-01525378v3〉

Partager

Métriques

Consultations de la notice

189

Téléchargements de fichiers

55