This repo contains source code for our paper "A Hybrid Graph Coloring Algorithm for GPUs" (link). We have re-implemented Iterative Parallel Graph Coloring (IPGC) and Edge Based Graph Coloring based on this previous work.
For IPGC, we have an optimized version of the algorithm that performs 36% faster than the previous work on average. A key optimization for our algorithm was to heuristically choose between two modes of graph traversal.
Obtain ggc from here.
Run ./skelsetup.py setup $GGC to setup the template directory,
where $GGC is the root directory containing the ggc IrGL compiler.
This will create softlinks to $GGC/rt and $GGC/skelapp in the
template directory and also setup variables in bmks/local.mk to
point to $GGC.
Also, the python packages cgen and toposort are required.
The implementations of the benchmarks can be found in seperate
folders in the bmks directory. (Assume cc is a benchmark for
the rest of the section).
Run make in the cc directory. If everything went well, you should
have see generated code in ../gensrc/cc, with the following files:
- A
kernel.cufile (the compiledcc.py) - A
support.cufile (a soft-linkedcc_support.cu) - A
Makefileto compile this using CUDA
Run make in this directory to get test_nontex, a binary that can be
run.
Note: IrGL optimizations provide better results. Running make in bmks/ipgc_bit with additional flags provides the best results:
make GGCFLAGS="--opt np --npf 8 --opt parcomb --opt oitergb"bmk2cfg contains the benchmark configuration for bmk2 benchmark
tool.
bmk2cfg/irgl.inputdb contains the graphs used for benchmarking.
Change the basepath in line 2 to the path of the directory in your
system which contains the graphs.
In the basepath, the .gr format graphs are assumed to be in
binary_files directory, the .mtx format graphs are assumed to
be in mtx_files directory and kokkos graphs in kokkos_binaries.
tools folder has the scripts to obtain the input graphs in the paper
and converting them to the format expected by ggc.