Comparison of Static and Dynamic Resource Allocation Strategies for Matrix Multiplication

Olivier Beaumont 1, 2 Lionel Eyraud-Dubois 1, 2 Abdou Guermouche 1, 3 Thomas Lambert 1, 2
1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
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
3 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Abstract : The tremendous increase in the size and heterogeneity of supercomputers makes it very difficult to predict the performance of a scheduling algorithm. In this context, relying on purely static scheduling and resource allocation strategies, that make scheduling and allocation decisions based on the dependency graph and the platform description, is expected to lead to large and unpredictable makespans whenever the behavior of the platform does not match the predictions. For this reason, the common practice in most runtime libraries is to rely on purely dynamic scheduling strategies, that make short-sighted scheduling decisions at runtime based on the estimations of the duration of the different tasks on the different available resources and on the state of the machine. In this paper, we consider the special case of Matrix Multiplication, for which a number of static allocation algorithms to minimize the amount of communications have been proposed. Through a set of extensive simulations, we analyze the behavior of static, dynamic, and hybrid strategies, and we assess the possible benefits of introducing more static knowledge and allocation decisions in runtime libraries.
Keywords : runtime scheduling static scheduling dynamic scheduling Matrix Multiplication hybrid strategies
Type de document :
Communication dans un congrès
26th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2015, Oct 2015, Florianopolis, Brazil. IEEE 27th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2015, 2015, Proceedings of the 26th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2015. 〈IEEE〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01163936
Contributeur : Olivier Beaumont <>
Soumis le : jeudi 15 octobre 2015 - 19:28:30
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : mercredi 26 avril 2017 - 23:58:24

Fichier

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

Identifiants

  • HAL Id : hal-01163936, version 2

Collections

INRIA | UNIV-BORDEAUX | LABRI | IMB

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Abdou Guermouche, Thomas Lambert. Comparison of Static and Dynamic Resource Allocation Strategies for Matrix Multiplication. 26th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2015, Oct 2015, Florianopolis, Brazil. IEEE 27th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2015, 2015, Proceedings of the 26th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2015. 〈IEEE〉. 〈hal-01163936v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

372

Téléchargements de fichiers

566

Contact


archive-ouverte@inria.fr