Cs242 PARALLELISM IN HASKELL Kathleen Fisher Reading:A Tutorial on Parallel and Concurrent Programming in Haskell Skip Section 5 on STM Thanks to Simon Peyton Jones,Satnam Singh,and Don Stewart for these slides
Kathleen Fisher cs242 Reading: A Tutorial on Parallel and Concurrent Programming in Haskell Skip Section 5 on STM Thanksto Simon Peyton Jones, Satnam Singh, and Don Stewart for these slides
The Grand challenge a Making effective use of multi- core hardware is the challenge for programming languages now. a Hardware is getting increasingly complicated Nested memory hierarchies Hybrid processors: GPU+ CPU, Cell, FPGA Massive compute power sitting mostly idle We need new programming models to program new commodity machines effectively
Making effective use of multi-core hardware is the challenge for programming languages now. Hardware is getting increasingly complicated: - Nested memory hierarchies - Hybrid processors: GPU + CPU, Cell, FPGA... - Massive compute power sitting mostly idle. We need new programming models to program new commodity machines effectively
Candidate models in haskell Explicit threads main : Io o do ch < newChan Non-deterministic by design forkIo (ioManager ch) Monadic, forkIo and sTm i forkIo (worker 1 ch) etc Semi-implicit parallelism Deterministic Pure: par and pseqr Data parallelism Deterministic Pure: parallel arrays Shared memory initially; distributed memory eventually; possibly even GPu
▪ Explicit threads ▪ Non-deterministic by design ▪ Monadic: forkIO and STM ▪ Semi-implicit parallelism ▪ Deterministic ▪ Pure: par and pseq ▪ Data parallelism ▪ Deterministic ▪ Pure: parallel arrays ▪ Shared memory initially; distributed memory eventually; possibly even GPUs… main :: IO () = do { ch <- newChan ; forkIO (ioManager ch) ; forkIO (worker 1 ch) ... etc ... }
Parallelism vs Concurrency a parallel program exploits real parallel computing resources to run faster while computing the same answer Expectation of genuinely simultaneous execution Deterministic A concurrent program models independent agents that can communicate and synchronize Meaningful on a machine with one processor Non-deterministic
A parallel program exploits real parallel computing resources to run faster while computing the same answer. - Expectation of genuinely simultaneous execution - Deterministic A concurrent program models independent agents that can communicate and synchronize. - Meaningful on a machine with one processor - Non-deterministic
Haskell Execution Model Thunk Pointer to the b implementation 10 I Values for free variables Storage slot for the result fib 0=0 fib 1=1 fib n =fib (n-1)+ fib(n-2)
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) 10 9 8 3 5 8 6 5 8 1 1 “Thunk” for fib 10 Pointer to the implementation Storage slot for the result Values for free variables