docs/users_guide/parallel.xml

   1 <?xml version="1.0" encoding="iso-8859-1"?>
   2 <sect1 id="lang-parallel">
   3   <title>Parallel Haskell</title>
   4   <indexterm><primary>parallelism</primary>
   5   </indexterm>
   6
   7   <para>There are two implementations of Parallel Haskell: SMP paralellism
   8     <indexterm><primary>SMP</primary></indexterm>
   9     which is built-in to GHC (see <xref linkend="sec-using-smp" />) and
  10     supports running Parallel Haskell programs on a single multiprocessor
  11     machine, and
  12     Glasgow Parallel Haskell<indexterm><primary>Glasgow Parallel Haskell</primary></indexterm>
  13     (GPH) which supports running Parallel Haskell
  14     programs on both clusters of machines or single multiprocessors.  GPH is
  15     developed and distributed
  16     separately from GHC (see <ulink url="http://www.cee.hw.ac.uk/~dsg/gph/">The
  17       GPH Page</ulink>).</para>
  18
  19   <para>Ordinary single-threaded Haskell programs will not benefit from
  20     enabling SMP parallelism alone.  You must expose parallelism to the
  21     compiler in one of the following two ways.</para>
  22
  23   <sect2>
  24     <title>Running Concurrent Haskell programs in parallel</title>
  25
  26     <para>The first possibility is to use concurrent threads to structure your
  27       program, and make sure
  28       that you spread computation amongst the threads.  The runtime will
  29       schedule the running Haskell threads among the available OS
  30       threads, running as many in parallel as you specified with the
  31       <option>-N</option> RTS option.</para>
  32   </sect2>
  33
  34   <sect2>
  35     <title>Annotating pure code for parallelism</title>
  36
  37     <para>The simplest mechanism for extracting parallelism from pure code is
  38       to use the <literal>par</literal> combinator, which is closely related to (and often used
  39       with) <literal>seq</literal>.  Both of these are available from <ulink
  40         url="../libraries/base/Control-Parallel.html"><literal>Control.Parallel</literal></ulink>:</para>
  41
  42 <programlisting>
  43 infixr 0 `par`
  44 infixr 1 `seq`
  45
  46 par :: a -&#62; b -&#62; b
  47 seq :: a -&#62; b -&#62; b</programlisting>
  48
  49     <para>The expression <literal>(x `par` y)</literal>
  50       <emphasis>sparks</emphasis> the evaluation of <literal>x</literal>
  51       (to weak head normal form) and returns <literal>y</literal>.  Sparks are
  52       queued for execution in FIFO order, but are not executed immediately.  If
  53       the runtime detects that there is an idle CPU, then it may convert a
  54       spark into a real thread, and run the new thread on the idle CPU.  In
  55       this way the available parallelism is spread amongst the real
  56       CPUs.</para>
  57
  58     <para>For example, consider the following parallel version of our old
  59       nemesis, <function>nfib</function>:</para>
  60
  61 <programlisting>
  62 import Control.Parallel
  63
  64 nfib :: Int -&#62; Int
  65 nfib n | n &#60;= 1 = 1
  66        | otherwise = par n1 (seq n2 (n1 + n2 + 1))
  67                      where n1 = nfib (n-1)
  68                            n2 = nfib (n-2)</programlisting>
  69
  70     <para>For values of <varname>n</varname> greater than 1, we use
  71       <function>par</function> to spark a thread to evaluate <literal>nfib (n-1)</literal>,
  72       and then we use <function>seq</function> to force the
  73       parent thread to evaluate <literal>nfib (n-2)</literal> before going on
  74       to add together these two subexpressions.  In this divide-and-conquer
  75       approach, we only spark a new thread for one branch of the computation
  76       (leaving the parent to evaluate the other branch).  Also, we must use
  77       <function>seq</function> to ensure that the parent will evaluate
  78       <varname>n2</varname> <emphasis>before</emphasis> <varname>n1</varname>
  79       in the expression <literal>(n1 + n2 + 1)</literal>.  It is not sufficient
  80       to reorder the expression as <literal>(n2 + n1 + 1)</literal>, because
  81       the compiler may not generate code to evaluate the addends from left to
  82       right.</para>
  83
  84     <para>When using <literal>par</literal>, the general rule of thumb is that
  85       the sparked computation should be required at a later time, but not too
  86       soon.  Also, the sparked computation should not be too small, otherwise
  87       the cost of forking it in parallel will be too large relative to the
  88       amount of parallelism gained.  Getting these factors right is tricky in
  89       practice.</para>
  90
  91     <para>More sophisticated combinators for expressing parallelism are
  92       available from the <ulink
  93         url="../libraries/base/Control-Parallel-Strategies.html"><literal>Control.Parallel.Strategies</literal></ulink> module.
  94       This module builds functionality around <literal>par</literal>,
  95       expressing more elaborate patterns of parallel computation, such as
  96       parallel <literal>map</literal>.</para>
  97   </sect2>
  98
  99 </sect1>
 100
 101 <!-- Emacs stuff:
 102      ;;; Local Variables: ***
 103      ;;; mode: xml ***
 104      ;;; sgml-parent-document: ("users_guide.xml" "book" "chapter" "sect1") ***
 105      ;;; End: ***
 106  -->