...

I am keen to get involved in open source project development as part of GSoC 2010 with Boost.

Hi Naresh, In additions to Nick's comments, I can help answer some of your other questions.

...

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.

I'm not quite sure I understand what you're asking, but GSoC projects are individual efforts. If you propose to do the work, then it should be /your/ work. There may be some other students working on sequential variants of those algorithms, but those would be more or less independent.

...

3. Can I get few more details of Computer Vision algorithms?

Computer Vision is not exactly my interest area so perhaps someone else can go into detail there.

I copied these over from last year's proposals. I think there's some interest in these algorithms (I think the domain came up in some discussion between the Geometry/Polygon folks), and I'm fairly certain that there's some support in CGAL for computer vision too. That said, I don't know much about them either :) Maybe Jeremiah can comment Andrew Sutton andrew.n.sutton@gmail.com

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@cs.indiana.edu> 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