Boost logo

Boost :

Subject: Re: [boost] [BGL] Trying to get a correclty working Parallel BFS code
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2009-11-11 12:22:34


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

Hi 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 :)

How are you verifying your result? 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);
}

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.

Cheers,
Nick




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk