New lower bounds for parallel computation

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 n, &OHgr; (log n) time is needed for addition, multiplication or bitwise OR of n numbers, when each number has 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 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 n. An &OHgr; (log n) lower bound is given for PRIORITY(∞) with no(1) processors on a function with inputs from {0, 1}, namely for the function ƒ(x1, … , xn,) = &Sgr; nl- 1 xlai where a is fixed and xi &egr; {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 nO(1) processors &OHgr;(@@@@log 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.

REFERENCES

• 1: AJTAI, M. ~-formulae on finite structures. Ann. Pure Appl. Logic 24 (1983), 1-48.
• 2: AWERBUCH, B., AND SHILOACH, Y. New connectivity and MSF algorithms for ultracomputers and PRAM. In Proceedings of the IEEE Conference on Parallel Processing. IEEE, New York, 1983 pp. 175-179.
• 3: P Beame, Limits on the power of concurrent-write parallel machines, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.169-176, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12147]
• 4: Paul William Beame , S. A. Cook, Lower bounds in parallel machine computation, 1987
• 5: 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]
• 6: CHANDRA, A., STOCKMEYER, L., AND VISHKIN, U. Constant depth reducibility. SlAM J. Comput. 13 (1984), 324-429.
• 7: 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]
• 8: 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]
• 9: F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22151]
• 10: 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]
• 11: FURST, M., SAXE, J., AND SIPSER, M. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theor. 17, 1 (1984), 13-28.
• 12: 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]
• 13: HARTMANIS, J. Generalized Kolmogorov-complexity and the structure of feasible computations. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1983, pp. 439-445.
• 14: J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
• 15: D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979 [doi>10.1145/359138.359141]
• 16: KUCERA, L. Parallel computation and conflicts in memory access. Inf. Proc. Lett. 14, 2 (1982), 93-96.
• 17: Ming Li , Paul M. B. Vitanyi, Tape versus queue and stacks: the lower bounds, Information and Computation, v.78 n.1, p.56-85, July 1988 [doi>10.1016/0890-5401(88)90003-X]
• 18: M Li , Y Yesha, New lower bounds for parallel computation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.177-187, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12148]
• 19: Ming Li , Yaacov Yesha, Separation and lower bounds for ROM and nondeterministic models of parallel computation, Information and Computation, v.73 n.2, p.102-128, May 1987 [doi>10.1016/0890-5401(87)90017-4]
• 20: MAASS, W. Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines. Trans. AMS 292, 2 (Dec. 1985), 675-693.
• 21: MEYER A UF DER HEIDE, F., AND REISCHUK, R. On limits to speed up parallel machines by large hardware and unbounded communication. In Proceedings of the 25th IEEE Symposium on Foundation of Computer Science. IEEE, New York, 1984, pp. 56-64.
• 22: MEYER AUF DER HEIDE, F., AND WIGDERSON, A. The complexity of parallel sorting. In Proceedings of the 26th IEEE Annual Symposium on Theory of Computing. IEEE, New York, 1985, pp. 532-540.
• 23: I Parberry, On the time required to sum n semigroup elements on a parallel machine with simultaneous writes, Proc. of the Aegean workshop on computing on VLSI algorithms and architectures, p.296-304, August 1986, Loutraki, Greece
• 24: PAUL, W. Kolmogorov complexity and lower bounds. In Proceedings of the 2nd International Conference on Fundamentals of Computation Theory. 1979.
• 25: PAUL, W., SEIFERAS, J., AND SIMON J. An information-theoretic approach to time bounds for online computations. J. Comput. Syst. Sci. 23 (1981), 108-126.
• 26: PREPARATA, F.P. New parallel-sorting schemes. IEEE Trans. Comput. C-27, 669.
• 27: REIF, J. An optimal algorithm for integer sorting, in Proceedings of the 26th IEEE Symposium on Foundation of Computer Science. IEEE, New York, 1985, pp. 494-504.
• 28: K R Reischuk, Parallel machines and their communication theoretical limits, 3rd annual symposium on theoretical aspects of computer science on STACS 86, p.359-368, January 1986, Orsay, France
• 29: SHILOACH, Y., AND VISHKIN, U. Finding the maximum, merging and sorting on parallel models of computation. J. Algorithms 2 ( 1981), 88-102.
• 30: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• 31: STOCKMEYER, L., AND VISHKIN, U. Simulation of random access machines by circuits. SIAM J. Comput. 13 (1984), 409-422.
• 32: VISHKIN, U., AND WIGDERSON, A. Trade-offs between depth and width in parallel computation. SIAMJ. ComPut. 14, 2 (May 1985), 303-314.
• 33: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

INDEX TERMS

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

Additional 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)

General Terms:
Algorithms, Theory, Verification