Multicore Programming

Spring 2019

Dept. of Computer Science, Vrije Universiteit Brussel

Instructor: Jennifer B. Sartor

When: Lectures: Fridays 13:00 - 15:00 (from 15 February until 24 May)     
Labs: Fridays 15:00 - 17:00
Where: SOFT at VUB lectures: room E.3.05, labs: room E.1.5
Instructor Email: jsartor@soft.vub.ac.be
Teaching Assistants: Janwillem Swalens (Erlang and Clojure): jswalens@vub.ac.be and Christophe De Troyer (OpenCL for GPU): cdetroye@vub.ac.be

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:

Schedule

Date Lecture Material Assignment
15 Feb Introduction, Laws of Parallel Programming, Hardware/Software Models N/A
22 Feb Erlang: introduction, sequential programming, concurrent programming N/A
1 Mar Erlang: distributed programming, fault tolerance, simple chat, multicore support Erlang Project due 5 April
8 Mar Java Concurrency: Introduction to concurrency in Java, comparison to Clojure Erlang Project due 5 April
15 Mar Clojure: introduction, sequential programming, sequences Erlang Project due 5 April
22 Mar Clojure: persistent data structures, state and concurrency (refs, atoms, agents) Erlang Project due 5 April
29 Mar Clojure: software-transactional memory, meta-circular implementation in Clojure Erlang Project due 5 April
5 Apr Clojure: software-transactional memory, meta-circular implementation in Clojure Clojure Project due 10 May
Easter break (6 April to 22 April) N/A Clojure Project due 10 May
26 Apr Intro to GPU Programming with OpenCL Clojure Project due 10 May
3 May GPU Programming with OpenCL Clojure Project due 10 May
10 May GPU Programming with OpenCL GPU Project due 10 June
17 May No lecture GPU Project due 10 June
24 May Concurrency: comparison of Java against message passing (Actors vs Threads) + channels GPU Project due 10 June

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:

Additional in-depth reading:

Lectures 2 & 3: Erlang

Slides available on Canvas.

Source code

Good, compact overview of the core language:

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

Additional in-depth reading:

Lecture 4: Introduction to Concurrency in Java

Slides available on Canvas.

Source code

Reading:

Additional in-depth reading:

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

Slides available on Canvas.

Source code

Recommended Reading:

Additional in-depth reading:

Lectures 7 & 8: Software-transactional Memory

Slides available on Canvas.

Source code on github

Recommended Reading:

Additional in-depth reading:

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:

Lecture 12: Actors vs Threads + Channel-based Concurrency

Slides available on Canvas.

Source code

Recommended Reading:

Additional in-depth reading:

Lecture 13: OpenMP and MPI (time-permitting)

Slides available on Canvas.

Recommended Reading:

Lecture 13.5: MapReduce (time-permitting)

Slides available on Canvas.

Source code on github

Recommended Reading:

Additional in-depth reading:

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:

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.