ghc/docs/users_guide/parallel.xml

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