ghc/docs/users_guide/parallel.sgml

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