Reducing Communication in Distributed Asynchronous Iterative Methods
Communication costs are an important factor in the performance of massively parallel algorithms. We present a new asynchronous parallel algorithm for solving sparse linear systems that reduces communication compared to other algorithms on distributed memory machines. Implemented using passive one sided remote memory access (RMA) MPI functions, the new method is a variation of the Southwell method, where rows are relaxed greedily, instead of sequentially, by choosing the row with the maximum residual norm. A process relaxes its rows if it holds the maximum residual norm among its neighbors at any given moment. Experimental results show that this method reduces communication costs compared to several other asynchronous iterative methods and the classic synchronous Jacobi method.
ICCS