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

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 Riko Jacob, Matteo Ceccarello, and Claus Brabrand at the IT University of Copenhagen. Teaching assistant Matteo Dusefante and Amund Lome. They help with exercises and approve (or not) the mandatory hand-ins.

Preliminary lecture plan

The script myj.sh seems to be a useful tool on the command line.

Note that the slides, exercises and code of this year's course will become available over time. Before that, the links are referencing the corresponding resource of last year's course.

Course week ISO week Date Who Subject Materials Exercises
1 35 31 Aug RJ 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 Handin Week 1

2 36 7 Sep RJ Threads and Locks: Designing thread-safe classes. Monitor pattern. Concurrent collections. Documenting thread-safety. Goetz chapters 4, 5; Bloch item 15; Slides week 2; Exercises week 2; Example code: pcpp-week02.zip Handin Week 2

3 37 14 Sep RJ Performance measurements. Sestoft: Microbenchmarks and supporting Java code; Slides week 3; Exercises week 3; Example code: pcpp-week03.zip; Optional: McKenney chapter 3 Handin Week 3

4 38 21 Sep RJ 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 4; Exercises week 4; Example code: pcpp-week04.zip. File with English words: words.zip Handin Week 4

5 39 28 Sep RJ 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 Handin Week 5

6 40 5 Oct RJ 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 Handin Week 6

7 41 12 Oct MC Threads and Locks: GUI applications. Cache coherence and performance consequences. Goetz chapters 9, 10.1-2; McKenney chapters 1-4; Slides week 7; Exercises week 7; Example code: pcpp-week07.zip Handin Week 7

42 20 Oct Fall break

8 43 26 Oct MC Threads and Locks: Testing concurrent programs. Goetz chapter 12; Herlihy and Shavit chapter 3; Slides week 8; Exercises week 8; Handin Week 8

9 44 2 Nov RJ 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; Eidenbenz, Wattenhofer 2011 paper; Slides week 9; Exercises week 9; Example code: pcpp-week09.zip Handin Week 9

10 45 9 Nov RJ Optimistic concurrency, lock-free data structures, Treiber stack, compare-and-swap. Consensus number. Goetz chapter 15; Herlihy and Shavit sections 5.1-5.2; Slides week 10; Exercises week 10; Example code: pcpp-week10.zip Handin Week 10

11 46 16 Nov RJ The Michael and Scott queue, progress concepts, Union Find, 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 Handin Week 11

12 47 23 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 on learnit Exercises week 12: see slides 50 and later Handin Week 12

13 48 30 Nov CB Message passing (no mutable shared memory), Erlang, Java+Akka. Slides week 13; Example code: see LearnIT No new Handin

14 49 7 Dec RJ Exam preparation See Archive

Course week	ISO week	Date	Who	Subject	Materials	Exercises
1	35	31 Aug	RJ	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	Handin Week 1
2	36	7 Sep	RJ	Threads and Locks: Designing thread-safe classes. Monitor pattern. Concurrent collections. Documenting thread-safety.	Goetz chapters 4, 5; Bloch item 15; Slides week 2; Exercises week 2; Example code: pcpp-week02.zip	Handin Week 2
3	37	14 Sep	RJ	Performance measurements.	Sestoft: Microbenchmarks and supporting Java code; Slides week 3; Exercises week 3; Example code: pcpp-week03.zip; Optional: McKenney chapter 3	Handin Week 3
4	38	21 Sep	RJ	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 4; Exercises week 4; Example code: pcpp-week04.zip. File with English words: words.zip	Handin Week 4
5	39	28 Sep	RJ	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	Handin Week 5
6	40	5 Oct	RJ	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	Handin Week 6
7	41	12 Oct	MC	Threads and Locks: GUI applications. Cache coherence and performance consequences.	Goetz chapters 9, 10.1-2; McKenney chapters 1-4; Slides week 7; Exercises week 7; Example code: pcpp-week07.zip	Handin Week 7
	42	20 Oct	Fall break
8	43	26 Oct	MC	Threads and Locks: Testing concurrent programs.	Goetz chapter 12; Herlihy and Shavit chapter 3; Slides week 8; Exercises week 8;	Handin Week 8
9	44	2 Nov	RJ	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; Eidenbenz, Wattenhofer 2011 paper; Slides week 9; Exercises week 9; Example code: pcpp-week09.zip	Handin Week 9
10	45	9 Nov	RJ	Optimistic concurrency, lock-free data structures, Treiber stack, compare-and-swap. Consensus number.	Goetz chapter 15; Herlihy and Shavit sections 5.1-5.2; Slides week 10; Exercises week 10; Example code: pcpp-week10.zip	Handin Week 10
11	46	16 Nov	RJ	The Michael and Scott queue, progress concepts, Union Find, 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	Handin Week 11
12	47	23 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 on learnit Exercises week 12: see slides 50 and later	Handin Week 12
13	48	30 Nov	CB	Message passing (no mutable shared memory), Erlang, Java+Akka.	Slides week 13; Example code: see LearnIT	No new Handin
14	49	7 Dec	RJ	Exam preparation	See Archive

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.cs.rochester.edu/~scott/papers/1996_PODC_queues.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