To avoid the conflicts in vertex value updating when parallel in edges, there are generally two scheme: 1. Maintain the update value in the edge, and finally doing reduce parallel in vertex. 2. Construct the connectivity graph for each edge and colorizing the edges, thus get edge sets where edges are independent within one set. Both method required some additional cost. The former requires extra storage for each edge, the later requires extra time and storage for the connectivity graph and colorization.
axiao
As a side note:
Ideally, we would like to color the graph with the minimum amount of colors to maximize parallelism and minimize overhead. Unfortunately, minimum vertex coloring is in NP-Hard so constructing a minimum vertex coloring for any significantly sized graph is usually out of the question. Instead you probably want to use some kind of greedy/approximation method. There is also probably potential for parallelism to do the coloring!
jkorn
@axiao Yep there are definitely parallel graph coloring algorithms out there. This paper describes a few: http://grids.ucs.indiana.edu/ptliupages/NPAC-SCCSIndex-PDFPreserved/sccs-0666.pdf
Of particular interest is page 7 and 8, then Jones-Plassman and largest-degree-first algorithms. These can be quite easily parallelized and are better than greedy colorings.
crow
According to the halide paper, they actualy use an algorithm from the paper "register allocation via coloring", by Chaitin, which provides what looks like a linear time heuristic for coloring the graph.
Interestingly, the motivation for that coloring algorithm was also motivated by some computational task -- allocating registers on a cpu
dmerigou
Coloring a dependency graph is also using in traditional compilers to determine register allocation of the variables.
To avoid the conflicts in vertex value updating when parallel in edges, there are generally two scheme: 1. Maintain the update value in the edge, and finally doing reduce parallel in vertex. 2. Construct the connectivity graph for each edge and colorizing the edges, thus get edge sets where edges are independent within one set. Both method required some additional cost. The former requires extra storage for each edge, the later requires extra time and storage for the connectivity graph and colorization.
As a side note:
Ideally, we would like to color the graph with the minimum amount of colors to maximize parallelism and minimize overhead. Unfortunately, minimum vertex coloring is in NP-Hard so constructing a minimum vertex coloring for any significantly sized graph is usually out of the question. Instead you probably want to use some kind of greedy/approximation method. There is also probably potential for parallelism to do the coloring!
@axiao Yep there are definitely parallel graph coloring algorithms out there. This paper describes a few: http://grids.ucs.indiana.edu/ptliupages/NPAC-SCCSIndex-PDFPreserved/sccs-0666.pdf
Of particular interest is page 7 and 8, then Jones-Plassman and largest-degree-first algorithms. These can be quite easily parallelized and are better than greedy colorings.
According to the halide paper, they actualy use an algorithm from the paper "register allocation via coloring", by Chaitin, which provides what looks like a linear time heuristic for coloring the graph.
Interestingly, the motivation for that coloring algorithm was also motivated by some computational task -- allocating registers on a cpu
Coloring a dependency graph is also using in traditional compilers to determine register allocation of the variables.