Analysis of Dynamic Scheduling Strategies for Matrix Multiplication on Heterogeneous Platforms

Olivier Beaumont 1, 2 Loris Marchal 3, 4
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The tremendous increase in the size and heterogeneity of supercomputers makes it very difficult to predict the perfor-mance of a scheduling algorithm. Therefore, dynamic solu-tions, 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 sched-ulers 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,. . .) and of dy-namic 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 sev-eral 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 dy-namic strategy and can be used in order to efficiently deter-mine thresholds used in dynamic scheduler, thus enabling to choose among them for a given problem and architecture.
Type de document :
Communication dans un congrès
ACM Symposium on High-Performance Parallel and Distributed Computing, Jun 2014, Vancouver, Canada. 2014, 〈10.1145/2600212.2600223〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01090254
Contributeur : Equipe Roma <>
Soumis le : jeudi 4 décembre 2014 - 10:56:51
Dernière modification le : mardi 16 janvier 2018 - 15:43:46
Document(s) archivé(s) le : lundi 9 mars 2015 - 05:55:43

Fichiers

article-HPDC-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Olivier Beaumont, Loris Marchal. Analysis of Dynamic Scheduling Strategies for Matrix Multiplication on Heterogeneous Platforms. ACM Symposium on High-Performance Parallel and Distributed Computing, Jun 2014, Vancouver, Canada. 2014, 〈10.1145/2600212.2600223〉. 〈hal-01090254〉

Partager

Métriques

Consultations de la notice

191

Téléchargements de fichiers

93