Chapter 39 of 39

Multicore Processors & Cache Coherence

Open your phone's settings and you will probably see something like "octa-core processor". Your laptop likely has between 4 and 16 cores. Twenty years ago almost every desktop chip had exactly one. What changed, and what new problems appeared when several cores started sharing the same memory?

This chapter answers both questions. First we see why the industry moved to multicore and how a multicore chip is organised. Then we study the central hardware problem of shared-memory multiprocessors: cache coherence, and the protocols (MSI, MESI, directories) that solve it.

A multicore processor (chip multiprocessor, CMP) is a single chip containing two or more independent processor cores, each able to run its own instruction stream, that share some on-chip resources (typically the last-level cache, the memory controller and the interconnect) and a single physical address space.

In terms of Parallel Processing & Flynn's Classification, a multicore chip is a MIMD shared-memory machine on one piece of silicon.


Why Multicore? The Power Wall

For decades, performance came from raising the clock frequency and from more instruction-level parallelism. Around 2004-2005 both ran into limits:

  • Power wall. The dynamic power of CMOS logic is roughly P = C x V2 x f (C: switched capacitance, V: supply voltage, f: clock frequency). Higher f also needs higher V, so power climbs much faster than performance. Chips reached the limit of what can be cooled (around 100 W or so for a desktop chip).
  • ILP wall. As we saw in Instruction-Level Parallelism & Superscalar Processors, wider and deeper cores give diminishing returns.
  • Memory wall. DRAM latency improved far more slowly than processor speed.

Meanwhile, Moore's law kept giving designers more transistors. The answer was to spend them on more cores rather than on one faster core.

A Quick Calculation

Suppose we lower both voltage and frequency by 15%. Power scales as V2 x f:

One core at 85% V and 85% f:
  power       = 0.85^2 x 0.85 = 0.85^3 = 0.614   (61% of the original)
  performance = 0.85                              (85% of the original)

Two such cores:
  power       = 2 x 0.614 = 1.23                  (23% more power)
  performance = up to 2 x 0.85 = 1.70             (70% more, IF the work parallelises)

The catch is in the last line: the extra throughput only appears if the software has enough thread-level parallelism, and Amdahl's law still applies. Multicore moved the burden of performance from hardware designers to programmers.


Organisation of a Multicore Chip

+----------------------------------------------------------------------+
|  Core 0           Core 1           Core 2           Core 3           |
| +-----------+    +-----------+    +-----------+    +-----------+     |
| | L1-I L1-D |    | L1-I L1-D |    | L1-I L1-D |    | L1-I L1-D |     |
| |    L2     |    |    L2     |    |    L2     |    |    L2     |     |
| +-----+-----+    +-----+-----+    +-----+-----+    +-----+-----+     |
|       |                |                |                |           |
|  =====+================+================+================+=====      |
|                 on-chip interconnect (bus, ring or mesh)             |
|  ==============================+===============================      |
|                                |                                     |
|                  +---------------------------+                       |
|                  |  shared L3 (last-level)   |                       |
|                  +-------------+-------------+                       |
|                                |                                     |
|                     memory controller --> DRAM                       |
+----------------------------------------------------------------------+
  • Private L1 (split into instruction and data) and usually a private L2 per core: small and fast.
  • Shared last-level cache (LLC), often L3: large, shared by all cores, so data used by several cores is stored once on chip.
  • Interconnect: a shared bus in small designs, a ring or a 2D mesh in larger ones.
  • Shared memory controllers and I/O.

Multicore vs Multiprocessor vs Multithreading

ApproachWhat is replicatedThreads run truly in parallel?Typical use
Multiprocessor (multi-socket)Whole chips, connected on a boardYesServers (often NUMA)
MulticoreCores on one chip; LLC and memory controller sharedYesAlmost every modern CPU
Simultaneous multithreading (SMT, e.g. Hyper-Threading)Only per-thread state (PC, registers); execution units sharedThey share one core's issue slotsFilling idle slots in a wide core

Multicore and SMT are combined in practice: an 8-core chip with 2-way SMT appears to the OS as 16 logical processors. Many phone chips also mix big (fast) and little (efficient) cores, called heterogeneous multicore.


The Cache Coherence Problem

Private caches are essential for speed, but they let several copies of the same memory block exist at once. If one core changes its copy, the others may keep using an old value.

Example

Memory holds X = 5. Caches are write-back and there is no coherence mechanism:

StepEventP1 cacheP2 cacheMemory
1P1 reads X5-5
2P2 reads X555
3P1 writes X = 7755
4P2 reads X75 (stale!)5

P2 reads 5 even though X was changed to 7. A third core missing in its cache would also get 5 from memory. A write-through cache would fix memory (it would become 7) but P2's cached copy would still be stale, so write-through alone is not enough.

A memory system is coherent if every read of a location returns the most recently written value of that location. In practice this means:
1. Program order: a processor that writes X and later reads X (with no other writes in between) gets its own value.
2. Write propagation: a write by one processor eventually becomes visible to the others.
3. Write serialization: all processors see the writes to the same location in the same order.

Coherence is about one location. The rules about the order in which writes to different locations become visible are called the memory consistency model, a separate topic introduced briefly at the end.


Approaches to Coherence

  • Software: mark shared data as non-cacheable, or have the compiler/OS flush caches at synchronisation points. Simple hardware, but slow and error-prone.
  • Hardware snooping protocols: every cache controller watches (snoops) all transactions on a shared broadcast medium (bus) and reacts to those that concern blocks it holds. Fits small systems with a bus or ring.
  • Hardware directory protocols: a directory records which caches hold each block, and messages are sent only to those caches. Scales to many cores.

Write-Invalidate vs Write-Update

When a processor writes a shared block, snooping protocols can do one of two things:

AspectWrite-invalidateWrite-update (write-broadcast)
Action on a writeInvalidate all other copies; writer gets the only valid copyBroadcast the new value to all caches holding a copy
Repeated writes by the same coreOnly the first write uses the busEvery write uses the bus
Other cores reading after the writeTake a miss and re-fetchHit immediately with the new value
Bus trafficLower in typical workloadsHigher
ExamplesMSI, MESI, MOESI (nearly all modern CPUs)Dragon, Firefly protocols

Invalidate-based protocols won in practice, because programs often write the same block many times before anyone else reads it.


The MSI Protocol

Each cache block in each cache is in one of three states:

StateMeaningCan read?Can write?Memory up to date?
M (Modified)Only valid copy, and it is dirtyYesYesNo
S (Shared)Clean copy; other caches may also hold itYesNo (must upgrade first)Yes
I (Invalid)Not present or not validNo (miss)No (miss)-

Bus transactions: BusRd (read a block to share it), BusRdX (read a block with intent to modify; others must invalidate), BusUpgr (I already have it in S, invalidate the others; no data needed), and Flush (a cache in M puts the dirty block on the bus, updating memory).

Transitions Caused by the Local Processor

Current stateProcessor read (PrRd)Processor write (PrWr)
IIssue BusRd → SIssue BusRdX → M
SHit, stay SIssue BusUpgr → M
MHit, stay MHit, stay M

Transitions Caused by Snooped Bus Transactions

Current stateAnother cache's BusRdAnother cache's BusRdX / BusUpgr
IIgnoreIgnore
SStay S→ I
MFlush (supply data, update memory) → SFlush → I
MSI state transitions   (label = event / action this cache takes)

Caused by this processor:            Caused by snooping another cache's request:
  I --PrRd / BusRd----------> S        S --BusRd (no action)--------> S
  I --PrWr / BusRdX---------> M        S --BusRdX or BusUpgr--------> I
  S --PrRd (hit)------------> S        M --BusRd / Flush------------> S
  S --PrWr / BusUpgr--------> M        M --BusRdX / Flush-----------> I
  M --PrRd, PrWr (hit)------> M        I --anything (ignore)--------> I

The key invariant: at any time, a block is either in M in exactly one cache (and I in all others), or in S/I in all caches. This "single writer or multiple readers" rule is what makes the stale read impossible.


The MESI Protocol

MSI has an annoying inefficiency. Most data is private: only one core ever uses it. With MSI, reading a private block puts it in S, and the first write then needs a BusUpgr, even though no one else has a copy. MESI (also called the Illinois protocol) adds a fourth state:

StateMeaningDirty?Other copies?
M (Modified)Only copy, modifiedYesNo
E (Exclusive)Only copy, clean (matches memory)NoNo
S (Shared)Clean, possibly in other cachesNoMaybe
I (Invalid)Not valid--
  • On a read miss, the cache issues BusRd. Other caches signal on a special shared line if they hold the block. If no one does, the block is loaded in E; otherwise in S.
  • A write to a block in E changes it to M silently, with no bus transaction, because no other copy can exist.
  • A cache holding a block in E that snoops a BusRd moves to S; on BusRdX it moves to I. (It does not need to flush, since E is clean.)

Worked Trace: MSI vs MESI

Three processors, one block X, write-back caches, all caches initially I. The access sequence is: P1 reads X, P1 writes X, P2 reads X, P3 reads X, P3 writes X, P1 reads X, P2 writes X.

MSI:

#EventBus actionData supplied byP1P2P3
1P1 readBusRdMemorySII
2P1 writeBusUpgr-MII
3P2 readBusRdP1 flushes (memory updated)SSI
4P3 readBusRdMemorySSS
5P3 writeBusUpgr-IIM
6P1 readBusRdP3 flushes (memory updated)SIS
7P2 writeBusRdXMemoryIMI

MESI: identical except for the first two steps.

#EventBus actionData supplied byP1P2P3
1P1 readBusRd (shared line not asserted)MemoryEII
2P1 writeNone (E → M silently)-MII

From step 3 on, the bus actions, data sources and states are exactly as in the MSI table (P1's M block is flushed and becomes S at step 3, and so on).

MSI: 7 bus transactions. MESI: 6. The saving looks small here, but for private data (read then written by a single thread, which is extremely common) MESI halves the bus traffic for those blocks. Notice also step 7: P2's block is in I, so a write needs the data as well as ownership, hence BusRdX rather than BusUpgr; memory is up to date because the remaining copies are all in S.

Variants Used in Real Processors

  • MOESI (used by AMD) adds O (Owned): a dirty block that is also shared. The owner supplies data to other caches and is responsible for the eventual write-back, so a BusRd to an M block does not force a write to memory.
  • MESIF (used by Intel) adds F (Forward): among several sharers, exactly one is designated to answer requests, avoiding multiple caches responding at once.

Directory-Based Coherence

Snooping needs every request to be broadcast to every cache. With many cores, the broadcast traffic and the number of snoop lookups become too large. A directory protocol instead keeps, for each memory block, a record of who has it.

Directory entry for one memory block (full bit-vector scheme, N = 8 cores):

  +-------+---+---+---+---+---+---+---+---+
  | state | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |   presence bits: 1 = core i has a copy
  +-------+---+---+---+---+---+---+---+---+
  |   S   | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |   cores 0 and 3 share the block
  +-------+---+---+---+---+---+---+---+---+

The directory is usually distributed: each block has a home node whose directory slice holds its entry.

  • Read miss: the requester sends a request to the home. If the block is clean, the home replies with data and sets the requester's presence bit. If it is dirty in some core, the home asks that owner to send the data (and update memory), then marks the block shared.
  • Write miss or upgrade: the home sends invalidation messages only to the cores whose presence bit is set, collects acknowledgements, then grants exclusive ownership and records the new owner.

Directory Storage Overhead

With a full bit vector, each block needs N presence bits plus a few state bits. Assume 64-byte (512-bit) blocks and 1 state (dirty) bit:

Overhead = (N + 1) / 512

N = 16  : 17 / 512  = 3.3%
N = 64  : 65 / 512  = 12.7%
N = 256 : 257 / 512 = 50.2%

The overhead grows linearly with the number of cores, which is why large systems use compressed schemes: limited pointers (store only a few sharer IDs), coarse vectors (one bit per group of cores) or sparse directories (track only blocks that are actually cached).

AspectSnoopingDirectory
How others are foundBroadcast to all cachesLook up the directory, send point-to-point messages
Interconnect neededBus or other broadcast medium (ring)Any network (mesh, etc.)
LatencyLow (one broadcast)Higher (extra hop through the home node)
ScalabilitySmall to medium core countsLarge core counts
Extra storageNone beyond state bitsDirectory entries

False Sharing

Coherence works on whole blocks (cache lines, typically 64 bytes), not on individual variables. Suppose two threads update two different variables that happen to lie in the same line:

#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>

struct counters_bad {            /* both counters share one 64-byte line */
    long a;                      /* updated only by thread 1 */
    long b;                      /* updated only by thread 2 */
};

struct counters_good {           /* each counter gets its own line */
    alignas(64) long a;
    alignas(64) long b;
};

int main(void) {
    printf("bad : size %zu, a at offset %zu, b at offset %zu\n",
           sizeof(struct counters_bad),
           offsetof(struct counters_bad, a), offsetof(struct counters_bad, b));
    printf("good: size %zu, a at offset %zu, b at offset %zu\n",
           sizeof(struct counters_good),
           offsetof(struct counters_good, a), offsetof(struct counters_good, b));
    return 0;
}

Output (GCC, x86-64 Linux):

bad : size 16, a at offset 0, b at offset 8
good: size 128, a at offset 0, b at offset 64

In counters_bad, a and b are 8 bytes apart, so (when the struct starts on a line boundary) they share one cache line. Every write by thread 1 to a invalidates the line in thread 2's cache, and every write by thread 2 to b invalidates it in thread 1's cache. The line "ping-pongs" between the cores although the threads never share any data. This is false sharing, and it can make a parallel program slower than the serial one. Padding or aligning each counter to its own line, as in counters_good, removes it at the cost of some wasted memory.

True sharing: cores access the same word, so coherence traffic is necessary. False sharing: cores access different words in the same block, so the traffic is caused only by the block granularity.


A Note on Memory Consistency

Coherence guarantees that everyone agrees on the order of writes to a single location. It does not say when a write to X becomes visible relative to a write to Y. Consider:

Initially data = 0, flag = 0
Core 1:  data = 42;  flag = 1;
Core 2:  while (flag == 0) ;   print(data);

Under sequential consistency (Lamport's model: the result is as if all operations ran in some single interleaved order that respects each core's program order), Core 2 must print 42. Real processors use weaker models for speed (write buffers can reorder stores and loads), so programmers rely on atomic operations and memory fences/barriers, which the hardware provides to enforce ordering where it matters. A full treatment belongs to advanced courses; for exams, remember the distinction: coherence = one location, consistency = ordering across locations.


Common Mistakes

  • Thinking write-through caches solve coherence. They keep memory current but do not update or invalidate other caches' copies.
  • Mixing up M and E. Both mean "only copy"; M is dirty, E is clean. Only M must flush on a snooped request.
  • Using BusUpgr for a write miss in state I. A cache in I has no data, so it needs BusRdX (data plus ownership). BusUpgr is only for S → M.
  • Forgetting that memory is updated when an M block is flushed on a BusRd in MSI/MESI, which is why the later sharers are in S with memory up to date.
  • Confusing coherence with consistency. Coherence is per location; consistency is about the order of accesses to different locations.
  • Treating false sharing as a correctness bug. The program still gives correct results; false sharing is a performance problem.

GATE and Interview Questions

Q1. Why did processor makers switch from faster single cores to multicore chips?

Dynamic power grows roughly as C V2 f, and higher frequencies need higher voltage, so clock speed hit the power and cooling limit (the power wall). ILP was also giving diminishing returns. Using the growing transistor budget for multiple, more modest cores gives more throughput per watt, provided software has thread-level parallelism.

Q2. With MSI, how many bus transactions does this sequence need: P1 reads X, P1 writes X, P1 reads X, P1 writes X (no other processor touches X)? And with MESI?

MSI: BusRd (I → S), then BusUpgr (S → M), then two hits: 2 transactions. MESI: BusRd loads the block in E (no sharers), then the write is a silent E → M, then hits: 1 transaction.

Q3. In MESI, P1 has X in M. P2 issues a read. What happens?

P1 snoops the BusRd, flushes the dirty block (supplying it to P2 and updating memory) and changes to S. P2 loads the block in S.

Q4. A directory uses a full bit vector for 32 cores with 32-byte blocks and 1 dirty bit. What is the storage overhead?

Each 256-bit block needs 32 + 1 = 33 bits, so the overhead is 33/256 = 12.9%.

Q5. What is false sharing and how do you avoid it?

Two cores repeatedly write different variables in the same cache line, causing the line to bounce between caches through invalidations even though no data is actually shared. Avoid it by padding or aligning frequently written per-thread data to separate cache lines, or by giving each thread local copies and combining at the end.

Q6. Snooping or directory: which scales better and why?

Directory. Snooping broadcasts every miss to all caches, so traffic and snoop lookups grow with the number of cores and need a broadcast medium. A directory sends messages only to the caches that actually hold the block, over any scalable network, at the cost of directory storage and an extra hop of latency.

Q7. What three properties define a coherent memory system?

Program order for a single processor's own reads and writes, write propagation (writes eventually become visible to all processors), and write serialization (all processors see writes to the same location in the same order).


Summary

  • The power wall (P ≈ C V2 f), the ILP wall and the memory wall moved the industry to multicore chips: several cores with private L1/L2 caches, a shared last-level cache and an on-chip interconnect.
  • Private caches create the cache coherence problem: a core can read a stale copy. Coherence requires write propagation and write serialization.
  • Snooping protocols watch a shared bus; write-invalidate (used almost everywhere) beats write-update in typical workloads.
  • MSI: Modified, Shared, Invalid; bus transactions BusRd, BusRdX, BusUpgr and Flush. MESI adds Exclusive so private data can be written without a bus transaction (7 vs 6 transactions in our trace). MOESI and MESIF are real-world variants.
  • Directory protocols track sharers per block and send targeted messages; they scale better but need storage ((N + 1)/512 overhead for 64-byte blocks with a full bit vector).
  • False sharing is coherence traffic caused by unrelated variables in the same line; fix it with padding and alignment.
  • Coherence concerns a single location; consistency concerns the ordering of accesses to different locations.