<?xml version="1.0" encoding="iso-8859-1"?>
<sect1 id="lang-parallel">
- <title>Parallel Haskell</title>
+ <title>Concurrent and Parallel Haskell</title>
<indexterm><primary>parallelism</primary>
</indexterm>
- <para>There are two implementations of Parallel Haskell: SMP paralellism
- <indexterm><primary>SMP</primary></indexterm>
- which is built-in to GHC (see <xref linkend="sec-using-smp" />) and
- supports running Parallel Haskell programs on a single multiprocessor
- machine, and
- Glasgow Parallel Haskell<indexterm><primary>Glasgow Parallel Haskell</primary></indexterm>
- (GPH) which supports running Parallel Haskell
- programs on both clusters of machines or single multiprocessors. GPH is
- developed and distributed
- separately from GHC (see <ulink url="http://www.cee.hw.ac.uk/~dsg/gph/">The
- GPH Page</ulink>).</para>
-
- <para>Ordinary single-threaded Haskell programs will not benefit from
- enabling SMP parallelism alone. You must expose parallelism to the
- compiler in one of the following two ways.</para>
-
- <sect2>
- <title>Running Concurrent Haskell programs in parallel</title>
+ <para>GHC implements some major extensions to Haskell to support
+ concurrent and parallel programming. Let us first establish terminology:
+ <itemizedlist>
+ <listitem><para><emphasis>Parallelism</emphasis> means running
+ a Haskell program on multiple processors, with the goal of improving
+ performance. Ideally, this should be done invisibly, and with no
+ semantic changes.
+ </para></listitem>
+ <listitem><para><emphasis>Concurrency</emphasis> means implementing
+ a program by using multiple I/O-performing threads. While a
+ concurrent Haskell program <emphasis>can</emphasis> run on a
+ parallel machine, the primary goal of using concurrency is not to gain
+ performance, but rather because that is the simplest and most
+ direct way to write the program. Since the threads perform I/O,
+ the semantics of the program is necessarily non-deterministic.
+ </para></listitem>
+ </itemizedlist>
+ GHC supports both concurrency and parallelism.
+ </para>
+
+ <sect2 id="concurrent-haskell">
+ <title>Concurrent Haskell</title>
+
+ <para>Concurrent Haskell is the name given to GHC's concurrency extension.
+ It is enabled by default, so no special flags are required.
+ The <ulink
+ url="http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/concurrent-haskell.ps.gz">
+ Concurrent Haskell paper</ulink> is still an excellent
+ resource, as is <ulink
+ url="http://research.microsoft.com/%7Esimonpj/papers/marktoberdorf/">Tackling
+ the awkward squad</ulink>.
+ </para><para>
+ To the programmer, Concurrent Haskell introduces no new language constructs;
+ rather, it appears simply as a library, <ulink
+ url="&libraryBaseLocation;/Control-Concurrent.html">
+ Control.Concurrent</ulink>. The functions exported by this
+ library include:
+ <itemizedlist>
+<listitem><para>Forking and killing threads.</para></listitem>
+<listitem><para>Sleeping.</para></listitem>
+<listitem><para>Synchronised mutable variables, called <literal>MVars</literal></para></listitem>
+<listitem><para>Support for bound threads; see the paper <ulink
+url="http://research.microsoft.com/%7Esimonpj/Papers/conc-ffi/index.htm">Extending
+the FFI with concurrency</ulink>.</para></listitem>
+</itemizedlist>
+</para>
+</sect2>
+
+ <sect2><title>Software Transactional Memory</title>
+
+ <para>GHC now supports a new way to coordinate the activities of Concurrent
+ Haskell threads, called Software Transactional Memory (STM). The
+ <ulink
+ url="http://research.microsoft.com/%7Esimonpj/papers/stm/index.htm">STM
+ papers</ulink> are an excellent introduction to what STM is, and how to use
+ it.</para>
+
+ <para>The main library you need to use is the <ulink
+ url="http://hackage.haskell.org/package/stm">
+ stm library</ulink>. The main features supported are these:
+<itemizedlist>
+<listitem><para>Atomic blocks.</para></listitem>
+<listitem><para>Transactional variables.</para></listitem>
+<listitem><para>Operations for composing transactions:
+<literal>retry</literal>, and <literal>orElse</literal>.</para></listitem>
+<listitem><para>Data invariants.</para></listitem>
+</itemizedlist>
+All these features are described in the papers mentioned earlier.
+</para>
+</sect2>
+
+<sect2><title>Parallel Haskell</title>
- <para>The first possibility is to use concurrent threads to structure your
- program, and make sure
- that you spread computation amongst the threads. The runtime will
+ <para>GHC includes support for running Haskell programs in parallel
+ on symmetric, shared-memory multi-processor
+ (SMP)<indexterm><primary>SMP</primary></indexterm>.
+ By default GHC runs your program on one processor; if you
+ want it to run in parallel you must link your program
+ with the <option>-threaded</option>, and run it with the RTS
+ <option>-N</option> option; see <xref linkend="using-smp" />).
+ The runtime will
schedule the running Haskell threads among the available OS
threads, running as many in parallel as you specified with the
<option>-N</option> RTS option.</para>
- </sect2>
+ <para>GHC only supports parallelism on a shared-memory multiprocessor.
+ Glasgow Parallel Haskell<indexterm><primary>Glasgow Parallel Haskell</primary></indexterm>
+ (GPH) supports running Parallel Haskell
+ programs on both clusters of machines, and single multiprocessors. GPH is
+ developed and distributed
+ separately from GHC (see <ulink url="http://www.cee.hw.ac.uk/~dsg/gph/">The
+ GPH Page</ulink>). However, the current version of GPH is based on a much older
+ version of GHC (4.06).</para>
+
+ </sect2>
<sect2>
<title>Annotating pure code for parallelism</title>
- <para>The simplest mechanism for extracting parallelism from pure code is
+ <para>Ordinary single-threaded Haskell programs will not benefit from
+ enabling SMP parallelism alone: you must expose parallelism to the
+ compiler.
+
+ One way to do so is forking threads using Concurrent Haskell (<xref
+ linkend="concurrent-haskell"/>), but the simplest mechanism for extracting parallelism from pure code is
to use the <literal>par</literal> combinator, which is closely related to (and often used
- with) <literal>seq</literal>. Both of these are available from <ulink
- url="../libraries/base/Control-Parallel.html"><literal>Control.Parallel</literal></ulink>:</para>
+ with) <literal>seq</literal>. Both of these are available from the <ulink
+ url="http://hackage.haskell.org/package/parallel">parallel library</ulink>:</para>
<programlisting>
infixr 0 `par`
-infixr 1 `seq`
+infixr 1 `pseq`
-par :: a -> b -> b
-seq :: a -> b -> b</programlisting>
+par :: a -> b -> b
+pseq :: a -> b -> b</programlisting>
<para>The expression <literal>(x `par` y)</literal>
<emphasis>sparks</emphasis> the evaluation of <literal>x</literal>
nfib :: Int -> Int
nfib n | n <= 1 = 1
- | otherwise = par n1 (seq n2 (n1 + n2 + 1))
+ | otherwise = par n1 (pseq n2 (n1 + n2 + 1))
where n1 = nfib (n-1)
n2 = nfib (n-2)</programlisting>
<para>For values of <varname>n</varname> greater than 1, we use
<function>par</function> to spark a thread to evaluate <literal>nfib (n-1)</literal>,
- and then we use <function>seq</function> to force the
+ and then we use <function>pseq</function> to force the
parent thread to evaluate <literal>nfib (n-2)</literal> before going on
to add together these two subexpressions. In this divide-and-conquer
approach, we only spark a new thread for one branch of the computation
(leaving the parent to evaluate the other branch). Also, we must use
- <function>seq</function> to ensure that the parent will evaluate
+ <function>pseq</function> to ensure that the parent will evaluate
<varname>n2</varname> <emphasis>before</emphasis> <varname>n1</varname>
in the expression <literal>(n1 + n2 + 1)</literal>. It is not sufficient
to reorder the expression as <literal>(n2 + n1 + 1)</literal>, because
the compiler may not generate code to evaluate the addends from left to
right.</para>
+ <para>
+ Note that we use <literal>pseq</literal> rather
+ than <literal>seq</literal>. The two are almost equivalent, but
+ differ in their runtime behaviour in a subtle
+ way: <literal>seq</literal> can evaluate its arguments in either
+ order, but <literal>pseq</literal> is required to evaluate its
+ first argument before its second, which makes it more suitable
+ for controlling the evaluation order in conjunction
+ with <literal>par</literal>.
+ </para>
+
<para>When using <literal>par</literal>, the general rule of thumb is that
the sparked computation should be required at a later time, but not too
soon. Also, the sparked computation should not be too small, otherwise
amount of parallelism gained. Getting these factors right is tricky in
practice.</para>
+ <para>It is possible to glean a little information about how
+ well <literal>par</literal> is working from the runtime
+ statistics; see <xref linkend="rts-options-gc" />.</para>
+
<para>More sophisticated combinators for expressing parallelism are
- available from the <ulink
- url="../libraries/base/Control-Parallel-Strategies.html"><literal>Control.Parallel.Strategies</literal></ulink> module.
+ available from the <literal>Control.Parallel.Strategies</literal>
+ module in the <ulink
+ url="http://hackage.haskell.org/package/parallel">parallel package</ulink>.
This module builds functionality around <literal>par</literal>,
expressing more elaborate patterns of parallel computation, such as
parallel <literal>map</literal>.</para>
</sect2>
+<sect2><title>Data Parallel Haskell</title>
+ <para>GHC includes experimental support for Data Parallel Haskell (DPH). This code
+ is highly unstable and is only provided as a technology preview. More
+ information can be found on the corresponding <ulink
+ url="http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell">DPH
+ wiki page</ulink>.</para>
+</sect2>
+
</sect1>
<!-- Emacs stuff:
;;; Local Variables: ***
- ;;; mode: xml ***
;;; sgml-parent-document: ("users_guide.xml" "book" "chapter" "sect1") ***
;;; End: ***
-->