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>
7 <para>GHC implements some major extensions to Haskell to support
8 concurrent and parallel programming. Let us first etablish terminology:
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
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.
24 GHC supports both concurrency and parallelism.
27 <sect2 id="concurrent-haskell">
28 <title>Concurrent Haskell</title>
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.
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>.
39 To the programmer, Concurrent Haskell introduces no new language constructs;
40 rather, it appears simply as a library, <ulink
41 url="../libraries/base/Control-Concurrent.html">
42 Control.Concurrent</ulink>. The functions exported by this
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>
55 <sect2><title>Software Transactional Memory</title>
57 <para>GHC now supports a new way to coordinate the activities of Concurrent
58 Haskell threads, called Software Transactional Memory (STM). The
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
64 <para>The main library you need to use STM is <ulink
65 url="../libraries/stm/Control-Concurrent-STM.html">
66 Control.Concurrent.STM</ulink>. The main features supported are these:
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>
74 All these features are described in the papers mentioned earlier.
78 <sect2><title>Parallel Haskell</title>
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="sec-using-smp" />).
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>
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>
103 <title>Annotating pure code for parallelism</title>
105 <para>Ordinary single-threaded Haskell programs will not benefit from
106 enabling SMP parallelism alone: you must expose parallelism to the
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 <ulink
113 url="../libraries/base/Control-Parallel.html"><literal>Control.Parallel</literal></ulink>:</para>
119 par :: a -> b -> b
120 seq :: a -> b -> b</programlisting>
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
131 <para>For example, consider the following parallel version of our old
132 nemesis, <function>nfib</function>:</para>
135 import Control.Parallel
137 nfib :: Int -> Int
138 nfib n | n <= 1 = 1
139 | otherwise = par n1 (seq n2 (n1 + n2 + 1))
140 where n1 = nfib (n-1)
141 n2 = nfib (n-2)</programlisting>
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>seq</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>seq</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
157 <para>When using <literal>par</literal>, the general rule of thumb is that
158 the sparked computation should be required at a later time, but not too
159 soon. Also, the sparked computation should not be too small, otherwise
160 the cost of forking it in parallel will be too large relative to the
161 amount of parallelism gained. Getting these factors right is tricky in
164 <para>More sophisticated combinators for expressing parallelism are
165 available from the <ulink
166 url="../libraries/base/Control-Parallel-Strategies.html"><literal>Control.Parallel.Strategies</literal></ulink> module.
167 This module builds functionality around <literal>par</literal>,
168 expressing more elaborate patterns of parallel computation, such as
169 parallel <literal>map</literal>.</para>
175 ;;; Local Variables: ***
177 ;;; sgml-parent-document: ("users_guide.xml" "book" "chapter" "sect1") ***