SC20 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Distributed Memory Graph Coloring Algorithms for Multiple GPUs

Workshop:IA^3 2020: 10th Workshop on Irregular Applications: Architectures and Algorithms

Authors: Ian Bogle (Rensselaer Polytechnic Institute (RPI)); Erik Boman, Karen Devine, and Sivasankaran Rajamanickam (Sandia National Laboratories); and George Slota (Rensselaer Polytechnic Institute (RPI))

Abstract: Graph coloring is often used in parallelizing scientific computations that run in distributed and multi-GPU environments; it identifies sets of independent data that can be updated in parallel. Many algorithms exist for graph coloring on a single GPU or in distributed memory, but hybrid MPI+GPU algorithms have been unexplored until this work, to the best of our knowledge. We present several MPI+GPU coloring approaches that use implementations of the distributed coloring algorithms of Gebremedhin et al. and the shared-memory algorithms of Deveci et al. The on-node parallel coloring uses implementations in KokkosKernels, which provide parallelization for both multicore CPUs and GPUs. We further extend our approaches to solve for distance-2 coloring, giving the first known distributed and multi-GPU algorithm for this problem. In addition, we propose novel methods to reduce communication in distributed graph coloring. Our experiments show that our approaches operate efficiently on inputs too large to fit on a single GPU and scale up to graphs with 76.7 billion edges running on 128 GPUs.


Back to IA^3 2020: 10th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing

Back to Full Workshop Archive Listing