Multicore Programming

2013-2014

Dept. of Computer Science, Vrije Universiteit Brussel
Cursusfiche (NL) | Content description (EN)

Lecturer: Tom Van Cutsem

Course schedule

For the principles behind this course, read my position paper or view the slides of my presentation at the Workshop on Curricula on Concurrency and Parallelism.

Examination details below.

Questions? Contact me.

Course overview

Processors are no longer growing faster. Instead, they are growing ever more parallel. Hardware architects are no longer using the additional transistors afforded by Moore's Law to make sequential processors faster, but instead to put more processing cores on a single chip, leading to so-called chip multiprocessors, or simply multicore processors. Unfortunately, this creates a problem for us, programmers. Before the turn of the century, you could simply wait another year and your program would run faster on next-generation processors. This free lunch is now officially over: you'll have to learn how to successfully write concurrent and parallel programs if you want your programs' performance to continue to scale with the hardware capacity.

This year, the course will primarily involve programming in Java, Erlang and Clojure. All of these programming languages feature direct support for concurrent programming. If you question the usefulness of non-mainstream functional languages like Erlang and Clojure, I am not alone in thinking that the ideas embedded in these languages are important going forward. Here is a preliminary list of topics to be discussed:

• Multicore Processors: what and why?
• Parallelism: Amdahl's Law, Gustafson's Law, speedup and scalability
• Hardware primer: architectures, caches, cache coherence
• Parallelism vs. Concurrency
• Parallelism: DAG model, fork/join, the Java Fork/Join framework
• Concurrency: shared-memory multithreading (in Java): locks, race conditions, deadlock
• Concurrency: message-passing models: actors, processes, channels (Clojure core.async)
• Actors in practice: an introduction to Erlang
• Practical functional programming: an introduction to Clojure
• Software-transactional memory
• (Time permitting: Google's MapReduce abstraction: parallel programming for data centers)

Is this course for you? (aka prerequisites)

I don't expect students entering this course to have any prior knowledge on concurrency or parallelism (after all, that is the topic of this course). I do expect advanced programming skills. In particular, I will not be explaining standard sequential programming in Java (i.e. I assume you have basic knowledge of object-oriented programming in a mainstream OO language such as C++/Java/C#).

I will introduce standard sequential programming in Erlang and Clojure, so no prior knowledge of these languages is necessary. However, as both of these languages are primarily functional, having had prior exposure to a language with first-class functions and higher-order programming is a big plus. For VUB students, having followed the SICP courses (structure and intepretation of computer programs) should be sufficient. For ULB students, it is highly recommended to first take this course as an elective.

2013-2014 Schedule

Study material

The main study material used in this course are slides, which can be downloaded from Pointcarre. For each lecture, I also provide relevant pointers to the literature (mostly to articles, books or papers freely available online). You are expected to at least read up on the "required reading" material referenced below.

Lecture 1: Introduction

Slides available on Pointcarre.

Source code

Required Reading:

• Herb Sutter, The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Dr. Dobb’s Journal, 30(3), March 2005
• Herb Sutter, James Larus, Software and the Concurrency Revolution, ACM Queue Vol. 3, No. 7, Sept. 2005

• Herb Sutter, Welcome to the Jungle, December 2011. A good article on current hardware trends, including multicore, manycore, hetereogeneous and cloud computing, and their effects on software.
• Charles E. Leiserson, Ilya B. Mirman How to Survive the Multicore Software Revolution (or at Least Survive the Hype)
• Wulf and McKee, Hitting the Memory Wall: Implications of the Obvious and this interesting follow-up.
• Gallery of processor cache effects
• False Sharing:
  • Nicholas Butler, Concurrency Hazards: False Sharing
  • Herb Sutter, Eliminate False Sharing, Dr. Dobb's Journal, May 2009
• Parallel Computing: a Journeyman's Programming Tour (pdf available on Pointcarre)
• The Landscape of Parallel Computing Research: A View from Berkeley

Lectures 2 & 3: Erlang

Slides available on Pointcarre.

Source code

Good, compact overview of the core language:

• Erlang Handbook by Bjarne Däcker (pdf freely available).

• Introductory Erlang course.
• The Erlang website, especially the documentation.
• Recommended books:
  • Programming Erlang (most recent, chapter 20 covers multicore programming in Erlang),
  • Concurrent Programming in Erlang (part 1 freely available).

Lecture 4: Introduction to concurrency in Java

Slides available on Pointcarre.

Source code

Required Reading:

• Course notes A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (Sections 6, 7 and 9). Courtesy of Dan Grossman.

• John Ousterhout, Why threads are a bad idea (for most purposes).

Lectures 5 & 6: Introduction to Clojure, Concurrency in Clojure

Slides available on Pointcarre.

Source code

Required Reading:

• The Clojure website, in particular the rationale and the article on State and Identity.

• Recommended book: Programming Clojure
• Clojure wikibook. The Learning by example section is particularly useful.
• Concurrency and Parallelism in Clojure.
• 4clojure.com is a website full of small problems that allow you to learn Clojure by example.
• clojuredocs.org contains lots of documentation and examples.

Lectures 7 & 8: Software-transactional Memory

Slides available on Pointcarre.

Source code on github

Required Reading:

• Clojure Refs and Transactions.

• Blog post by Daniel Spiwak on adding Software-transactional Memory to Scala.
• Article on STM and STM in Clojure. You can skip the "Clojure STM - Low Level" section.
• Beautiful Concurrency, a paper on Software-transactional memory in Haskell by Simon Peyton-jones.
• Herlihy and Shavit, The Art of Multiprocessor Programming, Chapter 18 on Software Transactional Memory.

Lectures 9 & 10: Fork/Join Parallelism

Slides available on Pointcarre.

Source code

Required Reading:

• Course notes A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (Sections 2-5). Courtesy of Dan Grossman.

• Doug Lea, A Java Fork/Join Framework.
• Charles E. Leiserson and Harald Prokop, A Minicourse on Multithreaded Programming.

Lecture 11a: Advanced shared-memory Concurrency

Slides available on Pointcarre.

Required Reading:

• Course notes A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (Sections 8 and 10). Courtesy of Dan Grossman.

• Textbook: Doug Lea, Concurrent Programming in Java: Design Principles and Patterns.
• Java.util.concurrent API overview.

Lecture 11b: Message-passing Concurrency: Actors vs Threads

Slides available on Pointcarre.

Source code

Required Reading:

• Gul Agha, Concurrent Object-oriented Programming. Communications of the ACM, Vol 33 (9), p. 125, 1990

Lecture 12: Channel-based Concurrency

Slides available on Pointcarre.

Required Reading:

• C.A.R. Hoare, Communicating Sequential Processes. Communications of the ACM, Vol 21 (8), 1978
• The Clojure core.async library.

• Rich Hickey's rationale behind the design of the Clojure core.async library.
• Concurrency in the Go programming language. Go is a relatively new language designed by Rob Pike at Google. It uses a model of concurrency based on CSP, but with weaker guarantees (e.g. processes, called goroutines in Go, are not fully isolated).
• The Occam-pi programming language. Occam-pi was one of the first practical programming languages building upon the CSP channel-based concurrency model.

Lecture 13 (Time permitting): MapReduce

Slides available on Pointcarre.

Source code on github

Required Reading:

• The original OSDI 2004 paper by Dean and Ghemawat (Google).

• 2008 course series on MapReduce at MIT by Google Engineers, in particular the lecture Intro to MapReduce by Michael Kleber, Google.
• Chapter 20 of Programming Erlang discusses a very simplistic MapReduce in Erlang.
• Short MapReduce tutorial and larger course.

Assessment and examination

For the theoretical part of this course, students are expected to attend the lectures and to read the required reading material. For the exercises, students are expected to attend the lab sessions.

Examination for this course is fully project-driven:

• The first programming project is to be made in Erlang (1/3 of the total score). The focus of this project is on the correct use of actors to manage concurrency.
• The second programming project is to be made in Clojure (1/3 of the total score). The focus of this project is on the correct use of shared-memory abstractions to manage concurrency.
• The third programming project is to be made in Java (1/3 of the total score). The focus of this project is on the efficient use of Fork/Join to speed up a computation using parallelism.
• All three projects are to be completed individually.
• All three programming projects must be submitted together with a brief accompanying report (see the project assignment for details on what should be in the report).
• Students must submit a solution for all three projects, and participate in the oral examination, in order to pass this course.

There is no traditional written exam for this course. During the oral exam (~25min), we will discuss your projects. There is no need to prepare a formal presentation. You will be asked to sketch your design, discuss your experiments and relate your findings to the topics seen during the lectures.

Project schedule and deadlines 2013-2014

• Erlang project announcement: 05/03
• Clojure project announcement: 26/03
• submit Erlang project: 27/04
• Java project announcement: 07/05
• submit Clojure project: 18/05
• submit Java project: 15/06
• project defenses 1st session: 24/06 and 25/06

Project assignments are made available via Pointcarré.