On Cluster Resource Allocation for Multiple Parallel Task Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2010

On Cluster Resource Allocation for Multiple Parallel Task Graphs

Henri Casanova
  • Fonction : Auteur
  • PersonId : 841811
Frédéric Suter

Résumé

Many scientific applications can be structured as Parallel Task Graphs (PTGs), that is, graphs of data-parallel tasks. Adding data-parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses additional scheduling challenges. In this paper, we study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance without compromising fairness among the PTGs. We consider the range of previously proposed scheduling algorithms applicable to this problem, both from the applied and the theoretical literature, and we propose minor improvements when possible. Our main contribution is an extensive evaluation of these algorithms in simulation, using both synthetic and real-world application configurations, using two different metrics for performance and one metric for fairness. We identify a handful of algorithms that provide good trade-offs when considering all these metrics. The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm.
Fichier principal
Vignette du fichier
RR-7224.pdf (358.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00461692 , version 1 (05-03-2010)

Identifiants

  • HAL Id : inria-00461692 , version 1

Citer

Henri Casanova, Frédéric Desprez, Frédéric Suter. On Cluster Resource Allocation for Multiple Parallel Task Graphs. [Research Report] RR-7224, INRIA. 2010, pp.31. ⟨inria-00461692⟩
242 Consultations
219 Téléchargements

Partager

Gmail Facebook X LinkedIn More