Re: Parallel Haskell: 2-year project to push real world use

* Roman Leshchinskiy [04.05.2010 10:02]:

On 04/05/2010, at 11:10, Christian Höner zu Siederdissen wrote:

...

* Ben Lippmeier [04.05.2010 02:21]:

...

You can certainly create an array with these values, but in the provided code it looks like each successive array element has a serial dependency on the previous two elements. How were you expecting it to parallelise?

actually, in reality it is rather more complex, in a 2d-array, each cell (i,j) requires a linear number of accesses to previously calculated cells that all have indices bounded by the current (i,j).

One of the simplest codes is like this:

forall i in [1..n] forall j in [i..n] set (i,j) to: minimum of (i,k)+(k,j) (forall k in [i+1..j-1])

Is this related to wavefront algorithms? Although those only access immediate neighbours IIRC.

There is some similarity, but this problem extends to a lot of dynamic program algorithms that work on matrices.

In any case, vector could well provide an operation like this:

cant_think_of_a_name :: Vector v a => Int -> (v a -> a) -> v a

The function would take the initialised prefix of the vector (starting with empty) and produce the next element. This would require a bit of hackery underneath but the interface would be safe and pure. Would something like this be useful?

This would be very useful in general, as a number of algorithms that now require lazy arrays or ST/IO could be written with pure code. With the correct index transformation, it should be possible to have everything laid out nicely.

...

Here http://www.tbi.univie.ac.at/newpapers/Abstracts/98-06-009.ps.gz is a description of a parallel version of RNAfold.

IIUC, this parallelises processing of each diagonal but computes the diagonals one after another. Could you perhaps store each diagonal as a separate (parallel) array? That would make things much simpler.

That is no problem at all.

...

I can make my libraries available under GPLv3, they just need a bit of love. This gives you a moderately complex algorithm for which there is, too, a highly optimized C version (RNAfold -d2, in the vienna rna package).

That would be fantastic!

Roman

Gruss, Christian