Back
 AM  Vol.4 No.12 A , December 2013
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.
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

 
 
Top