[Lemon-user] parallelization of LEMON library

[Alpár Jüttner]

Hi,

I'm sorry, but I don't understand your goals.

      * If MPI is in use, then why do you need thread safety at all? For
        MPI you need some efficient data structure serialization instead
        (in order to pass graphs and other data between the nodes).
      * I believe Parallel Boost Graph Library is for low level
        parallelization (i.e. it is able to execute e.g. a single
        shortest path execution in parallel). I guess their basic
        algorithm implementations are not the most effective in
        sequential mode.

Anyway, I look forward hearing about your experience with Parallel Boost
Graph Library. Parallel computation support is inevitable in order to
utilize the power of the future (in fact even the contemporary) high
performance computers.

Regards,
Alpar

On Sun, 2010-09-19 at 17:19 -0400, Raghava Mutharaju wrote:
> 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
>         
>         
>