Efficient low-contention parallel algorithms

ABSTRACT

The queue-read, queue-write (QRQW) PRAM model [GMR94] permits concurrent reading and writing, but at a cost proportional to the number of readers/writers to a memory location in a given step. The QRQW model reflects the contention properties of most parallel machines more accurately than either the well-studied CRCW or EREW models: the CRCW model does not adequately penalize algorithms with high contention to shared memory locations, while the EREW model is too strict in its insistence on zero contention at each step. Of primary practical and theoretical interest, then, is the design of fast and efficient QRQW algorithms for problems for which all previous algorithms either suffer from high contention, fail to be fast, or fail to be work-optimal. This paper describes low-contention, fast, work-optimal QRQW PRAM algorithms for the fundamental problems of finding a random permutation, parallel hashing, load balancing, and sorting. There is no known fast, work-optimal EREW algorithm known for finding a random permutation or for parallel hashing. For load balancing, we improve upon the EREW result whenever the ratio of the maximum to the average load is not too large. We show that the logarithmic dependence of the QRQW running time on this ratio is inherent by providing a matching lower bound. We demonstrate the performance advantage of a QRQW random permutation algorithm, compared with the popular EREW algorithm, by implementing and running both algorithms on the MasPar MP-1. Finally, we extend the work-time framework for the design of parallel algorithms to account for contention, and relate it to the QRQW PRAM model. We use our QRQW load balancing algorithm, as well as the QRQW linear compaction algorithm in [GMR94], to provide automatic tools for processor allocation—an issue that needs to be handled when translating an algorithm from its work-time presentation into the explicit PRAM description.

REFERENCES

• AH92: Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.463-472, September 1992, Orlando, Florida, United States
• AKS83: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• BCH+93: Guy E. Blelloch , Jonathan C. Hardwick , Siddhartha Chatterjee , Jay Sipelstein , Marco Zagha, Implementation of a portable nested data-parallel language, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.102-111, May 19-22, 1993, San Diego, California, United States
• BKK93: P. Beame, M. Kik, and M. Kutylowski. Information broadcasting by exclusive-write PRAMs. Parallel Processing Letters, 1993. To appear.
• Ble89: G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989 [doi>10.1109/12.42122]
• BM76: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• BMV92: O. Berkman, Y. Matias, and U. Vishkin. Randomized range-maxima in nearly-constant parallel time. computational complexity, 2:350-373, 1992.
• Bre74: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• Chl89: B. S. Chlebus, Parallel iterated bucket sort, Information Processing Letters, v.31 n.4, p.181-183, May 22, 1989 [doi>10.1016/0020-0190(89)90120-8]
• Col88: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• CV89: Richard Cole , Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation, v.81 n.3, p.334-352, June 1989 [doi>10.1016/0890-5401(89)90036-9]
• DM90: M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
• FKS84: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• Gil91: J. Gil. Fast load balancing on a PRAM. In Proc. of the 3rd 1EEE Symposium on Parallel and Distributed Computing, pages 10-17, December 1991.
• GM91: 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
• GM94a: Joseph Gil , Yossi Matias, Simple Fast Parallel Hashing, Proceedings of the 21st International Colloquium on Automata, Languages and Programming, p.239-250, July 11-14, 1994
• GM94b: J. Gil a#ad Y. Matias. Simple fast parallel hashing by oblivious execution. Technical report, AT&T Bell Laboratories, Murray Hill, N J, 1994. Submitted for publication.
• GMR94: Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
• GMV91: Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
• Hag89: T. Hagerup, Hybridsort revisited and parallelized, Information Processing Letters, v.32 n.1, p.35-39, July 3, 1989 [doi>10.1016/0020-0190(89)90066-5]
• Hag91: Torben Hagerup, Fast parallel generation of random permutations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.405-416, June 1991, Madrid, Spain
• JáJ92: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• KR90: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• KRS90: Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
• MA80: H. Meijer and S.G. Akl. The design and analysis of a new hybrid sorting algorithm. Information Processing Letters, 10:213-218, 1980.
• Mas91: MasPar Computer Corporation, 749 North Mary Avenue, Sunnyvale, CA 94086. MasPar System Overview, document 9300.0100, revision A 3, March 1991.
• Mat92: Y. Matias. Highly Parallel Randomized Aigorith. mica. PhD thesis, Tel Aviv University, israel, December 1992.
• MR89: G.L. Miller and J. H. ReiL Parallel tree contraction part 1: Fundamentals. In S. Mica}i, editor, Randomness and Computation, volume 5, pages 47-72. JAI Press, 1989.
• MS91: 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
• MV91: 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]
• MV92: Y. Matias and U. Vishkin. A note on simulations and integer sorting. Manuscript, 1992.
• Rei85: R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM Journal on Computing, 14(2):396-409, May 1985.
• Rei93: John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• RR89: S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
• Sie89: A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proc. o/the 30th IEEE Syrup. on Foundations of Computer Science, pages 20-25, 1989.
• Val90: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• Yao77: A.C.C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. of the 18th IEEE Syrup. on Foundations of Computer Science, pages 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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory, Verification