Ordonnancement avec tolérance aux pannes pour des tâches parallèles à nombre de processeurs programmable

Autor: Benoit, Anne, Le Fèvre, Valentin, Perotin, Lucas, Raghavan, Padma, Robert, Yves, Sun, Hongyang
Přispěvatelé: 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), 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), 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), Vanderbilt University [Nashville], Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Inria - Research Centre Grenoble – Rhône-Alpes, É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)
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Tâches parall
Ordonnancement tolérant aux pannes
scénario d’erreurs
Scéenario d’er
ordonnancement de liste
Approximation r
Resilient scheduling
Approximation ratios
Erreurs silenci
Moldable jobs
Silent errors
Parallel jobs
Modèles de ren
tâches parallèles
[INFO]Computer Science [cs]
nombre de processeurs variable
Nombre de proce
Failure scenario
Ordonnancement
List schedule
Ordonnancement tol ́erant aux pannes
tˆaches parall`eles
mod`eles de rendement
nombre de processeurs variable
sc ́enario d’erreurs
erreurs silencieuses
ordonnancement de liste
ordonnancement par paquets
facteurs d’approximatio
Facteurs d’appr
modèles de rendement
Speedup model
Transient errors
ordonnancement par paquets
Transient error
Failurescenario
Resilient sched
Batch schedule
erreurs silencieuses
facteurs d’approximation
Zdroj: [Research Report] RR-9340, Inria-Research Centre Grenoble – Rhône-Alpes. 2020
[Research Report] RR-9340, Inria-Research Centre Grenoble – Rhône-Alpes. 2021
Popis: 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.; Ce rapport étudie l’ordonnancement résilient de tâches sur des plateformes de calcul à haute performance. Dans le problème étudié, il est possible de choisir le nombre constant de processeurs effectuant chaque tâche, en déterminant le temps d’exécution de ces dernières selon différent modèles de rendement. Nous décrivons des algorithmes dont l’objectif est deminimiser le temps total d’exécution, sachant que les tâches sont susceptibles d’échouer et de devoir être ré-effectuées à chaque erreur. Ce problème est donc une généralisation du cadre classique où toutes les tâches sont connues à priori et n’échouent pas. Nous décrivons un algorithme d’ordonnancement par listes de priorité, et prouvons de nouvelles bornes d’approximation pour trois modèles de rendement classiques (roofline, communication, Amdahl). Nous décrivons également un algorithme d’ordonnancement par lots, au sein desquels les tâches pourront échouer un nombre limité de fois, et prouvons alors de nouvelles bornes d’approximation pour des rendements quelconques. Enfin, nous effectuons des expériences sur un ensemble complet d’exemples pour comparer les niveaux de performance de différentes variantes de nos algorithmes, significativement meilleurs que les algorithmes simples usuels .L’algorithme par listes surpasse l’algorithme par lots sur les modèles roofline et communication, tandis que l’inverse se produit pour le modèle Amdahl. Notre meilleure heuristique est en moyenne `a un facteur 1.47 d’une borne inférieure de la solution optimale, et à un facteur 1.8 dans le pire cas.
Databáze: OpenAIRE
Externí odkaz: