Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-02491495
Contributor : Equipe Roma <>
Submitted on : Wednesday, February 26, 2020 - 11:05:54 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:53 PM
Document(s) archivé(s) le : Wednesday, May 27, 2020 - 3:17:23 PM

File

rr9328.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02491495, 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. [Research Report] RR-9328, Inria Rhône-Alpes. 2020, pp.21. ⟨hal-02491495⟩

Share

Metrics

Record views

138

Files downloads

166