Relations between concurrent-write models of parallel computation

ABSTRACT

Shared-memory models for parallel computation (e.g. parallel RAMs) are very natural and already widely used for parallel algorithm design. The various models differ from each other mainly in the way they restrict simultaneous processor access to a shared memory cell. Understanding the relative power of these models is important for understanding the power of parallel computation. Two recent pioneering works shed some light in this question. Cook and Dwork [CD] (resp. Snir [S]) present problems that, for instances of size n, can be solved in O(1) time on an n-processor PRAM that allows simultaneous write (resp. read) access to shared memory, but require &Ohgr;(log n) time on a PRAM that forbids simultaneous write (resp. read) access, regardless of the number of processors. When allowing simultaneous write access, the model must include a write-conflict resolution scheme. Three such schemes were suggested in the literature, and in this paper we study their relative power. Here the situation is more sensitive, as a small increase in the number of processors allows constant time simulation of the strongest by the weakest. By fixing the number of processors and parametrizing the number of shared memory cells, we obtain tight separation results between the models, thereby partially answering open questions of Vishkin [V]. New lower bounds techniques are developed for this purpose.

REFERENCES

• 1: A.K. Chandra, L.J. Stockmeyer and U. Vishkin, Complexity Theory of Unbounded Fan-in Parallelism, Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pages 1-13.
• 2: Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802196]
• 3: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 4: Leslie M. Goldschlager, A universal interconnection pattern for parallel computers, Journal of the ACM (JACM), v.29 n.4, p.1073-1086, Oct. 1982 [doi>10.1145/322344.322353]
• 5: Ludek Kucera, Parallel Computation and Conflicts in Memory Access, Information Processing Letters, volume 14, number 2, 1982, pages 93-96. January 1963, pages 589-591.
• 6: Yossi Shiloach and Uzi Vishkin, An O(log n) Parallel Connectivity Algorithm, Journal of Algorithms, volume 3, 1982, pages 57-67.
• 7: Marc Snir, On Parallel Searching, Department of Computer Science, The Hebrew University of Jerusalem, Research Report 83-21, June 1983.
• 8: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 9: Uzi Vishkin, Implementation of Simultaneous Memory Address Access In Models That Forbid It, Tech. Rept. 210, Israel Institute of Technology, July 1981. (to appear in J. Alg.)
• 10: Uzi Vishkin and Avi Wigderson, Trade-offs Between Depth and Width in Parallel Computation, to appear in SIAM J. Computing.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.2 Network Protocols
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance