ghc/docs/users_guide/parallel.vsgml

   1 % both concurrent and parallel
   2 %************************************************************************
   3 %*                                                                      *
   4 <sect1>Concurrent and Parallel Haskell
   5 <label id="concurrent-and-parallel">
   6 <p>
   7 <nidx>Concurrent Haskell</nidx>
   8 <nidx>Parallel Haskell</nidx>
   9 %*                                                                      *
  10 %************************************************************************
  11
  12 Concurrent and Parallel Haskell are Glasgow extensions to Haskell
  13 which let you structure your program as a group of independent
  14 `threads'.
  15
  16 Concurrent and Parallel Haskell have very different purposes.
  17
  18 Concurrent Haskell is for applications which have an inherent
  19 structure of interacting, concurrent tasks (i.e. `threads').  Threads
  20 in such programs may be <em>required</em>.  For example, if a concurrent
  21 thread has been spawned to handle a mouse click, it isn't
  22 optional---the user wants something done!
  23
  24 A Concurrent Haskell program implies multiple `threads' running within
  25 a single Unix process on a single processor.
  26
  27 You will find at least one paper about Concurrent Haskell hanging off
  28 of <url name="Simon Peyton Jones's Web page"
  29 url="http://www.dcs.gla.ac.uk/~simonpj/">.
  30
  31 Parallel Haskell is about <em>speed</em>---spawning threads onto multiple
  32 processors so that your program will run faster.  The `threads'
  33 are always <em>advisory</em>---if the runtime system thinks it can
  34 get the job done more quickly by sequential execution, then fine.
  35
  36 A Parallel Haskell program implies multiple processes running on
  37 multiple processors, under a PVM (Parallel Virtual Machine) framework.
  38
  39 Parallel Haskell is still relatively new; it is more about ``research
  40 fun'' than about ``speed.'' That will change.
  41
  42 Again, check Simon's Web page for publications about Parallel Haskell
  43 (including ``GUM'', the key bits of the runtime system).
  44
  45 Some details about Parallel Haskell follow.  For more information
  46 about concurrent Haskell, see the Concurrent section in the <htmlurl
  47 name="GHC/Hugs Extension Libraries" url="libs.html"> documentation.
  48
  49 %************************************************************************
  50 %*                                                                      *
  51 <sect2>Features specific to Parallel Haskell
  52 <nidx>Parallel Haskell---features</nidx>
  53 <p>
  54 %*                                                                      *
  55 %************************************************************************
  56
  57 %************************************************************************
  58 %*                                                                      *
  59 <sect3>The @Parallel@ interface (recommended)
  60 <nidx>Parallel interface</nidx>
  61 <p>
  62 %*                                                                      *
  63 %************************************************************************
  64
  65 GHC provides two functions for controlling parallel execution, through
  66 the @Parallel@ interface:
  67
  68 <tscreen><verb>
  69 interface Parallel where
  70 infixr 0 `par`
  71 infixr 1 `seq`
  72
  73 par :: a -> b -> b
  74 seq :: a -> b -> b
  75 </verb></tscreen>
  76
  77 The expression @(x `par` y)@ <em>sparks</em> the evaluation of @x@
  78 (to weak head normal form) and returns @y@.  Sparks are queued for
  79 execution in FIFO order, but are not executed immediately.  At the
  80 next heap allocation, the currently executing thread will yield
  81 control to the scheduler, and the scheduler will start a new thread
  82 (until reaching the active thread limit) for each spark which has not
  83 already been evaluated to WHNF.
  84
  85 The expression @(x `seq` y)@ evaluates @x@ to weak head normal
  86 form and then returns @y@.  The @seq@ primitive can be used to
  87 force evaluation of an expression beyond WHNF, or to impose a desired
  88 execution sequence for the evaluation of an expression.
  89
  90 For example, consider the following parallel version of our old
  91 nemesis, @nfib@:
  92
  93 <tscreen><verb>
  94 import Parallel
  95
  96 nfib :: Int -> Int
  97 nfib n | n <= 1 = 1
  98        | otherwise = par n1 (seq n2 (n1 + n2 + 1))
  99                      where n1 = nfib (n-1)
 100                            n2 = nfib (n-2)
 101 </verb></tscreen>
 102
 103 For values of @n@ greater than 1, we use @par@ to spark a thread
 104 to evaluate @nfib (n-1)@, and then we use @seq@ to force the
 105 parent thread to evaluate @nfib (n-2)@ before going on to add
 106 together these two subexpressions.  In this divide-and-conquer
 107 approach, we only spark a new thread for one branch of the computation
 108 (leaving the parent to evaluate the other branch).  Also, we must use
 109 @seq@ to ensure that the parent will evaluate @n2@ <em>before</em>
 110 @n1@ in the expression @(n1 + n2 + 1)@.  It is not sufficient to
 111 reorder the expression as @(n2 + n1 + 1)@, because the compiler may
 112 not generate code to evaluate the addends from left to right.
 113
 114 %************************************************************************
 115 %*                                                                      *
 116 <sect3>Underlying functions and primitives
 117 <nidx>parallelism primitives</nidx>
 118 <nidx>primitives for parallelism</nidx>
 119 <p>
 120 %*                                                                      *
 121 %************************************************************************
 122
 123 The functions @par@ and @seq@ are wired into GHC, and unfold
 124 into uses of the @par#@ and @seq#@ primitives, respectively.  If
 125 you'd like to see this with your very own eyes, just run GHC with the
 126 @-ddump-simpl@ option.  (Anything for a good time...)
 127
 128 %************************************************************************
 129 %*                                                                      *
 130 <sect3>Scheduling policy for concurrent/parallel threads
 131 <nidx>Scheduling---concurrent/parallel</nidx>
 132 <nidx>Concurrent/parallel scheduling</nidx>
 133 <p>
 134 %*                                                                      *
 135 %************************************************************************
 136
 137 Runnable threads are scheduled in round-robin fashion.  Context
 138 switches are signalled by the generation of new sparks or by the
 139 expiry of a virtual timer (the timer interval is configurable with the
 140 @-C[<num>]@<nidx>-C&lt;num&gt; RTS option (concurrent,
 141 parallel)</nidx> RTS option).  However, a context switch doesn't
 142 really happen until the current heap block is full.  You can't get any
 143 faster context switching than this.
 144
 145 When a context switch occurs, pending sparks which have not already
 146 been reduced to weak head normal form are turned into new threads.
 147 However, there is a limit to the number of active threads (runnable or
 148 blocked) which are allowed at any given time.  This limit can be
 149 adjusted with the @-t<num>@<nidx>-t &lt;num&gt; RTS option (concurrent, parallel)</nidx>
 150 RTS option (the default is 32).  Once the
 151 thread limit is reached, any remaining sparks are deferred until some
 152 of the currently active threads are completed.