Skip to Main content Skip to Navigation

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
Abstract : In order to express parallelism, parallel sparse direct solvers take advantage of the elimination tree to exhibit tree-shaped task graphs, where nodes represent computational tasks and edges represent data dependencies. One of the pre-processing stages of sparse direct solvers consists of mapping computational resources (processors) to these tasks. The objective is to minimize the factorization time by exhibiting good data locality and load balancing. The proportional mapping technique is a widely used approach to solve this resource-allocation problem. It achieves good data locality by assigning the same processors to large parts of the elimination tree. However, it may limit load balancing in some cases. In this paper, we propose a dynamic mapping algorithm based on proportional mapping. This new approach, named Steal, relaxes the data locality criterion to improve load balancing. In order to validate the newly introduced method, we perform extensive experiments on the PaStiX sparse direct solver. It demonstrates that our algorithm enables better static scheduling of the numerical factorization while keeping good data locality.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download
Contributor : Equipe Roma <>
Submitted on : Wednesday, February 26, 2020 - 11:05:54 AM
Last modification on : Wednesday, October 14, 2020 - 9:22:02 AM
Long-term archiving on: : Wednesday, May 27, 2020 - 3:17:23 PM


Files produced by the author(s)


  • HAL Id : hal-02491495, version 1


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⟩



Record views


Files downloads