1 <?xml version="1.0" encoding="iso-8859-1"?>
2 <sect1 id="lang-parallel">
3 <title>Parallel Haskell</title>
4 <indexterm><primary>parallelism</primary>
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
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>
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>
24 <title>Running Concurrent Haskell programs in parallel</title>
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>
35 <title>Annotating pure code for parallelism</title>
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>
46 par :: a -> b -> b
47 seq :: a -> b -> b</programlisting>
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
58 <para>For example, consider the following parallel version of our old
59 nemesis, <function>nfib</function>:</para>
62 import Control.Parallel
64 nfib :: Int -> Int
65 nfib n | n <= 1 = 1
66 | otherwise = par n1 (seq n2 (n1 + n2 + 1))
68 n2 = nfib (n-2)</programlisting>
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
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
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>
102 ;;; Local Variables: ***
104 ;;; sgml-parent-document: ("users_guide.xml" "book" "chapter" "sect1") ***