This repository contains the implementation of a new parallel shared-memory Connected-Components algorithm, named Afforest. The algorithm uses subgraph sampling for a fast approximation phase, after which a component skip reduces the number of edges processed to be sub-linear.
The implementation relies on the GAP benchmark code for graph-related infrastructure. The actual implementation is under src/cc_afforest.cc. A CUDA-based GPU implementation can be found under the device/ directory.
Build:
$ make cc_afforest
Run Afforest on a Kronecker graph with 2^10 vertices and average degree 4 for 1 iteration and verify the results:
$ ./cc_afforest -g10 -k4 -n1 -v
Additional command line flags can be found with -h
To run the GPU version of Afforest, use:
$ make cuda
$ ./cc_cuda -g10 -k4 -n1 -v
Note that the cub submodule is required for this version.
For a full guideline and to execute full benchmark runs, follow the instructions under GAP.
The code can be compiled on Windows as well -- see under win/apps for a Visual Studio solution file.
Please cite this implementation by our publication: Michael Sutton, Tal Ben-Nun, Amnon Barak: "Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling", Symposium on Parallel and Distributed Processing, IPDPS 2018.
My Master thesis (2018) extending the above publication can be found here.