2015/04/18 by Mathias Jacquelin, Lin Lin, Jacquelin, Mathias +5 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Mathematical Software (cs.MS) #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC #cs.MS
paper · pdf · doi:10.48550/arxiv.1504.04714
arxiv created 2015/04/18 · openalex publication_date 2015/04/18 · arxiv updated 2015/04/21 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We develop a method for improving the parallel scalability of the recently developed parallel selected inversion algorithm [Jacquelin, Lin and Yang 2014], named PSelInv, on massively parallel distributed memory machines. In the PSelInv method, we compute selected elements of the inverse of a sparse matrix A that can be decomposed as A = LU, where L is lower triangular and U is upper triangular. Updating these selected elements of A-1 requires restricted collective communications among a subset of processors within each column or row communication group created by a block cyclic distribution of L and U. We describe how this type of restricted collective communication can be implemented by using asynchronous point-to-point MPI communication functions combined with a binary tree based data propagation scheme. Because multiple restricted collective communications may take place at the same time in the parallel selected inversion algorithm, we need to use a heuristic to prevent processors participating in multiple collective communications from receiving too many messages. This heuristic allows us to reduce communication load imbalance and improve the overall scalability of the selected inversion algorithm. For instance, when 6,400 processors are used, we observe over 5x speedup for test matrices. It also mitigates the performance variability introduced by an inhomogeneous network topology.