Asynchronous Approach to Memory Management in Sparse Multifrontal Methods on Multiprocessors

ABSTRACT

This research covers the Intel^{?}^{ }Direct Sparse Solver for Clusters, the software that implements a direct method for solving the Ax = b equation with sparse symmetric matrix A on a cluster. This method, researched by Intel, is based on Cholesky decomposition and could be considered as extension of functionality PARDISO from Intel^{?}^{ }MKL. To achieve an efficient work balance on a large number of processes, the so-called “multifrontal” approach to Cholesky decomposition is implemented. This software implements parallelization that is based on nodes of the dependency tree and uses MPI, as well as parallelization inside a node of the tree that uses OpenMP directives. The article provides a high-level description of the algorithm to distribute the work between both computational nodes and cores within a single node, and between different computational nodes. A series of experiments shows that this implementation causes no growth of the computational time and decreases the amount of memory needed for the computations.

Cite this paper

A. Kalinkin and K. Arturov, "Asynchronous Approach to Memory Management in Sparse Multifrontal Methods on Multiprocessors,"*Applied Mathematics*, Vol. 4 No. 12, 2013, pp. 33-39. doi: 10.4236/am.2013.412A004.

A. Kalinkin and K. Arturov, "Asynchronous Approach to Memory Management in Sparse Multifrontal Methods on Multiprocessors,"

References

[1] [1] I. S. Duff and J. K. Reid, “The Multifrontal Solution of Indefinite Sparse Symmetric Linear,” ACM Transactions on Mathematical Software, Vol. 9, No. 3, 1983, pp. 302325.

http://dx.doi.org/10.1145/356044.356047

[2] J. W. H. Liu, “The Multifronal Method for Sparse Matrix Solution: Theory and Practice,” Siam Review, Vol. 34, No. 1, 1992, pp. 82-109. http://dx.doi.org/10.1137/1034004

[3] P. R. Amestoy, I. S. Duff and C. Vomel, “Task Scheduling in an Asynchronous Distributed Memory Multifrontal Solver,” SIAM Journal on Matrix Analysis and Applications, Vol. 26, No. 2, 2005, pp. 544-565.

http://dx.doi.org/10.1137/S0895479802419877

[4] P. R. Amestoy, I. S. Duff, S. Pralet and C. Voemel, “Adapting a Parallel Sparse Direct Solver to SMP Architectures,” Parallel Computing, Vol. 29, No. 11-12, 2003, pp. 1645-1668.

http://dx.doi.org/10.1016/j.parco.2003.05.010

[5] P. R. Amestoy, A. Guermouche, J.-Y. L’Excellent and S. Pralet, “Hybrid Scheduling for the Parallel Solution of Linear Systems”, Parallel Computing, Vol. 32, No. 2, 2006, pp. 136-156.

http://dx.doi.org/10.1177/109434209300700105

[6] P. R. Amestoy and I. S. Duff, “Memory Management Issues in Sparse Multifrontal Methods on Multiprocessors,” The International Journal of Supercomputer Applications, Vol. 7, 1993, pp. 64-82.

[7] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent and J. Koster, “A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling,” SIAM Journal on Matrix Analysis and Applications, Vol. 23, No. 1, 2001, pp. 1541. http://dx.doi.org/10.1137/S0895479899358194

[8] M. Bollhofer and O. Schenk, “Combinatorial Aspects in Sparse Direct Solvers,” GAMM Mitteilungen, Vol. 29, 2006, pp. 342-367.

[9] O. Schenk and K. Gartner, “On Fast Factorization Pivoting Methods for Sparse Symmetric Indefinite Systems,” Technical Report, Department of Computer Science, University of Basel, 2004.

[10] G. Karypis and V. Kumar, “Parallel multilevel graph partitioning,” Processing of 10th International Parallel Symposium, 1996, pp. 314-319.

[11] G. Karypis and V. Kumar, “A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering,” Journal of Parallel and Distributed Computing, Vol. 48, 1998, pp. 71-85.

http://dx.doi.org/10.1006/jpdc.1997.1403

[12] K. Schloegel, G. Karypis and V. Kumar, “Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning” Euro-Par 2000 Parallel Processing, 2000, pp. 296-310

[13] A. Pothen and C. Sun, “A Mapping Algorithm for Parallel Sparse Cholesky Factorization,” SIAM: SIAM Journal on Scientific Computing, Vol. 14, No. 5, 1993, pp. 12531257.

http://dx.doi.org/10.1137/0914074

[14] G. Karypis and V. Kumar, “Parallel Multilevel Graph Partitioning,” Proceedings of the 10th International Parallel Processing Symposium, 1996, pp. 314-319.

[15] Metis, http://glaros.dtc.umn.edu/gkhome/views/metis

[16] MKL, Intel^{®} Math Kernel Library

http://software.intel.com/en-us/intel-mkl

[1] [1] I. S. Duff and J. K. Reid, “The Multifrontal Solution of Indefinite Sparse Symmetric Linear,” ACM Transactions on Mathematical Software, Vol. 9, No. 3, 1983, pp. 302325.

http://dx.doi.org/10.1145/356044.356047

[2] J. W. H. Liu, “The Multifronal Method for Sparse Matrix Solution: Theory and Practice,” Siam Review, Vol. 34, No. 1, 1992, pp. 82-109. http://dx.doi.org/10.1137/1034004

[3] P. R. Amestoy, I. S. Duff and C. Vomel, “Task Scheduling in an Asynchronous Distributed Memory Multifrontal Solver,” SIAM Journal on Matrix Analysis and Applications, Vol. 26, No. 2, 2005, pp. 544-565.

http://dx.doi.org/10.1137/S0895479802419877

[4] P. R. Amestoy, I. S. Duff, S. Pralet and C. Voemel, “Adapting a Parallel Sparse Direct Solver to SMP Architectures,” Parallel Computing, Vol. 29, No. 11-12, 2003, pp. 1645-1668.

http://dx.doi.org/10.1016/j.parco.2003.05.010

[5] P. R. Amestoy, A. Guermouche, J.-Y. L’Excellent and S. Pralet, “Hybrid Scheduling for the Parallel Solution of Linear Systems”, Parallel Computing, Vol. 32, No. 2, 2006, pp. 136-156.

http://dx.doi.org/10.1177/109434209300700105

[6] P. R. Amestoy and I. S. Duff, “Memory Management Issues in Sparse Multifrontal Methods on Multiprocessors,” The International Journal of Supercomputer Applications, Vol. 7, 1993, pp. 64-82.

[7] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent and J. Koster, “A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling,” SIAM Journal on Matrix Analysis and Applications, Vol. 23, No. 1, 2001, pp. 1541. http://dx.doi.org/10.1137/S0895479899358194

[8] M. Bollhofer and O. Schenk, “Combinatorial Aspects in Sparse Direct Solvers,” GAMM Mitteilungen, Vol. 29, 2006, pp. 342-367.

[9] O. Schenk and K. Gartner, “On Fast Factorization Pivoting Methods for Sparse Symmetric Indefinite Systems,” Technical Report, Department of Computer Science, University of Basel, 2004.

[10] G. Karypis and V. Kumar, “Parallel multilevel graph partitioning,” Processing of 10th International Parallel Symposium, 1996, pp. 314-319.

[11] G. Karypis and V. Kumar, “A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering,” Journal of Parallel and Distributed Computing, Vol. 48, 1998, pp. 71-85.

http://dx.doi.org/10.1006/jpdc.1997.1403

[12] K. Schloegel, G. Karypis and V. Kumar, “Parallel Multilevel Algorithms for Multi-Constraint Graph Partitioning” Euro-Par 2000 Parallel Processing, 2000, pp. 296-310

[13] A. Pothen and C. Sun, “A Mapping Algorithm for Parallel Sparse Cholesky Factorization,” SIAM: SIAM Journal on Scientific Computing, Vol. 14, No. 5, 1993, pp. 12531257.

http://dx.doi.org/10.1137/0914074

[14] G. Karypis and V. Kumar, “Parallel Multilevel Graph Partitioning,” Proceedings of the 10th International Parallel Processing Symposium, 1996, pp. 314-319.

[15] Metis, http://glaros.dtc.umn.edu/gkhome/views/metis

[16] MKL, Intel

http://software.intel.com/en-us/intel-mkl