Technical Report(pdf, abstract)

Tarjan's linear time, sequential algorithm for finding strongly connected
components (SCCs) in a graph relies on depth first search, which is thought to
be inherently sequential. Deterministic parallel algorithms identify SCCs in polylogarithmic time but require at least a quadratic number of processors,
which causes the work to exceed the sequential complexity bound for sparse
graphs. Randomized algorithms based on reachability --- the ability to get from
one vertex to another along a directed path --- greatly improve the work bound in the average case, but these algorithms do not perform well on all graphs. For instance, Divide-and-Conquer Strong Components (DCSC), a scalable, divide-and-conquer algorithm, has good expected theoretical limits on many graphs, but will perform poorly on graphs for which the average reachability is small. A related algorithm, MultiPivot, gives high probability guarantees on the total amount of work for all graphs, but this improvement requires additional calculation. This paper introduces two new algorithms, SCCMulti and SCCMulti-PriorityAware, which offer the same input independence as MultiPivot, but reduce the expected number of computations by a factor of O(log n). We also provide a characterization that allows us to better compare reachability-based SCC algorithms. Experimental results show that both of our algorithms scale up to hundreds of thousands of cores, that, unlike DCSC, they attain consistent performance regardless of the input graph, and that they are much faster than MultiPivot.