A more practical PRAM model

This paper introduces the Asynchronous PRAM model of computation, a variant of the PRAM in which the processors run asy ~chronously and there is an explicit charge for synchronization. A fanfily of Asynchrooous PRAM's are defined, varying in the types of synchronization steps permitted and the costs for accessing the shared memory. Algorithms, lower bounds, and simulation results are presented for an interesting member of the family. unit time in the model. Although an idealized model, the PRAM has proven to be a useful model for studying parallel computation (see KRS8 for a survey of results). The model is simple and relatively easy to use: its shared memory abstraction hides the details of the interprocessor communication and synchronization.