1 % both concurrent and parallel
2 %************************************************************************
4 <sect1>Concurrent and Parallel Haskell
5 <label id="concurrent-and-parallel">
7 <nidx>Concurrent Haskell</nidx>
8 <nidx>Parallel Haskell</nidx>
10 %************************************************************************
12 Concurrent and Parallel Haskell are Glasgow extensions to Haskell
13 which let you structure your program as a group of independent
16 Concurrent and Parallel Haskell have very different purposes.
18 Concurrent Haskell is for applications which have an inherent
19 structure of interacting, concurrent tasks (i.e. `threads'). Threads
20 in such programs may be <em>required</em>. For example, if a concurrent
21 thread has been spawned to handle a mouse click, it isn't
22 optional---the user wants something done!
24 A Concurrent Haskell program implies multiple `threads' running within
25 a single Unix process on a single processor.
27 You will find at least one paper about Concurrent Haskell hanging off
28 of <url name="Simon Peyton Jones's Web page"
29 url="http://www.dcs.gla.ac.uk/~simonpj/">.
31 Parallel Haskell is about <em>speed</em>---spawning threads onto multiple
32 processors so that your program will run faster. The `threads'
33 are always <em>advisory</em>---if the runtime system thinks it can
34 get the job done more quickly by sequential execution, then fine.
36 A Parallel Haskell program implies multiple processes running on
37 multiple processors, under a PVM (Parallel Virtual Machine) framework.
39 Parallel Haskell is still relatively new; it is more about ``research
40 fun'' than about ``speed.'' That will change.
42 Again, check Simon's Web page for publications about Parallel Haskell
43 (including ``GUM'', the key bits of the runtime system).
45 Some details about Concurrent and Parallel Haskell follow.
47 %************************************************************************
49 <sect2>Language features specific to Concurrent Haskell
51 <nidx>Concurrent Haskell---features</nidx>
53 %************************************************************************
55 %************************************************************************
57 <sect3>The @Concurrent@ interface (recommended)
59 <nidx>Concurrent interface</nidx>
61 %************************************************************************
63 GHC provides a @Concurrent@ module, a common interface to a
64 collection of useful concurrency abstractions, including those
65 mentioned in the ``concurrent paper''.
67 Just put @import Concurrent@ into your modules, and away you go.
68 To create a ``required thread'':
71 forkIO :: IO a -> IO a
74 The @Concurrent@ interface also provides access to ``I-Vars''
75 and ``M-Vars'', which are two flavours of <em>synchronising variables</em>.
76 <nidx>synchronising variables (Glasgow extension)</nidx>
77 <nidx>concurrency -- synchronising variables</nidx>
79 @IVars@<nidx>IVars (Glasgow extension)</nidx> are write-once
80 variables. They start out empty, and any threads that attempt to read
81 them will block until they are filled. Once they are written, any
82 blocked threads are freed, and additional reads are permitted.
83 Attempting to write a value to a full @IVar@ results in a runtime
86 newIVar :: IO (IVar a)
87 readIVar :: IVar a -> IO a
88 writeIVar :: IVar a -> a -> IO ()
91 @MVars@<nidx>MVars (Glasgow extension)</nidx> are rendezvous points,
92 mostly for concurrent threads. They begin empty, and any attempt to
93 read an empty @MVar@ blocks. When an @MVar@ is written, a
94 single blocked thread may be freed. Reading an @MVar@ toggles its
95 state from full back to empty. Therefore, any value written to an
96 @MVar@ may only be read once. Multiple reads and writes are
97 allowed, but there must be at least one read between any two
100 newEmptyMVar :: IO (MVar a)
101 newMVar :: a -> IO (MVar a)
102 takeMVar :: MVar a -> IO a
103 putMVar :: MVar a -> a -> IO ()
104 readMVar :: MVar a -> IO a
105 swapMVar :: MVar a -> a -> IO a
108 A <em>channel variable</em> (@CVar@) is a one-element channel, as
109 described in the paper:
113 newCVar :: IO (CVar a)
114 putCVar :: CVar a -> a -> IO ()
115 getCVar :: CVar a -> IO a
118 A @Channel@ is an unbounded channel:
122 newChan :: IO (Chan a)
123 putChan :: Chan a -> a -> IO ()
124 getChan :: Chan a -> IO a
125 dupChan :: Chan a -> IO (Chan a)
126 unGetChan :: Chan a -> a -> IO ()
127 getChanContents :: Chan a -> IO [a]
130 General and quantity semaphores:
134 newQSem :: Int -> IO QSem
135 waitQSem :: QSem -> IO ()
136 signalQSem :: QSem -> IO ()
139 newQSemN :: Int -> IO QSemN
140 signalQSemN :: QSemN -> Int -> IO ()
141 waitQSemN :: QSemN -> Int -> IO ()
144 Merging streams---binary and n-ary:
147 mergeIO :: [a] -> [a] -> IO [a]
148 nmergeIO :: [[a]] -> IO [a]
151 A <em>Sample variable</em> (@SampleVar@) is slightly different from a
154 <item> Reading an empty @SampleVar@ causes the reader to block
155 (same as @takeMVar@ on empty @MVar@).
156 <item> Reading a filled @SampleVar@ empties it and returns value.
158 <item> Writing to an empty @SampleVar@ fills it with a value, and
159 potentially, wakes up a blocked reader (same as for @putMVar@ on empty @MVar@).
160 <item> Writing to a filled @SampleVar@ overwrites the current value.
161 (different from @putMVar@ on full @MVar@.)
165 type SampleVar a = MVar (Int, MVar a)
167 emptySampleVar :: SampleVar a -> IO ()
168 newSampleVar :: IO (SampleVar a)
169 readSample :: SampleVar a -> IO a
170 writeSample :: SampleVar a -> a -> IO ()
173 Finally, there are operations to delay a concurrent thread, and to
174 make one wait:<nidx>delay a concurrent thread</nidx>
175 <nidx>wait for a file descriptor</nidx>
177 threadDelay :: Int -> IO () -- delay rescheduling for N microseconds
178 threadWaitRead :: Int -> IO () -- wait for input on specified file descriptor
179 threadWaitWrite :: Int -> IO () -- (read and write, respectively).
182 %************************************************************************
184 <sect2>Features specific to Parallel Haskell
185 <nidx>Parallel Haskell---features</nidx>
188 %************************************************************************
190 %************************************************************************
192 \subsubsubsection{The @Parallel@ interface (recommended)}
193 <nidx>Parallel interface</nidx>
195 %************************************************************************
197 GHC provides two functions for controlling parallel execution, through
198 the @Parallel@ interface:
200 interface Parallel where
208 The expression @(x `par` y)@ <em>sparks</em> the evaluation of @x@
209 (to weak head normal form) and returns @y@. Sparks are queued for
210 execution in FIFO order, but are not executed immediately. At the
211 next heap allocation, the currently executing thread will yield
212 control to the scheduler, and the scheduler will start a new thread
213 (until reaching the active thread limit) for each spark which has not
214 already been evaluated to WHNF.
216 The expression @(x `seq` y)@ evaluates @x@ to weak head normal
217 form and then returns @y@. The @seq@ primitive can be used to
218 force evaluation of an expression beyond WHNF, or to impose a desired
219 execution sequence for the evaluation of an expression.
221 For example, consider the following parallel version of our old
229 | otherwise = par n1 (seq n2 (n1 + n2 + 1))
230 where n1 = nfib (n-1)
234 For values of @n@ greater than 1, we use @par@ to spark a thread
235 to evaluate @nfib (n-1)@, and then we use @seq@ to force the
236 parent thread to evaluate @nfib (n-2)@ before going on to add
237 together these two subexpressions. In this divide-and-conquer
238 approach, we only spark a new thread for one branch of the computation
239 (leaving the parent to evaluate the other branch). Also, we must use
240 @seq@ to ensure that the parent will evaluate @n2@ <em>before</em>
241 @n1@ in the expression @(n1 + n2 + 1)@. It is not sufficient to
242 reorder the expression as @(n2 + n1 + 1)@, because the compiler may
243 not generate code to evaluate the addends from left to right.
245 %************************************************************************
247 \subsubsubsection{Underlying functions and primitives}
248 <nidx>parallelism primitives</nidx>
249 <nidx>primitives for parallelism</nidx>
251 %************************************************************************
253 The functions @par@ and @seq@ are wired into GHC, and unfold
254 into uses of the @par#@ and @seq#@ primitives, respectively. If
255 you'd like to see this with your very own eyes, just run GHC with the
256 @-ddump-simpl@ option. (Anything for a good time...)
258 You can use @par@ and @seq@ in Concurrent Haskell, though
259 I'm not sure why you would want to.
261 %************************************************************************
263 <sect2>Features common to Concurrent and Parallel Haskell
266 %************************************************************************
268 Actually, you can use the @`par`@ and @`seq`@ combinators
269 (really for Parallel Haskell) in Concurrent Haskell as well.
270 But doing things like ``@par@ to @forkIO@ many required threads''
271 counts as ``jumping out the 9th-floor window, just to see what happens.''
273 %************************************************************************
275 \subsubsubsection{Scheduling policy for concurrent/parallel threads}
276 <nidx>Scheduling---concurrent/parallel</nidx>
277 <nidx>Concurrent/parallel scheduling</nidx>
279 %************************************************************************
281 Runnable threads are scheduled in round-robin fashion. Context
282 switches are signalled by the generation of new sparks or by the
283 expiry of a virtual timer (the timer interval is configurable with the
284 @-C[<num>]@<nidx>-C<num> RTS option (concurrent, parallel)</nidx> RTS option).
285 However, a context switch doesn't really happen until the next heap
286 allocation. If you want extremely short time slices, the @-C@ RTS
287 option can be used to force a context switch at each and every heap
290 When a context switch occurs, pending sparks which have not already
291 been reduced to weak head normal form are turned into new threads.
292 However, there is a limit to the number of active threads (runnable or
293 blocked) which are allowed at any given time. This limit can be
294 adjusted with the @-t<num>@<nidx>-t <num> RTS option (concurrent, parallel)</nidx>
295 RTS option (the default is 32). Once the
296 thread limit is reached, any remaining sparks are deferred until some
297 of the currently active threads are completed.