Graph coloring and sparse matrix multiplication: a hammer and an incompatible nail

1 : Lawrence Berkeley National Laboratory

I will start by presenting our recent study on graph coloring algorithms on the GPU, which can be used for chromatic scheduling. I will then move to a sparse-matrix problem where we need a good scheduling algorithm. The sparse matrix-matrix multiplication is the workhorse of numerous data analytics algorithms including clustering, triangle counting, graph contraction, and betweenness centrality. While random permutations help with load imbalance at large scale, they tend to destroy locality. We would like a light-weight scheduling algorithm that is ideally work-stealing. The chromatic scheduling seems to be an imcompatible hammer for this task. I hope that the audience will respond with better ideas or with new research.

- Poster