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.
Original languageUndefined
Title of host publicationProceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages8
Number of pages12
ISBN (Print)978-1-4503-4092-2
DOIs
StatePublished - Mar 2016

Publication series

Name
PublisherACM

Fingerprint

Model checking
Parallel algorithms
Data structures
Scalability

Keywords

  • keywords strongly connected components
  • union-find
  • depth first search
  • EWI-26873
  • Parallel
  • METIS-316845
  • Multi-Core
  • Graph
  • Digraph
  • SCC
  • IR-99728
  • Algorithm

Cite this

Bloemen, V., Laarman, A., & van de Pol, J. C. (2016). Multi-Core On-The-Fly SCC Decomposition. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 (pp. 8). New York: Association for Computing Machinery (ACM). DOI: 10.1145/2851141.2851161

Bloemen, Vincent; Laarman, Alfons; van de Pol, Jan Cornelis / Multi-Core On-The-Fly SCC Decomposition.

Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016. New York : Association for Computing Machinery (ACM), 2016. p. 8.

Research output: Scientific - peer-reviewConference contribution

@inbook{48f248b88bbb485d80f3b704f1860c6f,
title = "Multi-Core On-The-Fly SCC Decomposition",
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.",
keywords = "keywords strongly connected components, union-find, depth first search, EWI-26873, Parallel, METIS-316845, Multi-Core, Graph, Digraph, SCC, IR-99728, Algorithm",
author = "Vincent Bloemen and Alfons Laarman and {van de Pol}, {Jan Cornelis}",
note = "eemcs-eprint-26873",
year = "2016",
month = "3",
doi = "10.1145/2851141.2851161",
isbn = "978-1-4503-4092-2",
publisher = "Association for Computing Machinery (ACM)",
pages = "8",
booktitle = "Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016",
address = "United States",

}

Bloemen, V, Laarman, A & van de Pol, JC 2016, Multi-Core On-The-Fly SCC Decomposition. in Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016. Association for Computing Machinery (ACM), New York, pp. 8. DOI: 10.1145/2851141.2851161

Multi-Core On-The-Fly SCC Decomposition. / Bloemen, Vincent; Laarman, Alfons; van de Pol, Jan Cornelis.

Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016. New York : Association for Computing Machinery (ACM), 2016. p. 8.

Research output: Scientific - peer-reviewConference contribution

TY - CHAP

T1 - Multi-Core On-The-Fly SCC Decomposition

AU - Bloemen,Vincent

AU - Laarman,Alfons

AU - van de Pol,Jan Cornelis

N1 - eemcs-eprint-26873

PY - 2016/3

Y1 - 2016/3

N2 - 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.

AB - 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.

KW - keywords strongly connected components

KW - union-find

KW - depth first search

KW - EWI-26873

KW - Parallel

KW - METIS-316845

KW - Multi-Core

KW - Graph

KW - Digraph

KW - SCC

KW - IR-99728

KW - Algorithm

U2 - 10.1145/2851141.2851161

DO - 10.1145/2851141.2851161

M3 - Conference contribution

SN - 978-1-4503-4092-2

SP - 8

BT - Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016

PB - Association for Computing Machinery (ACM)

ER -

Bloemen V, Laarman A, van de Pol JC. Multi-Core On-The-Fly SCC Decomposition. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016. New York: Association for Computing Machinery (ACM). 2016. p. 8. Available from, DOI: 10.1145/2851141.2851161