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

[Roman Leshchinskiy]

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

> * Ben Lippmeier <benl at ouroborus.net> [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.

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?

> 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.

> 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