X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=docs%2Fusers_guide%2Fparallel.xml;h=76d38dc6464031ed61928a6df316d172f81d5361;hb=d5ab3b5e415ebdff8906dcac3451e7448d6bdb11;hp=11c254789898d1d2c92eb9fd3f742cb8efe7d4fe;hpb=0065d5ab628975892cea1ec7303f968c3338cbe1;p=ghc-hetmet.git diff --git a/docs/users_guide/parallel.xml b/docs/users_guide/parallel.xml index 11c2547..76d38dc 100644 --- a/docs/users_guide/parallel.xml +++ b/docs/users_guide/parallel.xml @@ -1,203 +1,180 @@ - -Concurrent and Parallel Haskell - - -Concurrent Haskell -Parallel Haskell -Concurrent and Parallel Haskell are Glasgow extensions to Haskell -which let you structure your program as a group of independent -`threads'. + + Concurrent and Parallel Haskell + parallelism + + + 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 + a program by using multiple I/O-performing threads. While 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. + + + + Concurrent Haskell + + Concurrent Haskell is the name given to GHC's concurrency extension. + It is enabled by default, so no special flags are required. + The + Concurrent Haskell paper is still an excellent + resource, as is Tackling + the awkward squad. + + To the programmer, Concurrent Haskell introduces no new language constructs; + rather, it appears simply as a library, + Control.Concurrent. The functions exported by this + library include: + +Forking and killing threads. +Sleeping. +Synchronised mutable variables, called MVars +Support for bound threads; see the paper Extending +the FFI with concurrency. + + - -Concurrent and Parallel Haskell have very different purposes. - - - -Concurrent Haskell is for applications which have an inherent -structure of interacting, concurrent tasks (i.e. `threads'). Threads -in such programs may be required. For example, if a concurrent thread has been spawned to handle a mouse click, it isn't -optional—the user wants something done! - - - -A Concurrent Haskell program implies multiple `threads' running within -a single Unix process on a single processor. - - - -You will find at least one paper about Concurrent Haskell hanging off -of Simon Peyton -Jones's Web page. - - - -Parallel Haskell is about speed—spawning -threads onto multiple processors so that your program will run faster. -The `threads' are always advisory—if the -runtime system thinks it can get the job done more quickly by -sequential execution, then fine. - - - -A Parallel Haskell program implies multiple processes running on -multiple processors, under a PVM (Parallel Virtual Machine) framework. -An MPI interface is under development but not fully functional, yet. - - - -Parallel Haskell is still relatively new; it is more about “research -fun” than about “speed.” That will change. - - - -Check the GPH Page -for more information on “GPH” (Haskell98 with extensions for -parallel execution), the latest version of “GUM” (the runtime -system to enable parallel executions) and papers on research issues. A -list of publications about GPH and about GUM is also available from Simon's -Web Page. - - - -Some details about Parallel Haskell follow. For more information -about concurrent Haskell, see the module -Control.Concurrent in the library documentation. - - - -Features specific to Parallel Haskell -<indexterm><primary>Parallel Haskell—features</primary></indexterm> - - -The <literal>Parallel</literal> interface (recommended) -<indexterm><primary>Parallel interface</primary></indexterm> - - -GHC provides two functions for controlling parallel execution, through -the Parallel interface: + Software Transactional Memory + + GHC now supports a new way to coordinate the activities of Concurrent + 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: + +Atomic blocks. +Transactional variables. +Operations for composing transactions: +retry, and orElse. +Data invariants. + +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 + (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 ). + The runtime will + schedule the running Haskell threads among the available OS + threads, running as many in parallel as you specified with the + RTS option. + + GHC only supports parallelism on a shared-memory multiprocessor. + Glasgow Parallel HaskellGlasgow Parallel Haskell + (GPH) supports running Parallel Haskell + programs on both clusters of machines, and single multiprocessors. GPH is + developed and distributed + separately from GHC (see The + GPH Page). However, the current version of GPH is based on a much older + version of GHC (4.06). + + + + Annotating pure code for parallelism + + Ordinary single-threaded Haskell programs will not benefit from + enabling SMP parallelism alone: you must expose parallelism to the + compiler. + + 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: -interface Parallel where infixr 0 `par` infixr 1 `seq` par :: a -> b -> b -seq :: a -> b -> b - - - - - -The expression (x `par` y) sparks the evaluation of x -(to weak head normal form) and returns y. Sparks are queued for -execution in FIFO order, but are not executed immediately. At the -next heap allocation, the currently executing thread will yield -control to the scheduler, and the scheduler will start a new thread -(until reaching the active thread limit) for each spark which has not -already been evaluated to WHNF. - +seq :: a -> b -> b - -The expression (x `seq` y) evaluates x to weak head normal -form and then returns y. The seq primitive can be used to -force evaluation of an expression beyond WHNF, or to impose a desired -execution sequence for the evaluation of an expression. - - - -For example, consider the following parallel version of our old -nemesis, nfib: - + The expression (x `par` y) + sparks the evaluation of x + (to weak head normal form) and returns y. Sparks are + queued for execution in FIFO order, but are not executed immediately. If + the runtime detects that there is an idle CPU, then it may convert a + spark into a real thread, and run the new thread on the idle CPU. In + this way the available parallelism is spread amongst the real + CPUs. - + For example, consider the following parallel version of our old + nemesis, nfib: -import Parallel +import Control.Parallel nfib :: Int -> Int nfib n | n <= 1 = 1 | otherwise = par n1 (seq 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 -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 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. - - - - - -Underlying functions and primitives -<indexterm><primary>parallelism primitives</primary></indexterm> -<indexterm><primary>primitives for parallelism</primary></indexterm> - - -The functions par and seq are wired into GHC, and unfold -into uses of the par# and seq# primitives, respectively. If -you'd like to see this with your very own eyes, just run GHC with the - option. (Anything for a good time…) - - - - - -Scheduling policy for concurrent threads -<indexterm><primary>Scheduling—concurrent</primary></indexterm> -<indexterm><primary>Concurrent scheduling</primary></indexterm> - - -Runnable threads are scheduled in round-robin fashion. Context -switches are signalled by the generation of new sparks or by the -expiry of a virtual timer (the timer interval is configurable with the --C<num> RTS option (concurrent, -parallel) RTS option). However, a context switch doesn't -really happen until the current heap block is full. You can't get any -faster context switching than this. - - - -When a context switch occurs, pending sparks which have not already -been reduced to weak head normal form are turned into new threads. -However, there is a limit to the number of active threads (runnable or -blocked) which are allowed at any given time. This limit can be -adjusted with the -t <num> RTS option (concurrent, parallel) -RTS option (the default is 32). Once the -thread limit is reached, any remaining sparks are deferred until some -of the currently active threads are completed. - - - - - -Scheduling policy for parallel threads -<indexterm><primary>Scheduling—parallel</primary></indexterm> -<indexterm><primary>Parallel scheduling</primary></indexterm> - - -In GUM we use an unfair scheduler, which means that a thread continues to -perform graph reduction until it blocks on a closure under evaluation, on a -remote closure or until the thread finishes. - - - - + 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 + 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 + 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. + + 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 + the cost of forking it in parallel will be too large relative to the + amount of parallelism gained. Getting these factors right is tricky in + practice. + + More sophisticated combinators for expressing parallelism are + available from the Control.Parallel.Strategies module. + 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.