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
Url : http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20100504/0868cc1c/attachment.bin


More information about the Glasgow-haskell-users mailing list