In:
ACM SIGPLAN Notices, Association for Computing Machinery (ACM), Vol. 51, No. 8 ( 2016-11-09), p. 1-12
Abstract:
The main advantages of Tarjan's strongly connected component (SCC) algorithm are its linear time complexity and ability to return SCCs on-the-fly, while traversing or even generating the graph. Until now, most parallel SCC algorithms sacrifice both: they run in quadratic worst-case time and/or require the full graph in advance. The current paper presents a novel parallel, on-the-fly SCC algorithm. It preserves the linear-time property by letting workers explore the graph randomly while carefully communicating partially completed SCCs. We prove that this strategy is correct. For efficiently communicating partial SCCs, we develop a concurrent, iterable disjoint set structure (combining the union-find data structure with a cyclic list). We demonstrate scalability on a 64-core machine using 75 real-world graphs (from model checking and explicit data graphs), synthetic graphs (combinations of trees, cycles and linear graphs), and random graphs. Previous work did not show speedups for graphs containing a large SCC. We observe that our parallel algorithm is typically 10-30× faster compared to Tarjan's algorithm for graphs containing a large SCC. Comparable performance (with respect to the current state-of-the-art) is obtained for graphs containing many small SCCs.
Type of Medium:
Online Resource
ISSN:
0362-1340
,
1558-1160
DOI:
10.1145/3016078.2851161
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2016
detail.hit.zdb_id:
2079194-X
detail.hit.zdb_id:
282422-X
Permalink