Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
Ian Parberry, Pei Yan · SIAM Journal on Computing · 1991
The time required by a variant of the PRAM (a parallel machine model which consists of sequential processors which communicate by reading and writing into a common shared memory) to compute a certain class of functions called critical functions (which include the Boolean OR of n bits) is studied. Simultaneous reads from individual cells of the shared memory are permitted, but simultaneous writes are not. It is shown that any PRAM which computes a critical function must take at least $0.5\log n - O(1)$ steps, and that there exists a critical function which can be computed in $0.57\log n - O(1)$ steps. These bounds represent an improvement in the constant factor over those previously known.