Asynchronous algorithms for shared memory parallel computers
Ramesh Subramonian · 1992
We propose a new model of asynchronous parallel computation, the A-PRAM, which is a more realistic reflection of shared memory multi-processor systems than the synchronous Parallel Random Access Machine (PRAM) model. The PRAM assumption that all processors operate in lock-step synchrony is expensive to implement for large multi-processor systems. The PRAM model is good for designing algorithms and writing programs. However, its unrealistic assumptions distance it from practical machines. So, one of our goals is to allow programmers to write PRAM programs and then provide an efficient and correct simulation for these programs on realistic machines. We show that any n-processor PRAM program can be simulated on an A-PRAM with no loss in asymptotic efficiency using up to $n\over\log n$ processors, provided minor restrictions on the asynchrony are imposed. We achieve these results by using randomization to schedule sub-tasks of a parallel program. We use randomization in a novel way which makes our algorithms fault-tolerant and greatly reduces inefficiency arising out of busy-waiting. The resulting algorithms allow processors to (i) have arbitrary asynchronous behavior; (ii) fail at arbitrary times; (iii) join a computation at any time; and (iv) not require unique identifiers. We develop a performance metric for asynchronous parallel computations which we call work which is the total number of instructions (including busy-waiting) performed by a collection of parallel processors during a computation. We use work as a metric of performance since time is often not meaningful in an asynchronous environment. However, if there are p processors running nearly synchronously, then the time taken would be expected $O({work\over p}).$ In the A-PRAM setting, we design efficient algorithms for the following problems: computing an associative function, prefix sums, list ranking, sorting, transitive closure and evaluating a bounded degree fan-in circuit. We also propose hardware support for asynchrony, the TPRAM, a tagged A-PRAM. It uses memory tags to handle one of the fundamental problems of asynchrony, a slow write that overwrites a current, correct value. On this stronger model, we can get faster simulations, at the cost of a modest increase in total work.