May 2010 - Glasgow-haskell-users

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 03 May '10

03 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