### New lower bounds for parallel computationNew lower bounds for parallel computation

Access Restriction
Subscribed

 Author Li, Ming ♦ Yesha, Yaacov Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1989 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{n},$ &OHgr; (log $\textit{n})$ time is needed for addition, multiplication or bitwise OR of $\textit{n}$ numbers, when each number has $\textit{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 $\textit{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 $\textit{n}.An$ &OHgr; (log $\textit{n})$ lower bound is given for PRIORITY(∞) with $\textit{n}o(1)$ processors on a function with inputs from {0, 1}, namely for the function $ƒ(\textit{x}1,$ … , $\textit{xn},)$ = &Sgr; $\textit{n}\textit{l}-$ 1 $\textit{xlai}$ where $\textit{a}$ is fixed and $\textit{xi}$ ε {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 $\textit{nO}(1)$ processors &OHgr;(@@@@log $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1989-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 36 Issue Number 3 Page Count 10 Starting Page 671 Ending Page 680

#### Open content in new tab

Source: ACM Digital Library