Multicore Programming Final Review. Outline Intro to Parallelism and Concurrency Parallel Programming – Algorithms and Analysis Concurrent Programming.

Presentation on theme: "Multicore Programming Final Review. Outline Intro to Parallelism and Concurrency Parallel Programming – Algorithms and Analysis Concurrent Programming."— Presentation transcript:

1 Multicore Programming Final Review

2 Outline Intro to Parallelism and Concurrency Parallel Programming – Algorithms and Analysis Concurrent Programming – Mutual Exclusion and Linearizability – Spin Locks – Monitors – Concurrent Data Structures

3 Intro to Parallelism and Concurrency Java Multi-thread Programming – Start() Join() Parallelism vs. Concurrency – Different concerns

4 Parallel Programming Sum Array – start(); join(); fork-join framework；Dag – Divide and Conquer Algorithms – Prefix-sum, Filter, Parallel Sorting Work 、Span and Parallelism Programming with Divide and Conquer to solve some practical problems

5 Concurrent Programming Multi-threads access the shared resources – Correctness and Efficiency How to describe the correctness of concurrent programs – Mutual exclusion – Linearizability – Deadlock-free – Starvation-free – Lock-free – Wait-free

6 Mutual Exclusion What is mutual exclusion? How to prove mutual exclusion? Peterson lock guarantees mutual exclusion, starvation-free and dead-lock free

7 Linearizability Why do we need Linearizability? What is Linearizability? How to decide a linearizable execution history? What is Sequential Consistency? What is the difference and relationship between SC and Lin?

8 Spin Locks Ideal lock implementations are inefficient What is spin? Spin locks implementation depends on the low-level Archi. Local spin is good for cache hit. TAS, TTAS, CLH, MCS etc.

9 Monitor Spin wait and blocking Condition – await(),signal(),signalAll() Re-check is necessary after being waken. – While(B) {x.await()} To avoid lost-wake-up – Using signalAll() instead of signal() Programming with monitors.

10 Concurrent Data Structures Linked-list Set – Coarse-grained Synchronization – Fine-grained Synchronization – Optimistic – Lazy – Lock-free Hand-over-hand Locking

11 考试时间和方式 考试时间： 4 月 27 日 14:30 – 16:30 考试方式：闭卷 参考资料：上课课件、教材、课堂练习和 平时作业

12 考试题型 简答题 （ 12 题选 10 题回答 共 70 分） – Amdhal 定理、线程创建销毁 Dag 图、 Spin Lock 、 Java 线程同步方法以及 Monitor 的正确使用、可 线性化的判断 编程题 （ 2 题 共 30 分） – Fork-Join Framework 求解具体问题 – 使用锁和条件对象实现具体的共享访问协议

13 Thanks for learning this course! Hoping it is helpful for your future career!