R. B. Boppana
ABSTRACT
We obtain tight bounds on the relative powers of the Priority and Common models of parallel random-access machines (PRAMs). Specifically we prove that:
The Element Distinctness function of n integers, though solvable in constant time on a Priority PRAM with n processors, requires Ω(A(n,p)) time to solve on a Common PRAM with p ≥ n processors, where A(n,p) = n log n/p log (n/p log n + 1).
One step of a Priority PRAM with n processors can be simulated on a Common PRAM with p processors in Ο(A(n,p)) steps.
As an example, the results show that the time separation between Priority and Common PRAMs each with n processors is Θ(log n/log log n).
- M. Ajtai, D. Karabeg, J. Koml6s, and E. Szemer~di (1988), "Sorting in average time o(log n)," preprint.Google Scholar
- P. Beame and J. Hastad (1987), "Optimal bounds for decision problems on the CRGW P R,AM," 19th STOU, 83-93. Google ScholarDigital Library
- H. Chernoff (1952), "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, "Ann Math Sial. 23, 493-509.Google Scholar
- B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik (1988), "Efficient simulations between concurrent-read concurrent-write PRAM models," 13th Syrup. Math. Found. Comp. Sci., Lecture Notes in Comp. Sci. 324, Springer-Verlag, 231-239. Google ScholarDigital Library
- S. A. Cook, C. Dwork, and R. R. eischuk (1986), "Upper and lower bounds for parMlel random access machines without simultaneous writes," SIAM J. Comp. 15, 87-97. Google ScholarDigital Library
- I. Csiszfi. r and J. KSrner (1982), Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press. Google ScholarDigital Library
- F. E. Fich, F. Meyer auf der Heide, and A. Wigderson (1986), "Lower bounds for parallel random-access machines with unbounded shared memory," Advances in Computing Research.Google Scholar
- F. E. Fich, P. L. Ragde, and A. Wigderson (1988), "Simulations among concurrent-write PRAMs," Algorithmica 3, 43-52.Google ScholarDigital Library
- M. Fredman and J. Koml6s (1984), "On the size of separating systems and families of perfect hash functions,'' SIAM J. Alg. Disc. Meth. 5, 61-68.Google ScholarDigital Library
- R. L. Graham, B. L. Rothschild, and J. H. Spencer (1980), Ramsey Theory, John Wiley and Sons.Google Scholar
- V. Grolmusz and P. Ragde (1987), "incomparability in parallel computation," 28th FOCS, 89-98.Google Scholar
- J. KSrner (1986), "Fredman-Koml6s bounds and information theory," SIAM J. AIg. Disc. Megh. 7, 560- 570. Google ScholarDigital Library
- L. Ku~era (1982), "Parallel computation and conflicts in memory access," Inf. Proc. Letters 14, 93-96.Google ScholarCross Ref
- F. Meyer auf der Heide and A. Wigderson (1985), "The complexity of parallel sorting," 25th FOCS, 532- 540.Google Scholar
- P. Ragde, W. L. Steiger, E. Szemer~di, and A. Wigderson (1988), "The parallel complexity of element distinctness is f~((logn)~/2),'' SIAM J. Disc. Math. 1, 399-410. Google ScholarDigital Library
Index Terms
- Optimal separations between concurrent-write parallel machines
Recommendations
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access machines
It was shown some years ago that the computation time for many important Boolean functions of $n$ arguments on concurrent-read exclusive-write parallel random-access machines (CREW PRAMs) of unlimited size is at least $arphi (n) \approx 0.72\log_...
Improved Parallel Integer Sorting without Concurrent Writing
We show thatnintegers in the range 1, ,ncan be sorted stably on an EREW PRAM usingO(t) time andO(n(lognloglogn+(logn)2/t)) operations, for arbitrary givent lognloglogn, and on a CREW PRAM usingO(t) time andO(n(logn+logn/2t/logn)) operations, for ...
Simulations among concurrent-write PRAMs
AbstractThis paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [G], and the COMMON PRAM [K]. Improving the trivial and seemingly optimalO(logn) simulation, we show that ...
Comments