
Boost Users : 
Subject: Re: [Boostusers] [PBGL] Results of distributed BFS on multiple processors vs. on a single processor
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 20110423 05:09:01
On Friday, 22. April 2011 23:05:04 Nick Edmonds wrote:
> On Apr 22, 2011, at 11:01 AM, Cedric Laczny wrote:
> > On Friday, 22. April 2011 16:31:20 Steven Watanabe wrote:
> >> AMDG
> >>
> >> On 04/22/2011 05:59 AM, Cedric Laczny wrote:
> >>> it recently came to my mind again that the distributed BFS in the PBGL
> >>> seems to produce different results when applied to multiple processors
> >>> as to when applied to a single processor (s.
> >>> http://lists.boost.org/boost
> >>> users/2010/12/64783.php)
> >>> If this is true, I really would like to know what the reasoning is
> >>> behind this and it should be noted in the documentation of course to
> >>> help prevent surprises as in the discussion above.
> >>> Unfortunately, at that time, no definite answer was given and this
> >>> question puzzled me again now...
> >>> Any ideas on that?
> >>
> >> Why would you expect the results to be exactly the
> >> same? Parallelism usually introduces a certain
> >> amount of nondeterminism.
> >
> > I agree with you on that, generally. And it is good to note this
> > explicitly again.
> > However, maybe I just got a weird kind of perception/expectation here,
> > but especially for searchalgorithms, I would expect parallel algorithms
> > to return the same results as otherwise the question of correct
> > interpretation of the parallel results arises to me.
> > I mean, if you get different distanceresults depending on the number of
> > processors, what is then the use of distributed BFS, e.g. if you want to
> > know the BFSdistance from source to a specific vertex x?
>
> The current PBGL (and any other *correct* parallel BFS implementation) will
> explore one (of a family of valid) breadthfirst vertex ordering. For a
> variety of reasons the sequential visitor semantics do not map well to
> parallel execution however. Confusion about the semantics of visitors in
> a parallel context in combination with the fact that the ordering of
> vertex discovery and edge traversal within levels is necessarily
> nondeterministic often leads to confusion by users about the results
> returned by their BFS visitors. A correctly written visitor will return
> the same distance labels as the sequential implementation, but may not
> explore the vertices/edges in the same order.
Ok, that's interesting to know. IMHO, someone who simply wants to speed up the
computation of a BFS by using a parallelised version does generally not care
about the order of exploration but is interested only in the result, like the
distance labels, and for such a scenario that should be equal to the
sequential case. Good to know that this is in fact the case.
However, this brings me to question, why the parallel BFS boostexample then
returns different distance labels, depending on the number of involved
processors? Or is this just a misconception of the output?
>
> There is also the question of what the *output* of a breadthfirst search
> is. In sequential execution the cost of finding a breadthfirst ordering
> and exploring the graph breadthfirst are equivalent. In the parallel
> case it is sometimes desirable to compute a BFS ordering using an
> asymptotically more expensive algorithm such as singlesource shortest
> paths because it may expose more parallelism depending on the input graph.
> In the sequential BGL case the breadthfirst exploration of the graph and
> exposure of this ordering via visitor events is the output. In possible
> parallel implementations the output may be a BFS tree expressed using a
> predecessor map, or distance labels from the source of that tree. The
> point here is that the assumption of breadthfirst exploration may or may
> not be valid/necessary in the parallel case and relaxing this requirement
> to either some sort of relaxed topological traversal, or computation of a
> BFSordering using a nonbreadthfirst travers al is often more
> appropriate.
>
> In the rewrite of the PBGL I'm working on it's looking like the visitor
> concept will be mostly (or completely) absent, and a richer set of
> traversal primitives will replace/augment the general purpose BFS
> algorithm in the current version (since it proved inefficient to compose
> other algorithms on parallel BFS anyway).
>
> Hope that helps, and my apologies for not always having time to help answer
> the "my code using the PBGL returns results that don't make sense to me"
> questions.
>
Thank you for this elaborate answer. It made even more clear to me that the
parallel case for BFS holds some aspects that were not directly visible to me
at the beginning. I appreciate your efforts and would be happy if you could
perhaps have a more detailed look on the returned distances in the boost
example.
> Cheers,
> Nick
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
Best,
Cedric
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net