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

Publication

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. [doi] [pdf] [pptx] [video]

Summary: ECL-GC is a deterministic parallel graph-coloring algorithm for GPUs that builds upon the Jones-Plassmann algorithm with the largest-degree-first heuristic. In the base algorithm, the color assignment happens in decreasing order of vertex degrees. In each step, an independent set of high-degree vertices is identified and all of them are colored in parallel using the best possible colors. ECL-GC applies new algorithmic optimizations, called shortcuts, that increase the parallelism by identifying opportunities to color lower-priority vertices even when their higher-priority neighbors are still uncolored. It keeps a list of possible colors for each vertex, and, as soon as a vertex's higher-priority neighbors stop considering the best possible color of that vertex, it is assigned that color. The paper also describes a second shortcut, where the worst color in the list of possible colors is discarded if a vertex has a higher-priority neighbor with no overlap in the possible colors. Due to its ability to bypass the priority order while still guaranteeing the same color assignment as the serial algorithm, ECL-GC outperforms the state-of-the-art graph-coloring algorithms.




ECL-GC v1.2 with color reduction heuristics


The following work augments ECL-GC with two heuristics to reduce the number of colors needed.

Click on ECL-GC-ColorReduction_12.cu and ECLgraph.h to download the CUDA code. Click on the pdf link below for a description of ECL-GC-ColorReduction. Note that ECL-GC-ColorReduction 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-ColorReduction_12.cu -o ecl-gc-ColorReduction

To compute the coloring of the file graph.egr, enter:

./ecl-gc-ColorReduction graph.egr

Publication

G. Alabandi and M. Burtscher. "Improving the Speed and Quality of Parallel Graph Coloring." ACM Transactions on Parallel Computing, Vol. 9, No. 3, Article 10 (35 pages). September 2022. [doi] [pdf]

This work has been supported in part by the National Science Foundation under awards #1406304 and #1955367, by the Department of Energy, National Nuclear Security Administration under award #DE-NA0003969, and by equipment donations from NVIDIA Corporation.

Official Texas State University Disclaimer