ghc/docs/users_guide/parallel.vsgml

   1 % both concurrent and parallel
   2 %************************************************************************
   3 %*                                                                      *
   4 <sect1>Concurrent and Parallel Haskell
   5 <label id="concurrent-and-parallel">
   6 <p>
   7 <nidx>Concurrent Haskell</nidx>
   8 <nidx>Parallel Haskell</nidx>
   9 %*                                                                      *
  10 %************************************************************************
  11
  12 Concurrent and Parallel Haskell are Glasgow extensions to Haskell
  13 which let you structure your program as a group of independent
  14 `threads'.
  15
  16 Concurrent and Parallel Haskell have very different purposes.
  17
  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!
  23
  24 A Concurrent Haskell program implies multiple `threads' running within
  25 a single Unix process on a single processor.
  26
  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/">.
  30
  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.
  35
  36 A Parallel Haskell program implies multiple processes running on
  37 multiple processors, under a PVM (Parallel Virtual Machine) framework.
  38
  39 Parallel Haskell is still relatively new; it is more about ``research
  40 fun'' than about ``speed.'' That will change.
  41
  42 Again, check Simon's Web page for publications about Parallel Haskell
  43 (including ``GUM'', the key bits of the runtime system).
  44
  45 Some details about Concurrent and Parallel Haskell follow.
  46
  47 %************************************************************************
  48 %*                                                                      *
  49 <sect2>Language features specific to Concurrent Haskell
  50 <p>
  51 <nidx>Concurrent Haskell---features</nidx>
  52 %*                                                                      *
  53 %************************************************************************
  54
  55 %************************************************************************
  56 %*                                                                      *
  57 <sect3>The @Concurrent@ interface (recommended)
  58 <p>
  59 <nidx>Concurrent interface</nidx>
  60 %*                                                                      *
  61 %************************************************************************
  62
  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''.
  66
  67 Just put @import Concurrent@ into your modules, and away you go.
  68 To create a ``required thread'':
  69
  70 <tscreen><verb>
  71 forkIO :: IO a -> IO a
  72 </verb></tscreen>
  73
  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>
  78
  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
  84 error.  Interface:
  85 <tscreen><verb>
  86 newIVar     :: IO (IVar a)
  87 readIVar    :: IVar a -> IO a
  88 writeIVar   :: IVar a -> a -> IO ()
  89 </verb></tscreen>
  90
  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
  98 writes. Interface:
  99 <tscreen><verb>
 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
 106 </verb></tscreen>
 107
 108 A <em>channel variable</em> (@CVar@) is a one-element channel, as
 109 described in the paper:
 110
 111 <tscreen><verb>
 112 data CVar a
 113 newCVar :: IO (CVar a)
 114 putCVar :: CVar a -> a -> IO ()
 115 getCVar :: CVar a -> IO a
 116 </verb></tscreen>
 117
 118 A @Channel@ is an unbounded channel:
 119
 120 <tscreen><verb>
 121 data Chan a
 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]
 128 </verb></tscreen>
 129
 130 General and quantity semaphores:
 131
 132 <tscreen><verb>
 133 data QSem
 134 newQSem     :: Int   -> IO QSem
 135 waitQSem    :: QSem  -> IO ()
 136 signalQSem  :: QSem  -> IO ()
 137
 138 data QSemN
 139 newQSemN    :: Int   -> IO QSemN
 140 signalQSemN :: QSemN -> Int -> IO ()
 141 waitQSemN   :: QSemN -> Int -> IO ()
 142 </verb></tscreen>
 143
 144 Merging streams---binary and n-ary:
 145
 146 <tscreen><verb>
 147 mergeIO  :: [a]   -> [a] -> IO [a]
 148 nmergeIO :: [[a]] -> IO [a]
 149 </verb></tscreen>
 150
 151 A <em>Sample variable</em> (@SampleVar@) is slightly different from a
 152 normal @MVar@:
 153 <itemize>
 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.
 157     (same as @takeMVar@)
 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@.)
 162 </itemize>
 163
 164 <tscreen><verb>
 165 type SampleVar a = MVar (Int, MVar a)
 166
 167 emptySampleVar :: SampleVar a -> IO ()
 168 newSampleVar   :: IO (SampleVar a)
 169 readSample     :: SampleVar a -> IO a
 170 writeSample    :: SampleVar a -> a -> IO ()
 171 </verb></tscreen>
 172
 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>
 176 <tscreen><verb>
 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).
 180 </verb></tscreen>
 181
 182 %************************************************************************
 183 %*                                                                      *
 184 <sect2>Features specific to Parallel Haskell
 185 <nidx>Parallel Haskell---features</nidx>
 186 <p>
 187 %*                                                                      *
 188 %************************************************************************
 189
 190 %************************************************************************
 191 %*                                                                      *
 192 \subsubsubsection{The @Parallel@ interface (recommended)}
 193 <nidx>Parallel interface</nidx>
 194 %*                                                                      *
 195 %************************************************************************
 196
 197 GHC provides two functions for controlling parallel execution, through
 198 the @Parallel@ interface:
 199 <tscreen><verb>
 200 interface Parallel where
 201 infixr 0 `par`
 202 infixr 1 `seq`
 203
 204 par :: a -> b -> b
 205 seq :: a -> b -> b
 206 </verb></tscreen>
 207
 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.
 215
 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.
 220
 221 For example, consider the following parallel version of our old
 222 nemesis, @nfib@:
 223
 224 <tscreen><verb>
 225 import Parallel
 226
 227 nfib :: Int -> Int
 228 nfib n | n <= 1 = 1
 229        | otherwise = par n1 (seq n2 (n1 + n2 + 1))
 230                      where n1 = nfib (n-1)
 231                            n2 = nfib (n-2)
 232 </verb></tscreen>
 233
 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.
 244
 245 %************************************************************************
 246 %*                                                                      *
 247 \subsubsubsection{Underlying functions and primitives}
 248 <nidx>parallelism primitives</nidx>
 249 <nidx>primitives for parallelism</nidx>
 250 %*                                                                      *
 251 %************************************************************************
 252
 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...)
 257
 258 You can use @par@ and @seq@ in Concurrent Haskell, though
 259 I'm not sure why you would want to.
 260
 261 %************************************************************************
 262 %*                                                                      *
 263 <sect2>Features common to Concurrent and Parallel Haskell
 264 <p>
 265 %*                                                                      *
 266 %************************************************************************
 267
 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.''
 272
 273 %************************************************************************
 274 %*                                                                      *
 275 \subsubsubsection{Scheduling policy for concurrent/parallel threads}
 276 <nidx>Scheduling---concurrent/parallel</nidx>
 277 <nidx>Concurrent/parallel scheduling</nidx>
 278 %*                                                                      *
 279 %************************************************************************
 280
 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&lt;num&gt; 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
 288 allocation.
 289
 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 &lt;num&gt; 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.