Skip to Main content Skip to Navigation
Journal articles

Optimal Checkpointing Strategies for Iterative Applications

Yishu Du 1, 2, 3 Loris Marchal 1, 2 Guillaume Pallez 4 Yves Robert 1, 2 
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 TADAAM - Topology-Aware System-Scale Data Management for High-Performance Computing
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Abstract : This work provides an optimal checkpointing strategy to protect iterative applications from fail-stop errors. We consider a general framework, where the application repeats the same execution pattern by executing consecutive iterations, and where each iteration is composed of several tasks. These tasks have different execution lengths and different checkpoint costs. Assume that there are n tasks and that task a i , where 0 ≤ i < n, has execution time t i and checkpoint cost c i. A naive strategy would checkpoint after each task. Another naive strategy would checkpoint at the end of each iteration. A strategy inspired by the Young/Daly formula would work for √ 2µcave seconds, where µ is the application MTBF and cave is the average checkpoint time, and checkpoint at the end of the current task (and repeat). Another strategy, also inspired by the Young/Daly formula, would select the task a min with smallest checkpoint cost c min and would checkpoint after every p th instance of that task, leading to a checkpointing period pT , where T = n−1 i=0 a i is the time per iteration. One would choose the period so that pT ≈ √ 2µc min to obey the Young/Daly formula. All these naive and Young/Daly strategies are suboptimal. Our main contribution is to show that the optimal checkpoint strategy is globally periodic, and to design a dynamic programming algorithm that computes the optimal checkpointing pattern. This pattern may well checkpoint many different tasks, and this across many different iterations. We show through simulations, both from synthetic and real-life application scenarios, that the optimal strategy outperforms the naive and Young/Daly strategies.
Complete list of metadata

https://hal.inria.fr/hal-03338278
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Monday, September 27, 2021 - 10:55:05 AM
Last modification on : Friday, July 1, 2022 - 3:51:47 AM

File

tpds-complete.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Yishu Du, Loris Marchal, Guillaume Pallez, Yves Robert. Optimal Checkpointing Strategies for Iterative Applications. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2022, 33 (3), pp.507-522. ⟨10.1109/TPDS.2021.3099440⟩. ⟨hal-03338278v2⟩

Share

Metrics

Record views

85

Files downloads

167