×

Robust memory-aware mappings for parallel multifrontal factorizations. (English) Zbl 1360.65134

Summary: 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.

MSC:

65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation

Software:

MUMPS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] E. Agullo, {\it On the Out-of-Core Factorization of Large Sparse Matrices}, Ph.D. thesis, École Normale Supérieure de Lyon, 2008.
[2] E. Agullo, A. Guermouche, and J.-Y. L’Excellent, {\it Reducing the I/O volume in sparse out-of-core multifrontal methods}, SIAM J. Sci. Comput., 31 (2010), pp. 4774-4794. · Zbl 1205.65138
[3] P. R. Amestoy, I. S. Duff, J. Koster, and J.-Y. L’Excellent, {\it A fully asynchronous multifrontal solver using distributed dynamic scheduling}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15-41. · Zbl 0992.65018
[4] P. R. Amestoy, A. Guermouche, J.-Y. L’Excellent, and S. Pralet, {\it Hybrid scheduling for the parallel solution of linear systems}, Parallel Comput., 32 (2006), pp. 136-156.
[5] O. Beaumont and A. Guermouche, {\it Task scheduling for parallel multifrontal methods}, in Proceedings of Euro-Par 2007 Parallel Processing, 2007, pp. 758-766.
[6] I. S. Duff and J. K. Reid, {\it The multifrontal solution of indefinite sparse symmetric linear systems}, ACM Trans. Math. Software, 9 (1983), pp. 302-325. · Zbl 0515.65022
[7] I. S. Duff and J. K. Reid, {\it The multifrontal solution of unsymmetric sets of linear systems}, SIAM J. Sci. Statist. Comput., 5 (1984), pp. 633-641. · Zbl 0557.65017
[8] L. Eyraud-Dubois, L. Marchal, O. Sinnen, and F. Vivien, {\it Parallel scheduling of task trees with limited memory}, ACM Trans. Parallel Comput., 2 (2015), pp. 13:1-13:37, http://dx.doi.org/10.1145/2779052.
[9] A. George, {\it Nested dissection of a regular finite element mesh}, SIAM J. Numer. Anal., 10 (1973), pp. 345-363. · Zbl 0259.65087
[10] A. George, J. W. H. Liu, and E. Ng, {\it Communication results for parallel sparse Cholesky factorization on a hypercube}, Parallel Comput., 10 (1989), pp. 287-298. · Zbl 0687.65024
[11] A. Guermouche and J. Y. L’excellent, {\it Constructing memory-minimizing schedules for multifrontal methods}, ACM Trans. Math. Software, 32 (2006), pp. 17-32. · Zbl 1346.65019
[12] A. Guermouche, J.-Y. L’excellent, and G. Utard, {\it Impact of reordering on the memory of a multifrontal solver}, Parallel Comput., 29 (2003), pp. 1191-1218, http://dx.doi.org/10.1016/S0167-8191(03)00099-1.
[13] M. Jacquelin, L. Marchal, Y. Robert, and B. Uçar, {\it On optimal tree traversals for sparse matrix factorization}, in Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium, IEEE Computer Society, 2011, pp. 556-567.
[14] J.-Y. L’Excellent, {\it Multifrontal methods for large sparse systems of linear equations: Parallelism, memory usage, performance optimization and numerical issues}, habilitation à diriger des recherches, École Normale Supérieure de Lyon, 2012, also available online from http://tel.archives-ouvertes.fr/tel-00737751.
[15] J. W. H. Liu, {\it On the storage requirement in the out-of-core multifrontal method for sparse factorization}, ACM Trans. Math. Software, 12 (1986), pp. 249-264. · Zbl 0623.65031
[16] J. W. H. Liu, {\it An application of generalized tree pebbling to sparse matrix factorization}, SIAM J. Algebraic Discrete Methods, 8 (1987), pp. 375-395. · Zbl 0634.65015
[17] J. W. H. Liu, {\it The role of elimination trees in sparse factorization}, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 134-172. · Zbl 0697.65013
[18] S. Operto, J. Virieux, P. R. Amestoy, J.-Y. L’Excellent, L. Giraud, and H. Ben Hadj Ali, {\it{\it 3}D finite-difference frequency-domain modeling of visco-acoustic wave propagation using a massively parallel direct solver: A feasibility study}, Geophysics, 72 (2007), pp. 195-211, http://dx.doi.org/10.1190/1.2759835.
[19] A. Pothen and C. Sun, {\it A mapping algorithm for parallel sparse cholesky factorization}, SIAM J. Sci. Comput., 14 (1993), pp. 1253-1253. · Zbl 0785.65016
[20] G. N. Prasanna and B. R. Musicus, {\it Generalized multiprocessor scheduling and applications to matrix computations}, IEEE Trans. Parallel Distributed Systems, 7 (1996), pp. 650-664. · Zbl 0841.68016
[21] F.-H. Rouet, {\it Memory and Performance Issues in Parallel Multifrontal Factorizations and Triangular Solutions with Sparse Right-Hand Sides}, Ph.D. thesis, Institut National Polytechnique de Toulouse, 2012.
[22] C. Sánchez, H. B. Sipma, Z. Manna, and C. D. Gill, {\it Efficient distributed deadlock avoidance with liveness guarantees}, in Proceedings of the 6th ACM and IEEE International Conference on Embedded Software, ACM, 2006, p. 20.
[23] J. E. Savage, {\it Models of Computation: Exploring the Power of Computing}, Addison-Wesley, Reading, MA, 1998. · Zbl 0890.68059
[24] R. Schreiber, {\it A new implementation of sparse Gaussian elimination}, ACM Trans. Math. Software, 8 (1982), pp. 256-276. · Zbl 0491.65013
[25] W. M. Sid-Lakhdar, {\it Scaling Multifrontal Methods for the Solution of Large Sparse Linear Systems on Hybrid Shared-Distributed Memory Architectures}, Ph.D. dissertation, ENS Lyon, 2014.
[26] S. Wang, X. S. Li, J. Xia, Y. Situ, and M. V. De Hoop, {\it Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures}, SIAM J. Sci. Comput., 35 (2013), pp. C519-C544. · Zbl 1285.65017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.