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