Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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 &OHgr;(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 &Ogr;(A(n,p)) steps. As an example, the results show that the time separation between Priority and Common PRAMs each with n processors is &THgr;(log n/log log n).

REFERENCES

• 1: M. Ajtai, D. Karabeg, J. Koml6s, and E. Szemer~di (1988), "Sorting in average time o(log n)," preprint.
• 2: P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States [doi>10.1145/28395.28405]
• 3: 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.
• 4: Bogdan S. Chlebus , Krzysztof Diks , Torben Hagerup , Tomasz Radzik, Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models, Proceedings of the Mathematical Foundations of Computer Science 1988, p.231-239, August 29-September 02, 1988
• 5: Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
• 6: Imre Csiszar , Janos G. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Inc., Orlando, FL, 1982
• 7: 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.
• 8: F. E. Fich, P. L. Ragde, and A. Wigderson (1988), "Simulations among concurrent-write PRAMs," Algorithmica 3, 43-52.
• 9: 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.
• 10: R. L. Graham, B. L. Rothschild, and J. H. Spencer (1980), Ramsey Theory, John Wiley and Sons.
• 11: V. Grolmusz and P. Ragde (1987), "incomparability in parallel computation," 28th FOCS, 89-98.
• 12: János Körner, Fredman-Kolmo´s bounds and information theory, SIAM Journal on Algebraic and Discrete Methods, v.7 n.4, p.560-570, Oct. 1986 [doi>10.1137/0607062]
• 13: L. Ku~era (1982), "Parallel computation and conflicts in memory access," Inf. Proc. Letters 14, 93-96.
• 14: F. Meyer auf der Heide and A. Wigderson (1985), "The complexity of parallel sorting," 25th FOCS, 532- 540.
• 15: Prabhakar Ragde , William Steiger , Endre Szemerédi , Avi Widgerson, The parallel complexity of element distinctness is &OHgr;( :.PC12 :3WZ:Hlog:9T:Cn:A:9U)*, SIAM Journal on Discrete Mathematics, v.1 n.3, p.399-410, Aug. 1988 [doi>10.1137/0401040]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory