Re: blackholes and exception handling
On 02/05/10 12:10, Sebastian Fischer wrote: Is the above output intended? Yes. Interesting. Note that catching all exceptions is rarely the right thing to do. See http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Control-Exception.html#4 for more details. I should have written go_ahead :: NonTermination - IO () in the first place. 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. Pure code can't distinguish, but exception handling code in IO can. What makes me wary is that GHC distinguishes between different kinds of non-terminating computations (those it can detect as black holes and those it can't). As a consequence, the semantics of my program depends on how I define the infinite loop don't_launch_first (the program either writes to stdout or doesn't). For me, it is interesting to notice (and slightly disturbing) that this is intended and that the Control.Exception module defines the NonTermination exception to explicitly handle black holes. The imprecise exceptions paper that you referenced describes exactly this issue in some detail - see Section 4.4, the semantics of getException (which is a simpler version of catch). Basically, catch is non-deterministic, so when the value is _|_ it can make a non-deterministic choice between diverging or catching an exception. Cheers, Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Parallel Haskell: 2-year project to push real world use
| Does this mean DPH is ready for abuse? | | The wiki page sounds pretty tentative, but it looks like it's been awhile | since it's been updated. | | http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell In truth, nested data parallelism has taken longer than we'd hoped to be ready for abuse :-). We have not lost enthusiasm though -- Manual, Roman, Gabi, Ben, and I talk on the phone each week about it. I think we'll have something usable by the end of the summer. Meanwhile, as Duncan mentioned, the regular, shape-polymorphic data-parallel Repa library (described in our ICFP submission) is on Hackage, so you can certainly try that! Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
On Mon, May 3, 2010 at 11:12 AM, Simon Peyton-Jones simo...@microsoft.comwrote: | Does this mean DPH is ready for abuse? | | The wiki page sounds pretty tentative, but it looks like it's been awhile | since it's been updated. | | http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell In truth, nested data parallelism has taken longer than we'd hoped to be ready for abuse :-). We have not lost enthusiasm though -- Manual, Roman, Gabi, Ben, and I talk on the phone each week about it. I think we'll have something usable by the end of the summer. That's very encouraging! I think people (me included) have gotten the impression that the project ran into problems so challenging that it stalled. Perhaps a small status update once in a while would give people a better idea of what's going on. :) Cheers, Johan ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
On 03/05/2010, at 22:04, Johan Tibell wrote: On Mon, May 3, 2010 at 11:12 AM, Simon Peyton-Jones simo...@microsoft.com wrote: | Does this mean DPH is ready for abuse? | | The wiki page sounds pretty tentative, but it looks like it's been awhile | since it's been updated. | | http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell In truth, nested data parallelism has taken longer than we'd hoped to be ready for abuse :-). We have not lost enthusiasm though -- Manual, Roman, Gabi, Ben, and I talk on the phone each week about it. I think we'll have something usable by the end of the summer. That's very encouraging! I think people (me included) have gotten the impression that the project ran into problems so challenging that it stalled. Perhaps a small status update once in a while would give people a better idea of what's going on. :) We keep running into challenging problems (the last one was a volcano) but we never stall. Things like the new GHC inliner, vector, repa are all part of DPH work. Roman ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
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.cou...@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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users pgpHVv3Y8QOSQ.pgp Description: PGP signature ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
choener: To summarise: I need arrays that allow in-place updates. Many of the array libraries provide both mutable and immutable interfaces, typically in ST or IO, including vector. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
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? 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 ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
On 03/05/2010, at 10:04 PM, Johan Tibell wrote: On Mon, May 3, 2010 at 11:12 AM, Simon Peyton-Jones simo...@microsoft.com wrote: | Does this mean DPH is ready for abuse? | | The wiki page sounds pretty tentative, but it looks like it's been awhile | since it's been updated. | | http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell In truth, nested data parallelism has taken longer than we'd hoped to be ready for abuse :-). We have not lost enthusiasm though -- Manual, Roman, Gabi, Ben, and I talk on the phone each week about it. I think we'll have something usable by the end of the summer. That's very encouraging! I think people (me included) have gotten the impression that the project ran into problems so challenging that it stalled. Perhaps a small status update once in a while would give people a better idea of what's going on. :) I'm currently working full time on cleaning up Repa and adding more examples. I'll do a proper announcement on the mailing lists once I've got the wiki set up. It would have been today but community.haskell.org was flaking out yesterday. Ben. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
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. 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. 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. Roman ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
* 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]) 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 pgpvp6koeNTyt.pgp Description: PGP signature ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Parallel Haskell: 2-year project to push real world use
* Roman Leshchinskiy r...@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 pgp0ZLbRkPLyX.pgp Description: PGP signature ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
