Add parallelism

More cores, one memory

A multicore processor puts several cores in one package, sometimes on separate dies called chiplets (Unit 6 returns to them). Each core has its own PC, registers and pipeline, so it can run a different software thread. Caches nearest the cores are often private; farther out, the cores typically share a last-level cache, an interconnect, memory controllers and DRAM bandwidth.

When we say the cores share memory, we mean they can address the same bytes. It does not mean every access takes the same time. In the figure, each core reaches its nearby L1 before going through the shared interconnect. If two cores read the same address, both private caches may keep a copy and serve later reads locally. When one core writes, the caches need a way to prevent the other core from continuing to read its old copy.

The speedup limit: Amdahl's bound

To estimate how dividing work across cores affects execution time, keep the task fixed and separate its original time into serial and parallel portions. Suppose it takes 100 time units on one core: 10 units must run alone, while 90 can be divided evenly. Four cores reduce the parallel part to 90/4 = 22.5 units, but the serial 10 remain. Ideal time is therefore 32.5 units, for a speedup of 100/32.5 ≈ 3.08×.

This is Amdahl's bound. Let s be the serial fraction of the original execution time (not of source lines or operations), and P the number of equally fast cores. If the parallel fraction divides perfectly and adds no overhead, then

speedup ≤ 1 / (s + (1 − s) / P)

Keeping cached copies consistent

Suppose cores A and B have both cached the word x = 0. A writes x = 1 into its own cache. Without coordination between the caches, B could keep reading 0 from its old copy even after A's write completes.

Cache coherence addresses this problem one location at a time. Writes to x have one agreed order. When A takes ownership to write x = 1, B's old cache line becomes invalid: B cannot use those old bits for its next load of x. That load misses and obtains the current value. An invalidation protocol enforces this by granting permission to read or write each line:

Permission applies to a whole cache line, so writing x can also invalidate a cached copy of another variable in that line. This is the cause of false sharing, which we will trace below. Coherence does not make B execute another load, and it does not by itself order accesses to different addresses. Lesson 17 introduces the rules for that ordering.

Cache-line permissions: MSI

In the MSI protocol, each cached line carries one of three states: Modified, Shared or Invalid. The state describes whether this cache may read or write the line; it is separate from the data value stored there:

Try it: two caches, one line

Trace the textbook preset using a pair of states, (A, B). Both begin (I, I). A reads x and gets a copy: (S, I). B reads x too: (S, S). Two readers are allowed.

Now A writes x = 1. It requests ownership, invalidates B, and ends at (M, I). Memory may still say 0; A's M copy is the current one. When B reads again, it misses. In this model A supplies 1 and writes it back, so the pair returns to (S, S) and memory becomes 1. Finally B writes x = 2, leaving (I, M) while memory still says 1. Throughout the trace, the state says who may use a copy; the data value says what a read returns.

Play the preset below, then try your own reads and writes. Watch where the current value lives after each step, as well as the state letters.

False sharing: different variables, same line

Run the false sharing preset with x and y in one line. A only ever touches x and B only ever touches y. They never access the same variable, but each write requires ownership of the whole line. The first write acquires it; each subsequent alternating write transfers ownership to the other core: four ownership requests and three invalidations for four writes. Switch to separate lines and run it again. Each core takes its own line once and then hits in M: two requests and no invalidations.

For any trace, identify who has permission to read or write each line, where the current data lives, and whether writes to different variables require ownership transfers for the same line.

Store buffers let later loads proceed

Lesson 16 established a shared order of writes to x. Ordering operations on x relative to operations on y requires additional rules. Recall Lesson 15: a core can retire a store while its value waits in a store buffer on the way to the coherent cache. The core can continue and load a different address before that store becomes visible to other cores. If two cores both do this, each may read the old value at the other's address, even though each issued its own store first.

Sequential consistency: one order for all accesses

A memory consistency model specifies the permitted results of shared-memory operations. Under sequential consistency (SC), every thread's memory operations must fit in one global list. Each thread's operations keep their own program order in that list, and each load reads the latest write to its address earlier in the list. An outcome that cannot be described by such a list is impossible under SC.

Real CPUs and programming languages often permit additional outcomes to avoid unnecessary waiting; their exact rules differ. Here SC is an abstract baseline for the explorer. C++'s memory_order_seq_cst is a related, but separately defined, language guarantee.

Try it: can both threads read zero?

Start with x = 0 and y = 0. Thread A writes x = 1, then reads y into rA. Thread B writes y = 1, then reads x into rB. Each thread's load asks whether it can see the other's write. Step the two threads in any order. In the store-buffer model, also choose when each buffer drains, making its store visible. The explorer records each final (rA, rB) pair.

To produce (0, 0), first let A buffer x = 1 and B buffer y = 1. Neither store has reached coherent memory. A then reads y = 0; B reads x = 0. Let the buffers drain afterward. Each thread issued its store before its load, but neither load saw the other thread's buffered store. The explorer permits this execution. The next figure shows why SC excludes it.

The well-defined C++ counterpart uses atomic variables, whose individual loads and stores are indivisible with respect to other atomic accesses to the same object. All modifications to one atomic variable have a modification order: a single order for its writes and other updates. This per-variable order does not by itself order operations on x relative to operations on y. With relaxed ordering, (0, 0) is a defined, permitted outcome:

std::atomic<int> x{0}, y{0};
// thread A                                  // thread B
x.store(1, std::memory_order_relaxed);       y.store(1, std::memory_order_relaxed);
int rA = y.load(std::memory_order_relaxed);  int rB = x.load(std::memory_order_relaxed);
// rA == 0 && rB == 0 is allowed. Making all four operations memory_order_seq_cst forbids it.

Follow the "must come before" arrows for (0, 0):

Publishing data safely: release and acquire

A producer-consumer handoff requires a specific relationship: the producer's data write must be ordered before the consumer's data read. Suppose a producer writes data = 42, then signals that the data is ready. A consumer waits for that signal before reading the data. This is a one-shot publication: both objects are initialized before the threads start, ready starts false, one producer sets it true, and no one changes data afterward. In C++:

int data = 0;                       // ordinary, non-atomic
std::atomic<bool> ready{false};

// producer                          // consumer
data = 42;                           while (!ready.load(std::memory_order_acquire)) { }
ready.store(true,                    int v = data;   // guaranteed to see 42
            std::memory_order_release);

The required event is the consumer's acquire load reading the value written by the producer's release store. In C++, this creates a synchronizes-with relationship between those two operations. Combined with the order of statements in each thread, it orders the earlier data write before the later data read:

An acquire load that reads false has not observed the release store, so it establishes no handoff. That is why the consumer loops. Even the correct release/acquire pair makes no promise about when the producer will run or whether the wait will end.

The compiler enforces the language rule using the instructions the target CPU needs. For this pattern on x86, no extra fence instruction is often needed, though the operations still constrain compiler reordering. ARM and RISC-V may need special instructions or fences. The program states the required relationship; the implementation supplies the mechanism.

Separate atomic accesses can lose an increment

Two threads each increment a shared counter using an atomic load followed by a separate atomic store, as in c.store(c.load() + 1). These accesses create no data race: each load and each store is indivisible. The pair remains separate operations, however, so another thread can access the counter between the load and the store:

Atomicity of one variable does not protect a relationship between several variables. Making every field of a structure individually atomic, for example, does not by itself preserve a rule such as "balance equals the sum of entries". A lock can protect the whole update, provided every access that relies on the rule uses the same lock. Choose the tool for the relationship the algorithm needs, then measure its cost under contention.

To explain why a shared-memory program is correct, identify the language-level synchronization relationship: which acquire load reads which release store, or which lock acquisition follows which unlock. Then use the hardware model to explain how the implementation enforces it.

Three ways to share a core

A core may have room to issue several instructions in a cycle while its thread has only one ready instruction, or none while it waits for a cache miss. An operating-system context switch, as in Unit 2, saves one thread's state and restores another's; that is too much work to fill a single empty cycle. Hardware multithreading keeps several thread contexts resident in the core. The core can choose their ready instructions without an OS save-and-restore operation, using extra state and selection logic. The diagrams compare three ways to choose instructions from these contexts:

Separate register state and shared execution resources

Each resident thread needs its own place in the program and its own register values. Otherwise, two threads that both use the name x5 would overwrite each other's state. Their instructions can execute using the same ALUs and other execution units:

The operating system sees each hardware context as a separate logical processor and schedules software threads onto them. A chip with 4 cores × 2 contexts shows the OS 8 logical processors. Each pair shares the execution resources of one core. The OS can schedule many more software threads by taking turns, saving and restoring their state through memory as in Unit 2.

Try it: two dependency chains, one core

Thread A runs x5 = x5 + 1 four times starting from 0. Thread B runs x5 = x5 + 10 four times starting from 100. Each is a chain: every add needs the previous result, and in this model a result is usable the next cycle. Both threads use the name x5; it refers to each thread's own architectural register.

Count both threads finished separately from A finished. On two ports, A alone finishes its four adds in cycle 4. Alternating one thread per cycle makes A finish in cycle 7 and B in cycle 8. Ideal SMT finishes both in cycle 4. The eight-to-four comparison is a gain in combined throughput; A itself still needs four dependent steps.

Combined throughput and each thread's completion time

In the model, A completes one dependent add per cycle and B uses the other port, increasing the total work completed per cycle. Real threads also compete for caches, queues and bandwidth. Adding another thread on the same core, an SMT sibling, may slow the original thread even while total work per second rises. If the workload already saturates memory bandwidth, an additional sibling may offer little benefit or reduce throughput through contention. Whether SMT helps depends on the workload, the latency goal and the core. Shared resources can also leak timing information between siblings, which matters for security isolation.

Draw two register contexts connected to one shared set of execution resources. Then draw two physical cores, and explain what the second drawing has that the first doesn't.

Scalar versus vector

Suppose we compute c[i] = a[i] + b[i] for a long array. A scalar add instruction adds one pair of values. Scalar code repeats two loads, an add, a store and loop bookkeeping for each element. A vector add instruction can instead name four elementwise additions at once. The arithmetic still happens four times, but grouping it under fewer instructions can reduce the work of fetching, decoding and scheduling the loop. This groups independent array operations within one thread.

The figure counts only the add instructions. A complete loop still loads both inputs and stores the outputs; the vector version groups those memory operations too. The time needed for one vector instruction depends on how the hardware processes its elements.

Register capacity, active elements and physical lanes

A register's bit width is its storage capacity. Dividing it by the element width, the number of bits per value, tells us how many elements fit. An instruction may use only some of those positions. The hardware performs the element operations in datapaths called physical lanes; for a given operation and element width, the lanes determine how many elements it can process side by side.

Fixed-width SIMD, such as x86 SSE/AVX and Arm NEON, specifies register widths in the instruction set. Scalable vector instruction sets, such as Arm's Scalable Vector Extension (SVE) and RISC-V's V extension, allow a loop to adapt to implementations with different register lengths. A RISC-V V loop asks vsetvl how many elements to process in its next group, then uses the returned count:

In RISC-V V, VLEN is the number of bits in one vector register, SEW is the selected element width in bits, and LMUL is the vector register group multiplier. LMUL determines the register capacity used by an operand: one register, a group of registers, or a fraction of one. The maximum element count for that configuration is VLMAX = VLEN × LMUL / SEW. For VLEN = 128 bits, LMUL = 1 and SEW = 32 bits, VLMAX = 4. This is a capacity limit; physical lanes and execution time depend on the implementation.

The returned vl selects the element count for the current iteration. The tail is the final partial group when the number of remaining elements is smaller than the group's capacity. A RISC-V loop handles it by using a smaller count. Often vl equals min(remaining, VLMAX), but the specification permits other values in some cases; advancing by the returned count keeps the loop correct.

A mask, also called a predicate, selects active positions individually with on/off bits. Arm SVE commonly uses predicates to handle a tail: an instruction such as whilelt marks positions whose indices are less than N, and the loop can advance by the implementation's vector length. The explorer below models this masked approach.

Handle the last partial group

With ten elements and groups of four, the first two groups cover positions 0–3 and 4–7. The last group reaches positions 8–11, but only 8 and 9 exist. A mask turns off the final two positions. In this model, masked-off positions make no memory access; they neither read past the array nor write output. Reading past the end and discarding the extra values afterward would still touch memory the program may not own.

Lower position utilization does not by itself mean a slower loop: width 8 uses fewer group instructions. It also does not reduce the useful data needed by the computation. Every element still needs two 4-byte inputs and one 4-byte output, or 12 bytes of logical array traffic.

Dependencies, reductions and data layout

The elementwise addition above is a candidate for vectorization, replacing scalar loop operations with vector operations, because each c[i] can be computed independently, provided the output does not overlap inputs in a way that creates a dependency. A loop-carried dependency occurs when one iteration uses a result from another. A reduction, such as summing an array into one value, combines results from different positions. The figure shows both cases:

A compiler must preserve the program's result when it changes the order of iterations. With exact integer arithmetic, the recurrence on the left can be rewritten as a[i] = a[0] + i, making each result independent. Applying that rewrite to a program also requires checking its arithmetic rules: overflow or floating-point rounding can make the expressions behave differently. More generally, a compiler needs to prove that a vector schedule preserves the required dependencies, or use a runtime check to select a safe version. Array overlap matters when it creates such a dependency: a[i] = a[i] + b[i] works if a and b name the same array, whereas an offset overlap can make one iteration rely on a neighbor's write.

Reductions pose a different issue. A tree combines values efficiently, but it changes the grouping of additions. With floating-point numbers, that can change rounding, so a vector sum may not be bit-identical to a sequential left-to-right sum.

Data layout affects the loads that feed these operations. Suppose records are stored as [{x, y}, {x, y}, …], an array of structures. A loop that uses only x reads values separated by each record's y. In a structure of arrays, x[] and y[] are separate, so successive x values are adjacent. Contiguous values usually suit vector loads better when a loop uses many elements of one field. A gather instruction can load elements from separate addresses; how many cache lines those addresses touch still affects the cost. If vector instructions increase the rate of arithmetic enough, memory bandwidth can limit further speedup.

Distinguish a software thread, a hardware context, a vector element and a physical lane. Then handle a tail safely with a mask or a returned vector length.

Consider two software threads running on different physical cores. Each adds a 10-element slice of two arrays using width-4 vectors, then increments its own "done" counter. Their output elements do not overlap, but their counters occupy the same cache line. Before opening the answer, count the vector groups and useful bytes, then identify cache lines that both cores write.

A program can combine all four forms of parallelism. The gain still depends on how much independent work exists and which resource limits it. For a side-by-side view of hardware organizations and programming models, see A map of parallel machines and programs. Unit 5 takes the same questions to GPUs: many more logical threads, groups executing together, and a memory system that must keep them supplied.

Model assumptions and further reading

Every explorer on this page is a teaching model: coherence steps are whole transactions, the ordering explorer models only store buffers, the SMT explorer models only issue ports, and the vector explorer models only groups and masks. For the precise rules, go to the primary sources:

• C++ memory model: data races and happens-before, atomic ordering (release, acquire, seq_cst), and std::barrier (working draft of the standard).
• x86: Sewell, Owens et al., x86-TSO, the store-buffer model this page's explorer simplifies.
• SMT: Intel's 64 and IA-32 Architectures Optimization Reference Manual, on which resources hardware threads share.
• Vectors: the RISC-V "V" vector extension (vsetvl, VLMAX, tail handling) and Arm's introduction to SVE (predicates, whilelt).