ECL-MIS is a maximal independent set algorithm. The CUDA implementation thereof is very fast and produces relatively large sets. It operates on graphs stored in binary CSR format.
Click on ECL-MIS_10.cu and ECLgraph.h to download the CUDA code or on ECL-MIS_10.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 this license and that by downloading ECL-MIS you agree to the terms and conditions set forth in this license.
The CUDA code can be compiled as follows:
nvcc -O3 -arch=sm_35 ECL-MIS_10.cu -o ecl-mis
The OpenMP C++ code can be compiled as follows:
g++ -O3 -march=native -fopenmp ECL-MIS_10.cpp -o ecl-mis
To compute the MIS of the file
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.