Current work - mishraj343/Parallel-Programming-Solution-to-the-Graph-Coloring-Problem GitHub Wiki

Objective Given a graph G(V,E), find a coloring c:V to N such that no two adjacent vertices have the same color. We wish to minimize the number of colors. Exact solution is NP-hard But linear-time greedy methods work well in practice.

Applications: Parallel scheduling, register allocation, sparse matrix ordering, preconditioning, AD.

Software

Often embedded within other software (not exposed). General-purpose libraries: Zoltan(2): Load balancing and combinatorial scientific computing. ColPack: Focus on automatic differentiation. cuSparse 7: GPU only. Easy to implement serial greedy but parallel is harder Our goal: Portable parallel shared-memory coloring for wide range of architectures (multicore, MIC, GPU)

Parallel Algorithms

The serial greedy algorithm is inherently sequential. very difficult to parallelize. The two most important parallel algorithms:

  1. Jones-Plassmann (’93): Color sequence of independent sets.
  2. Gebremedhin-Manne (‘00): Speculative/iterative coloring. To improve parallelism, allow some mistakes (coloring conflicts), go back and fix them later.We prefer GM due to less synchronization,#colors are similar for both.GM was shown faster on distributed-memory (Bozdag et al, 2008).Conjecture this is true on shared-memory.

Implementation Issues

Conflict resolution options: Serial: When #conflicts is small, recolor these vertices in serial. Parallel: Iterate and recolor until all conflicts resolved. How to find smallest available color: Typically, a “forbidden” array is used but this requires a lot of memory max-degree is often too pessimistic upper bound, especially for powerlaw graphs. Limited fast memory on GPU. Dynamic reallocation too expensive on Xeon Phi and GPU. We chose to examine a fixed chunk of colors (64) at a time. May need multiple passes.