- 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

New trac policy
by Ian Lynagh 30 Apr '10

30 Apr '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

ANNOUNCE: GHC version 6.12.2
by Ian Lynagh 27 Apr '10

27 Apr '10

============================================================== The (Interactive) Glasgow Haskell Compiler -- version 6.12.2 ============================================================== The GHC Team is pleased to announce a new patchlevel release of GHC. This release contains a number of bugfixes relative to 6.12.1, so we recommend upgrading. Release notes are here: http://haskell.org/ghc/docs/6.12.1/html/users_guide/release-6-12-2.html How to get it ~~~~~~~~~~~~~ The easy way is to go to the web page, which should be self-explanatory: http://www.haskell.org/ghc/ We supply binary builds in the native package format for many platforms, and the source distribution is available from the same place. Packages will appear as they are built - if the package for your system isn't available yet, please try again later. Background ~~~~~~~~~~ Haskell is a standard lazy functional programming language; the current language version is Haskell 98, agreed in December 1998 and revised December 2002. GHC is a state-of-the-art programming suite for Haskell. Included is an optimising compiler generating good code for a variety of platforms, together with an interactive system for convenient, quick development. The distribution includes space and time profiling facilities, a large collection of libraries, and support for various language extensions, including concurrency, exceptions, and foreign language interfaces (C, whatever). GHC is distributed under a BSD-style open source license. A wide variety of Haskell related resources (tutorials, libraries, specifications, documentation, compilers, interpreters, references, contact information, links to research groups) are available from the Haskell home page (see below). On-line GHC-related resources ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Relevant URLs on the World-Wide Web: GHC home page http://www.haskell.org/ghc/ GHC developers' home page http://hackage.haskell.org/trac/ghc/ Haskell home page http://www.haskell.org/ Supported Platforms ~~~~~~~~~~~~~~~~~~~ The list of platforms we support, and the people responsible for them, is here: http://hackage.haskell.org/trac/ghc/wiki/Contributors Ports to other platforms are possible with varying degrees of difficulty. The Building Guide describes how to go about porting to a new platform: http://hackage.haskell.org/trac/ghc/wiki/Building Developers ~~~~~~~~~~ We welcome new contributors. Instructions on accessing our source code repository, and getting started with hacking on GHC, are available from the GHC's developer's site run by Trac: http://hackage.haskell.org/trac/ghc/ Mailing lists ~~~~~~~~~~~~~ We run mailing lists for GHC users and bug reports; to subscribe, use the web interfaces at http://www.haskell.org/mailman/listinfo/glasgow-haskell-users http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs There are several other haskell and ghc-related mailing lists on www.haskell.org; for the full list, see http://www.haskell.org/mailman/listinfo/ Some GHC developers hang out on #haskell on IRC, too: http://www.haskell.org/haskellwiki/IRC_channel Please report bugs using our bug tracking system. Instructions on reporting bugs can be found here: http://www.haskell.org/ghc/reportabug

3 4

FFI calls: is it possible to allocate a small memory block on a stack?
by Denys Rtveliashvili 27 Apr '10

27 Apr '10

Good morning, Yesterday I did a few tests to measure the performance of FFI calls and found that the calls themselves are very quick (1-2 nanosecond). However, there is a kind of FFI calls when one have to allocate a temporary memory block (for a struct, or a temporary buffer). One of examples is a call to "gettimeofday" or "clock_gettime". Unfortunately, the usual way of doing it (using the "alloca" function) is quite slow (~40 nanoseconds). I was wondering, is there any way to allocate a small chunk of data on a thread's stack? That should be cheap, as by large it is just a shift of a pointer and, perhaps, a few other trivial operations. I understand that it is not safe to allocate large blocks on the stack. But we could possibly have a function similar to "alloca" which would allocate small blocks on stack and would use the "alloca" for big ones. With kind regards, Denys Rtveliashvili

7 17