The Asynchronous PRAM: A Semi-Synchronous Model for Shared Memory MIMD Machines (Thesis)

TitleThe Asynchronous PRAM: A Semi-Synchronous Model for Shared Memory MIMD Machines (Thesis)
Publication TypeTechnical Report
Year of Publication1989
AuthorsGibbons, P. B.
Other Numbers561

This thesis introduces the Asynchronous PRAM model of computation, of the design and analysis of algorithms that are suitable for large parallel machines in which processors communicate via a distributed, shared memory. The Asynchronous PRAM is a variant of the well-studied PRAM model which differs from the PRAM in two important respects: (i) the processors run asynchronously and there is an explicit charge for synchronization, and (ii) there is a non-unit time cost to access the shared memory.Many new algorithms are presented for the Asynchronous PRAM model. We modify a number of PRAM algorithms for improved asymptotic time and processor complexity in the Asynchronous PRAM. We show general classes of problems for which the time complexity can be improved by restructuring the computation. We prove lower bounds that reflect limitation on information flow and load balancing in this model. Simulation results between the Asynchronous PRAM and various known synchronous models are presented as well.We introduce a post office gossip game for studying the inherent synchronization complexity of coordinating processors using pairwise synchronization primitives. Results are presented that compare the relative power of various such primitives. These results and techniques are used to reduce the amount of synchronization in Asynchronous PRAM algorithms.Furthermore, we discuss a programming model based on the Asynchronous PRAM. We introduce the notion of a semi-synchronous programming model, a model for repeatable asynchronous programs. Repeatable programs, in which the output and all intermediate results are the same every time the program is run on a particular input, greatly simplify the tasks of writing, debugging, analyzing, and testing programs.Finally, we discuss hardware support for the Asynchronous PRAM model. In particular, we present a cache protocol suitable for the Asynchronous PRAM and a new technique for barrier synchronous PRAM and a new technique for barrier synchronization.

Bibliographic Notes

ICSI Technical Report TR-89-062

Abbreviated Authors

P. B. Gibbons

ICSI Publication Type

Technical Report