Robust memory-aware mappings for parallel multifrontal factorizations

Emmanuel Agullo (1) , Patrick Amestoy (2, 3) , Alfredo Buttari (2, 4) , Abdou Guermouche (1) , Jean-Yves L'Excellent (5) , François-Henry Rouet (3, 6)

1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
2 IRIT - Institut de recherche en informatique de Toulouse
3 ENSEEIHT - Ecole Nationale Supérieure d'Electrotechnique, d'Electronique, d'Informatique, d'Hydraulique et de Télécommunications
4 CNRS - Centre National de la Recherche Scientifique
5 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
6 LBNL - Lawrence Berkeley National Laboratory [Berkeley]

We study the memory scalability of the parallel multifrontal factorization of sparse matrices. In particular, we are interested in controlling the active memory specific to the multifrontal factorization. We illustrate why commonly used mapping strategies (e.g., the proportional mapping) cannot provide a high memory efficiency, which means that they tend to let the memory usage of the factorization grow when the number of processes increases. We propose " memory-aware " algorithms that aim at maximizing the granularity of parallelism while respecting memory constraints. These algorithms provide accurate memory estimates prior to the factorization and can significantly enhance the robustness of a multifrontal code. We illustrate our approach with experiments performed on large matrices. 1. Introduction. We consider the memory scalability of sparse direct methods for the solution of linear systems on distributed-memory architectures. We focus on the multifrontal method [6, 7]. In this method, the consumed memory space consists of the factors to be computed (e.g., the L U factors of a given matrix A) and some temporary data that we call the active memory and that we describe in detail in the next section. Both the size of the factors and of the active memory depend on the input matrix permutation [12] (nested dissection methods are commonly used on large size problems); in this work we focus on studying the memory consumption resulting from different mapping techniques for a fixed matrix permutation. The active memory can represent a significant fraction of the total memory, and, as we will show in Section 2, it does not naturally scale when the number of processes increases. This means that the total memory usage of the factorization can dangerously grow with the number of processes. This highlights the need for mapping and scheduling algorithms that are able to control the active memory. In Section 3, we suggest memory-aware mapping algorithms that aim at maximizing the granularity of parallelism under a given memory constraint (the maximum memory usage of a process). We illustrate our approach in Section 4 with experiments carried out on large matrices using up to 256 processes. Although we focus on the multifrontal method, our study can be applied to any application with a tree-shaped workflow graph since, as we recall in the next subsection , the multifrontal method relies on the so-called elimination tree [24]. A similar problem has also been recently explored from a more theoretical point of view [8].

Mots clés: AMS subject classifications 05C50; 65F05; 65F50; 68W10

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Emmanuel Agullo, Patrick Amestoy, Alfredo Buttari, Abdou Guermouche, Jean-Yves L'Excellent, et al.. Robust memory-aware mappings for parallel multifrontal factorizations. SIAM Journal on Scientific Computing, 2016. ⟨hal-01334113v1⟩