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

Christian Höner zu Siederdissen choener at tbi.univie.ac.at
Tue May 4 04:37:09 EDT 2010

```* Roman Leshchinskiy <rl at cse.unsw.edu.au> [04.05.2010 10:02]:
> 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.

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available