Practical Concurrent and Parallel Programming 2019

(PCPP) (KSPRCPP1KU) E2019

In this MSc course, you learn how to write correct and efficient concurrent and parallel software, primarily using Java, on standard shared-memory multicore hardware. The course covers basic mechanisms such as threads, locks and shared memory as well as more advanced mechanisms such as parallel streams for bulk data, transactional memory, message passing, and lock-free data structures with compare-and-swap. It covers concepts such as atomicity, safety, liveness and deadlock. It covers how to measure and understand the performance and scalability of parallel programs. It covers methods to find bugs in concurrent programs.

For exercises and more information, see the course LearnIT site (restricted access). For formal rules, see the official course description.

The course is taught by Thomas Dybdahl Ahle and designed together with Peter Sestoft, Riko Jacob and Claus Brabrand at the IT University of Copenhagen. Teaching assistants are Jorgel Këci, Jon Voigt Tøttrup and Amund Ranheim Lome who help with exercises and approve (or not) the mandatory hand-ins.

Surprises in Parallelism and Java

1 Week 35 Aug 29th Thursday

Concurrent and parallel programming, why, what is so hard. Threads and locks in Java, shared mutable memory, mutual exclusion, visibility, volatile fields, atomic operations, avoiding sharing (thread confinement, stack confinement), immutability, final, safe publication.

Materials: Goetz chapters 1, 2, 3; Sutter paper; McKenney chapter 2; Bloch item 66

Handin at LearnIT.

Threads and Locks

2 Week 36 Sep 5th Thursday

Designing thread-safe classes. Monitor pattern. Concurrent collections. Documenting thread-safety.

Materials: Goetz chapters 4, 5; Bloch item 15; jcip-annotations.jar

Handin at LearnIT.

Performance measurements

3 Week 37 Sep 12th Thursday

Materials: Sestoft: Microbenchmarks and supporting Java code; Optional: McKenney chapter 3, (The Art of) (Java) Benchmarking

Handin at LearnIT.

Streams

4 Week 38 Sep 19th Thursday

Java 8 parallel streams for bulk data and parallel array prefix operations. Functional interfaces, lambda expressions, method reference expressions.

Materials: Sestoft: Java Precisely 3rd edition sections 11.13, 11.14, 23, 24, 25; get draft on LearnIT and associated example code. Also File with English words.

Handin at LearnIT.

Threads and Locks 2

5 Week 39 Sep 26th Thursday

Tasks and the Java executor framework. Concurrent pipelines, wait() and notifyAll().

Materials: Goetz chapters 5.3, 6, 8; Bloch items 68, 69

Handin at LearnIT.

Threads and Locks 3

6 Week 40 Oct 3rd Thursday

Concurrent hash maps: performance and scalability case study.

Materials: Goetz chapter 11, 13.5

Handin at LearnIT.

GUI applications

7 Week 41 Oct 10th Thursday

Cache coherence and performance consequences.

Materials: Goetz chapters 9, 10.1-2; McKenney chapters 1-4

Handin at LearnIT.

Fall break

8 Week 42

No exercises or lecture this week.

Threads and Locks 5

9 Week 43 Oct 24th Thursday

Testing concurrent programs.

Materials: Goetz chapter 12; Herlihy and Shavit chapter 3

Handin at LearnIT.

Transactional Memory

10 Week 44 Oct 31st Thursday

Transactional memory with Multiverse: Multiverse API Javadoc and file multiverse-core-0.7.0.jar.

Materials: Harris et al 2008 paper; Herlihy and Shavit sections 18.1-18.2; Cascaval et al 2008 paper; Eidenbenz, Wattenhofer 2011 paper;

Handin at LearnIT.

Title to be Determined

11 Week 45 Nov 7th Thursday

Optimistic concurrency, lock-free data structures, Treiber stack, compare-and-swap. Consensus number.

Materials: Goetz chapter 15; Herlihy and Shavit sections 5.1-5.2

Handin at LearnIT.

Title to be Determined

12 Week 46 Nov 14th Thursday

The Michael and Scott queue, progress concepts, Union Find, work-stealing queues.

Materials: Michael and Scott paper and Chase and Lev paper sections 1, 2 and 5

Handin at LearnIT.

Title to be Determined

13 Week 47 Nov 21st Thursday

Introduction to message passing concurrency (no mutable shared memory), Introduction to Erlang, Introduction to Java+Akka.

Materials: Erlang chapter 1, 2, 5

Handin at LearnIT.

Title to be Determined

14 Week 48 Nov 28th Thursday

Message passing (no mutable shared memory), Erlang, Java+Akka.

Materials: Just the slides

Handin at LearnIT.

Exam preparation

15 Week 49 Dec 5th Thursday

Materials: See Materials -> Archive

Handin at LearnIT.

Mandatory course materials

Books

Articles

Other

Optional course materials

Even more optional materials

Resources

Archive