Parallel Haskell: 2-year project to push real world use
Roman Leshchinskiy
rl at cse.unsw.edu.au
Tue May 4 04:02:09 EDT 2010
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
More information about the Glasgow-haskell-users
mailing list