ECL-CC v1.1
ECL-CC is a connected components graph algorithm. The CUDA implementation thereof is quite fast. It operates on graphs stored in binary CSR format. Converters to this format as well as several already converted graphs can be found here.
Click on ECL-CC_11.cu and ECLgraph.h to download the CUDA code or on ECL-CC_11.cpp and ECLgraph.h to download the OpenMP C++ code (with g++ intrinsics). Click on one of the links below for a description of ECL-CC. Note that ECL-CC is protected by the license included in the beginning of the code.
The CUDA code can be compiled as follows:
nvcc -O3 -arch=sm_35 ECL-CC_11.cu -o ecl-cc
The OpenMP C++ code can be compiled as follows:
g++ -O3 -march=native -fopenmp ECL-CC_11.cpp -o ecl-cc
To compute the connected components of the file graph.egr, enter:
./ecl-cc graph.egr
Publications
J. Jaiganesh and M. Burtscher. "A High-Performance Connected Components Implementation for GPUs."
Proceedings of the 2018 ACM International Symposium on High-Performance Parallel and Distributed Computing. June 2018.
[doi]
[pdf]
[pptx]
[talk]
Summary: ECL-CC is a parallel algorithm for finding the connected components of an undirected graph on GPUs. It is based on the label propagation technique, which assigns unique labels to the vertices and propagates the minimum labels among adjacent vertices until a fixed point is reached. ECL-CC optimizes the initialization phase by starting with the ID of the first neighbor that has a smaller ID. The propagation phase is based on a new union-find implementation that is specifically designed for fast GPU execution. Moreover, it achieves load balancing by processing vertices at thread, warp, or block granularity depending on their degrees. To further boost the performance, ECL-CC is implemented in a lock-free and asynchronous manner.
This work has been supported in part by the National Science Foundation under Grant No. 1406304 as well as by equipment donations from NVIDIA Corporation.
|