Re: [boost] GSoC Parallel BGP implementation

Subject: Re: [boost] GSoC Parallel BGP implementation
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2010-03-19 20:34:07

On Mar 19, 2010, at 4:59 PM, Naresh Reddy Sankapelly wrote:

> hi,
> 
> I am naresh, a student pursuing B.Tech 4th year from Indian Institute of
> Information
> Technology- Allahabad, India.
> 
> I am keen to get involved in open source project development as part of GSoC
> 2010 with Boost. I went though the ideas list provided in the site. I'm
> interested to work on parallel graph algorithms for BGL in particular with
> graph connectives project. I took this because I have worked on
> parallelizing graph algorithms as a part of my Parallel Computing course.
> 
> I would be happy to know few things.
> 1. Can I work on library of my own for parallel computing like Intel's TBB
> ?or should I use MPI only?
> 2. It would be helpful for me if I can have one more student working on
> sequential part of graph algorithms. Is it allowed? If it is, and any one
> interested please reply me back.
> 3. Can I get few more details of Computer Vision algorithms?
> 
> I look forward to your replies soon.
> 
> Thanks

Hi Naresh,

While we're definitely interested in students writing new parallel algorithms, I would prefer that new algorithms support distributed memory at a minimum (thus libraries like TBB or languages like Cilk are not sufficient).  There is definitely room for a 'Multicore-BGL' project, but at the moment the prevailing wisdom in the group is that SIMD or fine-grained parallel graph algorithms would best be developed as a branch of BGL, not Parallel BGL.  There's a bit of work to be done on lock-free data structures and making property maps thread-safe that would have to happen before 'Multicore BGL' would be feasible.  Most of it is relatively straightforward, but there are some tricky parts, such as combining dependent property-map updates without locking wherever possible (playing games with data layout and whatever atomics are around, i.e. double-word CAS), etc.  In any case, 'Multicore-BGL' is significantly more than a summer project I firmly believe.  Some of the work I just mentioned will probably get done in the context of the following project though...

We are doing some very preliminary work on hybrid-parallel graph algorithms in Parallel BGL that support thread-level parallelism inside distributed algorithms.  The current work utilizes a generalized active messaging layer that is very lightweight on top of MPI, eventually we'd like to switch to running over GASNet or directly on top of the network driver to further reduce latencies.  You would have to be exceptionally careful to preserve performance if you wanted to use TBB or another task-parallel library and I believe that the composition we have put together makes writing threaded code without a task-library completely reasonable.  The work is still in its infancy (we're submitting the first paper on it next week, and the only other public mention was a talk at SIAM-PP) so I'm not sure it's ready for outside collaborators but I'd be willing to talk about it.

Computer Vision is not exactly my interest area so perhaps someone else can go into detail there.  If someone can toss out appropriate algorithms then I can definitely comment on how hard they'd be to implement in Parallel BGL.

Cheers,
Nick