Multicore Processing

01 Introduction

Until the mid-2000s, CPU clock speeds grew steadily and single-threaded programs grew faster for free. That ended. Modern CPUs gain performance by adding cores rather than by increasing clock speed, because pushing the clock higher runs into hard physical limits on power consumption and heat dissipation. For software to benefit from this generation of hardware, it must expose parallelism — and threads are the primary mechanism for doing so.

The kernel-thread model from Lesson 4.3 makes parallelism possible: the kernel can dispatch different threads of the same process onto different CPU cores simultaneously. This lesson examines whether it delivers what it promises. The short answer is that parallelism is real, but scaling is sublinear — a program that uses four threads on a four-core machine does not complete in a quarter of the time, and the reasons why are deeply informative about how modern hardware works.

The lesson covers five topics. First, the distinction between concurrency and true parallelism. Second, the hardware mechanisms that make parallelism possible and the costs they impose: caches, cache coherence, and false sharing. Third, the memory consistency models that define what reorderings are permitted and how languages expose them. Fourth, Amdahl's law, which formalises why speedup is sublinear. Fifth, the practical limits — lock contention, memory bandwidth, synchronization overhead, and NUMA effects — that shape the design of parallel programs. By the end, you will have both the theory that predicts scaling and the measurement techniques to verify it empirically.

02 Learning objectives

This lesson contributes to U4.3 and to course learning outcomes CLO2 and CLO8.

03 Required reading

• OSTEP — Chapter 26, the section on hardware considerations in concurrency. OSTEP's treatment of cache coherence and memory barriers is concise and approachable.
• Operating System Concepts — Chapter 4, Section 4.5, Multicore Programming. The classical presentation of the challenges of parallel programming.
• Patterson & Hennessy — Computer Architecture: A Quantitative Approach, the chapter on memory hierarchy and multiprocessor systems. For the hardware side of cache coherence.
• Amdahl, G. M. — Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. AFIPS, 1967. The original paper introducing the speedup law.
• Linux man pages: man 1 taskset, man 1 lscpu, man 1 perf-stat, man 7 numa. These tools let you observe the multicore behaviour discussed in the lesson.

04 Core content

4.1 Concurrency versus parallelism

The two terms are often used interchangeably, but they describe different things. Getting the distinction right is the foundation of everything that follows.

Concurrency

Multiple tasks are making progress during the same time period. On a single CPU core, concurrency is achieved by rapid context switching — the processor alternates between tasks so quickly that they appear to run at once, but only one is executing at any instant. Concurrency is about dealing with many things at once.

Parallelism

Multiple tasks are executing at the same instant, on different CPU cores. This requires hardware with more than one core. Parallelism is about doing many things at once.

A multithreaded program on a single-core machine is concurrent but not parallel: the threads interleave on one core. The same program on a multicore machine is both concurrent and parallel: the threads genuinely execute at the same time. The thread abstraction is the same in both cases; only the hardware changes what is achieved.

A useful way to remember the distinction: concurrency is a program property, parallelism is a hardware property. You can write concurrent code that runs on any machine. Whether it runs in parallel depends on how many cores the machine has.

4.2 The hardware: cores, caches, and coherence

Every core in a modern CPU has its own private L1 cache (and often its own L2 cache), and the cores share a larger L3 cache and the main memory. This design is what makes parallelism fast: each core can service most of its memory accesses without contending with the others. But it also creates a fundamental problem, because the same memory location may be cached in the private caches of several cores at once.

Suppose core 0 writes to address X, and later core 1 reads address X. If core 1's copy of X is stale — because core 0's write did not propagate to it — core 1 will read the wrong value. The hardware must prevent this. The mechanism that ensures every core sees a consistent view of memory is called cache coherence.

Cache coherence is maintained by a hardware protocol, of which the most common family is MESI (and its variants). Under MESI, each cache line is in one of four states:

• Modified (M). This core has a dirty copy — it has been written to and the write has not yet reached main memory. No other core has a valid copy.
• Exclusive (E). This core has a clean copy matching main memory, and no other core has a copy. It can transition to Modified on a write without notifying anyone.
• Shared (S). Multiple cores have clean copies matching main memory. Any core can read the line; a write requires coordination with the others.
• Invalid (I). This core's copy is stale or absent. A read or write will miss and must fetch from another core or from main memory.

When a core wants to write to a line that is currently Shared, it must first invalidate the copies in the other caches — a process that involves sending messages on the coherence bus. When a core reads a line that another core holds in Modified state, the modified copy must be written back or forwarded before the read can proceed.

Coherence traffic is the fundamental cost of sharing mutable data across cores. When a variable is written frequently by several cores, each write forces the others to invalidate their copies, and each subsequent read requires a fetch. The line bounces between cores at cache-line granularity, and the effective cost of a write becomes the cost of the coherence protocol rather than the cost of a local cache update.

4.3 False sharing

The coherence protocol operates on cache lines — typically 64 bytes on x86-64 — not on individual variables. This leads to a subtle and surprisingly impactful performance problem.

Consider two threads running on two cores, each incrementing its own private counter. The counters are declared as adjacent elements of an array:

struct counters {
    long a;   /* thread 0 increments this */
    long b;   /* thread 1 increments this */
} c;

Logically, the two threads never touch the same variable. In a correct memory model, there is no reason for them to slow each other down. But a and b are adjacent in memory — 8 bytes each, so both live in the same 64-byte cache line. When thread 0 writes to a, the coherence protocol invalidates the line in thread 1's cache. When thread 1 writes to b, it invalidates the line in thread 0's cache. The line bounces between the two cores at every increment, and throughput collapses.

This is false sharing: sharing that exists at the cache-line level but not at the level of the program's logic. It is called "false" because the threads do not actually share the variables; they only share the cache line that happens to contain them.

False sharing is easy to demonstrate and easy to fix once you know about it. The fix is padding: ensure that variables written by different threads fall on different cache lines. The exact size of the padding must match the cache line size of the target architecture — 64 bytes on x86-64 and most ARM cores today, 128 bytes on some others — and cross-platform code often pads to a safe upper bound.

The classic way to express padding in C is with a union or a char array sized to force alignment:

#define CACHE_LINE_SIZE 64

struct padded_counter {
    long value;
    char padding[CACHE_LINE_SIZE - sizeof(long)];
};

Modern C and C++ offer a portable alternative: alignas(64) or _Alignas(64) can be applied to a variable to force it onto a 64-byte boundary, and the compiler handles the layout. Either approach gives the same result: the two variables end up in different cache lines, and the coherence traffic disappears.

4.4 Memory consistency models

Cache coherence ensures that every core sees a consistent view of a single memory location. A related but distinct question is what order the operations on different memory locations appear to happen in. This is the domain of the memory consistency model.

The problem is that modern CPUs reorder memory operations for performance. When the programmer writes code that stores to A and then stores to B, the hardware may reorder these operations on the bus — because they are to different addresses, there is no hardware reason to keep them in order. If the program requires A to be visible before B, this reordering breaks the program's assumptions.

A memory consistency model is a formal specification of what reorderings the hardware is permitted to make. Three models matter in practice:

Sequential consistency

Every memory operation appears to happen in program order, and every thread's operations appear in a single global order that is consistent across all threads. This is the strongest model and the easiest to reason about — it matches the intuition most programmers have. It is also the most expensive to implement, because it requires the hardware to enforce the ordering on every operation. No modern general-purpose CPU provides it by default for all operations.

Total Store Order (TSO)

The x86 and x86-64 model. Stores may be reordered with subsequent loads to different addresses, but not with each other, and loads are not reordered with each other. The reordering that is permitted corresponds to the CPU's store buffer: a store may still be in the buffer when a later load executes, so the load does not see the store's effect. TSO is close to sequential consistency in practice, and x86 programmers can usually write correct concurrent code without explicit memory barriers — but not always.

Relaxed (or weakly ordered)

The ARM and POWER models. Almost no ordering is guaranteed: loads and stores may be reordered against each other, in essentially every combination. Correct code must insert explicit memory barriers, or use language-level primitives that do so. ARM has been the dominant mobile architecture for years and is now on the desktop through Apple Silicon, so even programmes that used to target x86 only must now be written to handle relaxed ordering.

Programming languages abstract over the hardware models. In C11 and C++11 and later, the <stdatomic.h> and <atomic> headers provide atomic operations with an explicit memory-ordering argument:

• memory_order_relaxed — atomicity only, no ordering.
• memory_order_acquire — no subsequent operations may be reordered before this one.
• memory_order_release — no prior operations may be reordered after this one.
• memory_order_acq_rel — both acquire and release.
• memory_order_seq_cst — the strongest, matching sequential consistency. The default if unspecified.

The reason this matters for multicore programming is that correct synchronization depends on the ordering model. A lock that appears correct on x86 may fail on ARM if it uses only relaxed atomics, because the compiler and the CPU are free to reorder the operations that the lock depends on. Getting this right is subtle, and it is a good reason to use the standard synchronization primitives (mutexes, condition variables, C11 atomics with proper ordering) rather than hand-rolling your own.

4.5 Amdahl's law

Even when a program has no cache-coherence problems and no synchronization, its speedup from parallelism is bounded. The bound is expressed by Amdahl's law, which answers the question: if a fraction p of a program's work is parallelisable and the remaining fraction s = 1 − p is inherently serial, what speedup is possible with N processors?

speedup(N) = 1 / (s + p / N)

The law shows that the serial fraction dominates the result. As N grows large, the speedup approaches 1/s, which is the maximum speedup the program can ever achieve, no matter how many cores are available.

The table is the practical heart of the lesson. Even a modest serial fraction — 10% — caps the speedup at 10× no matter how many cores the machine has. And with 25% serial, the ceiling is 4×, which is achieved at around sixteen cores: adding more cores beyond that buys almost nothing.

In real programs, the "serial fraction" includes more than just the code that cannot be parallelised. It includes the initialization phase, the final reduction of partial results, the portion of the work performed while holding a lock, and the overhead of thread creation and synchronization. Because each of these grows as threads are added to the system, the effective serial fraction often increases with N, making scaling worse than Amdahl's law alone predicts. This observation is formalised in a related law — Gustafson's law — which considers a fixed problem size per core rather than a fixed total problem size, and gives a much more optimistic view. Amdahl's law is the right model when the goal is to finish a fixed job faster; Gustafson's law is the right model when the goal is to solve larger problems in the same time.

4.6 Practical scaling limits

Beyond Amdahl's law and cache coherence, four specific mechanisms limit the scaling of real parallel programs.

4.7 Multicore scheduling in Linux

The kernel's scheduler plays a central role in determining how well a parallel program scales. Linux's multicore scheduler has three main concerns:

• Load balancing. When a CPU core becomes idle and there are runnable tasks on other cores, the kernel migrates a task to the idle core. This is done by a per-core idle balancer that runs when a core has no work, and by periodic load-balancing passes.
• Affinity and cache locality. Moving a task between cores destroys its cache locality — the L1 and L2 caches on the new core do not hold the task's working set. The kernel therefore tries to keep each task on the same core when possible, migrating only when the benefit of balancing outweighs the cost of the migration.
• NUMA awareness. On multi-socket systems, the scheduler tries to keep threads on the socket where their memory is allocated, and to migrate threads between sockets only when necessary. On Linux, NUMA balancing is a configurable feature and interacts closely with the memory manager.

From user space, several tools let you influence or observe these decisions. The taskset command pins a process or thread to a specific set of cores. The numactl command controls memory placement on NUMA systems. Both are covered in the interactive activity below.

4.8 Measuring parallel speedup

The metrics that matter for a parallel program are the same ones used in Unit 3 for scheduling, adapted to the parallel setting:

• Speedup. The ratio of the time to complete the task on one core to the time on N cores. S(N) = T(1) / T(N).
• Efficiency. The speedup divided by the number of cores. E(N) = S(N) / N. An efficiency of 1.0 means perfect scaling; anything less indicates overhead or a serial fraction.
• Scalability. How the speedup or efficiency changes as N grows. A program is scalable if the speedup continues to grow roughly linearly (or at least continues to grow usefully) as cores are added.

Measuring these values is a matter of running the same workload under different thread counts and recording the elapsed times. The worked example below walks through this in detail, and the interactive activity has you perform the measurement on your own VM.

4.9 What scalable parallel programs look like

Programs that scale well tend to share a set of design characteristics. If you are writing parallel code, these are the principles to keep in mind.

• Partition the work, not the data structure. Split the computation into independent pieces that touch disjoint regions of memory. Each thread works on its own slice, and no coordination is needed while the work is being done.
• Reduce shared mutable state. The less shared mutable state a program has, the less synchronization it needs and the fewer coherence events it generates. Prefer immutable data, thread-local accumulators, and per-thread copies that are combined at the end.
• Combine partial results at the end. Each thread produces its own partial result, and a single reduction step at the end combines them. This is the canonical "map-reduce" pattern and it eliminates almost all synchronization from the hot path.
• Watch the cache. Design data structures for cache locality. If a thread reads a batch of nearby items rather than scattered items, it uses its cache more efficiently and the coherence traffic goes down.
• Pad shared structures. Any struct that has fields written by different threads should be padded to avoid false sharing.
• Measure, do not assume. The interaction between the workload, the hardware, and the scheduler is complex enough that predictions are unreliable. Measure the speedup at several thread counts and observe where it stops improving.

05 Worked example

To make the concepts concrete, measure the speedup of a simple parallel workload at increasing thread counts, and then demonstrate the effect of false sharing by measuring two versions of the same computation.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

#define N 1000

static double A[N][N];
static double B[N][N];
static double C[N][N];

typedef struct { int row_start, row_end; } chunk_t;

static void *worker(void *arg) {
    chunk_t *c = arg;
    for (int i = c->row_start; i < c->row_end; i++) {
        for (int j = 0; j < N; j++) {
            double s = 0.0;
            for (int k = 0; k < N; k++) s += A[i][k] * B[k][j];
            C[i][j] = s;
        }
    }
    return NULL;
}

int main(int argc, char **argv) {
    int nthreads = (argc > 1) ? atoi(argv[1]) : 1;

    /* Initialise A and B */
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) { A[i][j] = i + j; B[i][j] = i - j; }

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);

    pthread_t t[nthreads];
    chunk_t   c[nthreads];
    int per = N / nthreads;
    for (int w = 0; w < nthreads; w++) {
        c[w].row_start = w * per;
        c[w].row_end   = (w == nthreads - 1) ? N : (w + 1) * per;
        pthread_create(&t[w], NULL, worker, &c[w]);
    }
    for (int w = 0; w < nthreads; w++) pthread_join(t[w], NULL);

    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("threads=%d  time=%.3f s\n", nthreads, elapsed);
    return 0;
}

gcc -Wall -Wextra -g -O2 -pthread -o matmul matmul.c
for n in 1 2 4; do ./matmul $n; done

threads=1  time=8.10 s
threads=2  time=4.15 s
threads=4  time=2.30 s

threads=8  time=1.95 s
speedup:  4.15×
efficiency: 0.52

/* Version A — no padding, all counters share a cache line */
struct counters_a {
    long value[4];
} ca;

/* Version B — padded, each counter on its own cache line */
struct counters_b {
    long value;
    char padding[64 - sizeof(long)];
} cb[4];

Version A (no padding):
    time:        8.42 s

Version B (padded):
    time:        0.31 s

speedup:         27×

perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./program

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• Concurrency means tasks make progress during the same time period; parallelism means they execute at the same instant on different cores. Concurrency is a program property; parallelism is a hardware property.
• Multicore hardware has private per-core caches and shared main memory. Cache coherence protocols such as MESI ensure every core sees a consistent view of memory, at the cost of coherence traffic when mutable data is shared.
• False sharing occurs when two threads write distinct variables that happen to occupy the same cache line. The line bounces between cores on every write, often destroying performance. The fix is padding to separate cache lines.
• Memory consistency models — sequential consistency, TSO, relaxed — specify what reorderings the hardware permits. Portable concurrent code uses language-level atomic operations with explicit memory-ordering arguments rather than relying on any hardware model.
• Amdahl's law bounds the speedup of a parallel program by its serial fraction. A 10% serial fraction caps speedup at 10×, regardless of how many cores are available.
• Other practical limits on scaling: lock contention, memory bandwidth, synchronization overhead, and NUMA effects. Each one bounds speedup independently of the core count.
• Scalable parallel programs partition work rather than data structures, minimise shared mutable state, combine partial results at the end, watch cache locality, pad shared structures, and measure rather than assume.
• Linux's scheduler balances load across cores, preserves cache and NUMA locality where possible, and exposes controls (taskset, numactl) for pinning threads to specific cores.

11 References

• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 26. Available online at ostep.org.
• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 4, Section 4.5.
• Amdahl, G. M. Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. AFIPS, 1967.
• Patterson, D. A., & Hennessy, J. L. Computer Architecture: A Quantitative Approach, 6th ed., Appendix B (memory hierarchy) and Chapter 5 (thread-level parallelism). Morgan Kaufmann, 2017.
• McKenney, P. E. Is Parallel Programming Hard, And, If So, What Can You Do About It? Available online at kernel.org/pub/linux/kernel/people/paulmck/perfbook/.
• Drepper, U. What Every Programmer Should Know About Memory. Red Hat, 2007.
• Linux man-pages: man 1 lscpu, man 1 taskset, man 1 numactl, man 1 perf-stat.