Access Restriction

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

   Open content in new tab
Source: ACM Digital Library