New lower bounds for parallel computation

Publisher Website
Google Scholar
Abstract
Lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write PRAM with unlimited shared memory and unlimited power of individual processors (denoted by PRIORITY(∞)): It is proved that with a number of processors polynomial in n , Ω (log n ) time is needed for addition, multiplication or bitwise OR of n numbers, when each number has n ' bits. Hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. This improves a beautiful result of Meyer auf der Heide and Wigderson [22]. They proved a log n lower bound using Ramsey-type techniques. Using Ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. However, for the case of polynomially many processors, this upper bound is more than a polynomial in n . An Ω (log n ) lower bound is given for PRIORITY(∞) with n o(1) processors on a function with inputs from {0, 1}, namely for the function ƒ( x 1 , … , x n ,) = Σ n l - 1 x l a i where a is fixed and x i ε {0, 1}. Finally, by a new efficient simulation of PRIORITY(∞) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a PRIORITY(∞) cannot compute PARITY in constant time, and with n O(1) processors Ω(√log n ) time is needed. The simulation technique is of independent interest since it can serve as a general tool to translate circuit lower bounds into PRAM lower bounds. Further, the lower bounds in (1) and (2) remain valid for probabilistic or nondeterministic concurrent-read concurrent-write PRAMS.

This publication has 14 references indexed in Scilit: