X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=docs%2Fusers_guide%2Fparallel.xml;h=b8e73166e4e4e500ed898a53cd660792f4af549a;hb=bc86456c292fe73aa0bbb4daceaf3f966d59968c;hp=3d14622cf15ed723db881025d3ad1cfcb4d3e206;hpb=bd45ccd370162016fef7d0b4dec3518119ab392c;p=ghc-hetmet.git diff --git a/docs/users_guide/parallel.xml b/docs/users_guide/parallel.xml index 3d14622..b8e7316 100644 --- a/docs/users_guide/parallel.xml +++ b/docs/users_guide/parallel.xml @@ -4,24 +4,24 @@ parallelism - GHC implements some major extensions to Haskell to support - concurrent and parallel programming. Let us first etablish terminology: + GHC implements some major extensions to Haskell to support + concurrent and parallel programming. Let us first establish terminology: Parallelism means running a Haskell program on multiple processors, with the goal of improving performance. Ideally, this should be done invisibly, and with no semantic changes. - Concurrency means implementing + Concurrency means implementing a program by using multiple I/O-performing threads. While a - concurrent Haskell program can run on a + concurrent Haskell program can run on a parallel machine, the primary goal of using concurrency is not to gain performance, but rather because that is the simplest and most direct way to write the program. Since the threads perform I/O, the semantics of the program is necessarily non-deterministic. - GHC supports both concurrency and parallelism. + GHC supports both concurrency and parallelism. @@ -33,12 +33,12 @@ url="http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/concurrent-haskell.ps.gz"> Concurrent Haskell paper is still an excellent resource, as is Tackling + url="http://research.microsoft.com/%7Esimonpj/papers/marktoberdorf/">Tackling the awkward squad. To the programmer, Concurrent Haskell introduces no new language constructs; rather, it appears simply as a library, + url="&libraryBaseLocation;/Control-Concurrent.html"> Control.Concurrent. The functions exported by this library include: @@ -55,15 +55,15 @@ the FFI with concurrency. Software Transactional Memory GHC now supports a new way to coordinate the activities of Concurrent - Haskell threads, called Software Transactional Memory (STM). The + Haskell threads, called Software Transactional Memory (STM). The STM papers are an excellent introduction to what STM is, and how to use it. - The main library you need to use STM is - Control.Concurrent.STM. The main features supported are these: + The main library you need to use is the + stm library. The main features supported are these: Atomic blocks. Transactional variables. @@ -78,12 +78,12 @@ All these features are described in the papers mentioned earlier. Parallel Haskell GHC includes support for running Haskell programs in parallel - on symmetric, shared-memory multi-processor + on symmetric, shared-memory multi-processor (SMP)SMP. By default GHC runs your program on one processor; if you want it to run in parallel you must link your program with the , and run it with the RTS - option; see ). + option; see ). The runtime will schedule the running Haskell threads among the available OS threads, running as many in parallel as you specified with the @@ -109,15 +109,15 @@ All these features are described in the papers mentioned earlier. One way to do so is forking threads using Concurrent Haskell (), but the simplest mechanism for extracting parallelism from pure code is to use the par combinator, which is closely related to (and often used - with) seq. Both of these are available from Control.Parallel: + with) seq. Both of these are available from the parallel library: infixr 0 `par` -infixr 1 `seq` +infixr 1 `pseq` -par :: a -> b -> b -seq :: a -> b -> b +par :: a -> b -> b +pseq :: a -> b -> b The expression (x `par` y) sparks the evaluation of x @@ -136,24 +136,35 @@ import Control.Parallel nfib :: Int -> Int nfib n | n <= 1 = 1 - | otherwise = par n1 (seq n2 (n1 + n2 + 1)) + | otherwise = par n1 (pseq n2 (n1 + n2 + 1)) where n1 = nfib (n-1) n2 = nfib (n-2) For values of n greater than 1, we use par to spark a thread to evaluate nfib (n-1), - and then we use seq to force the + and then we use pseq to force the parent thread to evaluate nfib (n-2) before going on to add together these two subexpressions. In this divide-and-conquer approach, we only spark a new thread for one branch of the computation (leaving the parent to evaluate the other branch). Also, we must use - seq to ensure that the parent will evaluate + pseq to ensure that the parent will evaluate n2 before n1 in the expression (n1 + n2 + 1). It is not sufficient to reorder the expression as (n2 + n1 + 1), because the compiler may not generate code to evaluate the addends from left to right. + + Note that we use pseq rather + than seq. The two are almost equivalent, but + differ in their runtime behaviour in a subtle + way: seq can evaluate its arguments in either + order, but pseq is required to evaluate its + first argument before its second, which makes it more suitable + for controlling the evaluation order in conjunction + with par. + + When using par, the general rule of thumb is that the sparked computation should be required at a later time, but not too soon. Also, the sparked computation should not be too small, otherwise @@ -161,19 +172,31 @@ nfib n | n <= 1 = 1 amount of parallelism gained. Getting these factors right is tricky in practice. + It is possible to glean a little information about how + well par is working from the runtime + statistics; see . + More sophisticated combinators for expressing parallelism are - available from the Control.Parallel.Strategies module. + available from the Control.Parallel.Strategies + module in the parallel package. This module builds functionality around par, expressing more elaborate patterns of parallel computation, such as parallel map. +Data Parallel Haskell + GHC includes experimental support for Data Parallel Haskell (DPH). This code + is highly unstable and is only provided as a technology preview. More + information can be found on the corresponding DPH + wiki page. + +