Evaluating graph coloring on GPUs

A.V. Pascal Grosset, Peihong Zhu, Shusen Liu, Suresh Venkatasubramanian, Mary Hall
School of Computing, University of Utah, Salt Lake City, Utah, USA
Proceedings of the 16th ACM symposium on Principles and practice of parallel programming (PPoPP ’11), 2011


   title={Evaluating graph coloring on GPUs},

   author={Grosset, A.V.P. and Zhu, P. and Liu, S. and Venkatasubramanian, S. and Hall, M.},

   booktitle={Proceedings of the 16th ACM symposium on Principles and practice of parallel programming},





Download Download (PDF)   View View   Source Source   



This paper evaluates features of graph coloring algorithms implemented on graphics processing units (GPUs), comparing coloring heuristics and thread decompositions. As compared to prior work on graph coloring for other parallel architectures, we find that the large number of cores and relatively high global memory bandwidth of a GPU lead to different strategies for the parallel implementation. Specifically, we find that a simple uniform block partitioning is very effective on GPUs and our parallel coloring heuristics lead to the same or fewer colors than prior approaches for distributed-memory cluster architecture. Our algorithm resolves many coloring conflicts across partitioned blocks on the GPU by iterating through the coloring process, before returning to the CPU to resolve remaining conflicts. With this approach we get as few color (if not fewer) than the best sequential graph coloring algorithm and performance is close to the fastest sequential graph coloring algorithms which have poor color quality.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: