Concurrency and Parallelism

concurrent program: unrelated tasks at the same time
- game server: chat, database, inputs, feedback, physics
- doesn't require multiple cores
parallel program: single problem split to multiple cores
another distinction: interaction with outside world
blurred boundary
- traditional programming languages use the same set of primitives

Haskell threads

cheap: sparks, green threads
let OS & runtime do the scheduling

Semi-explicit parallelism

f x y = (x + y) + g x + h y

referential transparency
each subexpression could be evaluated in parallel
too many of them
give control to user :)

Sparks (1)

Prelude Control.Parallel> :t par
par :: a -> b -> b
a `par` b

it could be a good idea to evaluate a in parallel with b.
create spark to run in parallel, if possible (available Haskell thread)
spark for a --> thread for a
return b

Sparks (2)

Prelude Control.Parallel> :t pseq 
pseq :: a -> b -> b
a `pseq` b

evaluate a in current thread then return b
ensures work is done in the right place

f `par` e `pseq` f + e

$ time ./B +RTS -N2
100000020000000
0.84s user 0.02s system 190% cpu 0.478 total

Compiling and running

two runtime supports
- non-threaded: all threads on the same OS thread
- threaded: multiple OS threads, overhead, multicore

ghc --make -threaded -rtsopts file.hs

if using threaded runtime we can alter number of cores to be used
+RTS ... -RTS: list of runtime arguments

./exec arg +RTS -N2 -RTS arg

`seq` and `pseq`

Prelude> :t seq
seq :: a -> b -> b

seq is strict in both arguments
pseq is strict only in the first one

a `seq` b
b `seq` a `seq` b

in case of seq compiler decides what to evaluate first (opportunity)
in case of pseq user decides what to be evaluated first (promise)

How much to evaluate? (1)

import Debug.Trace

martor x = trace ("called for " ++ show x) x

list n = trace "generating list" $ map martor [1..n]

main = do
  print $ trace "computing" $ list 2
  let l = trace "new list" $ list 2
  print $ trace "once" l
  print $ trace "twice" l
  let l = trace "with seq" $ let l = list 2 in l `seq` l
  print $ trace "seq" l

what output?

How much to evaluate? (2)

Main> main
computing
generating list
[called for 1
1,called for 2
2]
once
new list
generating list
[called for 1
1,called for 2
2]
twice
[1,2]
seq
with seq
generating list
[called for 1
1,called for 2
2]

NF, HNF, WHNF

normal form: completely evaluated
head normal form: evaluated until outermost constructor (head)
weak head normal form: evaluate until first function abstraction

42
(2, "hello")
\x -> (x + 1)
1 + 2
(1 + 1, 2 + 2)
\x -> 2 + 2
'h' : ("e" ++ "llo")
(\x -> x + 1) 2
"he" ++ "llo"

seq ad pseq evaluate to WHNF

Strictness (eager conversion to NF)

($!) :: (a -> b) -> a -> b

Remember

f $ x = f x

f $! g x

is a strict version of

f $ g x

More stricntess

f x !y !z t = ...

data Complex a = !a :+ !a

stricness evaluator inside compiler

Sequential sort

import System.Environment

mySort (x:xs) = lesser ++ x:greater
  where
    lesser = mySort [y | y <- xs, y < x]
    greater = mySort [y | y <- xs, y >= x]
mySort _ = []

main = do
  args <- getArgs
  let n:_ = map read args
  print $ length $ mySort [n, n-1 .. 0]

$ time ./4 5000 +RTS -N2
5001

real    0m17.506s
user    0m10.619s
sys     0m2.863s

Parallel sort

import Control.Parallel
import System.Environment

mySort (x:xs) = greater `par` (lesser `pseq` lesser ++ x:greater)
  where
    lesser = mySort [y | y <- xs, y < x]
    greater = mySort [y | y <- xs, y >= x]
mySort _ = []

main = do
  args <- getArgs
  let n:_ = map read args
  print $ length $ mySort [n, n-1 .. 0]

$ time ./2 5000 +RTS -N2
5001

real    0m7.559s
user    0m5.926s
sys     0m1.613s

Measuring performance

using time as a global measure is wrong:
- measure multiple things at once
- invisible data dependencies
- benchmarking a thunk instead of actual work
use ThreadScope

$ ghc --make -threaded -eventlog -rtsopts 2.hs
$ ./2 5000 +RTS -ls -N2
$ threadscope 2.eventlog

Measuring performance

Performance results

a lot of problems
- one thread runs longer
- only one thread constructs sparks
- garbage collection
cannot solve them here
Strategies
- conversions to WHNF and NF

instance NFData ... where
  rnf = ...

Explicit Parallelism or Concurrency

Prelude Control.Concurrent> :t forkIO
forkIO :: IO () -> IO ThreadId
Prelude Control.Concurrent> :t forkOS
forkOS :: IO () -> IO ThreadId

forkOS constructs a new OS thread
best is to use forkIO

import Control.Concurrent

thread x = do
  putStrLn $ "Thread " ++ show x

main = do
  forkIO $ thread 42

$ ./3 +RTS -N2
Thread 42
$ ./3 +RTS -N2
$

More Threads

import Control.Concurrent

thread x = do
  putStrLn $ "Thread " ++ show x

main = do
  forkIO $ thread 1
  forkIO $ thread 2
  forkIO $ thread 3
  forkIO $ thread 4
  forkIO $ thread 5
  forkIO $ thread 6

$ ./5 +RTS -N2
Thread 1
Thread 3
Thread 5

Even More Threads

import Control.Concurrent
import Control.Monad

thread x = do
  putStrLn $ "Thread " ++ show x

main = do
  mapM (forkIO . thread) [1..6]

$ ./6 +RTS -N2
Thread 1
$ ./6 +RTS -N2
Thread 1
Thread 3
Thread 5
$ ./6 +RTS -N2
Thread 1
Thread 6
$ ./6 +RTS -N2
Thread 2

non-deterministic

Main thread

special role
when it finishes --> entire program finishes
no permanent deadlocks

Simple Communication Between Threads

newMVar :: a -> IO (MVar a)
newEmptyMVar :: IO (MVar a)
putMVar :: MVar a -> a -> IO ()
takeMVar :: MVar a -> IO a
tryPutMVar :: MVar a -> a -> IO Bool
tryTakeMVar :: MVar a -> IO (Maybe a)

single element box: either full or empty
blocking semantics:
- put in full --> sleep
- take from empty --> sleep
many other combinators (see readMVar for example)

Synchronizing Threads

import Control.Concurrent

thread :: Int -> MVar () -> IO ()
thread x v = do
  putStrLn $ "Thread " ++ show x
  putMVar v ()

main = do
  v <- newEmptyMVar
  forkIO $ thread 42 v
  takeMVar v

Synchronizing Threads

import Control.Concurrent
import Control.Monad

thread :: Int -> MVar () -> IO ()
thread x v = do
  putStrLn $ "Thread " ++ show x
  putMVar v ()

main = do
  vars <- replicateM 6 newEmptyMVar
  mapM (forkIO . uncurry thread) (zip [1..6] vars)
  mapM_ takeMVar vars

Advanced Communication Between Threads

MVars perfectly good for one-shot communication
Need one-way communication

newChan :: IO (Chan a)
dupChan :: Chan a -> IO (Chan a)
readChan :: Chan a -> IO a
writeChan :: Chan a -> a -> IO ()

readChan from empty --> blocks
writeChan never blocks
Chans are unbounded

Chan Example

import Control.Concurrent

thread :: Int -> Chan Int -> MVar Int -> IO ()
thread x c v = do
  putStrLn $ "Thread " ++ show x
  threadDelay 100000
  a <- readChan c
  b <- readChan c
  putMVar v (a + b)
  return ()

main = do
  v <- newEmptyMVar
  c <- newChan
  forkIO $ thread 42 c v
  writeChan c 40
  writeChan c 2
  s <- readMVar v
  print s

Broadcast Example

import Control.Concurrent
import Control.Monad

thread :: Int -> Chan Int -> MVar () -> IO ()
thread x c v = do
  s <- readChan c
  putStrLn $ "Thread " ++ show x ++ " read " ++ show s
  putMVar v ()

main = do
  c <- newChan
  vars <- replicateM 6 newEmptyMVar
  chans <- replicateM 6 (dupChan c)
  mapM (forkIO . \(x,y,z) -> thread x y z) $ [(x, chans !! x, vars !! x) | x <- [0..5]]
  threadDelay 1000000
  writeChan c 42
  mapM_ takeMVar vars

Problems :: Deadlocks

import Control.Concurrent

thread out inn v = do
  modifyMVar_ out $ \x -> do
    yield
    modifyMVar_ inn $ \y -> return (y + 1)
    return (x + 1)
  putStrLn "done"
  putMVar v ()

main = do
  a <- newMVar 1
  b <- newMVar 2
  v <- newEmptyMVar
  v' <- newEmptyMVar
  forkIO $ thread a b v
  forkIO $ thread b a v'
  takeMVar v
  takeMVar v'

Software Transactional Memory

promising new approach

atomically :: STM a -> IO a

atomicity && isolation

readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()

composability

withdraw :: Account -> Int -> STM ()
withdraw acc amount = do
  bal <- readTVar acc
  writeTVar acc (bal - amount)

deposit :: Account -> Int -> STM ()
deposit acc amount = withdraw acc (- amount)

STM - Bank account

import Control.Concurrent
import Control.Concurrent.STM

type Account = TVar Int

newAccount = newTVarIO 0

...

limitedWithdraw :: Account -> Int -> STM ()
limitedWithdraw acc amount = do
  bal <- readTVar acc
  check (amount <= 0 || amount <= bal)
  writeTVar acc (bal - amount)

t1 a = atomically $ deposit a 10
t2 a = atomically $ limitedWithdraw a 6

main = do
  a <- newAccount
  mapM forkIO [t1 a, t2 a, t2 a, t2 a, t1 a]
  threadDelay 1000000

Data Parallel Haskell (1)

par / seq: light, hard granularity
forkIO / MVar / Chan / STM: more precise, more complex
tradeoff abstraction - precision
nested data parallelism

Data Parallel Haskell (2)

Do the same thing in parallel to every element of a large collection
no explicit threads
no explicit communication
good & clear cost model
good locality
easy partitioning

sumsq :: [: Float :] → Float
sumsq a = sumP [: x*x | x ← a :]

break array into N (num cores) chunks & run sequential loops

Data Parallel Haskell (3)

Each thing you do may in turn be a nested parallel computation
flattening: compiler transformation to transform nested program into a flat one

type Vector = [: Float :]
type Matrix = [: Vector :]

matMul :: Matrix → Vector → Vector
matMul m v = [: vecMul r v | r ← m :]

Data Parallel Haskell (4)

arbitrary nesting
flattening at compile time
good cost model, no explicit parallelism
project to map on GPU cores
still in alpha

Conclusions

parallelism vs concurrency
3 types of parallelism:
- semi-explicit: sparks, par, pseq
- explicit: threads, STM, MVars, Chans
- nested
strategies

Concurrent and Multicore Programming in Haskell

Concurrency and Parallelism

Haskell threads

Semi-explicit parallelism

Sparks (1)

Sparks (2)

Compiling and running

`seq` and `pseq`

How much to evaluate? (1)

How much to evaluate? (2)

NF, HNF, WHNF

Strictness (eager conversion to NF)

More stricntess

Sequential sort

Parallel sort

Measuring performance

Measuring performance

Performance results

Explicit Parallelism or Concurrency

More Threads

Even More Threads

Main thread

Simple Communication Between Threads

Synchronizing Threads

Synchronizing Threads

Advanced Communication Between Threads

Chan Example

Broadcast Example

Problems :: Deadlocks

Other Problems

Software Transactional Memory

STM - Bank account

Data Parallel Haskell (1)

Data Parallel Haskell (2)

Data Parallel Haskell (3)

Data Parallel Haskell (4)

Conclusions

End

Concurrent and Multicore Programming in Haskell

Concurrency and Parallelism

Haskell threads

Semi-explicit parallelism

Sparks (1)

Sparks (2)

Compiling and running

seq and pseq

How much to evaluate? (1)

How much to evaluate? (2)

NF, HNF, WHNF

Strictness (eager conversion to NF)

More stricntess

Sequential sort

Parallel sort

Measuring performance

Measuring performance

Performance results

Explicit Parallelism or Concurrency

More Threads

Even More Threads

Main thread

Simple Communication Between Threads

Synchronizing Threads

Synchronizing Threads

Advanced Communication Between Threads

Chan Example

Broadcast Example

Problems :: Deadlocks

Other Problems

Software Transactional Memory

STM - Bank account

Data Parallel Haskell (1)

Data Parallel Haskell (2)

Data Parallel Haskell (3)

Data Parallel Haskell (4)

Conclusions

End

`seq` and `pseq`