Connected Components

We are interested in the pragmatic aspects of parallel algorithms for finding connected components. This work compares several CRCW algorithms and optimizations of these algorithms. In particular, the fastest algorithm tested was developed as part of this work and is a hybrid of the other algorithms used. Comparisons have been made using NESL on a Connection Machine 2 and a Cray Y-MP/C90.

Ongoing work is primarily in Fortran on multiple processors of the Cray Y-MP/C90. The goal is to optimize the hybrid algorithm as much as possible. This work is being driven partly by the DIMACS Challenge.

Papers

A Comparison of Data-Parallel Algorithms for Connected Components, by John Greiner, CMU-CS-93-191, Aug. 1993. Paper and abstract.

A Comparison of Parallel Algorithms for Connected Components, by John Greiner, from the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 27-29, 1994. Paper, abstract, slides, and talk notes.

The technical report contains more details about the optimizations and code. The conference paper contains more recent information, including the hybrid algorithm. A book chapter version in preparation contains more explanation about how the algorithms work.

Code

A couple algorithms written in NESL: Awerbuch and Shiloach's, Hirschberg, Chandra, and Sarwate's.

The NESL code used in John Greiner's papers includes versions of

the Awerbuch and Shiloach algorithm,
the Shiloach and Vishkin algorithm,
a "Random Mate" algorithm,
a "Hybrid" algorithm, which combines the elements of the previous algorithms,

and some routines common to these algorithms and graph generation routines.

Up to the Irregular Algorithms page or John Greiner's research.