Lecture 6: Multicore Programming

What this lecture covers

This lecture explains why modern processors have multiple cores instead of one fast core, and surveys the software tools used to program them. It follows a lecture on general performance engineering and precedes deeper coverage of races, parallelism analysis and scheduling in this course on performance engineering.

After watching, you should be able to explain why clock speeds stalled around 2004, describe at a high level how the MSI cache coherence protocol keeps shared memory consistent across cores, and compare four concurrency platforms — Pthreads, Intel Threading Building Blocks, OpenMP and Cilk — using the same recursive Fibonacci example implemented in each.

Key ideas

• End of clock scaling: shrinking transistors let voltage drop and clock frequency rise while holding power density constant, until leakage current stopped further voltage reduction around 2004-2005, capping clock speed near 4 GHz.
• Chip multiprocessor (CMP): the response to that wall — using the transistors Moore's law still provides to add more cores per chip rather than a faster single core.
• Cache coherence: the problem of keeping cached copies of the same memory location consistent across cores after one core writes to it.
• MSI protocol: a basic coherence protocol where each cache line is Modified, Shared, or Invalid; a write to a Shared line invalidates all other cached copies of that line.
• Concurrency platform: software that abstracts processor cores and handles synchronization, communication and load balancing so programmers don't implement these by hand.
• Fork-join parallelism: the pattern used throughout the lecture's Fibonacci example, where independent recursive calls can run concurrently and then join before combining results.
• Work stealing: the scheduling approach Cilk uses to balance tasks dynamically across cores, with a provable efficiency guarantee that OpenMP's and TBB's schedulers lack.
• Serial elision: in Cilk, removing the cilk_spawn/cilk_sync/cilk_for keywords yields a valid, correct sequential program, which makes debugging correctness separately from parallel performance easier.

Walkthrough

Why multicore (1:01)

The lecture opens with Moore's law (transistor counts doubling roughly every two years) and the flattening of clock frequency around 2004-2005. Shrinking transistors previously allowed lower voltage and higher frequency at constant power density, but leakage current stopped further voltage reduction. Projections showed that continuing to raise frequency would push power density past that of a nuclear reactor and eventually the sun's surface, so vendors redirected the extra transistors into multiple cores per chip instead.

Abstract multicore architecture and cache coherence (7:05)

The lecture introduces a simplified chip multiprocessor model: cores with private caches, a shared last-level cache, a shared memory controller, and I/O, all connected by a network. It then works through an example of stale cached data after one processor updates a shared value, motivating the MSI protocol: cache lines (64 bytes on the course machines) are tagged Modified, Shared or Invalid, and a modifying write invalidates other cached copies of that line, which can cause performance-costly "invalidation storms" when many cores write the same location.

Concurrency platforms and the Fibonacci example (19:26)

A recursive, deliberately inefficient (exponential-time) Fibonacci function is used as a running example because its two recursive calls are independent and can run in parallel, recursively, at every level of the call tree. The lecture implements this same function under each of four platforms.

Pthreads (24:36)

Pthreads is described as a low-level, do-it-yourself API: pthread_create and pthread_join manage threads directly. The Fibonacci implementation only spawns one thread per call (not recursively), giving at most a 1.5x speedup on two cores, and requires manual argument marshalling through a struct. The lecture calls this style similar to programming in assembly before compilers existed, and lists its problems: high thread-creation overhead (over 10^4 cycles), limited scalability, poor modularity, and error-prone manual load balancing.

Threading Building Blocks (39:47)

TBB, a C++ library from Intel, lets programmers define tasks (via an execute function) rather than manage threads directly, using a work-stealing scheduler. Its Fibonacci implementation recursively spawns child tasks, extracting more parallelism than the Pthreads version. TBB also provides parallel for/reduce templates, concurrent container classes, and mutual exclusion primitives.

OpenMP (45:02)

OpenMP uses compiler pragmas (#pragma omp task, #pragma omp taskwait, shared/private clauses) to mark parallel regions in C, C++ or Fortran, again running on native threads underneath. The Fibonacci example is shown to be much shorter than the Pthreads version. OpenMP supports loop parallelism, reductions, several scheduling policies and standard synchronization constructs like barriers and atomics.

Cilk Plus (50:05)

Cilk Plus (the platform used for the rest of the course) adds cilk_spawn, cilk_sync and cilk_for as small linguistic extensions to C/C++, plus vector-parallelism features. Cilk's scheduler uses work stealing and is provably efficient, unlike OpenMP's or TBB's. The lecture shows the Fibonacci example (cilk_spawn/cilk_sync), a parallel in-place matrix transpose using cilk_for, and warns that a naive cilk_for summation into a shared variable creates a determinacy race — solved with a Cilk reducer (CILK_C_REDUCER_OPAD). It also covers the serial elision property, the Cilksan race detector, and the Cilkscale scalability analyzer.

Before you watch

• Review earlier lectures in this course on caches and coarsening, since the coherence and coarsening ideas here build on that material.
• Basic familiarity with C/C++ function calls and pointers helps with the Pthreads and TBB code walkthroughs.

Check your understanding

1. Why did chip vendors stop increasing clock frequency around 2004-2005, and how did they use the transistors Moore's law kept providing instead?
2. In the MSI protocol, what happens to other caches' copies of a cache line when one processor writes to it?
3. Why does the Pthreads implementation of Fibonacci in the lecture only achieve about a 1.5x speedup on two cores?
4. What does "serial elision" mean in Cilk, and why is it useful for debugging?
5. Why does a naive parallel loop that increments a shared sum variable produce incorrect results, and how does a Cilk reducer fix it?