- Glasgow-haskell-users

Re: Parallel Haskell: 2-year project to push real world use
by John Lato 05 May '10

05 May '10

> From: Roman Leshchinskiy <rl(a)cse.unsw.edu.au> Following on this discussion, I have an algorithm that currently uses BLAS to do the heavy work. I'd like to try to get it working with DPH or Repa, although my prior attempts have been less than successful. I have a vector of vectors where each element depends upon the previous two; I can use zipWithP to generate each successive element, but I don't see how to create the entire structure. I could use "unfold" if one were provided. The best approach I can think of is to create a sequential list of element-vectors. Also, where is scanP? I don't see it in Data.Array.Parallel.Prelude (GHC-6.12.1). Cheers, John

1 0

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

* Roman Leshchinskiy <rl(a)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(a)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

2 1

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

* Ben Lippmeier <benl(a)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]) So, either I use destructive updates or need a tricky way to extend the already computed part of the array with the new part (i,j). The above code shows only why I need destructive updates. RNA folding is one of those where it is needed. I will try to distill the code down to an example that shows a possibility for parallelization. I would want to use this for future algorithms where it makes much more sense (O(n^4) or more), but that still first update an array element, and then access it later. Here http://www.tbi.univie.ac.at/newpapers/Abstracts/98-06-009.ps.gz is a description of a parallel version of RNAfold. > > Repa arrays don't support visible destructive update. For many algorithms you should't need it, and it causes problems for parallelisation. > > I'm actively writing more Repa examples now. Can you sent me some links explaining the algorithm that you're using, and some example data + output? > > Thanks, > Ben. > > > > On 04/05/2010, at 9:21 AM, Christian Höner zu Siederdissen wrote: > > > a = array (1,10) [ (i,f i) | i <-[1..10]] where > > f 1 = 1 > > f 2 = 1 > > f i = a!(i-1) + a!(i-2) > > > > (aah, school ;) > > > > Right now, I am abusing vector in ST by doing this: > > > > a <- new > > a' <- freeze a > > forM_ [3..10] $ \i -> do > > write a (a'!(i-1) + a!(i-2)) > > > > Let's say I wanted to do something like this in dph (or repa), does that > > work? We are actually using this for RNA folding algorithms that are at > > least O(n^3) time. For some of the more advanced stuff, it would be > > really nice if we could "just" parallelize. > > > > To summarise: I need arrays that allow in-place updates. > > > > Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are > > using vector right now. On a single core, it performs really great -- > > even compared to C-code that has been optimized a lot. > > > > Thanks and "Viele Gruesse", > > Christian >

2 1

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

* Roman Leshchinskiy <rl(a)cse.unsw.edu.au> [04.05.2010 02:32]: > On 04/05/2010, at 09:21, Christian Höner zu Siederdissen wrote: > > > Hi, > > > > on that topic, consider this (rather trivial) array: > > > > a = array (1,10) [ (i,f i) | i <-[1..10]] where > > f 1 = 1 > > f 2 = 1 > > f i = a!(i-1) + a!(i-2) > > > > (aah, school ;) > > > > Right now, I am abusing vector in ST by doing this: > > > > a <- new > > a' <- freeze a > > forM_ [3..10] $ \i -> do > > write a (a'!(i-1) + a!(i-2)) > > > > Let's say I wanted to do something like this in dph (or repa), does that > > work? We are actually using this for RNA folding algorithms that are at > > least O(n^3) time. For some of the more advanced stuff, it would be > > really nice if we could "just" parallelize. > > Do you really just need a prefix sum? These are easily parallelisable if the operator is associative. For instance, you could implement the Fibonacci sequence as: > > mapP fst $ scanP (\(a,b) _ -> (a+b,a)) (1,0) $ replicateP n (0,0) > > and DPH would parallelise it. That's how I would write the above with vector as well. That is, kind of, the fun part: you have (1) a number of vectors whose values depend on each other (bad!) (2) in-place update (bad!) (3) rather trivial calculations for each element (mostly: sum, minimum, fold, map, backpermute) (good!), we have simple semiring calculations here > > > To summarise: I need arrays that allow in-place updates. > > In-place updates + parallelism = bad! That's oversimplifying, of course. But the transformations underlying DPH, for instance, simply don't work in the presence of side effects. The thing is, you can write the algorithm in a way such that each operation on index "k" (whatever dimension k has) only requires access to values <=k and those values will never change again. The problem is that more than one vector is involved making it less fun to write code like your fibonacci example. > > > Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are > > using vector right now. On a single core, it performs really great -- > > even compared to C-code that has been optimized a lot. > > That's great to know! Do you (or anyone else) by any chance have any benchmarks you could share? At the moment, I'm only benchmarking vector with a couple of rather simplistic algorithms which is a bit of a problem. 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). I am giving a talk wednesday, after that I'll prepare the libraries for hackage. Gruss, Christian

1 0

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

Hi, on that topic, consider this (rather trivial) array: a = array (1,10) [ (i,f i) | i <-[1..10]] where f 1 = 1 f 2 = 1 f i = a!(i-1) + a!(i-2) (aah, school ;) Right now, I am abusing vector in ST by doing this: a <- new a' <- freeze a forM_ [3..10] $ \i -> do write a (a'!(i-1) + a!(i-2)) Let's say I wanted to do something like this in dph (or repa), does that work? We are actually using this for RNA folding algorithms that are at least O(n^3) time. For some of the more advanced stuff, it would be really nice if we could "just" parallelize. To summarise: I need arrays that allow in-place updates. Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are using vector right now. On a single core, it performs really great -- even compared to C-code that has been optimized a lot. Thanks and "Viele Gruesse", Christian * Duncan Coutts <duncan.coutts(a)googlemail.com> [30.04.2010 17:11]: > On Fri, 2010-04-30 at 10:25 -0400, Tyson Whitehead wrote: > > On April 30, 2010 06:32:55 Duncan Coutts wrote: > > > In the last few years GHC has gained impressive support for parallel > > > programming on commodity multi-core systems. In addition to traditional > > > threads and shared variables, it supports pure parallelism, software > > > transactional memory (STM), and data parallelism. With much of this > > > research and development complete, and more on the way, the next stage > > > is to get the technology into more widespread use. > > > > Does this mean DPH is ready for abuse? > > This project is about pushing the practical use of the parallel > techniques that are already mature, rather than about pushing research > projects along further. > > So this project is not really about DPH. On the other hand it's possible > someone might be able to make more immediate use of the dense, regular > parallel arrays which has been a recent spinoff of the DPH project. They > have the advantage of being considerably easier to implement, but much > less expressive than the full sparse, nested parallel arrays. > > Duncan > > _______________________________________________ > Glasgow-haskell-users mailing list > Glasgow-haskell-users(a)haskell.org > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

4 3

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

Sorry, to make it more clear: in the line: > write a (a'!(i-1) + a!(i-2)) only > (a'!(i-1) + a!(i-2)) would need to be parallel, as there we typically have a sum/minimum or whatever. The forM_ over each index does not need to be, since we have to fill the array anyway... * Christian Höner zu Siederdissen <choener(a)tbi.univie.ac.at> [04.05.2010 01:22]: > Hi, > > on that topic, consider this (rather trivial) array: > > a = array (1,10) [ (i,f i) | i <-[1..10]] where > f 1 = 1 > f 2 = 1 > f i = a!(i-1) + a!(i-2) > > (aah, school ;) > > Right now, I am abusing vector in ST by doing this: > > a <- new > a' <- freeze a > forM_ [3..10] $ \i -> do > write a (a'!(i-1) + a!(i-2)) > > Let's say I wanted to do something like this in dph (or repa), does that > work? We are actually using this for RNA folding algorithms that are at > least O(n^3) time. For some of the more advanced stuff, it would be > really nice if we could "just" parallelize. > > To summarise: I need arrays that allow in-place updates. > > Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are > using vector right now. On a single core, it performs really great -- > even compared to C-code that has been optimized a lot. > > Thanks and "Viele Gruesse", > Christian

1 0

blackholes and exception handling
by Sebastian Fischer 03 May '10

03 May '10

Hello, GHC can spot (some) non-terminating computations and terminate with blackhole: <<loop>> instead of running indefinitely. With exception handling one can handle such situations. The following program 'launches missiles': import Control.Exception main = do handle go_ahead don't_launch_first launch_missiles don't_launch_first = don't_launch_first go_ahead :: SomeException -> IO () go_ahead _ = putStr "go ahead, " launch_missiles = putStr "fire!" The output of this program is go ahead, fire! although, don't_launch_first is a non-terminating computation. Without black-hole detection this code would never 'launch missiles'. Is the above output intended? The idea behind black-hole detection is that one bottom is as good as another [1]. Consequently, exception handling may not distinguish between non-termination and other errors. Is the equation _|_ `catch` const a = a supposed to hold in general (for every kind of bottom)? Or is it a bug in GHC that programmers can handle black-hole errors? Sebastian [1] A semantics for imprecise exceptions http://portal.acm.org/citation.cfm?id=301637 -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

4 4

Cutting down GHC installation to bare minimum
by leledumbo 03 May '10

03 May '10

I notice that many of the installed libs aren't required for learning Haskell. What libs are required so I can get the bare minimum version of GHC? Also, is there any automatic way so that I don't have to manually delete the folders and edit package.conf? -- View this message in context: http://old.nabble.com/Cutting-down-GHC-installation-to-bare-minimum-tp28374… Sent from the Haskell - Glasgow-haskell-users mailing list archive at Nabble.com.

4 4

New trac policy
by Ian Lynagh 01 May '10

01 May '10

Hi all, We have made some changes to the way in which we use trac, our bug tracker. The details are all documented here: http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions#TheBugTracker but the highlights are below. We no longer have branch milestones (like 6.12-branch). Instead, we will make better use of the ticket priorities to differentiate tickets: * highest priority tickets are blockers for that release * high priority tickets are those that we also plan to fix before releasing * we will also try to fix as many lower priority tickets as possible Any tickets that are more than 2 major releases old (e.g. filed against 6.10, when 6.14 is about to be released) will be moved to the _|_ milestone, unless there is reason to keep them more visible (e.g. a patch attached for review, or significant support in the CC field). Thanks Ian

1 0

Default value for numCapabilities?
by Dimitry Golubovsky 30 Apr '10

30 Apr '10

Hi, As a followup to the discussion [1] about the portable way to find the number of CPUs/cores: how is the default value of numCapabilities [2] set when +RTS -N is not on the command line? Does GHC runtime figure out the number of cores itself, or it is by default 1 unless specified on the command line? Thanks. --------------------------- [1] http://haskell.org/pipermail/haskell-cafe/2010-April/076911.html [2] http://hackage.haskell.org/packages/archive/base/latest/doc/html/GHC-Conc.h… -- Dimitry Golubovsky Anywhere on the Web

5 9