Efficient and high-quality sparse graph coloring on GPUs

摘要

Graph coloring has been broadly used to discover concurrency in parallel computing. To speed uprngraph coloring for large-scale datasets, parallel algorithms have been proposed to leverage modernGPUs.rnExistingGPUimplementations either have limited performance or yield unsatisfactoryrncoloring quality (too many colors assigned).We present a work-efficient parallel graph coloringrnimplementation on GPUs with good coloring quality. Our approach uses the speculative greedyrnscheme, which inherently yields better quality than the method of finding maximal independentrnset. To achieve high performance on GPUs, we refine the algorithm to leverage efficient operatorsrnand alleviate conflicts.We also incorporate common optimization techniques to further improvernperformance. Our method is evaluated with both synthetic and real-world sparse graphs on thernNVIDIA GPU. Experimental results show that our proposed implementation achieves averagedrn4.1 × (up to 8.9 × ) speedup over the serial implementation. It also outperforms the existing GPUrnimplementation fromtheNVIDIACUSPARSElibrary (2.2× average speedup), while yieldingmuchrnbetter coloring quality than CUSPARSE.