X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=docs%2Fusers_guide%2Fparallel.xml;h=1f29d2c0d7207a2f196b51b338745231e8c1b7c2;hb=c76c69c5b62f1ca4fa52d75b0dfbd37b7eddbb09;hp=11c254789898d1d2c92eb9fd3f742cb8efe7d4fe;hpb=0065d5ab628975892cea1ec7303f968c3338cbe1;p=ghc-hetmet.git diff --git a/docs/users_guide/parallel.xml b/docs/users_guide/parallel.xml index 11c2547..1f29d2c 100644 --- a/docs/users_guide/parallel.xml +++ b/docs/users_guide/parallel.xml @@ -1,204 +1,100 @@ - -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 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: - - - + + Parallel Haskell + parallelism + + + There are two implementations of Parallel Haskell: SMP paralellism + SMP + which is built-in to GHC (see ) and + supports running Parallel Haskell programs on a single multiprocessor + machine, and + Glasgow Parallel HaskellGlasgow Parallel Haskell + (GPH) which supports running Parallel Haskell + programs on both clusters of machines or single multiprocessors. GPH is + developed and distributed + separately from GHC (see The + GPH Page). + + Ordinary single-threaded Haskell programs will not benefit from + enabling SMP parallelism alone. You must expose parallelism to the + compiler in one of the following two ways. + + + Running Concurrent Haskell programs in parallel + + The first possibility is to use concurrent threads to structure your + program, and make sure + that you spread computation amongst the threads. 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. + + + + Annotating pure code for parallelism + + 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 - - - +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. - + 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. - -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: - - - + 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. +