ECL-MIS v1.3
ECL-MIS is a maximal independent set graph algorithm. The CUDA implementation thereof is quite fast and produces relatively large sets. 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-MIS_13.cu and ECLgraph.h to download the CUDA code or on ECL-MIS_13.cpp and ECLgraph.h to download the OpenMP C++ code. Click on one of the links below for a description of ECL-MIS. Note that ECL-MIS 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-MIS_13.cu -o ecl-mis
The OpenMP C++ code can be compiled as follows:
g++ -O3 -march=native -fopenmp ECL-MIS_13.cpp -o ecl-mis
To compute the MIS of the file graph.egr, enter:
./ecl-mis graph.egr
Publications
M. Burtscher, S. Devale, S. Azimi, J. Jaiganesh, and E. Powers. "A High-Quality and Fast Maximal Independent Set Implementation for GPUs."
ACM Transactions on Parallel Computing, Vol. 5, No. 2, Article 8 (27 pages). December 2018.
[pdf] [pptx] [video]
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.
|