Re: [Boost-users] [PBGL] Results of distributed BFS on multiple processors vs. on a single processor

Subject: Re: [Boost-users] [PBGL] Results of distributed BFS on multiple processors vs. on a single processor
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-23 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 non-determinism.
> > 
> > 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 search-algorithms, 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 distance-results depending on the number of
> > processors, what is then the use of distributed BFS, e.g. if you want to
> > know the BFS-distance 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) breadth-first 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
> non-deterministic 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 boost-example 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 breadth-first search
> is.  In sequential execution the cost of finding a breadth-first ordering
> and exploring the graph breadth-first are equivalent.  In the parallel
> case it is sometimes desirable to compute a BFS ordering using an
> asymptotically more expensive algorithm such as single-source shortest
> paths because it may expose more parallelism depending on the input graph.
>  In the sequential BGL case the breadth-first 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 breadth-first 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
> BFS-ordering using a non-breadth-first 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

Best,

Cedric