Skip to Main content Skip to Navigation
Reports

Resilient Scheduling of Moldable Parallel Jobs to Cope with Silent Errors

Abstract : We study the resilient scheduling of moldable parallel jobs on high-performance computing (HPC) platforms. Moldable jobs allow for choosing a processor allocation before execution, and their execution time obeys various speedup models. The objective is to minimize the overall completion time of the jobs, or the makespan, when jobs can fail due to silent errors and hence may need to be re-executed after each failure until successful completion. Our work generalizes the classical scheduling framework for failure-free jobs. To cope with silent errors, we introduce two resilient scheduling algorithms, LPA-List and Batch-List, both of which use the List strategy to schedule the jobs. Without knowing a priori how many times each job will fail, LPA-List relies on a local strategy to allocate processors to the jobs, while Batch-List schedules the jobs in batches and allows only a restricted number of failures per job in each batch. We prove new approximation ratios for the two algorithms under several prominent speedup models (e.g., roofline, communication, Amdahl, power, monotonic, and a mixed model). An extensive set of simulations is conducted to evaluate different variants of the two algorithms, and the results show that they consistently outperform some baseline heuristics. Overall, our best algorithm is within a factor of 1.6 of a lower bound on average over the entire set of experiments, and within a factor of 4.2 in the worst case.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/hal-02614215
Contributor : Anne Benoit Connect in order to contact the contributor
Submitted on : Monday, January 25, 2021 - 3:05:38 PM
Last modification on : Thursday, January 20, 2022 - 4:14:00 PM

File

rr9340-v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02614215, version 2

Collections

Citation

Anne Benoit, Valentin Le Fèvre, Lucas Perotin, Padma Raghavan, Yves Robert, et al.. Resilient Scheduling of Moldable Parallel Jobs to Cope with Silent Errors. [Research Report] RR-9340, Inria - Research Centre Grenoble – Rhône-Alpes. 2021. ⟨hal-02614215v2⟩

Share

Metrics

Les métriques sont temporairement indisponibles