Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
Stephen A Cook, Cynthia Dwork, Rüdiger Reischuk · SIAM Journal on Computing · 1986
One of the frequently used models for a synchronous parallel computer is that of a parallel random access machine, where each processor can read from and write into a common random access memory. Different processors may read the same memory location at the same time, but simultaneous writing is disallowed. We show that even if we allow nonuniform algorithms, an arbitrary number of processors, and arbitrary instruction sets, $\Omega (\log n)$ is a lower bound on the time required to compute various simple functions, including sorting n keys and finding the logical “or” of n bits. We also prove a surprising time upper bound of $.72\log _2 n$ steps for these functions, which beats the obvious algorithms requiring $\log _2 n$ steps.If simultaneous writes are allowed, there are simple algorithms to compute these functions in a constant number of steps.