[Lemon-user] parallelization of LEMON library

[Raghava Mutharaju]

Hello Alpar,

Thank you for the rely and the inputs :)
I meant the thread safe graph data structures. I looked around into couple
of parallel graph processing frameworks and I am finally going with Parallel
Boost Graph Library. The graph is distributed across the cluster and the
underlying communication mechanism as of now is MPI. So it also fits into
the mechanism of parallelism that you were recommending.

Regards,
Raghava.

On Sun, Sep 19, 2010 at 12:30 AM, Alpár Jüttner <alpar at cs.elte.hu> wrote:

> Hi,
>
> > Was there any attempt made by anyone to use external thread libraries
> > with LEMON and parallelize it?
>
> It depends on what do you mean by parallelization.
>
>      * If you mean thread safe graph data structures, then yes, he have
>        plans to make our basic date types (graphs and maps) thread
>        safe. This will allow multiple execution of (same/different)
>        algorithms on the same underlying graph in parallel.
>        There are two non-exclusive proposals for doing it, see
>        http://lemon.cs.elte.hu/trac/lemon/ticket/223 and
>        http://lemon.cs.elte.hu/trac/lemon/ticket/224 for some
>        discussions and proof-of-the-concept implementations.
>      * If you mean parallel implementation of certain algorithms, then
>        currently I cannot see any attempt for doing it, though any
>        contribution in this field is warmly welcome, of course.
>
> Two more comments:
>
> Firstly, there are several the studies proposing multi thread
> implementation of basic algorithms like shortest path, min. cost flow,
> matching etc. However, the running time penalty seems to be too large in
> all of these implementation - i.e. they demonstrates that using more and
> more processor they can improve something on the time needed to
> accomplish the task, but the overall cpu resource consumption increases
> dramatically.
>
> Therefore, for most of the large scale computations, I recommend using
> the sequential implementation of the basic algorithms and do the
> parallelization on a higher level. That's why the thread safe data
> structure implementations are of higher priority for us.
>
> Secondly, in the long rung, I feel the real scalable answer to
> parallelization is not the multi-thread solutions, but instead the
> message passing based distributed ones. Many people argues that not only
> is the message passing based parallelization more scalable but also it
> is much safer and more reliable from software engineering point-of-view.
> See e.g. http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf
>
> I pretty much agree with these arguments.
>
> Regards,
> Alpar
>
>
> > Regards,
> > Raghava.
> > _______________________________________________
> > Lemon-user mailing list
> > Lemon-user at lemon.cs.elte.hu
> > http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100919/716b31d2/attachment.html>