On Monday, 13. December 2010 16:57:23 Mattia Lambertini wrote:
I am not familiar with METIS at all, so is there a way to
provide the underlying graph in a more intuitive format? An actual image
would
be nice. Or again, the dot-output for graphviz?
An image of the graph distributed among two processes. http://lamberti.web.cs.unibo.it/bfs.png
Thank you. I confused the graph here with the resulting BFS tree.
If i get your point, process 0 starts a bfs with the n0 as root and process 1 starts with n4 as root cause n0 and n4 are the local node 0 of each process.
Although it might be that process 1 sees n4 as its root, I don't see why this should be the case. It is more like the BFS starting at n0 reaches n4 and thus might take this node as the start-node of a second BFS running in process 1. But you seem to have got the general idea.
And the ouput is the minimum distance value of each node discovered via n0 and n4 either? To what end?
The reason why it takes the minimum distance is simply "by its design". If you look at my last mail, a distributed algorithm needs to take care that during its execution an already visited/finished part of the problem will not be arbitrarily changed at a later moment. Because a BFS starting at n4 will reach one of its neighbors "faster" than it would when starting at n0, n4 gets the first chance to write some result (although a node per-se usually will not perform an action...). When n0 is now at the node that n4 already has finished, the program needs to know what to do, how to handle that situation. And the BFS-visitor of PBGL simply states that the value (which will be assigned to the label in the output) of a node is supposed to be the smallest. If I correctly intepretate the question "To what end?" you are wondering why it is the smallest value and not the one that it should have when being executed with a single process? If so, this would impose a checking of the process ID and at the long end this would lead, IMHO, to a distributed-BFS version that is actually fairly the same as the serial version. After all, it would have to wait each time for process 0 reaching that node and the running time should become equal (maybe worse due to the distributed overhead) to the serial version. So would/should be the result of the distributed execution... This is what the documentation says: <quote> 3. Since multiple distance values may be written for each vertex, we must always choose the best value we can find to update the distance map. The distributed property map distance needs to resolve distances to the smallest distance it has seen. For instance, process 0 may find vertex u at level 3 but process 1 finds it at level 5: the distance must remain at 3. To do this, we state that the property map's role is as a distance map, which introduces an appropriate reduction operation: set_property_map_role(vertex_distance, distance); <\quote>
This is the ouput with three processes:
graph g { subgraph cluster_0 { label="p0"; n0[label=0]; n1[label=0]; }
n0 -- n2; n1 -- n1; n1 -- n3; n1 -- n4;
subgraph cluster_1 { label="p1"; n2[label=0]; n3[label=1]; }
n2 -- n1; n2 -- n3; n3 -- n4;
subgraph cluster_2 { label="p2"; n4[label=0]; }
n4 -- n0; n4 -- n1; }
This seems to confirm your explanation (at least what i understood of your explanation).
It seems so, yes. However, I am wondering why node n1 (the one with the self- loop) is assigned a value of 0. If my explanation holds, this could only occur when a separate process is started on that node. But the grouping of the subgraphs (matching the number of processes) does not indicate this. It might very well be that this depends on the internals of the distributed BFS implementation or general concept of distributing processes over vertices in PBGL/MPI/whatever... It might sound a bit vague and could be a little bit to biased as a valid speculation, but it might be that process 0 is available after finding out that all adjacent vertices have their own processes running and process 0 is "spawned" freshly on node n1, which is at the same time a neighbor of n4 and n2. The reason why n1 gets its "own" process might be similar to the reason why n4 gets its "own" process in the two-process execution. Recognizing (or validating) a pattern might need further executions with higher process numbers and/or executing the BFS for other graphs. It might be of particular interest to see how a linear graph behaves, where each vertex has only one predecessor and one successor (except for the "source" and the "sink") Unfortunately, I can't really confirm that this is the correct behavior nor can I say that there's something in particular going wrong. This doesn't help you much probably. I apologize for that. Maybe you could tell why you are particularily into a distributed BFS? There are of course obvious reasons like "It exists and I have the hardware here, so I want to use it". It might be that your reason is more specific and there's an alternative or a work-around possible?! I do understand that you are supposed to solve a particular problem and not deal with the correction or validation of some code. The sad truth is that working on an actual problem and veryfing that the basis (even for off-the-shelf products) works as expected (here rather as designed) go more-or-less hand-in- hand. I had to experience that several times already. So unless someone else is dropping in to confirm (or not) the behavior of the PBGL BFS, it would be interesting (at least for me ;) to see how it behaves for different scenarios (like more processes or linear graphs) in order to shed some more light on this. Best, Cedric