ECLMIS v1.3
ECLMIS 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 ECLMIS_13.cu and ECLgraph.h to download the CUDA code or on ECLMIS_13.cpp and ECLgraph.h to download the OpenMP C++ code. Click on one of the links below for a description of ECLMIS. Note that ECLMIS 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 ECLMIS_13.cu o eclmis
The OpenMP C++ code can be compiled as follows:
g++ O3 march=native fopenmp ECLMIS_13.cpp o eclmis
To compute the MIS of the file graph.egr , enter:
./eclmis graph.egr
Publications
M. Burtscher, S. Devale, S. Azimi, J. Jaiganesh, and E. Powers. "A HighQuality and Fast Maximal Independent Set Implementation for GPUs."
ACM Transactions on Parallel Computing, Vol. 5, No. 2, Article 8 (27 pages). December 2018.
[doi]
[pdf]
[pptx]
[video]
Summary: ECLMIS is a deterministic parallel algorithm for computing Maximal Independent Sets (MIS) on GPUs. It builds upon Luby's algorithm. ECLMIS starts by assigning priorities to the vertices based on their degrees with a deterministic random tie breaker. It then selects the vertices with the highest priority among their neighbors in parallel, includes them in the MIS, and marks their neighbors as excluded. These steps are asynchronously repeated until every vertex is either included or excluded. ECLMIS employs several optimizations to improve the speed of the computation as well as the size of the MIS. Based on the observation that a vertex's status only changes once (from undecided to either included or excluded), ECLMIS combines the status and the priority information of a vertex in a single byte, thus reducing the memory footprint. It avoids explicit synchronization by exploiting the fact that singlebyte reads and writes are naturally atomic. The partially random priority values that are inversely proportional to a vertex's degree enable ECLMIS to find relatively large sets.
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.
