Performance Analysis of Asynchronous Parallel Jacobi

The directed acyclic graph (DAG) associated with a parallel al- gorithm captures the order in which separate local computations are completed and how their outputs are subsequently used in further com- putations. Unlike in a synchronous parallel algorithm the DAG asso- ciated with an asynchronous parallel algorithm is not predetermined. Instead it is a product of the asynchronous timing dynamics of the machine and, as such, it is best thought of as a pseudorandom vari- able. In this paper we present a new tighter bound on the rate of convergence of asynchronous parallel Jacobi (APJ), which is based on statistical properties of the DAG and is valid for systems which satisfy a standard sufficient condition for convergence. We also describe an experiment in which we make a precise log of the calculations taking place during an implementation of APJ on a distributed memory multicore machine, which enables us to reconstruct and study the DAG. We demonstrate that our bound provides a good approximation of the true rate of convergence in these examples and show how problems in the algorithm�s implementation can affect the asynchronous timing dynamics and in turn the rate of convergence of the algorithm