Multicore Programming

Spring 2019

Dept. of Computer Science, Vrije Universiteit Brussel

Instructor: Jennifer B. Sartor

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.

In this course, we will study different paradigms that make parallelism/concurrency tradeoffs. The first is message-passing, which we will explore through Erlang. The second is using software transactional memory on a shared-memory machine, which we will explore using Clojure. We will touch on shared-memory programming using Java's threads. Then we will study how to get massive parallelism by programming on Graphics Processing Units (GPUs) using OpenCL. 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
• 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
• General-purpose programming on a Graphics Processing Unit with OpenCL
• (Time permitting: Google's MapReduce abstraction: parallel programming for data centers)
• (Time permitting: OpenMP and MPI)

Schedule

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#). We will look at example code in C and C++ when learning OpenCL, but you can largely program in Python for the project.

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.

Study Material

The main study material used in this course are slides, which can be downloaded from Canvas. For each lecture, I also provide relevant pointers to the literature (mostly to articles, books or papers freely available online). Reading material is listed below, which you are encouraged to read.

Lecture 1: Introduction

Slides available on Canvas.

Source code

Recommended 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 Canvas)
• The Landscape of Parallel Computing Research: A View from Berkeley

Lectures 2 & 3: Erlang

Slides available on Canvas.

Source code

Good, compact overview of the core language:

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

Also, a good paper on how to collect and measure experimental results correctly, and another interesting one:

• Statistically Rigorous Java Performance Evaluation by Georges, Buytaert, and Eeckhout (OOPSLA 2007).
• Rigorous Benchmarking in Reasonable Time by Kalibera and Jones (ISMM 2013).

• 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 Canvas.

Source code

Reading:

• Course notes A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency (Sections 2, 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 Canvas.

Source code

Recommended 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 Canvas.

Source code on github

Recommended 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.

Lecture 9-11: GPU Programming with OpenCL

Slides available on Canvas.

Lab exercises are available for the 3 OpenCL labs, with solutions links included.

Useful Links:

• Hands On OpenCL course that includes the materials used for lectures and lab exercises.
• ACM OpenCL course with extra useful information and slides.
• Wikipedia page about OpenCL.
• Official OpenCL webpage from Khronos.

Lecture 12: Actors vs Threads + Channel-based Concurrency

Slides available on Canvas.

Source code

Recommended Reading:

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

• 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: OpenMP and MPI (time-permitting)

Slides available on Canvas.

Recommended Reading:

• Recent course on OpenMP and MPI from which I'm using the slides, which also has exercises and goes into more depth if you are interested.
• OpenMP consortium webpage
• Message Passing Interface Forum

Lecture 13.5: MapReduce (time-permitting)

Slides available on Canvas.

Source code on github

Recommended 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.

Grading and Assessment

For the theoretical part of this course, students are expected to attend the lectures and are encouraged to read the 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, particular transactional memory.
• The third programming project is to be made in OpenCL (1/3 of the total score). The focus of this project is on the efficient use of the GPU to speed up a computation using a large amount of 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 (~30 minutes), 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.

Academic Honesty

You are required to do your own work. Don't copy code. It's okay to talk about general concepts or algorithms, or even benchmark sets for the projects (if explicitly permitted), but don't share pseudocode or code. You can talk about problems you are having on assignments, but do not show code to classmates to get debugging help. Either use debugging tools or ask the instructor or teaching assistants for more specific help. The best way to do this is to avoid talking to others about the program while you are at the computer. If you have questions on what constitutes cheating or questions about this policy, please talk to the instructor.

Acknowledgements

This course was largely developed by Tom Van Cutsem over the years. I have made small adaptations to it, but it largely remains the class he developed. I thank him for all his materials, including a position paper over the principles of the course, and the slides of his presentation at the Workshop on Curricula on Concurrency and Parallelism.