Speeding up Parallel Graph Coloring
Abstract.
This paper presents
new efficient
parallel algorithms for finding approximate solutions to graph coloring
problems. We consider an existing shared memory
parallel graph coloring algorithm and suggest several enhancements both
in
terms of ordering the
vertices so as to minimize cache misses, and performing vertex-to-processor
assignments based on graph partitioning
instead of random allocation.
We report experimental results that demonstrate the performance of our
algorithms on an IBM Regatta
supercomputer when up to 12 processors are used. Our
implementations use
OpenMP for parallelization and
Metis for graph partitioning. The experiments show that we get up to a
70 \% reduction in runtime
compared to the previous algorithm.
Full
paper in PDF
|