Enhancing scalability and load balancing of Parallel Selected Inversion via tree-based asynchronous communication

We develop a method for improving the parallel scalability of computations that involve asynchronous task execution. We apply this method to 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. Computing 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 using asynchronous point-to-point MPI communications combined with a binary tree based data propagation scheme. Because multiple restricted collective communications may take place at the same time, 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 that the use of this heuristic leads to over 5x speedup for a number of test matrices. It also mitigates the performance variability introduced by an inhomogeneous network topology.