This slide really stuck with me because it made me see the immediate impact of graph theory in computer science. We recently learned about chromatic numbers in graph theory. It makes sense that in a dependency graph, all nodes with the same color form an independent set because they cannot have any edges between them. In this way, we can run an independent set of nodes in our CUDA launch independently as there are no dependencies.
aeu
Is there a limit on the number of colors that we can use, or a number that we aim for (the color being an analogy to the number of independent sets)? 3-coloring is NP-complete, so I would assume we don't have that strict of a limit but what if there are, for example, 100 nodes and happens to have 80 colors?
hofstee
@aeu you would need to have as many colors as necessary to guarantee independence. The Liszt paper says they use this algorithm for their graph coloring. They (Liszt) mention that on the meshes they had tested there were no more than 6 colors required, and I believe that most typical meshes for this domain would fall around that range as well.
patrickbot
Their mesh elements are at most 3 dimensional objects (cells), and so there is probably some fairly low bound on the chromatic number of these meshes, and the approximation probably won't do too badly either.
Liszt meshes (at least the ones in the paper) contained millions of elements. Even if we need a hundred colors, each color might still have thousands of elements, so we can still exploit the independence of these elements by running them in parallel and it should make up for the overhead of approximating a coloring for the graph.
hofstee
@patrickbot the Liszt paper was actually the one where I got the 6 color statement. My original post was worded a bit ambiguously.
patrickbot
@hofstee I think your original post was clear -- I just wanted to provide some mathematical intuition for why it might be as low as 6 and to emphasize that the meshes have millions of nodes.
1pct
So can we think of the the algorithm as having a barrier between processing two different colors?
Josephus
I'd tried using something like graph coloring for Assignment 2 to parallelize the shading across circles, but I wasn't able to get performance within bounds in time. Would some sort of graph coloring algorithm have worked for Assignment 2? Is the efficiency of graph coloring bounded by number of nodes or amount of computation per node?
This slide really stuck with me because it made me see the immediate impact of graph theory in computer science. We recently learned about chromatic numbers in graph theory. It makes sense that in a dependency graph, all nodes with the same color form an independent set because they cannot have any edges between them. In this way, we can run an independent set of nodes in our CUDA launch independently as there are no dependencies.
Is there a limit on the number of colors that we can use, or a number that we aim for (the color being an analogy to the number of independent sets)? 3-coloring is NP-complete, so I would assume we don't have that strict of a limit but what if there are, for example, 100 nodes and happens to have 80 colors?
@aeu you would need to have as many colors as necessary to guarantee independence. The Liszt paper says they use this algorithm for their graph coloring. They (Liszt) mention that on the meshes they had tested there were no more than 6 colors required, and I believe that most typical meshes for this domain would fall around that range as well.
Their mesh elements are at most 3 dimensional objects (cells), and so there is probably some fairly low bound on the chromatic number of these meshes, and the approximation probably won't do too badly either.
Liszt meshes (at least the ones in the paper) contained millions of elements. Even if we need a hundred colors, each color might still have thousands of elements, so we can still exploit the independence of these elements by running them in parallel and it should make up for the overhead of approximating a coloring for the graph.
@patrickbot the Liszt paper was actually the one where I got the 6 color statement. My original post was worded a bit ambiguously.
@hofstee I think your original post was clear -- I just wanted to provide some mathematical intuition for why it might be as low as 6 and to emphasize that the meshes have millions of nodes.
So can we think of the the algorithm as having a barrier between processing two different colors?
I'd tried using something like graph coloring for Assignment 2 to parallelize the shading across circles, but I wasn't able to get performance within bounds in time. Would some sort of graph coloring algorithm have worked for Assignment 2? Is the efficiency of graph coloring bounded by number of nodes or amount of computation per node?