Abstract

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, \textbackslash Omega (\textbackslash 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\textbackslash log ₂ n steps for these functions, which beats the obvious algorithms requiring \textbackslash log ₂ n steps.If simultaneous writes are allowed, there are simple algorithms to compute these functions in a constant number of steps.