Abstract
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.
- D. Zuckerman, "Linear degree extractors and the inapproximability of max clique and chromatic number," Theory of Computing, vol. 3, no. 1, pp. 103--128, 2007.Google ScholarCross Ref
- H. Al-Omari and K. Sabri, "New graph coloring algorithms," Am. J. Math. & Stat, vol. 2, no. 4, pp. 739--741, 2006.Google Scholar
- A. Gebremedhin and F. Manne, "Scalable parallel graph coloring algorithms," Concurrency: Practice and Experience, vol. 12, no. 12, pp. 1131--1146, 2000.Google ScholarCross Ref
- A. M. F. B. E. C. Bozdag, D Gebremedhin, "A framework for scalable greedy coloring on distributed-memory parallel computers," Journal of Parallel and Distributed Computing, vol. 68, no. 4, pp. 515--535, 2008. Google ScholarDigital Library
- "The university of florida sparse matrix collection.Google Scholar
Index Terms
- Evaluating graph coloring on GPUs
Recommendations
Evaluating graph coloring on GPUs
PPoPP '11: Proceedings of the 16th ACM symposium on Principles and practice of parallel programmingThis 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 ...
Parallel graph coloring algorithms for distributed GPU environments
AbstractGraph 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 ...
Highlights- We present the first multi-GPU graph coloring implementation.
- Our framework ...
Evaluating the Performance of the hipSYCL Toolchain for HPC Kernels on NVIDIA V100 GPUs
IWOCL '20: Proceedings of the International Workshop on OpenCLFuture HPC leadership computing systems for the United States Department of Energy will utilize GPUs for acceleration of scientific codes. These systems will utilize GPUs from various vendors which places a large focus on the performance portability of ...
Comments