ColorTM: High-Performance and Balanced Parallel Graph Coloring on Multicore Platforms

ColorTM contains two parallel graph coloring algorithms for multicore platforms: (i) ColorTM: assigns colors to the vertices of the graph using multiple parallel threads and leveraging Hardware Transactional Memory (HTM), and (ii) BalColorTM: re-colors a subset of the vertices of the graph to produce color classes with almost the same sizes, i.e., having almost the same number of vertices assigned to each color class produced. Both algorithms are written in C programming language and can be used to color any arbitrary real-world graph.

Cite ColorTM

Please cite the following papers if you find this repository useful:

Bibtex entries for citation:

@inproceedings{Giannoula2018ISC,
    author={Giannoula, Christina and Goumas, Georgios and Koziris, Nectarios},
    title={{Combining HTM with RCU to Speed up Graph Coloring on Multicore Platforms}}, 
    year = {2018},
    booktitle={High Performance Computing},
}

@article{giannoula2023high,
  title={High-performance and balanced parallel graph coloring on multicore platforms},
  author={Giannoula, Christina and Peppas, Athanasios and Goumas, Georgios and Koziris, Nectarios},
  journal={The Journal of Supercomputing},
  volume={79},
  number={6},
  pages={6373--6421},
  year={2023},
  publisher={Springer}
}

Repository Structure

We point out next the repository structure and some important folders and files.
The "ColorTM" includes the (unbalanced) ColorTM algorithm.
The "BalColorTM" includes the balanced BalColorTM algorithm.
The "inputs" directory includes a bash script to download real-world graph files (in mtx format) from the Suite Sparse Matrix Collection.

.
+-- LICENSE
+-- README.md
+-- inputs/ 
+-- ColorTM/ 
+-- BalColorTM/ 

Requirements

The ColorTM and BalColorTM kernels are designed to run on a multicore CPU machine with Hardware Transactional Memory (HTM) support.

Running ColorTM and BalColorTM

Clone the Git Repository

git clone https://github.com/cgiannoula/ColorTM.git

cd ColorTM

Download Input Graph Files

cd inputs

./download_graphs.sh 

Run the ColorTM algorithm

cd ColorTM 
make

## Manually Run  
./ColorTM -g /path/to/input/graph/file.mtx -n <number_of_parallel_threads>

## Use the Script
./run.sh 

Run the BalColorTM algorithm

cd BalColorTM 
make

## Manually Run  
./BalColorTM -g /path/to/input/graph/file.mtx -n <number_of_parallel_threads>

## Use the Script
./run.sh 

Support

For any suggestions for improvement, any issues related to the ColorTM and BalColorTM kernels or for reporting bugs, please contact Christina Giannoula at christina.giann<at>gmail.com.