Assefaw H. Gebremedhin
Computer Science Dep.
Old Dominion University
Norfolk, USA
Email: assefaw@cs.odu.edu
and
Fredrik Manne and Tom Woods
Dep. of Informatics
University of Bergen
Bergen, Norway
Email fredrikm,tomw@ii.uib.no
This paper presents new efficient parallel algorithms for an approximate solution to the graph coloring problem (GCP). The GCP asks for an assignment of the fewest number of colors to vertices such that any two adjacent vertices receive different colors. It arises in a number of high performance computing scenarios such as parallel numerical computations, adaptive grid refinement, and optimization. In a parallel application a graph coloring is usually performed in order to partition the work associated with the vertices into independent subtasks such that the subtasks can be performed concurrently.
In [Gebremedhin & Manne,2000] we developed a practical shared memory parallel algorithm for the GCP. Unlike most other previous parallel algorithms for this problem, our algorithm gave speed-up as more processors were employed. The algorithm is based on randomly assigning an equal number of vertices to each processor. These are then colored concurrently by the processors while using information about already colored vertices (both local and non-local). As two adjacent vertices might be colored simultaneously by two different processors the vertices can receive the same color and thus lead to an inconsistent coloring. Therefore a second parallel stage is used to validate the coloring and detect any conflicts which are resolved in a final sequential step.
In the current paper we carefully analyze the impact of remote memory access on the running time of this algorithm. In particular, we suggest several enhancements to the algorithm by performing the assignment of vertices to processors not in a random fashion but instead based on graph partitioning techniques. These aim at partitioning the graph into a specified number of components such that the number of vertices in each component is roughly the same and the inter-component edges are as few as possible. These reorderings of the graph give a substantial increase in the overall percentage of local memory access and hence results in a faster algorithm.
Moreover, graph partitioning provides an opportunity for further reduction in runtime as we can now divide the graph on each processor in a "local" graph that will be colored correctly after the first round of the algorithm and a "boundary" graph where the coloring must be verified and possibly corrected.
We report experimental results that show the performance of our algorithms on an IBM Regatta supercomputer when up to 20 processors are used. Our implementation uses OpenMP for parallelization and Metis for graph partitioning. In addition to the basic GCP, we report results on the distance-2 coloring problem, a coloring problem in which vertices within distance 2 from each other are required to be assigned different colors. Distance-2 graph coloring finds applications in numerical optimization and facility location problems.