Multi-Core On-The-Fly SCC Decomposition

Vincent Bloemen, Alfons Laarman, Jan Cornelis van de Pol

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    17 Citations (Scopus)
    254 Downloads (Pure)

    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
    Publication statusPublished - Mar 2016

    Publication series

    Name
    PublisherACM

    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). https://doi.org/10.1145/2851141.2851161