May 2010 - Glasgow-haskell-users

Parallelization of Dynamic Programming Algorithms
by Christian Höner zu Siederdissen 16 May '10

16 May '10

Hi, continuing the above discussion "Parallel Haskell, 2 year project", here is what i want to do: - put an (almost) trivial program here that is a dynamic programming program but requires no other knowledge (like Bioinformatics or whatever). This one is attached. - write the same program but using one array for each diagonal so that it could be parallelized; using the vector package. - finally, lets see if something like that works in dph. - hint: we are typically interested in both, a final result and the table(s) for backtracking! + other topic: publish Haskell libraries for RNA-folding so that there is a benchmark against a C program, mainly for Roman and the 2-3 other people out there using Haskell for bioinformatics ;-) + other topic: if I start benchmarking in earnest, should I use HEAD because of the inliner bugs? Gruss, Christian PS: Dynamic Programming on a very high level, to see what kind of stuff I would like to be able to do (in parallel ;-) http://bibiserv.techfak.uni-bielefeld.de/adp/

1 0

HEADS UP: bugs in GHC 6.12.2
by Simon Marlow 12 May '10

12 May '10

Hi folks, I'm sorry to say that in GHC 6.12.2, as a result of fixing a couple of bugs in 6.12.1, we (well, I) managed to introduce some more serious ones: http://hackage.haskell.org/trac/ghc/ticket/4038 http://hackage.haskell.org/trac/ghc/ticket/4041 The first causes gtk2hs programs to crash, and we have a report of it affecting hmatrix too. There's no workaround unfortunately: the problem is that we changed some data structures related to FFI calls, with the result that a nested callback (calling out to C, back to Haskell, out to C again and back to Haskell in the same thread) can result in a crash or a bogus result. The second causes lazy bytestring's hGetContents to block waiting for a full buffer, when it should just return the data already read. You can work around this by using bytestring-0.9.1.5 instead of the supplied 0.9.1.6. We'll put out 6.12.3 with fixes for these as soon as possible. In the meantime, if you are still on 6.12.1 and not encountering any problems, I don't recommend upgrading. Sorry for the inconvenience. Cheers, Simon

1 0

Custom reducing functions for DPH
by Edward Z. Yang 10 May '10

10 May '10

Hello all, I was asking this question on #haskell and thoughtpolice directed me here for a possibly more up-to-date information. Some of the important primitives offered by Data Parallel Haskell are reduction primitives such as sumP and prodP, which take a data parallel array and reduce it to a single value. I was wondering what the current capabilities for end-users interested in implementing their own reduction primitives were. In particular, if I want to run data parallel computations on strings, I will generally want a more exotic set of combining operators. thoughtpolice informed me that GHC 6.10 seemed to have sumP/prodP hard coded into the vectorisation and optimisation stages, so this didn't really seem possible in userspace. I'm interested to know if this situation has changed. No hard feelings if it hasn't; I'm really just playing around with DPH and seeing what it can do. :-) Cheers, Edward

2 1

-O vs. -O2
by Roman Leshchinskiy 10 May '10

10 May '10

Whenever I do cabal sdist on one of my projects, I get this warning: Distribution quality warnings: 'ghc-options: -O2' is rarely needed. Check that it is giving a real benefit and not just imposing longer compile times on your users. This finally got me curious and I did a nofib run to compare -O to -O2. The results are below (this is with the current HEAD). Is there a real-world example of -O2 causing significantly longer compile times without providing a real benefit? If not, would it perhaps make sense for Cabal to use -O2 by default or even for GHC to make the two flags equivalent? Roman NoFib Results -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed -------------------------------------------------------------------------------- anna +2.5% -0.2% 0.08 0.11 ansi +0.0% +0.0% 0.00 0.01 atom +0.0% +0.0% 0.20 +0.0% awards +0.0% +0.0% 0.00 0.01 banner +0.0% +0.0% 0.00 0.01 bernouilli +0.0% +0.0% +0.0% +0.5% boyer +0.0% -0.3% 0.03 0.04 boyer2 +0.2% +0.0% 0.00 0.01 bspt +0.4% +0.0% 0.00 0.02 cacheprof +0.6% +0.0% +0.0% +0.0% calendar +0.2% +0.1% 0.00 0.01 cichelli +0.0% -0.0% 0.07 0.08 circsim +0.2% -0.0% -1.4% +0.3% clausify +0.2% -6.8% 0.03 0.04 comp_lab_zift +0.8% +0.7% 0.17 0.19 compress +0.0% +0.0% 0.14 0.16 compress2 +2.3% -1.3% 0.14 0.17 constraints +0.0% +0.0% -0.4% -0.0% cryptarithm1 +0.0% +0.0% +0.0% -0.3% cryptarithm2 +0.0% -4.7% 0.01 0.02 cse +0.0% +0.0% 0.00 0.01 eliza +0.0% +0.0% 0.00 0.01 event +0.2% +1.5% 0.14 0.16 exp3_8 +0.0% +0.0% 0.10 0.11 expert +0.4% +0.4% 0.00 0.01 fem +0.5% +1.0% 0.02 0.02 fft +0.2% -1.6% 0.03 0.04 fft2 +0.2% +0.0% 0.06 0.07 fibheaps +0.2% +0.4% 0.03 0.04 fish +0.0% +0.0% 0.01 0.03 fluid +2.1% -1.9% 0.01 0.02 fulsom +0.2% +0.0% +0.0% -0.5% gamteb +0.7% -2.1% 0.07 0.09 gcd +0.0% -1.7% 0.02 0.02 gen_regexps +0.0% +0.0% 0.00 0.01 genfft +0.0% -0.3% 0.03 0.03 gg +0.5% -0.8% 0.01 0.02 grep +0.2% +0.0% 0.00 0.01 hidden +0.3% +0.0% -3.2% -3.5% hpg +0.2% +0.0% 0.14 +0.6% ida +0.5% -0.7% 0.07 0.08 infer +0.0% +0.0% 0.04 0.05 integer +0.0% +0.0% +0.0% +0.0% integrate +0.0% +0.0% +0.0% +0.0% knights +0.7% -13.4% 0.00 0.01 lcss +0.0% -0.0% -0.8% -0.7% life +0.0% +0.0% 0.20 -1.0% lift +0.2% +3.6% 0.00 0.01 listcompr +0.0% +0.0% 0.09 0.12 listcopy +0.0% -0.0% 0.10 0.13 maillist +0.0% -0.2% 0.05 +0.2% mandel +0.0% +0.0% 0.07 0.09 mandel2 +0.2% -67.2% 0.00 0.00 minimax +0.0% +0.4% 0.00 0.01 mkhprog +0.0% +0.0% 0.00 0.01 multiplier +0.0% +0.0% 0.09 0.11 nucleic2 +0.0% +0.0% 0.06 0.07 para +0.9% +0.5% +6.4% +5.5% paraffins +0.4% +0.2% 0.07 0.10 parser +0.5% +0.3% 0.03 0.04 parstof +0.2% -2.5% 0.00 0.01 pic +0.4% -0.8% 0.00 0.02 power +0.4% +0.0% +0.0% +0.8% pretty +0.2% -2.9% 0.00 0.01 primes +0.0% +0.0% 0.05 0.06 primetest +0.2% +0.0% +0.0% +0.6% prolog +0.2% -0.9% 0.00 0.01 puzzle +0.0% +0.0% 0.14 0.16 queens +0.0% -72.0% 0.01 0.02 reptile +0.2% +0.0% 0.01 0.02 rewrite +0.2% +0.0% 0.01 0.02 rfib +0.0% +0.0% 0.04 0.05 rsa +0.0% +0.0% 0.06 0.07 scc +0.0% +0.0% 0.00 0.01 sched +0.2% +0.6% 0.02 0.03 scs +0.8% -0.4% +0.0% +1.4% simple +0.2% +0.0% +0.0% +0.0% solid +0.0% -0.0% 0.11 0.13 sorting +0.2% +0.0% 0.00 0.01 sphere +0.0% +0.5% 0.08 0.09 symalg +0.5% -0.0% 0.03 0.04 tak +0.0% +0.0% 0.01 0.02 transform +0.6% -0.0% +0.0% +0.7% treejoin +0.2% -2.0% 0.20 +3.5% typecheck +0.0% +0.3% 0.19 +0.0% veritas +1.0% -0.3% 0.00 0.01 wang +0.0% -1.0% 0.07 0.09 wave4main +0.0% +0.0% +3.7% +1.4% wheel-sieve1 +0.2% +0.0% +0.0% -0.8% wheel-sieve2 +0.2% +0.0% 0.14 0.17 x2n1 +0.0% -1.3% 0.02 0.03 -------------------------------------------------------------------------------- Min +0.0% -72.0% -3.2% -3.5% Max +2.5% +3.6% +6.4% +5.5% Geometric Mean +0.2% -3.0% +0.2% +0.4%

6 8

Parallel Haskell: 2-year project to push real world use
by Duncan Coutts 08 May '10

08 May '10

GHC HQ and Well-Typed are very pleased to announce a 2-year project funded by Microsoft Research to push the real-world adoption and practical development of parallel Haskell with GHC. We are seeking organisations to take part: read on for details. 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. This project aims to do the engineering work to solve whatever remaining practical problems are blocking organisations from making serious use of parallelism with GHC. The driving force will be the *applications* rather than the *technology*. We will work in partnership with a small number of commercial or scientific users who are keen to make use of parallel Haskell. We will work with these partners to identify the issues, major or minor, that are hindering progress. The project is prepared to handle system issues, covering everything from compiler and runtime system through to more mundane platform and tool problems. Meanwhile our partners will contribute their domain-specific expertise to use parallel Haskell to address their application. We are now seeking organisations to take part in this project. Organisations do not need to contribute financially but should be prepared to make a significant commitment of their own time. We expect to get final confirmation of the project funding in June and to start work shortly thereafter. Well-Typed will coordinate the project, working directly with both the participating organisations and the Simons at GHC HQ. If you think your organisation may be interested then get in touch with me, Duncan Coutts, via info(a)well-typed.com. -- Duncan Coutts, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

6 7

strong type derivation in ghc 6.12 compared to 6.12
by Seyed Hosein Attarzadeh Niaki 07 May '10

07 May '10

I have problems with upgrading some already working code for GHC 6.12. The following code: ----------------------------------------------------------- {-# LANGUAGE DeriveDataTypeable, GeneralizedNewtypeDeriving, TemplateHaskell #-} import Data.Data import Language.Haskell.TH.Syntax class Nat a class (Data a, Lift a) => ProcType a instance (Lift a, Nat s) => Lift (FSVec s a) where lift (FSVec xs) = undefined newtype Nat s => FSVec s a = FSVec {unFSVec :: [a]} deriving (Eq, Typeable, Data) -- The following line does not cause a problem in GHC 6.10 -- instance (Typeable s, Nat s, ProcType a) => ProcType (FSVec s a) ----------------------------------------------------------- works fine in ghc 6.10.4 and I get (extra stuff removed): // *Main> :i FSVec newtype (Nat s) => ... instance (Data a, Typeable s, Nat s) => Data (FSVec s a) -- Defined at ghctest.hs:16:26-29 ... // but in 6.12.2 what I get is: // *Main> :i FSVec newtype (Nat s) => ... instance (Data s, Data a, Nat s) => Data (FSVec s a) ... // So, although the last line in the above code compiles correctly in ghc 6.10.4, in 6.12.2 GHC complains with: // ghctest.hs:19:10: Could not deduce (Data s) from the context (Typeable s, Nat s, ProcType a) arising from the superclasses of an instance declaration at ghctest.hs:19:10-64 Possible fix: add (Data s) to the context of the instance declaration In the instance declaration for `ProcType (FSVec s a)' Failed, modules loaded: none. // Why are they different? Why 6.12 derives a stronger constraint? Is it a bug or it was not working correctly before? -- Hosein Attarzadeh

3 2

segmentation fault in Gtk2Hs callbacks
by Axel Simon 07 May '10

07 May '10

Good morning, I'm looking at ticket http://hackage.haskell.org/trac/ghc/ticket/4038 and wonder who is to blame: - this segmentation fault occurs in Gtk2Hs' callbacks (i.e. a Haskell function pointer is being passed to C land) and in a signal (where a general machinery is used to invoke a Haskell function), thus, it doesn't seem to be the way callbacks are used - the segfault only occurs in ghc 6.12.2 not in ghc 6.12.1 However, in the release notes of 6.12.2 there are no changes indicated that look like the RTS has changed. So I would like to simply ask: Are any of the GHC developers aware of any change in the concurrency or GC behaviour in GHC's RTS? Have any other parameters changed (perhaps something with multithreading?). Neither Gtk2Hs nor GHC seem to have changed, yet, there are these intermittend segfaults. It would be good to know which part is the culprit. Thanks, Axel

2 1

standalone binary deriving
by Ben 05 May '10

05 May '10

compiling the following fragment in ghci {-# LANGUAGE StandaloneDeriving #-} import Data.Binary (Binary) newtype Pair a b = Pair (a,b) deriving instance (Binary a, Binary b) => Binary (Pair a b) results in the following message: Prelude> :load "/Users/catbee/Documents/dev/haskell/savestream/foo.hs" [1 of 1] Compiling Main ( /Users/catbee/Documents/dev/haskell/savestream/foo.hs, interpreted ) ghc: panic! (the 'impossible' happened) (GHC version 6.12.1 for i386-apple-darwin): genDerivBinds: bad derived class binary-0.5.0.2:Data.Binary.Binary{tc rkt} Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug should i file a bug report? b

2 1

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