Multicore Programming

Spring 2017

Dept. of Computer Science, Vrije Universiteit Brussel

Instructor: Jennifer B. Sartor

When: Lectures: Wednesdays 13:00 - 15:00 (lectures from 15 February until 24 May)      Labs: Wednesdays 10:00 - 12:00 (covering the material of the week before, so starting on 22 February)
Where: SOFT at VUB lectures: room D.3.08, labs: room E.1.7
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 16 April
8 Mar Java Concurrency: Introduction to concurrency in Java Erlang Project due 16 April
15 Mar Clojure: introduction, sequential programming, sequences Erlang Project due 16 April
22 Mar Clojure: persistent data structures, state and concurrency (refs, atoms, agents) Erlang Project due 16 April
29 Mar Clojure: software-transactional memory, meta-circular implementation in Clojure Erlang Project due 16 April
Easter break (1 April to 16 April) N/A Erlang Project due 16 April
19 Apr @ 10am Clojure: software-transactional memory, meta-circular implementation in Clojure Clojure Project due 14 May
19 Apr @ 1pm Intro to GPU Programming with OpenCL Clojure Project due 14 May
26 Apr No lecture, but 2 lab sessions at 10am and at 1pm Clojure Project due 14 May
3 May GPU Programming with OpenCL Lab exercises Clojure Project due 14 May
10 May GPU Programming with OpenCL Lab exercises Clojure Project due 14 May
17 May Concurrency: comparison of Java against message passing (Actors vs Threads) + channels GPU Project due 11 June
24 May OpenMP and MPI or MapReduce GPU Project due 11 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#).

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

Source code

Recommended Reading:

Additional in-depth reading:

Lectures 2 & 3: Erlang

Slides available on Pointcarre.

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

Source code

Reading:

Additional in-depth reading:

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

Slides available on Pointcarre.

Source code

Recommended Reading:

Additional in-depth reading:

Lectures 7 & 8: Software-transactional Memory

Slides available on Pointcarre.

Source code on github

Recommended Reading:

Additional in-depth reading:

Lecture 9-11: GPU Programming with OpenCL

Slides available on Pointcarre.

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

Useful Links:

Lecture 12: Actors vs Threads + Channel-based Concurrency

Slides available on Pointcarre.

Source code

Recommended Reading:

Additional in-depth reading:

Lecture 13: OpenMP and MPI (time-permitting)

Slides available on Pointcarre.

Recommended Reading:

Lecture 13.5: MapReduce (time-permitting)

Slides available on Pointcarre.

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 (~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.

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