Design and Comparison of Resilient Scheduling Heuristics for Parallel Jobs

Autor: Anne Benoit, Yves Robert, Hongyang Sun, Valentin Le Fèvre, Padma Raghavan
Přispěvatelé: Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Vanderbilt University [Nashville], Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), The data from Mira logs was generated from resources of the Argonne Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC02-06CH11357., Inria - Research Centre Grenoble – Rhône-Alpes
Rok vydání: 2020
Předmět:
Zdroj: IPDPS Workshops
APDCM 2020-Workshop on Advances in Parallel and Distributed Computational Models (colocated with IPDPS)
APDCM 2020-Workshop on Advances in Parallel and Distributed Computational Models (colocated with IPDPS), May 2020, New Orleans, LA, United States. pp.1-27
[Research Report] RR-9296, Inria-Research Centre Grenoble – Rhône-Alpes. 2019, pp.31
DOI: 10.1109/ipdpsw50202.2020.00099
Popis: This paper focuses on the resilient scheduling of parallel jobs on highperformance computing (HPC) platforms to minimize the overall completion time, or makespan. We revisit the problem by assuming that jobs are subject to transient or silent errors, and hence may need to be re-executed each time they fail to complete successfully. This work generalizes the classical framework where jobs are known offline and do not fail: in this classical framework, list scheduling that gives priority to longest jobs is known to be a 3-approximation when imposing to use shelves, and a 2-approximation without this restriction. We show that when jobs can fail, using shelves can be arbitrarily bad, butunrestricted list scheduling remains a 2-approximation. The paper focuses on the design of several heuristics, some list-based and some shelf-based, along with different priority rules and backfflling options. We assess and compare their performance through an extensive set of simulations, using both synthetic jobs and log traces from the Mira supercomputer.; Ce rapport s’intéresse à l’ordonnancement résilient de tâches parallèles sur des plates-formes de calcul haute performance (HPC), avec pour but de minimiser le temps total d’exécution. Nous considérons que les tâches sont confrontées à des erreurs silencieuses, et il faut donc les ré exécuter après chaque faute afin d’avoir une exécution correcte. Ces travaux généralisent le cadre classique où les tâches sont connues avant l’exécution et ne sont pas confrontées à des erreurs. Dans le cas sans erreurs, les ordonnancements de liste donnant la priorité aux plus longues tâches sont connus pour être une 3-approximation pour un ordonnancement par étagères, et une 2-approximation sans la restriction des étagères. Nous montrons qu’avec des erreurs, l’utilisation d’étagères peut aboutir à un ordonnancement arbitrairement loin de l’optimal, alors que l’ordonnancement de liste classique reste une 2-approximation. Nous concevons plusieurs heuristiques, à base de listes ou d’étagères, avec différentes règles de priorité et de réservation. Nous évaluons et comparons leur performance dans une campagne de simulations, en utilisant à la fois des tâches générées aléatoirement, et des tâches d’applications exécutées sur le supercalculateur Mira.
Databáze: OpenAIRE
Externí odkaz: