[Lemon-user] parallelization of LEMON library

[Alpár Jüttner]

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