search

kokkos / kokkos-kernels

Kokkos C++ Performance Portability Programming Ecosystem: Math Kernels - Provides BLAS, Sparse BLAS and Graph Kernels
Other
305 stars 96 forks source link

Unsymmetric Graph Coloring #37

Open mndevec opened 7 years ago

mndevec commented 7 years ago

Graph coloring problem is normally defined on the structurally symmetric graphs. Current kokkos-kernels implementation assumes the graph is symmetric, if it is not a preprocessing is required to symmetrize the graph. This symmetrization step can be significantly expensive.

Instead the plan is to implement a distance-1 graph coloring that will also work on unsymmetric graphs. The development cant be tracked in the branch: https://github.com/mndevec/kokkos-kernels/tree/develop_unsymmetric_coloring

egboman commented 7 years ago

I think this is a good idea and may have several use cases. The speculative/optimistic coloring method can be extended to this case but it requires some thought. Even in serial multiple passes may be needed to resolve "chains" in the graph (as pointed out by Mehmet). In parallel, we have to be careful about how to do the conflict resolution. For an edge (i,j) only either i or j needs be recolored but we don't know if (j,i) is in the graph. A simple option would be to recolor both i and j but this could potentially cause deadlock or non-termination (if both threads keep picking same color).