Parallel graph coloring : Parallel graph coloring on multi-core CPUs

Abstract: In recent times an evident trend in hardware is to opt for multi-core CPUs. This has lead to a situation where an increasing number of sequential algorithms are parallelized to fit these new multi-core environments. The greedy Multi-Coloring algorithm is a strictly sequential algorithm that is used in a wide range of applications. The application in focus is on decomposition by graph coloring for preconditioning techniques suitable for iterative solvers like the and methods. In order to perform all phases of these iterative solvers in parallel the graph analysis phase needs to be parallelized. Albeit many attempts have been made to parallelize graph coloring non of these attempts have successfully put the greedy Multi-Coloring algorithm into obsolescence. In this work techniques for parallel graph coloring are proposed and studied. Quantitative results, which represent the number of colors, confirm that the best new algorithm, the Normann algorithm, is performing on the same level as the greedy Multi-Coloring algorithm. Furthermore, in multi-core environments the parallel Normann algorithm fully outperforms the classical greedy Multi-Coloring algorithm for all large test matrices. With the features of the Normann algorithm quantified and presented in this work it is now possible to perform all phases of iterative solvers like and methods in parallel.