Practical Concurrent and Parallel Programming (PCPP) (KSPRCPP1KU) E2016

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 performance and scalability of parallel programs. It covers methods to find bugs in concurrent programs.
For exercises, quizzes, and much more information, see the course LearnIT site (restricted access).
For formal rules, see the official course description.
The course is designed and taught by Peter Sestoft and Claus Brabrand at the IT University of Copenhagen. Teaching assistants Alexander Bock, Amund Ranheim Lome, Gediminas Kucas, and Sigurt Bladt Dinesen help with exercises and approve (or not) the mandatory hand-ins.
Exam questions January 2017 and supporting code. Very many exam solutions were very good and thoughtful, as evidenced by the statistics: 4x-3 + 6x00 + 3x02 + 4x4 + 6x7 + 12x10 + 31x12 for an average of 8.2 and a pass rate of 85% (of those who handed in something).

Preliminary lecture plan

Course week ISO week Date Who Subject Materials Exercises
1 35 2 Sep PS 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. Goetz chapters 1, 2, 3; Sutter paper; McKenney chapter 2; Bloch item 66; Slides week 1; Exercises week 1; Example code: pcpp-week01.zip Exercises week 1

2 36 9 Sep PS Threads and Locks: Designing thread-safe classes. Monitor pattern. Concurrent collections. Documenting thread-safety. Goetz chapters 4, 5; Slides week 2; Exercises week 2; Example code: pcpp-week02.zip Mandatory handin 1

3 37 16 Sep PS Java 8 parallel streams for bulk data and parallel array prefix operations. Functional interfaces, lambda expressions, method reference expressions. Sestoft: Java Precisely 3rd edition (PDF excerpt, see LearnIT) sections 11.13, 11.14, 23, 24, 25; and associated example code. Slides week 3; Exercises week 3; Example code: pcpp-week03.zip. File with English words: words.zip Exercises week 3

4 38 23 Sep PS Performance measurements. Sestoft: Microbenchmarks and supporting Java code; Slides week 4; Exercises week 4; Example code: pcpp-week04.zip; Optional: McKenney chapter 3 Mandatory handin 2

5 39 30 Sep PS Threads and Locks: Tasks and the Java executor framework. Concurrent pipelines, wait() and notifyAll(). Goetz chapters 5.3, 6, 8; Bloch items 68, 69; Slides week 5; Exercises week 5; Example code: pcpp-week05.zip Exercises week 5

6 40 7 Oct PS Threads and Locks: Concurrent hash maps: performance and scalability case study. Goetz chapter 11, 13.5; Slides week 6; Exercises week 6; Example code: pcpp-week06.zip Mandatory handin 3

7 41 14 Oct PS Threads and Locks: GUI applications. Cache coherence and performance consequences. Goetz chapter 9; McKenney chapters 1-4; Slides week 7; Exercises week 7; Example code: pcpp-week07.zip Exercises week 7

42 21 Oct Fall break

8 43 28 Oct PS Threads and Locks: Testing concurrent programs. Goetz chapter 12; Herlihy and Shavit chapter 3; Slides week 8; Exercises week 8; Example code: pcpp-week08.zip Mandatory handin 4

9 44 4 Nov AB Transactional memory with Multiverse: Multiverse API Javadoc and file multiverse-core-0.7.0.jar. Harris et al 2008 paper; Herlihy and Shavit sections 18.1-18.2; Cascaval et al 2008 paper; Slides week 9; Exercises week 9; Example code: pcpp-week09.zip Exercises week 9

10 45 11 Nov PS Optimistic concurrency, lock-free data structures, Treiber stack, compare-and-swap. Goetz chapter 15; Slides week 10; Exercises week 10; Example code: pcpp-week10.zip Mandatory handin 5

11 46 18 Nov PS The Michael and Scott queue, progress concepts, work-stealing queues. Michael and Scott paper and Chase and Lev paper sections 1, 2 and 5; Slides week 11; Exercises week 11; Example code: pcpp-week11.zip Exercises week 11

12 47 25 Nov CB Introduction to message passing concurrency (no mutable shared memory), Introduction to Erlang, Introduction to Java+Akka. Erlang chapter 1, 2, 5; Slides week 12; Exercises week 12: see slides 50 and later Exercises week 12

13 48 2 Dec CB Message passing (no mutable shared memory), Erlang, Java+Akka. Slides week 13; Example code: see LearnIT Mandatory handin 6 is in lecture 12 slides 50 and later

14 49 9 Dec KFL, PS (1) PS: Java vs C# memory model; (2) Ken Friis Larsen, DIKU: Using Rust's type system to control shared mutable memory and avoid some concurrency problems Slides week 14: part 1; part 2; Example code: pcpp-week14.zip No new exercises

Course week	ISO week	Date	Who	Subject	Materials	Exercises
1	35	2 Sep	PS	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.	Goetz chapters 1, 2, 3; Sutter paper; McKenney chapter 2; Bloch item 66; Slides week 1; Exercises week 1; Example code: pcpp-week01.zip	Exercises week 1
2	36	9 Sep	PS	Threads and Locks: Designing thread-safe classes. Monitor pattern. Concurrent collections. Documenting thread-safety.	Goetz chapters 4, 5; Slides week 2; Exercises week 2; Example code: pcpp-week02.zip	Mandatory handin 1
3	37	16 Sep	PS	Java 8 parallel streams for bulk data and parallel array prefix operations. Functional interfaces, lambda expressions, method reference expressions.	Sestoft: Java Precisely 3rd edition (PDF excerpt, see LearnIT) sections 11.13, 11.14, 23, 24, 25; and associated example code. Slides week 3; Exercises week 3; Example code: pcpp-week03.zip. File with English words: words.zip	Exercises week 3
4	38	23 Sep	PS	Performance measurements.	Sestoft: Microbenchmarks and supporting Java code; Slides week 4; Exercises week 4; Example code: pcpp-week04.zip; Optional: McKenney chapter 3	Mandatory handin 2
5	39	30 Sep	PS	Threads and Locks: Tasks and the Java executor framework. Concurrent pipelines, wait() and notifyAll().	Goetz chapters 5.3, 6, 8; Bloch items 68, 69; Slides week 5; Exercises week 5; Example code: pcpp-week05.zip	Exercises week 5
6	40	7 Oct	PS	Threads and Locks: Concurrent hash maps: performance and scalability case study.	Goetz chapter 11, 13.5; Slides week 6; Exercises week 6; Example code: pcpp-week06.zip	Mandatory handin 3
7	41	14 Oct	PS	Threads and Locks: GUI applications. Cache coherence and performance consequences.	Goetz chapter 9; McKenney chapters 1-4; Slides week 7; Exercises week 7; Example code: pcpp-week07.zip	Exercises week 7
	42	21 Oct	Fall break
8	43	28 Oct	PS	Threads and Locks: Testing concurrent programs.	Goetz chapter 12; Herlihy and Shavit chapter 3; Slides week 8; Exercises week 8; Example code: pcpp-week08.zip	Mandatory handin 4
9	44	4 Nov	AB	Transactional memory with Multiverse: Multiverse API Javadoc and file multiverse-core-0.7.0.jar.	Harris et al 2008 paper; Herlihy and Shavit sections 18.1-18.2; Cascaval et al 2008 paper; Slides week 9; Exercises week 9; Example code: pcpp-week09.zip	Exercises week 9
10	45	11 Nov	PS	Optimistic concurrency, lock-free data structures, Treiber stack, compare-and-swap.	Goetz chapter 15; Slides week 10; Exercises week 10; Example code: pcpp-week10.zip	Mandatory handin 5
11	46	18 Nov	PS	The Michael and Scott queue, progress concepts, work-stealing queues.	Michael and Scott paper and Chase and Lev paper sections 1, 2 and 5; Slides week 11; Exercises week 11; Example code: pcpp-week11.zip	Exercises week 11
12	47	25 Nov	CB	Introduction to message passing concurrency (no mutable shared memory), Introduction to Erlang, Introduction to Java+Akka.	Erlang chapter 1, 2, 5; Slides week 12; Exercises week 12: see slides 50 and later	Exercises week 12
13	48	2 Dec	CB	Message passing (no mutable shared memory), Erlang, Java+Akka.	Slides week 13; Example code: see LearnIT	Mandatory handin 6 is in lecture 12 slides 50 and later
14	49	9 Dec	KFL, PS	(1) PS: Java vs C# memory model; (2) Ken Friis Larsen, DIKU: Using Rust's type system to control shared mutable memory and avoid some concurrency problems	Slides week 14: part 1; part 2; Example code: pcpp-week14.zip	No new exercises

Mandatory course materials

Goetz et al: Java Concurrency in Practice, Addison-Wesley 2006. The Academic Bookstore will sell it at ITU at start of term. Also at Amazon.co.uk. Example code at http://jcip.net/.
Herlihy and Shavit: The Art of Multiprocessor Programming. Revised first edition, Morgan Kaufmann 2012. Chapters 3 (safety and liveness concepts) and 18.1, 18.2 (compositionality, transactional memory). At Amazon.co.uk
Sestoft: Microbenchmarks in Java and C#. Free at http://www.itu.dk/people/sestoft/papers/benchmarking.pdf with the corresponding Java example code.
Sestoft: Java Precisely 3rd edition (MIT Press 2016, draft), sections 11.13, 11.14, 23, 24, 25. PDF available from LearnIt.
Harris, Marlow, Peyton-Jones, Herlihy: Composable memory transactions. Communications of the ACM 51, 8 (August 2008) 91-100; PDF available from LearnIT.
Cascaval et al: Software Transactional Memory: Why Is It Only a Research Toy? ACM Queue 2008. Free at http://queue.acm.org/detail.cfm?id=1454466
The Multiverse Software Transactional Memory library for Java: Multiverse API Javadoc (local copy) and the multiverse-core-0.7.0.jar (library implementation).
Michael and Scott: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. PODC 1996. Free at http://www.research.ibm.com/people/m/michael/podc-1996.pdf
Chase and Lev: Dynamic circular work- stealing deque, SPAA'05, 2005, sections 1, 2 and 5; see also LearnIT.
Armstrong, Virding, Williams: Concurrent Programming in Erlang. Part 1 free at http://www.erlang.org/download/erlang-book-part1.pdf.

Optional course materials

Bloch: Effective Java. Second edition, Addison-Wesley 2008. Item 15 on immutability and items 66-73 on concurrency. At Amazon.co.uk. Contains much other wisdom for Java (and .NET) developers; you should own this book and use it.
Sestoft: Java Precisely. Second edition, MIT Press 2005. Especially chapters 9 and 10 on classes, inner classes and anonymous classes, and chapter 16 on threads. At Amazon.co.uk
Sutter: The free lunch is over. Free at http://www.gotw.ca/publications/concurrency-ddj.htm
If you want a deep understanding of how modern multicore cache and memory hardware design affects concurrency performance, these seem to be good overviews, although far too detailed for this course: McKenney: Memory barriers, a hardware view for software hackers (IBM, 2010) and Drepper: What every programmer should know about memory (Redhat, 2007).
Budd, Lipton, Sayward, DeMillo: The design of a prototype mutation system for software testing, 1978. Free at http://www.computer.org/csdl/proceedings/afips/1978/5086/00/50860623.pdf.
On transactional memory: Peyton Jones: Beautiful concurrency, 2007; and Larus and Kozyrakis: Transactional memory, 2008 (free access within ITU); and Dan Grossman's very enlightening analogy between transactional memory and garbage collection; and hardware support via the Intel Transaction Synchronization Extensions (2012) and also pages 8-1 through 8-24 of the Instruction Set Extensions Programming Reference; Robert Ennals: Software transactional memory should not be obstruction-free, 2006, PDF; and a response to Cascaval's critique of STM by Dragojevic et al: Why STM can be more than a research toy CACM, April 2011. (PDF accessible for free from within ITU's network).
On memory models: see Java Language Specification below; and Ostrovsky: The C# Memory Model in Theory and Practice, in MSDN Magazine, part 1 (December 2012) and part 2 (January 2013); and The C# Language Specification (standard Ecma-334), especially section 10.10 and 17.4.3, and Joseph Albahari's Threading in C# Part 4: Advanced Threading.
Akka+Java Actor Snapshot
The Akka+Java documentation
Video Talk on Akka by Viktor Klang (on YouTube)
Video Talk on Akka by Jonas Boner (on YouTube)
- Slides for the Video Talk on Akka (from GOTO conference, Aarhus, Denmark).

Even more optional materials

Nancy Leveson's 1995 report on the Therac-25 accidents, caused by incompetent concurrent programming.
Per Brinch Hansen on Java's insecure parallelism, 1999.
Hoare's paper on monitors, CACM 17, 10 (October 1974) 549-557.
The CERT Secure Coding Standard for Java especially sections 09 on Locking, 10-12 on Threads, and 08 on Visibility and Atomicity.
McKenney (ed.): Is Parallel Programming Hard, And, If So, What Can You Do About It? IBM 10 March 2014. Free at https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html. Chapters 2 and 3.
A good book about .NET parallel programming is Campbell, Johnson, Miller, Toub: Parallel Programming with Microsoft .NET, Design Patterns for Decomposition and Coordination on Multicore Architectures. Microsoft Press 2010. There is an online version and also a printed version at Amazon.com.
M. Herlihy: Wait-free synchronization. ACM Toplas 11, 1 (January 1991) 124-149. Free PDF at Herlihy's homepage.
N. Shavit: Data structures in the multicore age. Communications of the ACM 54, 3 (March 2011) 76-84. Free inside ITU from the ACM Digital Library.

Java resources

Java concurrency tutorial. Free at http://docs.oracle.com/javase/tutorial/essential/concurrency/.
Java streams tutorial, parallelism section. Free at http://docs.oracle.com/javase/tutorial/collections/streams/parallelism.html.
Java Swing GUI Toolkit tutorial, concurrency lesson at http://docs.oracle.com/javase/tutorial/uiswing/concurrency/index.html.
Java 8 class library documentation online.
Java 8 development kit download
Java 8 language specification in PDF and online as HTML; especially 17.1 synchronization and 8.3.1.4 volatile fields and 17.5 final field semantics and the somewhat complicated 17.4 memory model.
Brian Goetz about the design of the Java 1.5 memory model: part 1 and part 2, IBM 2004.
JSR 305 thread-safety annotations jar file for @GuardedBy and similar. Download the jar file, put it someplace such as ~/lib/jsr305-3.0.0.jar, add import javax.annotation.concurrent.GuardedBy; to your Java source files, and mention the jar file on the classpath when compiling Java files, as in javac -cp ~/lib/jsr305-3.0.0.jar *.java
Akka homepage. http://akka.io/ (Documentation, FAQ, Download, ...).
Akka+Java API