A comparison of parallel algorithms for connected components

ABSTRACT

This paper presents a comparison of the pragmatic aspects of some parallel algorithms for finding connected components, together with optimizations on these algorithms. The algorithms being compared are two similar algorithms by Shiloach-Vishkin [22] and Awerbuch-Shiloach [2], a randomized contraction algorithm based on algorithms by Reif [21] and Phillips [20], and a hybrid algorithm [11]. Improvements are given for the first two to improve performance significantly, although without improving their asymptotic complexity. The hybrid combines features of the others and is generally the fastest of those tested. Timings were made using NESL [4] code as executed on a Connection Machine 2 and Cray Y-MP/C90.

REFERENCES

• 1: A. Agrawal, L. Nekludova, and W. Lim. A parallel O(log n) algorithm for finding connected components in planar images. Technical Report TMC-122, Thinking Machines Corporation, Feb. 1987.
• 2: B. Awerbuch and Y. Shfloach. New connectivity and MSF algorithms for Ultracomputer and P RAM. In Proceedings of the International Conference on Parallel Processing, pages 175-179, 1983.
• 3: 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]
• 4: Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
• 5: Guy E. Blelloch , Jonathan C. Hardwick, Class Notes: Programming Parallel Algorithms CS 15-840B (Fall 1992), Carnegie Mellon University, Pittsburgh, PA, 1993
• 6: 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
• 7: P. D. Coddington and C. F. Baillie. Parallel cluster algorithms. Nuclear Physics B, Proceedings Supplements, 20:76-79, 1991.
• 8: H. G. Evertz. Vectorized cluster search. Nuclear Physics B, Proceedings Supplements, pages 620-622, 1992.
• 9: Hillel Gazit, An optimal randomized parallel algorithm for finding connected components in a graph, SIAM Journal on Computing, v.20 n.6, p.1046-1067, Dec. 1991 [doi>10.1137/0220066]
• 10: J. Greiner. A comparison of data-parallel algorithms for connected components. Technical Report CMU-CS-93- 191, Carnegie Mellon University, Aug. 1993.
• 11: John Greiner , Guy E. Blelloch, Connected components algorithms, High performance computing: problem solving with parallel and vector architectures, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 12: S. Hambrusch and L. TeWinkel. A study of connected component labeling algorithms on the MPP. In 3rd International Conference on Supercomput,ng, volume 1, pages 477-483, May 1988.
• 13: 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]
• 14: 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]
• 15: 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]
• 16: W. Lira. Fast algorithms for labeling connected components in 2-D arrays. Technical Report TMC-125, Thinking Machines Corporation, Nov. 1987.
• 17: W. Lim, A. Agrawal, and L. Neldudova. A fast parallel algorithm for labeling connected components in image arrays. Technical Report TMC-124, Thinking Machines Corporation, Apr. 1987.
• 18: H. Mino. A vectorized algorithm for cluster formation in the Swendsen-Wang dynamics.Computer Physics Communications, 66:25-30, 1991.
• 19: P. M. Pardalos and C. S. Rentala. Computational aspects of a parallel algorithm to find the connected components of a graph. Technical Report CS-89-01, Pennsylvania State University Department of Computer Science, 1989.
• 20: C. A. Philips, Parallel graph contraction, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.148-157, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72952]
• 21: J. H. Reif. Optimal parallel algorithms for integer sorting and graph connectivity. Technical Report TR-08-85, Harvard University, Mar. 1985.
• 22: 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]
• 23: R. H. Swendsen and J.-S. Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Physical! Review Letters, 58(2):86-88, Jan. 1987.
• 24: D. Talmor. Personal communication. 1991.
• 25: J. Woo and S. Sahni. Hypercube computing: Connected components. Journal of Supercomputing, 3:209- 234, 1989.
• 26: X. D. Yang. An improved algorithm for labeling connected components in a binary image. Technical Report 89-981, Cornell University, Mar. 1989.
• 27: M. Zagha. Personal communication. Feb. 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Measurement, Performance, Theory