Simulations among concurrent-write PRAMs

This paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM G], and the COMMON PRAM K]. Improving the trivial and seemingly optimalO(logn) simulation, we show that one step of a PRIORITY machine can be simulated byO(logn/(log logn)) steps of a COMMON machine with the same number of processors (and more memory). We further prove that this is optimal, if processor communication is restricted in a natural way.Support for this research was provided by NSF Grants MCS-8402676 and MCS-8120790, DARPA Contract No. N00039-84-C-0089, an IBM Faculty Development Award, and an NSERC postgraduate scholarship.