ECL-GC v1.2


ECL-GC is a graph-coloring algorithm with shortcutting that is quite fast. The CUDA implementation thereof is quite fast and the C++/OpenMP implementation is quite fast on low-degree graphs. 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-GC_12.cu and ECLgraph.h to download the CUDA code or on ECL-GC_12.cpp and ECLgraph.h to download the OpenMP C++ code. Click on one of the links below for a description of ECL-GC. Note that ECL-GC 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-GC_12.cu -o ecl-gc

The OpenMP C++ code can be compiled as follows:

g++ -O3 -march=native -fopenmp ECL-GC_12.cpp -o ecl-gc

To compute the coloring of the file graph.egr, enter (followed by the thread count for the OpenMP code):

./ecl-gc graph.egr

Publications

G. Alabandi, E. Powers, and M. Burtscher. "Increasing the Parallelism of Graph Coloring via Shortcutting." Proceedings of the 2020 ACM Conference on Principles and Practice of Parallel Programming, pp. 262-275. February 2020. [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.

Official Texas State University Disclaimer