I. Parallelism Techniques
 A. Basic Concepts
------------------------------------------
DO WE NEED LANGUAGE SUPPORT FOR PARALLELISM?

Consider

     e0 e1 e2

Why doesn't Haskell just evaluate 
   all subexpressions in parallel?






------------------------------------------
------------------------------------------
     EXAMPLE PARALLEL ALGORITHM

How to sort a list in parallel?
   psort :: (Ord a) => [a] -> [a]













------------------------------------------
  1. what has to be expressed?
------------------------------------------
      WHAT DO WE HAVE TO EXPRESS?

Say:
   - how to divide up work into tasks
   - how to order parts of computation
        (what cannot be done in parallel)


------------------------------------------
     Do we need to say what computations execute on what processors?
     Do we need to say what percentage of a processor each task gets?
------------------------------------------
        HASKELL'S EVAL MONAD

in module Control.Parallel.Strategies

data Eval a = Done a
  runEval :: Eval a -> a
  rpar :: a -> Eval a     
  rseq :: a -> Eval a

instance Monad Eval where
  return = Done
  m >>= k = case m of
              (Done x) -> k x

------------------------------------------
------------------------------------------
         EXAMPLE: PARMAP

> parMap :: (a -> b) -> [a] -> Eval [b]
> parMap f [] = return []
> parMap f (a:as) = 
>    do b <- rpar (f a)
>       bs <- parMap f as
>       return (b:bs)


from "Parallel and Concurrent Programming in Haskell"
by Simon Marlow, p.13
------------------------------------------
  2. separating and composing specifications of parallelism
------------------------------------------
            STRATEGIES

Goal: separate specification of how to parallelize
      from specification of data computation

module Control.Parallel.Strategies

type Strategy a = a -> Eval a
using :: a -> Strategy a -> a
x `using` s = runEval (s x)

r0 :: Strategy a                   -- do nothing
rseq :: Strategy a                 -- evaluate argument to WHNF (minimally)
rdeepseq :: NFData a => Strategy a -- evaluate arg to NF (fully)

------------------------------------------
------------------------------------------
             EXAMPLE: PARLIST

Problem: mix of algorithm + parallelism directives

parMap :: (a -> b) -> [a] -> Eval [b]
parMap f [] = return []
parMap f (a:as) = 
   do b <- rpar (f a)
      bs <- parMap f as
      return (b:bs)

Goal: extract the strategy for parallelism,
      separate it from the algorithm

idea: map a given strategy on elements
      to strategy on whole list

parList :: Strategy a -> Strategy [a]
parList strat [] =
parList strat (x:xs) =
   do 






With parList can define

> myParMap :: (a -> b) -> [a] -> [b]
> myParMap f xs = (map f xs) `using` parList rseq

------------------------------------------
  3. Examples
   a. Sudoku
   b. Hailstone or 3x+1 problem
 B. Amdhal's law
------------------------------------------
             AMDHAL'S LAW

Speedup = serial clock time / parallel time

Why can't we speed up our program 4 times
   if we have 4 Cores?

 - There are parts of the program we can't parallelize

 Let P be the fraction of computation that can be parallelized
 Let S be the speedup achieved for P

 The the serial execution fraction is (1-P)
 The fraction of the time taken by parallel part is P/S

 So overall speedup is: 
            1 
       ___________
      (1-P) + (P/S)
------------------------------------------