Coloring Graphs with Intervals for Parallel Computing

Graph coloring is commonly used to schedule computations on parallel systems. Given a good estimation of the computational requirement for each task, one can refine the model by adding a weight to each vertex. Instead of coloring each vertex with a single color, the problem is to color each vertex with an interval of colors.
Stencil graphs appear naturally in the parallelization of applications, where the location of an object in a space affects the state of neighboring objects. Rectilinear decompositions of a space generate conflict graphs that are 9-pt stencils for 2D problems and 27-pt stencils for 3D problems. We show that the 5-pt stencil and 7-pt stencil relaxations of the problem can be solved in polynomial time. We prove that the decision problem on 27-pt stencil is NP-Complete. We evaluate the effectiveness of several different algorithms experimentally.
Executing graph algorithms in a parallel or distributed context is a challenging problem. It is possible that the algorithm picks a partial order with long chains, which limits its utility to parallel applications. We investigate how distributed dataflow graph algorithms obtain a partial order and how one could favor orders with shorter long chains. We study the behavior of these different algorithms on randomly generated RMAT graphs and real-world graphs. We show that our ordering methods can significantly reduce the length of the longest chain.