Convergence Models and Surprising Results for the Asynchronous Jacobi Method

Asynchronous iterative methods for solving linear systems have been gaining attention due to the high cost of synchronization points in massively parallel codes. Since future parallel computers will likely achieve exascale performance, synchronization may become the primary bottleneck. Historically, theory on asynchronous iterative methods has focused on proving that an asynchronous version of a fixed point method will converge. Additionally, some theory has shown that asynchronous methods can be faster, which has been supported by shared memory experiments. In this paper, we introduce a new way to model asynchronous Jacobi using propagation matrices, which are similar in concept to iteration matrices. With this model, we show that asynchronous Jacobi can reduce the error even if some processes are delayed for a long period of time, which could be due to a hardware malfunction or a large imbalance. We also show that asynchronous Jacobi can converge when synchronous Jacobi does not. We compare model results to shared and distributed memory implementation results, and show that in practice, asynchronous Jacobi's convergence rate improves as we increase the number of processes.