Scheduling Moldable Jobs on Failure-Prone Platforms
Anne Benoît, Valentin Le Fèvre, Lucas Perotin, Padma Raghavan, Yves Robert, Hongyang Sun · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
This paper focuses on the resilient scheduling of moldable parallel jobson high-performance computing (HPC) platforms. Moldable jobs allow for choosing aprocessor allocation before execution, and their execution time obeys various speedup models. The scheduling objective is to minimize the overall completion time, or makespan, assuming that jobs are subject to arbitrary failure scenarios, and hence may need to bere-executed each time they fail until they complete successfully. This work generalizes the classical framework where jobs are known offline and do not fail. We introduce alist-based algorithm, and prove new approximation ratios for three prominent speedupmodels (roofline, communication, Amdahl). We also introduce a batch-based algorithm,where each job is allowed only a restricted number of failures per batch, and prove a new approximation ratio for the arbitrary speedup model. We conduct an extensive set of simulations to evaluate and compare different variants of the two algorithms, and the results show that they consistently outperform the baseline heuristics. In particular, the list algorithm performs better for the roofline and communication models, while the batch algorithm has better performance for the Amdahl’s model. Overall, our best algorithm is within a factor of 1.47 of a lower bound on average over the whole set of experiments, and within a factor of 1.8 in the worst case.