2019 · 20 citations · 27 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismGraph AlgorithmsGraph ColoringGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsBenchmark DatasetsGpgpu ComputingGpu Parallel AlgorithmsGpu Programming ModelsGraph ProcessingGreedy ColoringIndependent Set AlgorithmsParallel Graph Algorithms
We design and implement parallel graph coloring algorithms on the GPU using two different abstractions—one data-centric (Gunrock), the other linear-algebra-based (GraphBLAS). We analyze the impact of variations of a baseline independent-set algorithm on quality and runtime. We study how optimizations such as hashing, avoiding atomics, and a max-min heuristic affect performance. Our Gunrock graph coloring implementation has a peak 2x speed-up, a geomean speed-up of 1.3x and produces 1.6x more colors over previous hardwired state-of-the-art implementations on real-world datasets. Our GraphBLAS implementation of Luby's algorithm produces 1.9x fewer colors than the previous state-of-the-art parallel implementation at the cost of 3x extra runtime, and 1.014x fewer colors than a greedy, sequential algorithm with a geomean speed-up of 2.6x.
27
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations
Register allocation via coloring
Gregory J. Chaitin, Marc Auslander, Ashok K. Chandra et al. · Computer Languages · 1981 · 731 citations