Lesson 14: Concurrency & Parallelism

• video
• Threads cannot be implemented as a library
  Hans-J. Boehm. PLDI 2005.

Gist

• The end of Moore’s law rears its cliché head. The need for parallelism to sustain advances in computing.
• Kinds of parallel programming models.
  • Message passing.
  • Shared memory. (The predominant model in the early 21st century.)
  • Data parallelism.
  • Task parallelism.
  • Actors.
• The problem of semantics in shared-memory multithreading, as demonstrated by an imaginary extension to Bril.

Imagine this setup code:

zero: int = const 0;
one: int = const 1;
a: ptr<int> = alloc one;
b: ptr<int> = alloc one;
store a zero;
store b zero;

that stores 0 in two pointers, a and b. Then imagine these two threads running concurrently:

# thread 1
store a one;
bv: int = load b;

# thread 2
store b one;
av: int = load a;

What are the possible values of av and bv at the end? If you said the set {(0, 1), (1, 0), (1, 1)}, then you’re implicitly imagining that parallel execution looks like an interleaving of the instructions from parallel threads. That would be nice! It’s a memory model called sequential consistency. (For more on memory models, I strongly recommend a primer by Sorin, Hill, and Wood.)

• Sequential consistency and its discontents.
  • The happens-before relation, due to Lamport.
  • Demonstrating a C program that violates SC.
• Memory consistency models, more generally.
  • Defining data races.
  • The C++11 memory model and DRF⇒SC.
  • The Java memory model’s long tale of woe.
• Threads cannot be implemented as a library.
  • Attempt 1: Just compile programs normally, I guess? The lesson is that there need to be special “privileged” operations for synchronization.
  • Attempt 2: Synchronization operations are “black-box” calls that can’t be analyzed interprocedurally. Some very tricky examples due to Boehm where things can go wrong: when optimizations that are perfectly fine in a single-threaded context are completely incorrect in a multi-threaded context, even when there are no threading calls anywhere in sight.

Tasks

There are no tasks for this lesson other than pondering the deep weirdness of programming with shared-memory multithreading. Good luck on your course project!

This is the last lesson of CS 6120. If you’re taking the self-guided version of the course, please fill out this feedback form. I would love to know who has taken the class—and I want your opinions about how to make it better!