Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Improving mapping for sparse direct solvers: A trade-off between data locality and load balancing

Changjiang Gou 1, 2 Ali Al Zoobi 3 Anne Benoit 1 Mathieu Faverge 4 Loris Marchal 1 Grégoire Pichon 1 Pierre Ramet 4
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Résumé : Les solveurs parallèles directs creux se servent de l’arbre d’ élimination pour obtenir des graphes de tâches sous forme d’arbres, où les nœuds représentent des tâches de calcul, et les arêtes des dépendances de données. Une des premières étapes de ces solveurs consiste à placer les tâches sur les ressources (les processeurs). Le but est de minimiser le temps de factorisation, en ayant un bon équilibrage de charge et une bonne localité des données. La technique de place-ment proportionnel est utilisée afin d’avoir une bonne localité : un même processeur va traiter une branche de l’arbre d’élimination et il y a peu de communications à faire lors de la factorisation. Cependant, dans certains cas, l’équilibrage de charge n’est pas parfait. Nous proposons un nouvel algorithme dynamique de placement, basé sur le placement proportionnel, qui améliore l’équilibrage de charge au prix d’une légère perte en localité. De nombreuses expériences et simulations sur le solveur direct creux PaStiX permettent de démontrer que notre algorithme permet un meilleur ordonnancement pour la factorisation numérique, tout en gardant une bonne localité des données.
Type de document :
Communication dans un congrès
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-02973315
Contributeur : Equipe Roma <>
Soumis le : mercredi 21 octobre 2020 - 09:24:58
Dernière modification le : lundi 16 novembre 2020 - 09:58:14

Fichier

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

Identifiants

  • HAL Id : hal-02973315, version 1

Citation

Changjiang Gou, Ali Al Zoobi, Anne Benoit, Mathieu Faverge, Loris Marchal, et al.. Improving mapping for sparse direct solvers: A trade-off between data locality and load balancing. EuroPar 2020 - 26th International European Conference on Parallel and Distributed Computing, Aug 2020, Warsaw / Virtual, Poland. ⟨hal-02973315⟩

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

72