Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers

This paper develops shared memory algorithms for asynchronous processor systems that require the same expected work as the best PRAM algorithms. These algorithms operate efficiently under general asynchronous processor behavior (where individual processor speeds are allowed to vary widely over time). This paper achieves these results by employing a methodology that uses randomization to schedule subtasks of a parallel program. The resulting algorithms allow processors to (i) have arbitrary asynchronous behavior, (ii) have fail-stop errors, (iii) join a computation at any time, and (iv) have no unique identifiers. This paper develops a performance metric for asynchronous parallel computations, called work, which is the total number of instructions (including busy-waiting instructions) performed by a collection of parallel processors during a computation. The main result is to compute any associative function of n variables with O (n) expected work, using up to n/ n^* n asynchronous processors, and with O (n n) expected work using up to n processors. These results provide a synchronization primitive that can be used to transform any PRAM program into an asynchronous PRAM program.