docs/users_guide/parallel.xml

   1 <?xml version="1.0" encoding="iso-8859-1"?>
   2 <sect1 id="lang-parallel">
   3   <title>Concurrent and Parallel Haskell</title>
   4   <indexterm><primary>parallelism</primary>
   5   </indexterm>
   6
   7   <para>GHC implements some major extensions to Haskell to support
   8   concurrent and parallel programming.  Let us first establish terminology:
   9   <itemizedlist>
  10         <listitem><para><emphasis>Parallelism</emphasis> means running
  11           a Haskell program on multiple processors, with the goal of improving
  12           performance.  Ideally, this should be done invisibly, and with no
  13           semantic changes.
  14             </para></listitem>
  15         <listitem><para><emphasis>Concurrency</emphasis> means implementing
  16           a program by using multiple I/O-performing threads.  While a
  17           concurrent Haskell program <emphasis>can</emphasis> run on a
  18           parallel machine, the primary goal of using concurrency is not to gain
  19           performance, but rather because that is the simplest and most
  20           direct way to write the program.  Since the threads perform I/O,
  21           the semantics of the program is necessarily non-deterministic.
  22             </para></listitem>
  23   </itemizedlist>
  24   GHC supports both concurrency and parallelism.
  25   </para>
  26
  27   <sect2 id="concurrent-haskell">
  28     <title>Concurrent Haskell</title>
  29
  30   <para>Concurrent Haskell is the name given to GHC's concurrency extension.
  31   It is enabled by default, so no special flags are required.
  32    The <ulink
  33               url="http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/concurrent-haskell.ps.gz">
  34               Concurrent Haskell paper</ulink> is still an excellent
  35               resource, as is <ulink
  36               url="http://research.microsoft.com/%7Esimonpj/papers/marktoberdorf/">Tackling
  37               the awkward squad</ulink>.
  38   </para><para>
  39   To the programmer, Concurrent Haskell introduces no new language constructs;
  40   rather, it appears simply as a library, <ulink
  41   url="&libraryBaseLocation;/Control-Concurrent.html">
  42               Control.Concurrent</ulink>.  The functions exported by this
  43               library include:
  44   <itemizedlist>
  45 <listitem><para>Forking and killing threads.</para></listitem>
  46 <listitem><para>Sleeping.</para></listitem>
  47 <listitem><para>Synchronised mutable variables, called <literal>MVars</literal></para></listitem>
  48 <listitem><para>Support for bound threads; see the paper <ulink
  49 url="http://research.microsoft.com/%7Esimonpj/Papers/conc-ffi/index.htm">Extending
  50 the FFI with concurrency</ulink>.</para></listitem>
  51 </itemizedlist>
  52 </para>
  53 </sect2>
  54
  55    <sect2><title>Software Transactional Memory</title>
  56
  57     <para>GHC now supports a new way to coordinate the activities of Concurrent
  58     Haskell threads, called Software Transactional Memory (STM).  The
  59     <ulink
  60     url="http://research.microsoft.com/%7Esimonpj/papers/stm/index.htm">STM
  61     papers</ulink> are an excellent introduction to what STM is, and how to use
  62     it.</para>
  63
  64    <para>The main library you need to use is the <ulink
  65   url="http://hackage.haskell.org/package/stm">
  66               stm library</ulink>. The main features supported are these:
  67 <itemizedlist>
  68 <listitem><para>Atomic blocks.</para></listitem>
  69 <listitem><para>Transactional variables.</para></listitem>
  70 <listitem><para>Operations for composing transactions:
  71 <literal>retry</literal>, and <literal>orElse</literal>.</para></listitem>
  72 <listitem><para>Data invariants.</para></listitem>
  73 </itemizedlist>
  74 All these features are described in the papers mentioned earlier.
  75 </para>
  76 </sect2>
  77
  78 <sect2><title>Parallel Haskell</title>
  79
  80   <para>GHC includes support for running Haskell programs in parallel
  81   on symmetric, shared-memory multi-processor
  82       (SMP)<indexterm><primary>SMP</primary></indexterm>.
  83   By default GHC runs your program on one processor; if you
  84      want it to run in parallel you must link your program
  85       with the <option>-threaded</option>, and run it with the RTS
  86       <option>-N</option> option; see  <xref linkend="using-smp" />).
  87       The runtime will
  88       schedule the running Haskell threads among the available OS
  89       threads, running as many in parallel as you specified with the
  90       <option>-N</option> RTS option.</para>
  91
  92   <para>GHC only supports parallelism on a shared-memory multiprocessor.
  93     Glasgow Parallel Haskell<indexterm><primary>Glasgow Parallel Haskell</primary></indexterm>
  94     (GPH) supports running Parallel Haskell
  95     programs on both clusters of machines, and single multiprocessors.  GPH is
  96     developed and distributed
  97     separately from GHC (see <ulink url="http://www.cee.hw.ac.uk/~dsg/gph/">The
  98       GPH Page</ulink>).  However, the current version of GPH is based on a much older
  99     version of GHC (4.06).</para>
 100
 101   </sect2>
 102   <sect2>
 103     <title>Annotating pure code for parallelism</title>
 104
 105   <para>Ordinary single-threaded Haskell programs will not benefit from
 106     enabling SMP parallelism alone: you must expose parallelism to the
 107     compiler.
 108
 109     One way to do so is forking threads using Concurrent Haskell (<xref
 110     linkend="concurrent-haskell"/>), but the simplest mechanism for extracting parallelism from pure code is
 111       to use the <literal>par</literal> combinator, which is closely related to (and often used
 112       with) <literal>seq</literal>.  Both of these are available from the <ulink
 113         url="http://hackage.haskell.org/package/parallel">parallel library</ulink>:</para>
 114
 115 <programlisting>
 116 infixr 0 `par`
 117 infixr 1 `pseq`
 118
 119 par  :: a -&#62; b -&#62; b
 120 pseq :: a -&#62; b -&#62; b</programlisting>
 121
 122     <para>The expression <literal>(x `par` y)</literal>
 123       <emphasis>sparks</emphasis> the evaluation of <literal>x</literal>
 124       (to weak head normal form) and returns <literal>y</literal>.  Sparks are
 125       queued for execution in FIFO order, but are not executed immediately.  If
 126       the runtime detects that there is an idle CPU, then it may convert a
 127       spark into a real thread, and run the new thread on the idle CPU.  In
 128       this way the available parallelism is spread amongst the real
 129       CPUs.</para>
 130
 131     <para>For example, consider the following parallel version of our old
 132       nemesis, <function>nfib</function>:</para>
 133
 134 <programlisting>
 135 import Control.Parallel
 136
 137 nfib :: Int -&#62; Int
 138 nfib n | n &#60;= 1 = 1
 139        | otherwise = par n1 (pseq n2 (n1 + n2 + 1))
 140                      where n1 = nfib (n-1)
 141                            n2 = nfib (n-2)</programlisting>
 142
 143     <para>For values of <varname>n</varname> greater than 1, we use
 144       <function>par</function> to spark a thread to evaluate <literal>nfib (n-1)</literal>,
 145       and then we use <function>pseq</function> to force the
 146       parent thread to evaluate <literal>nfib (n-2)</literal> before going on
 147       to add together these two subexpressions.  In this divide-and-conquer
 148       approach, we only spark a new thread for one branch of the computation
 149       (leaving the parent to evaluate the other branch).  Also, we must use
 150       <function>pseq</function> to ensure that the parent will evaluate
 151       <varname>n2</varname> <emphasis>before</emphasis> <varname>n1</varname>
 152       in the expression <literal>(n1 + n2 + 1)</literal>.  It is not sufficient
 153       to reorder the expression as <literal>(n2 + n1 + 1)</literal>, because
 154       the compiler may not generate code to evaluate the addends from left to
 155       right.</para>
 156
 157     <para>
 158       Note that we use <literal>pseq</literal> rather
 159       than <literal>seq</literal>.  The two are almost equivalent, but
 160       differ in their runtime behaviour in a subtle
 161       way: <literal>seq</literal> can evaluate its arguments in either
 162       order, but <literal>pseq</literal> is required to evaluate its
 163       first argument before its second, which makes it more suitable
 164       for controlling the evaluation order in conjunction
 165       with <literal>par</literal>.
 166     </para>
 167
 168     <para>When using <literal>par</literal>, the general rule of thumb is that
 169       the sparked computation should be required at a later time, but not too
 170       soon.  Also, the sparked computation should not be too small, otherwise
 171       the cost of forking it in parallel will be too large relative to the
 172       amount of parallelism gained.  Getting these factors right is tricky in
 173       practice.</para>
 174
 175     <para>It is possible to glean a little information about how
 176       well <literal>par</literal> is working from the runtime
 177       statistics; see <xref linkend="rts-options-gc" />.</para>
 178
 179     <para>More sophisticated combinators for expressing parallelism are
 180       available from the <literal>Control.Parallel.Strategies</literal>
 181       module in the <ulink
 182         url="http://hackage.haskell.org/package/parallel">parallel package</ulink>.
 183       This module builds functionality around <literal>par</literal>,
 184       expressing more elaborate patterns of parallel computation, such as
 185       parallel <literal>map</literal>.</para>
 186   </sect2>
 187
 188 <sect2><title>Data Parallel Haskell</title>
 189   <para>GHC includes experimental support for Data Parallel Haskell (DPH). This code
 190         is highly unstable and is only provided as a technology preview. More
 191         information can be found on the corresponding <ulink
 192         url="http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell">DPH
 193         wiki page</ulink>.</para>
 194 </sect2>
 195
 196 </sect1>
 197
 198 <!-- Emacs stuff:
 199      ;;; Local Variables: ***
 200      ;;; sgml-parent-document: ("users_guide.xml" "book" "chapter" "sect1") ***
 201      ;;; End: ***
 202  -->