ECL-SCC v1.0
ECL-SCC is a new parallel algorithm for detecting strongly connected components in directed graphs. The CUDA implementation is quite fast, especially on mesh graphs. It operates on graphs stored in binary CSR format. Converters to this format can be found here.
Click on ECL-SCC_10.cu and ECLgraph.h to download the CUDA code. Alternatively, the code and sample inputs are also available on github. See the paper listed below for a description of ECL-SCC. Note that ECL-SCC is protected by the 3-Clause BSD license.
The code can be compiled as follows:
nvcc -O3 -arch=sm_70 ECL-SCC_10.cu -o ecl-scc
To compute the SCC of the file mesh.egr, enter:
./ecl-scc mesh.egr
Sample inputs
Publication
G. Alabandi, W. Sands, G. Biros, and M. Burtscher. "A GPU Algorithm for Detecting Strongly Connected Components."
Proceedings of the 2023 ACM/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis. Article 17, pp. 1-13. November 2023.
[doi]
[pdf]
[pptx]
[talk]
Summary: ECL-SCC is an efficient data-driven, edge-centric parallel algorithm for computing SCCs of a directed graph on GPUs. It is based on the observation that, in each SCC, there is a unique vertex with the maximum ID among the vertices in that SCC. Identifying this maximum-ID-vertex on the incoming and outgoing paths of each vertex has the potential to demarcate multiple SCCs simultaneously. This approach of allowing all vertices to simultaneously act as pivots increases the parallelism. Not following a depth- or breadth-first search order, avoiding recursion, and eliding atomic operations by exploiting the monotonicity of the maximum-ID propagation make ECL-SCC particularly GPU-friendly. On average, ECL-SCC outperforms state-of-the-art parallel SCC algorithms by about 2x on power-law graphs and by 6.5x on mesh graphs from radiation transport simulations.
This work has been supported in part by the Department of Energy, National Nuclear Security Administration under Award Number DE-NA0003969, by the National Science Foundation under Award Number 1955367, and by equipment donations from NVIDIA Corporation.
|