X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=docs%2Fusers_guide%2Fparallel.xml;fp=docs%2Fusers_guide%2Fparallel.xml;h=11c254789898d1d2c92eb9fd3f742cb8efe7d4fe;hb=0065d5ab628975892cea1ec7303f968c3338cbe1;hp=0000000000000000000000000000000000000000;hpb=28a464a75e14cece5db40f2765a29348273ff2d2;p=ghc-hetmet.git diff --git a/docs/users_guide/parallel.xml b/docs/users_guide/parallel.xml new file mode 100644 index 0000000..11c2547 --- /dev/null +++ b/docs/users_guide/parallel.xml @@ -0,0 +1,210 @@ + + +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: + + + + + +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. + + + +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: + + + + + +import 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. + + + + + + + + +