A Generic Approach to Scheduling and Checkpointing Workflows

Li Han (1, 2) , Valentin Le Fèvre (1) , Louis-Claude Canon (3, 1) , Yves Robert (1, 4) , Frédéric Vivien (1)

1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
2 ECNU - East China Normal University [Shangaï]
3 FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
4 ICL - Innovative Computing Laboratory [Knoxville]

This work deals with scheduling and checkpointing strategies to execute scientific workflows on failure-prone large-scale platforms. To the best of our knowledge, this work is the first to target fail-stop errors for arbitrary workflows. Most previous work addresses soft errors, which corrupt the task being executed by a processor but do not cause the entire memory of that processor to be lost, contrarily to fail-stop errors. We revisit classical mapping heuristics such as HEFT and MinMin and complement them with several checkpointing strategies. The objective is to derive an efficient trade-off between checkpointing every task (CkptAll), which is an overkill when failures are rare events, and checkpointing no task (CkptNone), which induces dramatic re-execution overhead even when only a few failures strike during execution. Contrarily to previous work, our approach applies to arbitrary workflows, not just special classes of dependence graphs such as M-SPGs (Minimal Series-Parallel Graphs). Extensive experiments report significant gain over both CkptAll and CkptNone, for a wide variety of workflows.

Ce travail porte sur l’ordonnancement et les stratégies de checkpoint utiles à l’exécution d’applications scientifiques structurées en forme de graphes de tâches, sur des plateformes à grande échelle, sensibles aux fautes. A notre connaissance, ce travail est le premier à traiter des erreurs fatales pour des graphes de tâches arbitraires. La plupart des travaux existants traitent des erreurs silencieuses, qui corrompent la tâche en train d’être exécutée sur un processeur mais ne provoquent pas la disparition totale de la mémoire de ce processeur, contrairement aux erreurs fatales. Nous revisitons les heuristiques d’allocation classiques telles que HEFT et MinMin, auxquelles nous rajoutons plusieurs stratégies de checkpoint. L’objectif est de trouver un juste milieu efficace entre checkpointer toutes les tâches (CkptAll), ce qui est trop lourd quand les erreurs surviennent rarement, et n’en checkpointer aucune (CkptNone), ce qui induit des temps de ré-exécution élevés, même quand seulement quelques fautes surgissent durant l’exécution. Contrairement à ce qui a été fait précédemment, notre approche s’applique à des graphes de tâches quelconques, pas seulement à certaines classes spéciales de graphes de tâches comme les M-SPGs (Graphe Série-Parallèle Minimal). Plusieurs expériences montrent un gain significatif par rapport à CkptAll et CkptNone, pour une large variété de graphes de tâches.

Mots clés: fail-stop error

Mots clés: workflow; checkpoint; erreur fatale; résilience

Domaines: Informatique [cs]

Li Han, Valentin Le Fèvre, Louis-Claude Canon, Yves Robert, Frédéric Vivien. A Generic Approach to Scheduling and Checkpointing Workflows. [Research Report] RR-9167, Inria. 2018, pp.1-29. ⟨hal-01766352v2⟩