clarification question: the algorithm now proceeds by cycling through updating edges that belong to each color ?
update edges that that red nodes have
update edges that blue nodes have
...
....
If this is the case, then there is actually some edges that can be updated but are not. For instance when we are updating edges that red nodes have, the edge from node 0 to node 2 can also be updated.
jazzbass
I may have misunderstood this problem, but...
Shouldn't we be coloring edges, not nodes? With node coloring, when we run the red nodes in parallel, the edge (4,6) and the edge (6,9) would be updating the value for node 6 concurrently, and we might have a lost update.
Shouldn't we be doing something like this? (warning, pasteboard image, I'm not sure how long will the URL persist). We would use the same color for edges that don't have any node in common (neither the source or the destination).
After coloring the edges, we can safely update all of the edges of the same color in parallel.
byeongcp
@jazzbass I think we process all the edges that are attached to the vertices of the same color. So the set of edges attached to 4 and the set of edges attached to 9 would not have any intersection.
Though, I'm still not sure if I understand this algorithm correctly. It seems to me that if we are processing the set of edges attached to the vertices of the same color in parallel, the number of sequential steps required is the number of colors we've used to color the graph. So, does Listz try to minimize the number of colors it use when it colors the graph (I think this would be the case because having less color means we are reducing the sequential part of our computation)?
HLAHat
I think I understand what's happening here. The numbers in the graph signify all of the spawned threads. Note that the threads already know what data they will access. If you check the array at the top of the slide, you can see all the data values (the letters) that are being updated by each thread. So, for example, Threads 0 and 1 both access the data at A, so the system must ensure only Thread 0 or 1 are in A at a time.
The conflict graph is just a representation of which threads could potentially destroy updates made by other threads. It doesn't actually mean anything to the code implemented by the programmer. It's an abstraction made by the system. So, if you see an edge between two nodes, that means there is potential for a conflict between those threads. The graph coloring just gives subsets of threads that can be run concurrently without risk of conflict. So, all the blue nodes are threads that can be run concurrently, all the green nodes are threads that can be run concurrently, etc.
clarification question: the algorithm now proceeds by cycling through updating edges that belong to each color ?
If this is the case, then there is actually some edges that can be updated but are not. For instance when we are updating edges that red nodes have, the edge from node 0 to node 2 can also be updated.
I may have misunderstood this problem, but...
Shouldn't we be coloring edges, not nodes? With node coloring, when we run the red nodes in parallel, the edge (4,6) and the edge (6,9) would be updating the value for node 6 concurrently, and we might have a lost update.
Shouldn't we be doing something like this? (warning, pasteboard image, I'm not sure how long will the URL persist). We would use the same color for edges that don't have any node in common (neither the source or the destination).
After coloring the edges, we can safely update all of the edges of the same color in parallel.
@jazzbass I think we process all the edges that are attached to the vertices of the same color. So the set of edges attached to 4 and the set of edges attached to 9 would not have any intersection.
Though, I'm still not sure if I understand this algorithm correctly. It seems to me that if we are processing the set of edges attached to the vertices of the same color in parallel, the number of sequential steps required is the number of colors we've used to color the graph. So, does Listz try to minimize the number of colors it use when it colors the graph (I think this would be the case because having less color means we are reducing the sequential part of our computation)?
I think I understand what's happening here. The numbers in the graph signify all of the spawned threads. Note that the threads already know what data they will access. If you check the array at the top of the slide, you can see all the data values (the letters) that are being updated by each thread. So, for example, Threads 0 and 1 both access the data at A, so the system must ensure only Thread 0 or 1 are in A at a time.
The conflict graph is just a representation of which threads could potentially destroy updates made by other threads. It doesn't actually mean anything to the code implemented by the programmer. It's an abstraction made by the system. So, if you see an edge between two nodes, that means there is potential for a conflict between those threads. The graph coloring just gives subsets of threads that can be run concurrently without risk of conflict. So, all the blue nodes are threads that can be run concurrently, all the green nodes are threads that can be run concurrently, etc.