What Makes Affinity-Based Schedulers So Efficient ?

Olivier Beaumont 1, 2 Loris Marchal 3
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : The tremendous increase in the size and heterogeneity of supercomputers makes it very difficult to predict the performance of a scheduling algorithm. Therefore, dynamic solutions, where scheduling decisions are made at runtime have overpassed static allocation strategies. The simplicity and efficiency of dynamic schedulers such as Hadoop are a key of the success of the MapReduce framework. Dynamic schedulers such as StarPU, PaRSEC or StarSs are also developed for more constrained computations, e.g. task graphs coming from linear algebra. To make their decisions, these runtime systems make use of some static information, such as the distance of tasks to the critical path or the affinity between tasks and computing resources (CPU, GPU,\ldots) and of dynamic information, such as where input data are actually located. In this paper, we concentrate on two elementary linear algebra kernels, namely the outer product and the matrix multiplication. For each problem, we propose several dynamic strategies that can be used at runtime and we provide an analytic study of their theoretical performance. We prove that the theoretical analysis provides very good estimate of the amount of communications induced by a dynamic strategy, thus enabling to choose among them for a given problem and architecture.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00875487
Contributeur : Olivier Beaumont <>
Soumis le : mardi 22 octobre 2013 - 10:57:16
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 7 avril 2017 - 14:34:18

Fichier

RRRuntimeSchedulers.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00875487, version 1

Citation

Olivier Beaumont, Loris Marchal. What Makes Affinity-Based Schedulers So Efficient ?. 2013. 〈hal-00875487〉

Partager

Métriques

Consultations de la notice

375

Téléchargements de fichiers

153