[Boost-users] Parallel BGL status in Boost

[Mathieu Malaterre]

Hi there,

I am getting lost with the status of PBGL in boost. Is it officially
in Boost now ? I am reading some documentation such as:

http://charm.cs.uiuc.edu/charmWorkshop/slides/2009_PBGL_Lumsdaine.pptx

And it appears there are multiple implementations (see slide #54),
namely 'the Parallel BGL' (is there only one?) and the (Parallel)
BGL-VTK. Documentation links to : http://www.osl.iu.edu/research/pbgl
but this page has not been updated in years, and recent commit AFAIK
did happen directly within boost, right ?

Is there some threads I am missing, I have been following boost
users list but could not find any thread relevant.

Basically all I am interested in is how do you provide an iterator
interface in a parallel environment where vertex/edge are not local to
the machine.

Thanks
--
Mathieu
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Nick Edmonds]

On Sep 3, 2009, at 12:02 PM, Mathieu Malaterre wrote:

> Hi there,
>
> I am getting lost with the status of PBGL in boost. Is it officially
> in Boost now ? I am reading some documentation such as:
>

Yep, PBGL as in the distributed data structures, MPI infrastructure,
and distributed algorithms is now in Boost.

> http://charm.cs.uiuc.edu/charmWorkshop/slides/2009_PBGL_Lumsdaine.pptx
>
> And it appears there are multiple implementations (see slide #54),
> namely 'the Parallel BGL' (is there only one?) and the (Parallel)
> BGL-VTK. Documentation links to : http://www.osl.iu.edu/research/pbgl
> but this page has not been updated in years, and recent commit AFAIK
> did happen directly within boost, right ?

The (Parallel) BGL-VTK project you mention is simply a set of wrappers
that allow (Parallel) BGL to be used as a back-end to VTK. Kitware is
the official holder of the sources here I believe, but if you need
more info I can tell you who to talk to. That slide references a
single core project, the Parallel BGL, and several interfaces (the
Python ones, which I don't maintain but could probably track down
someone for you to talk to about them), as well as the aforementioned
VTK wrapper.

Yep, that webpage is desperately out of date, I'm a terrible
webmaster. Updating it (and the attendant performance numbers) has
been on my todo list for ages. I'd make more promises, but they'd
probably sound hollow now. So when I actually do it, it will be a
pleasant surprise.

>
>
> Is there some threads I am missing, I have been following boost
> users list but could not find any thread relevant.
>
> Basically all I am interested in is how do you provide an iterator
> interface in a parallel environment where vertex/edge are not local to
> the machine.

Structural information about the graph is only available on the
process that owns that portion of the graph. Currently PBGL
distributes the graph using a row-wise decomposition of the adjacency
matrix. This means that calling vertices(g) returns the local vertex
set owned by the calling process. The result of calling edges(g)
depends on the directed category of the edge, but basically iterates
over incident edges. Attempting to access structural information that
is not local to the calling process, i.e. calling out_edges(v, g)
where 'v' is not owned by the calling process is invalid and results
in undefined behavior.

If you want more details, to know why things work the way they do now,
or how they might work in the future, feel free to ask away.

Thanks,
Nick

[Mathieu Malaterre]

On Thu, Sep 3, 2009 at 10:37 PM, Nick Edmonds<nged...@cs.indiana.edu> wrote:
> Yep, PBGL as in the distributed data structures, MPI infrastructure, and
> distributed algorithms is now in Boost.

Cool, I did not see it in the changelog, so I was confused.

> Yep, that webpage is desperately out of date, I'm a terrible webmaster.
>  Updating it (and the attendant performance numbers) has been on my todo
> list for ages.  I'd make more promises, but they'd probably sound hollow
> now.  So when I actually do it, it will be a pleasant surprise.

So that it serve as reference to anyone reading this. The
documentation have been updated, simply not uploaded neither on
boost.org page nor on the old PBGL page. It is available locally as:

file:///path/to/boost/libs/graph_parallel/doc/html/index.html

> Structural information about the graph is only available on the process that
> owns that portion of the graph.  Currently PBGL distributes the graph using
> a row-wise decomposition of the adjacency matrix.  This means that calling
> vertices(g) returns the local vertex set owned by the calling process.  The
> result of calling edges(g) depends on the directed category of the edge, but
> basically iterates over incident edges.  Attempting to access structural
> information that is not local to the calling process, i.e. calling
> out_edges(v, g) where 'v' is not owned by the calling process is invalid and
> results in undefined behavior.

ok that clears things quite a bit !

> If you want more details, to know why things work the way they do now, or
> how they might work in the future, feel free to ask away.

'in the future', what do you mean ? What are the actual plans ?

Thanks again,

[Nick Edmonds]

On Sep 4, 2009, at 8:24 AM, Mathieu Malaterre wrote:

> On Thu, Sep 3, 2009 at 10:37 PM, Nick
> Edmonds<nged...@cs.indiana.edu> wrote:
>> Yep, PBGL as in the distributed data structures, MPI
>> infrastructure, and
>> distributed algorithms is now in Boost.
>
> Cool, I did not see it in the changelog, so I was confused.
>
>
>> Yep, that webpage is desperately out of date, I'm a terrible
>> webmaster.
>> Updating it (and the attendant performance numbers) has been on my
>> todo
>> list for ages. I'd make more promises, but they'd probably sound
>> hollow
>> now. So when I actually do it, it will be a pleasant surprise.
>
> So that it serve as reference to anyone reading this. The
> documentation have been updated, simply not uploaded neither on
> boost.org page nor on the old PBGL page. It is available locally as:
>
> file:///path/to/boost/libs/graph_parallel/doc/html/index.html
>

Yep, 1.40 is unfortunately missing the proper redirect in libs/
graph_parallel to libs/graph_parallel/doc/html/index.html. I've fixed
this in the trunk. When 1.41 goes out hopefully the docs will show up
on boost.org, this was due to my ignorance w.r.t. how docs got to the
webpage during the release process.

>> Structural information about the graph is only available on the
>> process that
>> owns that portion of the graph. Currently PBGL distributes the
>> graph using
>> a row-wise decomposition of the adjacency matrix. This means that
>> calling
>> vertices(g) returns the local vertex set owned by the calling
>> process. The
>> result of calling edges(g) depends on the directed category of the
>> edge, but
>> basically iterates over incident edges. Attempting to access
>> structural
>> information that is not local to the calling process, i.e. calling
>> out_edges(v, g) where 'v' is not owned by the calling process is
>> invalid and
>> results in undefined behavior.
>
> ok that clears things quite a bit !
>
>> If you want more details, to know why things work the way they do
>> now, or
>> how they might work in the future, feel free to ask away.
>
> 'in the future', what do you mean ? What are the actual plans ?

Well, there are lots of plans... Hybrid parallelism (distributed
memory + threads), 2-dimensional decomposition for graphs (as opposed
to the current row-wise decomposition), and alternates to MPI as a
communication infrastructure amongst many less important plans (and
the thesis project I'm keeping under my hat because I haven't
published enough about it to claim it yet). There's also a very
nascent project to do multi-core/highly multi-threaded BGL, starting
from the BGL sources as opposed to PBGL.

That's the short list, as (if?) we get more people working on the
project there's lots more to be done as well.

Thanks,
Nick

[Nick Edmonds]

On Sep 4, 2009, at 8:24 AM, Mathieu Malaterre wrote:

> On Thu, Sep 3, 2009 at 10:37 PM, Nick
> Edmonds<nged...@cs.indiana.edu> wrote:
>> Yep, PBGL as in the distributed data structures, MPI
>> infrastructure, and
>> distributed algorithms is now in Boost.
>
> Cool, I did not see it in the changelog, so I was confused.
>
>> Yep, that webpage is desperately out of date, I'm a terrible
>> webmaster.
>> Updating it (and the attendant performance numbers) has been on my
>> todo
>> list for ages. I'd make more promises, but they'd probably sound
>> hollow
>> now. So when I actually do it, it will be a pleasant surprise.
>
> So that it serve as reference to anyone reading this. The
> documentation have been updated, simply not uploaded neither on
> boost.org page nor on the old PBGL page. It is available locally as:
>
> file:///path/to/boost/libs/graph_parallel/doc/html/index.html
>

Yep, 1.40 is unfortunately missing the proper redirect in libs/

graph_parallel to libs/graph_parallel/doc/html/index.html. I've fixed
this in the trunk. When 1.41 goes out hopefully the docs will show up
on boost.org, this was due to my ignorance w.r.t. how docs got to the
webpage during the release process.

>> Structural information about the graph is only available on the

>> process that
>> owns that portion of the graph. Currently PBGL distributes the
>> graph using
>> a row-wise decomposition of the adjacency matrix. This means that
>> calling
>> vertices(g) returns the local vertex set owned by the calling
>> process. The
>> result of calling edges(g) depends on the directed category of the
>> edge, but
>> basically iterates over incident edges. Attempting to access
>> structural
>> information that is not local to the calling process, i.e. calling
>> out_edges(v, g) where 'v' is not owned by the calling process is
>> invalid and
>> results in undefined behavior.
>
> ok that clears things quite a bit !
>
>> If you want more details, to know why things work the way they do
>> now, or
>> how they might work in the future, feel free to ask away.
>
> 'in the future', what do you mean ? What are the actual plans ?
>

Well, there are lots of plans... Hybrid parallelism (distributed

memory + threads), 2-dimensional decomposition for graphs (as opposed
to the current row-wise decomposition), and alternates to MPI as a
communication infrastructure amongst many less important plans (and
the thesis project I'm keeping under my hat because I haven't
published enough about it to claim it yet). There's also a very
nascent project to do multi-core/highly multi-threaded BGL, starting
from the BGL sources as opposed to PBGL.

That's the short list, as (if?) we get more people working on the
project there's lots more to be done as well.

Thanks,
Nick

> Thanks again,

[Jose]

On Sat, Sep 12, 2009 at 9:42 PM, Nick Edmonds <nged...@cs.indiana.edu> wrote:

> yet).  There's also a very nascent project to do multi-core/highly
> multi-threaded BGL, starting from the BGL sources as opposed to PBGL.

Any pointers ? It would be nice if they look at using the map-reduce
library (boost candidate)