Concurrent threads and optimal parallel minimum spanning trees algorithm

ABSTRACT

This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(logn) time. Specifically, we present a new algorithm to solve these problems in O(logn) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the “OR” of nbit requires &OHgr;(log n time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.

REFERENCES

• 1: Roy Armoni , Amnon Ta-Shma , Avi Wigderson , Shiyu Zhou, SL ⊆L^4/3, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.230-239, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258593]
• 2: B. Awerbuch , Y. Shiloach, New connectivity and MSF algorithms for shuffle-exchange network and PRAM, IEEE Transactions on Computers, v.36 n.10, p.1258-1263, Oct. 1987 [doi>10.1109/TC.1987.1676869]
• 3: Bernard Chazelle, A Faster Deterministic Algorithm for Minimum Spanning Trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.22, October 19-22, 1997
• 4: Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000 [doi>10.1145/355541.355562]
• 5: Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
• 6: CHONG, K. W. 1996. Finding minimum spanning trees on the EREW PRAM. In Proceedings of the International Computer Symposium (Taiwan, China). pp. 7-14.
• 7: Ka Wong Chong , Tak Wah Lam, Finding connected components in O(log n loglog n) time on the EREW PRAM, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.11-20, January 25-27, 1993, Austin, Texas, United States
• 8: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 9: Richard Cole , Philip N. Klein , Robert E. Tarjan, Finding minimum spanning forests in logarithmic time and linear work using random sampling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.243-250, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237563]
• 10: COLE, R., AND VISHKIN, U. 1986. Approximate and exact parallel scheduling with applications to list, tree, and graph problems. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 478-491.
• 11: 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]
• 12: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 13: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 14: GAZIT, H. 1986. An optimal randomized parallel algorithm for finding connected components in a graph. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 492-501.
• 15: Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can shared-memory model serve as a bridging model for parallel computation?, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.72-83, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258500]
• 16: Shay Halperin , Uri Zwick, Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.438-447, January 28-30, 1996, Atlanta, Georgia, United States
• 17: Yujie Han , Robert A. Wagner, An efficient and fast parallel-connected component algorithm, Journal of the ACM (JACM), v.37 n.3, p.626-642, July 1990 [doi>10.1145/79147.214077]
• 18: 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]
• 19: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 20: Donald B. Johnson , Panagiotis Metaxas, Connected components in O(lg3/2|V|) parallel time for the CREW PRAM (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.688-697, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185437]
• 21: Donald B. Johnson , Panagiotis Metaxas, A parallel algorithm for computing minimum spanning trees, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.363-372, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141917]
• 22: David Ron Karger, Random sampling in graph optimization problems, Stanford University, Stanford, CA, 1995
• 23: David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
• 24: David R. Karger , Noam Nisan , Michal Parnas, Fast connected components algorithms for the EREW PRAM, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.373-381, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141920]
• 25: 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
• 26: Yael Maon , Baruch Schieber , Uzi Vishkin, Parallel ear decomposition search (EDS) and st-numbering in graphs, Theoretical Computer Science, v.47 n.3, p.277-298, Nov., 1986
• 27: MILLER,G.L.,AND RAMACHANDRAN, V. 1986. Efficient parallel ear decomposition with applications. Manuscript. MSRI, Berkeley, Calif.
• 28: NISAN, N., SZEMEREDI, E., AND WIGDERSON, A. 1992. Undirected connectivity in O(log 1.5 n) space. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 24-29.
• 29: Seth Pettie, Finding Minimum Spanning Trees in O(m alpha(m,n)) Time, University of Texas at Austin, Austin, TX, 1999
• 30: Seth Pettie , Vijaya Ramachandran, A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.233-244, August 08-11, 1999
• 31: Seth Pettie , Vijaya Ramachandran, An Optimal Minimum Spanning Tree Algorithm, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.49-60, July 09-15, 2000
• 32: Chung Keung Poon , Vijaya Ramachandran, A Randomized Linear Work EREW PRAM Algorithm to Find a Minimum Spanning Forest, Proceedings of the 8th International Symposium on Algorithms and Computation, p.212-222, December 17-19, 1997
• 33: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 34: TARJAN,R.E.,AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14, 862-874.
• 35: 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]
• 36: VISHKIN, U. 1985. On efficient parallel strong orientation. Inf. Proc. Lett. 20, 235-240.

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
EREW PRAM, connected components, minimum spanning trees, parallel algorithms