Lower bounds in parallel machine computation
Paul W. Beame, Stephen A Cook · 1987
In this thesis we prove lower bounds for parallel random access machines (PRAM's) which consist of processors acting synchronously and accessing a common shared memory. PRAM's were introduced by Fortune and Wyllie and Goldschlager and have proved to be very popular among researchers wishing to describe parallel algorithms. We consider versions of the PRAM model with three different kinds of rules for concurrently accessing the shared memory: exclusive read-exclusive write (EREW), concurrent read-exclusive write (CREW), and concurrent read-concurrent write (CRCW). For the CRCW PRAM, we prove a distinction between the computation of functions that have a large output range and decision problems that have a two element range. We give a CRCW PRAM lower bound for function computation which is based on the range of the function involved. This yields a tight $\Omega$(log n) lower bound for the problem of summing n integers of n bits each. By much more complicated techniques we show that parity and a large number of other decision problems have tight $\Omega$(log n/log log n) lower bounds on the CRCW PRAM. These are the only tight bounds known for non-trivial decision problems on the CRCW PRAM. Furthermore, by similar methods we show that for every $T = o$(log n/log log n) there are functions related to those defined by Sipser that can be easily computed in time T but not in time $T - 2$. This yields a strict time hierarchy of CRCW PRAM's with polynomially bounded resources. Our results are distinguished from most previous lower bound work for PRAM's in that they do not place restrictions on the instruction sets of the machines and (when necessary) they only place very minimal restrictions on the resources available for computations. The results we prove complement and extend two previous lower bounds for such general PRAM's: a tight $\Omega$(log n) lower bound by Cook, Dwork and Reischuk on the time to compute the OR of n bits on the CREW PRAM, and tight lower bounds by Vishkin and Wigderson for computing parity on the CRCW PRAM in the case that only very small numbers of memory cells are available. (Abstract shortened with permission of author.)