One, two, three . . . infinity: lower bounds for parallel computation

ABSTRACT

In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRIORITY PRAM. These models differ in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds. We consider PRAM's with n processors, each having arbitrary computational power. We provide the first separation results between these two models in two extreme cases: when the size m of the shared memory is small (m ≤ n&egr;, &egr; < 1), and when it is infinite. In the case of small memory, the PRIORITY model can be faster than the COMMON model by a factor of &THgr;(log n), and this lower bound holds even if the COMMON model is probabilistic. In the case of infinite memory, the gap between the models can be a factor of &OHgr;(log log log n). We develop new proof techniques to obtain these results. The technique used for the second lower bound is strong enough to establish the first tight time bounds for the PRIORITY model, which is the strongest parallel computation model. We show that finding the maximum of n numbers requires &THgr;(log log n) steps, generalizing a result of Valiant for parallel computation trees.

REFERENCES

• B: Berne, C. Grap/,s and Hyperp'&phs, North- Holland, 1973.
• CD: 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]
• FRW: Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806745]
• FW: 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]
• Ga: Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
• Go: 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]
• GRS: Graham, R.L., RothschiM, B.L., and Spencer, J.H. Ramsey Theory, Wiley and Sons, 1080.
• Gr: Albert Gordon Greenberg, Efficient algorithms for multiple access channels, 1983
• Ha: Hansel, G. Nombre miu~~ de cootacts de creature oeueca/res pour ~er une fouo- Ciou booleeuue symetrique de ~ v~ables, C. R Acad. Sci. Paris 258,1964, pp. 6037-6040.
• KMR: Kun~, il., Miller, G., and Rudolph, L. Sublinear Parallel AlgoritAm for C!omputing tAe Greatest Common Divisor of TWo latef~rs, Proc. 25fa Annual Symposium on Foundations of Computer Science, 1984, pp. ?-11.
• Ku: Kucer~, L. Parallel Computation and Conflicts in Memory Access, Information Processing Letters, vol. 14, no. 2, 1982, pp. 95*96.
• MR: Meyer Auf der Heide, F., and Reischuk, R. On the Limits to Speed Up Parallel Machines by Lar~ Hardware and Unbounded Communico. t/on, Proc. 25fA Annual Symposium on Foundations of Computer Science, 1984, pp. 56*64.
• Pi: Pippenger, N. An Informstion. TAeoretic Me. tbod in Combinatorial Theory, Journal of Combinatorial Theory, vol. 23, no. 1, July 1977, pp. 99-104.
• SV: ShUoach, Y., and Vishkin, U. Findinf~ The Maximum, Merg/ua' and Sorting* On Parallel Models of Computation, J.Alg, v.2, 1981, pp. 88-102.
• TV: Tarjao, R.E, Vishkiu, U. F/ud/u&, Biconnected Components and Computin~ Tree Functions in Logarithmic Parallel Time, Proc. 25th Annual Symposium on Foundations of Computer Sci* ence, 1984, pp. 12-20.
• V: Valiant, L. Parallelism in Computation Prob. Ictus, SIAM J. Comput., vol. 4, no. 5, 1975, pp. 348-3~.
• VW: Vishkia, U., and Wigderson, A. Trade-offs Between Depth and Width in PaedJel Computa. tiou, to appear in SIAM J. Computing.
• Y: Yao, A. Probabilistic Computations: Towards & Unified Measure of Complexity, Proc. 18fh Annual Symposium on Foundations of Computer Science, 19T?, pp.222-227.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory, Verification