Toward Computation-Efficient High-Quality Graph Coloring on GPUs

Abstract

Graph coloring at scale on GPUs forces a quality–performance trade-off: strict priority orderings such as Smallest-Last (SL) reduce the number of colors but serialize the priority-allocation (PA) phase and throttle parallelism, leaving the high-quality, GPU-fast region of the coloring-quality versus execution-time plane historically empty. Our prior conference framework, CHROMA, populated this region with cuSL—the first GPU-parallel realization of SL priority allocation—plus three quality/runtime optimizations, a learned predictor for its elastic parameter, and a partitioner-agnostic module for graph exceeding single-GPU memory capacity. For single GPU configuration, CHROMA achieves up to a <inline-formula> <tex-math notation="LaTeX">$17.4\times $ </tex-math></inline-formula> geometric-mean PA speedup over a parallel CPU baseline at comparable quality. In this paper, we propose CHROMAv2 that pushes CHROMA further along this Pareto frontier with three contributions: Adaptive Workload-balance Decrement (AWD), a per-iteration warp-/CTA-centric dispatch that removes the residual decrement imbalance of static policies; an aggressive elastic-parameter prediction (AEP) family that enlarges the elastic parameter’s range without color quality degradation; and an online bumping controller that widens peeling granularity through PA’s long tail. AWD alone delivers a 1.18–<inline-formula> <tex-math notation="LaTeX">$1.28\times $ </tex-math></inline-formula> geometric-mean PA speedup (1.13–<inline-formula> <tex-math notation="LaTeX">$1.17\times $ </tex-math></inline-formula> end-to-end), online bumping improves large-graph runtime by up to 54% without sacrificing coloring quality, and CHROMAv2 overall attains up to a <inline-formula> <tex-math notation="LaTeX">$1.68\times $ </tex-math></inline-formula> geometric-mean single-GPU speedup compared with our previous version. We open-source CHROMA to facilitate future research.