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-11-11 16:31:08

On Wed, Nov 11, 2009 at 9:22 AM, Nick Edmonds <ngedmond_at_[hidden]>wrote:

>
> On Nov 10, 2009, at 6:53 PM, Sandeep Gupta wrote:
>
>  On Tue, Nov 10, 2009 at 2:51 PM, Nick Edmonds <ngedmond_at_[hidden]
>> >wrote:
>>
>>  --snip--  (sorry, first reply was too big)
>>>
>>>
>>>
>>>  Hi Nick,
>>>>>
>>>>>  Thanks for the explanation of the distributed BFS. This is indeed
>>>>> quite
>>>>>
>>>> helpful. Especially at later stages.  I haven't gotten to a point to
>>>> comment
>>>> on the data model but the current architecture is swell from what I can
>>>> judge.
>>>>
>>>> I hesitate to ask explanation at every minor detail but I now confused
>>>> about passing the same vertex descriptor. Specifically I didn't quite
>>>> grasp
>>>> the statement  "source vertex just has to be
>>>> graph_traits<Graph>::vertex_descriptor, which you can construct using
>>>> vertex() call if you want to generate it from a global vertex index".
>>>> The source vertex has to graph_traits<Graph>::vertex_descriptor which I
>>>> takes two arguments the index and the graph --these two parameters can
>>>> only
>>>> identify local vertices. For global vertices we need global descriptors
>>>> which also require the owner.
>>>>
>>>> Appreciate your help in clarifying this.
>>>>
>>>> Thanks
>>>> Sandeep
>>>>
>>>>
>>> The vertex() call takes a global index and constructs a
>>> vertex_descriptor,
>>> which is basically a pair containing the local index and the owning
>>> process.
>>> vertex(i, g) will construct the i'th vertex descriptor in g on any
>>> process,
>>> regardless of where the vertex is actually stored.  The confusion is that
>>> there are two indices here, global indices, and local indices.  The graph
>>> distribution object maps between the two.  vertex() takes a global index,
>>> specifically for this use case.
>>>
>>> Hope that helps,
>>>
>>>
>>>
>>  Hi Nick,
>>>
>>>  Sorry, I didn't mean to imply that your first reply was too big. Your
>> explanation of how the PBFS is actually working is indeed quite helpful.
>> Just that rIght now I just too focussed on get the code working. Ofcourse,
>> when I dig deeper I would certainly have to refer to your exposition.
>>
>> Right now in the code  I am passing vertex(0,g) to all processes.
>> This means, based upon the explanation, that we are performing BFS on all
>> processes from the node with global identifier as 0. But still the code is
>> not outputting right result. There is something more to it or I again
>> misunderstood your explanation.
>>
>> Thanks for your patience.
>>
>> Sandeep
>>
>
>
> I didn't mean that you implied my reply was too big, this thread just
> exceeded the 75k limit on messages so I trimmed it :)
>
>  Ahh..I see.

> How are you verifying your result?
>

I used this code to output results.
     BOOST_FOREACH(Vertex vtx, vertices(g))
    {
      int local_idx = get(vidx, vtx);
      std::cout<<pid<<":"<<local_idx<<"  :  "<<get(distance,
vtx)<<std::endl;
    }

Try inserting:
>
> BGL_FORALL_EDGES(e, g, Graph) {
>  request(distance, target(e, g));  // to fetch all the distances where one
> endpoint of an edge is non-local
> }
>
> synchronize(distance); // deliver fetched distances
>
> BGL_FORALL_EDGES(e, g, Graph) {
>  assert(get(distance, target(e, g)) <= get(distance, source(e, g)) + 1);
> }
>
>

I did that. The assertions don't fail. However the BFS output was still
incorrect.

Let me know if that passes.  Also, can you give me the type of
> distributed_property_map?  I'll also attach the version of your code I
> cleaned up a while ago in case things haven't changed much and it's still
> useful.  This version of the code passes for me.
>
> Can't un-ravel the full type but its  of type "property_map<Graph,
vertex_distance_t>::type" . The code  you gave doesn't pass for me :-(.  The
level output for number of process = 1 is
Node ID    :  Level
0  :  0
1  :  1
2  :  2
3  :  2
4  :  1

But for np = 2 it is
1: distance of 0_at_1 = 3 (should be <= 2)
Finished Parallel BFS
Node ID    :  Level
0  :  0
1  :  1
2  :  2
3  :  3
4  :  1
5  :  4294967295

Whats more strange is that your code overestimates the depth values which
previous version underestimates the depth values. What machine/boost version
are you running your code.

thanks
Sandeep

 <http://lists.boost.org/mailman/listinfo.cgi/boost>