ghc/docs/users_guide/parallel.sgml

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