Load balancing requires &OHgr;(log*n) expected time

ABSTRACT

In order to obtain very fast parallel algorithms, it is almost always necessary to have some sort of load balancing procedure, so that processors which have finished their required tasks can help processors which have not. If the overloaded processors are not helped, then the expected time of the entire algorithm suffers. In general, we would like to distribute the remaining work as evenly as possible among the processors, or more formally, given at most n independent tasks distributed in an arbitrary way among n processors, we would like to redistribute the tasks so that each processor contains O(1) tasks. We show here that even on the strongest randomized CRCW PRAM model, for a simple random distribution tasks load balancing requires &OHgr;(log* n) expected time. Gil, Matias, and Vishkin [9] give an O(log* n) expected time randomized algorithm which solves the load balancing problem in the worst case, so the lower bound is tight. By reduction we show that both Padded Sort [12], and Linear Approximate Compaction [13] require &OHgr;(log* n) expected time. We note that our basic technique is one of the few parallel lower bound techniques known which only require 0/1 inputs. We also note that the bounds given in this paper do not place any restriction on the instruction set of the machine, the amount of information which can be stored in a memory cell, or on the number of memory cells.

REFERENCES

• 1: Miklos Ajtai , Michael Ben-Or, A theorem on probabilistic constant depth Computations, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.471-474, December 1984 [doi>10.1145/800057.808715]
• 2: D. Angluin and L. G. Valiant, "Fast probabilistic algorithms for hamiltonian circuits and matchings," }. o/Comp, and System Sci., pp. 155-193, 1979.
• 3: Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989 [doi>10.1145/65950.65958]
• 4: Dany Breslauer , Zvi Galil, An optimal O(log n)time parallel string matching algorithm, SIAM Journal on Computing, v.19 n.6, p.1051-1058, Dec. 1990 [doi>10.1137/0219072]
• 5: Dany Breslauer , Zvi Galil, A lower bound for parallel string matching, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.439-443, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103465]
• 6: 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]
• 7: J. Gil, "Fast load balancing on pram,' Manuscript, 1990.
• 8: Joseph Gil , Yossi Matias, Fast hashing on a PRAM—designing by expectation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 28-30, 1991, San Francisco, California, United States
• 9: J. Gil, Y. Matias, and U. Vishkin, "A fast parallel dictionary," in Proc. 3~nd Syrup. on Found. of Comp. Sci., 1991. to appear.
• 10: T. Hagerup, "Fast parallel space allocation, estimation and integer sorting," Technical Report no. pending, Max-Planck-Institut ffir Informatik, 1991.
• 11: Torben Hagerup , T. Radzik, Every robust CRCW PRAM can efficiently simulate a PRIORITY PRAM, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.117-124, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97677]
• 12: Philip D. MacKenzie , Quentin F. Stout, Ultra-fast expected time parallel algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.414-423, January 28-30, 1991, San Francisco, California, United States
• 13: Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
• 14: U. Vishkin, Deterministic sampling—a new technique for fast pattern matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.170-180, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100235]
• 15: A. Yao, "Probabilistic computations: Towards a unified measure of complexity," in Proc. 18th Syrup. on Found. o/Comp. Sci., pp. 222-227, 1977.

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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Theory, Verification