Re: [boost] GSoC Parallel BGP implementation

Subject: Re: [boost] GSoC Parallel BGP implementation
From: Naresh Reddy Sankapelly (nareshsankapelly_at_[hidden])
Date: 2010-03-26 14:28:00

> 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 men
>  tioned will probably get done in the context of the following project
> though...

I would like to work on the above mentioned project. I would request
Nick Edmonds  to give me few more details about the work.
Thank you,
Naresh S.
On 3/20/10, Nick Edmonds <ngedmond_at_[hidden]> wrote:
> 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 men
>  tioned 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
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Naresh Reddy S.
IIIT-Allahabad