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:

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

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

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]

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:

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

Publications

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. [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.