### Abstract

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 |

Place of Publication | New York |

Publisher | Association for Computing Machinery (ACM) |

Pages | 8 |

Number of pages | 12 |

ISBN (Print) | 978-1-4503-4092-2 |

DOIs | |

Publication status | Published - Mar 2016 |

### Publication series

Name | |
---|---|

Publisher | ACM |

### 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

*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

}

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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)

CY - New York

ER -