Re: [boost] [BGL] Trying to get a correclty working Parallel BFS code

Subject: Re: [boost] [BGL] Trying to get a correclty working Parallel BFS code
From: Sandeep Gupta (gupta.sandeep_at_[hidden])
Date: 2009-10-27 03:05:04

On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Mon, 26 Oct 2009, Sandeep Gupta wrote:
>
>  Hi All,
>>  I  have spent significant effort on parallel bfs. Currently its almost
>> working. I would really appreciate some help to get it running correctly.
>> I
>> have attached the code (self contained and requires no input file).
>> I think I have followed all the guidelines regarding distributed property
>> maps mentioned in the docs (
>>
>> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
>> ).
>> I am out of ideas of where things can could have gone wrong.
>>
>
> The graph is distributed by source vertex across all processors, and so you
> need to add them on every processor (or at least on the processor that owns
> them, which is probably not processor 0).  Thus, your graph is missing
> whichever edges would be on processor 1, leading to incorrect results.  Try
> adding all of the edges on all processors and see if this fixes your
> problem.
>
> -- Jeremiah Willcock
>
>

Jeremiah, thanks so much looking into this promptly. I took cues from
building distributed graph section of distributed adjacency list page which
has an example:

///---------------Begin example

Graph g(n); // initialize with the total number of vertices, n
if (process_id(g.process_group()) == 0) {
  // Only process 0 loads the graph, which is distributed automatically
  int source, target;
  for (std::cin >> source >> target)
    add_edge(vertex(source, g), vertex(target, g), g);
}

// All processes synchronize at this point, then the graph is complete
synchronize(g.process_group());
//---------End

Looking at this, it seems that distribution happens automatically which is
what the manual says.
This is further confirmed when I output the subgraphs at each process.

Subgraph For process 0
  n0 -> n1;
  n0 -> n2;
  n1 -> n2;
  n1 -> n3;
  n2 -> n3;
  n3 -> n4;
  n3 -> n6;
Subgraph End

Subgraph For process 1
  n4 -> n5;
Subgraph End

As you suggested I also tried adding all the edges on all the processes.
Unfortunately, the problem still remains the same. The BFS output is

Node ID    :  Level
0  :  0
1  :  1
2  :  1
3  :  2
4  :  3
5  :  4294967295
6  :  3

and the edges gets duplicated
Subgraph For process 0
  n0 -> n1;
  n0 -> n2;
  n0 -> n1;
  n0 -> n2;
  n1 -> n2;
  n1 -> n3;
  n1 -> n2;
  n1 -> n3;
  n2 -> n3;
  n2 -> n3;
  n3 -> n4;
  n3 -> n6;
  n3 -> n4;
  n3 -> n6;
Subgraph End

 Subgraph For process 1
  n4 -> n5;
  n4 -> n5;
Subgraph End

Hope this  clarifies  the problem a bit better and that i helps to pinpoint
the source of error. Appreciate your input.

Thanks
Sandeep