Checkpointing strategies for parallel jobs

Abstract : This work provides an analysis of checkpointing strategies for minimizing expected job execution times in an environment that is subject to processor failures. In the case of both sequential and parallel jobs, we give the optimal solution for exponentially distributed failure inter-arrival times, which, to the best of our knowledge, is the rst rigorous proof that periodic check- pointing is optimal. For non-exponentially distributed failures, we develop a dynamic programming algorithm to maximize the amount of work completed before the next failure, which provides a good heuristic for minimizing the ex- pected execution time. Our work considers various models of job parallelism and of parallel checkpointing overhead. We rst perform extensive simulation experiments assuming that failures follow Exponential or Weibull distributions, the latter being more representative of real-world systems. The obtained results not only corroborate our theoretical ndings, but also show that our dynamic programming algorithm signi cantly outperforms previously proposed solutions in the case of Weibull failures. We then discuss results from simulation experi- ments that use failure logs from production clusters. These results con rm that our dynamic programming algorithm signi cantly outperforms existing solutions for real-world clusters.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00560582
Contributor : Marin Bougeret <>
Submitted on : Friday, April 22, 2011 - 3:16:41 PM
Last modification on : Friday, May 3, 2019 - 12:08:01 PM
Long-term archiving on : Sunday, December 4, 2016 - 2:25:32 AM

File

RR-7520.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

335

Files downloads

400