* Roman Leshchinskiy <r...@cse.unsw.edu.au> [04.05.2010 10:02]: > On 04/05/2010, at 11:10, Christian Höner zu Siederdissen wrote: > > > * Ben Lippmeier <b...@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
pgpYlSqAujDbf.pgp
Description: PGP signature
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
