Multicore Programming

2011-2012

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

Lecturer: Tom Van Cutsem

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 summary below below (full exam/project details here).

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: laws, scalability (speedup and efficiency)
• 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: channels (Occam-pi) and actors
• Actors in practice: an introduction to Erlang
• Google's MapReduce abstraction: parallel programming for data centers
• Practical functional programming: an introduction to Clojure
• Software-transactional memory

2011-2012 Schedule

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

Required Reading:

• Part 1 of Concurrent Programming in Erlang, 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, see above).

Lectures 4 & 5: 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.

Lectures 5 & 6: Shared-memory Concurrency

Slides available on Pointcarre.

Source code

Required Reading:

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

• Textbook: Doug Lea, Concurrent Programming in Java: Design Principles and Patterns.
• Java.util.concurrent API overview.
• John Ousterhout, Why threads are a bad idea (for most purposes).

Lecture 7: Message-passing Concurrency: Actors vs Threads, Channels

Slides available on Pointcarre.

Source code

Required Reading:

• Gul Agha, Concurrent Object-oriented Programming. Communications of the ACM, Vol 33 (9), p. 125, 1990
• C.A.R. Hoare, Communicating Sequential Processes. Communications of the ACM, Vol 21 (8), 1978

• The Occam-pi programming language.
• The JCSP library.

Lecture 8: 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.

Lectures 9 & 10: 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.
• 4clojure.com is a website full of small problems that allow you to learn Clojure by example.

Lectures 11 & 12: 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.

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 is as follows:

• After each lecture, students participate in a short quiz via Pointcarré. Students get 1 week to participate. Participation will be valued more highly than strict correctness of the results. (20% of the total score)
• Examination will proceed via two programming projects:
  • one to be solved in the Erlang programming language (40% of the total score)
  • one to be solved in the Clojure programming language (40% of the total score)

Students must participate in all three tasks (quiz, Erlang project, Clojure project) in order to pass.

Full exam/project details.