Cache coherence — MESI protocol in multicore: Exercises

The four states, in one line each so nothing here is unearned:

M = only valid copy, dirty (DRAM stale), writable.
E = only valid copy, clean (matches DRAM), writable silently.
S = read-only copy, clean, others may share.
I = garbage, a miss.

Level 1 — Recognition

Exercise 1.1

A line is in state E in Core0's cache and nowhere else. Core0 issues a write hit to that line. What bus transaction is broadcast, and what is the new state?

Recall Solution

New state: M. Bus transactions: zero (silent upgrade). In E you already know you are the sole owner — the snoop response when you loaded said "no sharers". So there is nobody to invalidate. You flip E → M in-place and broadcast nothing. This is the whole reason the E state exists (the sole-owner optimisation).

Exercise 1.2

For each state, say whether DRAM holds the up-to-date value: M, E, S, I.

Recall Solution

M: DRAM is stale — the cache owns the truth; a write-back is owed.
E: DRAM is up-to-date (clean).
S: DRAM is up-to-date (clean).
I: irrelevant — this cache has no valid copy; DRAM may or may not be current, but this line can't answer. Only M implies a dirty, owed write-back.

Level 2 — Application

Exercise 2.1

Two cores, both start I, X=0 in DRAM. Trace the state of both caches after each of these operations in order:

Core0 reads X
Core1 reads X
Core0 writes X=7

Recall Solution

Step	Action	Bus	Core0	Core1
start	—	—	I	I
1	Core0 read miss	BusRd, no sharer	E	I
2	Core1 read miss	BusRd, Core0 sees it (E)→S, supplies data	S	S
3	Core0 write hit in S	BusUpgr/Invalidate	M	I
After step 1 Core0 is E (sole owner). Step 2 turns the E copy into two S copies. Step 3 requires single-writer status, so Core0 broadcasts an invalidate; Core1's S drops to I and Core0 goes to M.

Exercise 2.2

Same setup as 2.1, but instead do:

Core0 reads X
Core0 writes X=5
Core1 reads X

How many bus transactions total, and what value does Core1 end up with?

Recall Solution

3 bus transactions? No — count carefully: 2. Core1 reads value 5.

Core0 read miss → BusRd (transaction #1). Core0 → E.
Core0 write hit in E → silent upgrade to M (transaction #0 — none!).
Core1 read miss → BusRd (transaction #2). Core0 snoops in M → flushes 5 cache-to-cache and drops to S; Core1 installs S with 5. Total bus transactions = 2. The silent E→M in step 2 is why the write cost nothing on the bus.

Level 3 — Analysis

Core0 repeatedly writes a[0], Core1 repeatedly writes a[1]. Both integers live in the same 64-byte line. They alternate strictly: C0 write, C1 write, C0 write, C1 write, … for 6 writes total (3 each), starting from both I.

How many coherence transactions that transfer the line (BusRdX/flush events) occur across these 6 writes?

Recall Solution

5 line transfers.

Write 1 (C0): line in I → BusRdX, install M. (transfer #1 — the compulsory miss)
Write 2 (C1): I → BusRdX, C0 flushes & → I, C1 → M. (transfer #2)
Write 3 (C0): I → BusRdX, C1 flushes & → I, C0 → M. (transfer #3)
Write 4 (C1): BusRdX, transfer #4
Write 5 (C0): BusRdX, transfer #5
Write 6 (C1): BusRdX, transfer #6 The first write is a normal compulsory miss; the next 5 are pure false-sharing ping-pong. General rule: for $n$ strictly alternating writes the line transfers $n$ times, but the first is unavoidable, so $n - 1 = 5$ are wasted coherence traffic. See figure below.

Figure — Cache coherence — MESI protocol in multicore

Pad a[0] and a[1] onto separate 64-byte lines (alignas(64)). Now how many line transfers for the same 6 writes?

Recall Solution

2 line transfers. Each core touches its own line, which nobody else ever accesses. C0's first write: I→M via one BusRdX; every later C0 write is an M hit, silent. Same for C1. So exactly 1 compulsory miss per core = 2 total, and zero coherence ping-pong. We cut traffic from 6 → 2 by spending 56 bytes of padding. Trading memory for bus bandwidth is the standard fix.

Level 4 — Synthesis

Exercise 4.1 — AMAT with coherence misses

Use the parent's model: $AMAT = t_{hit} + p_{miss} \cdot t_{miss}, p_{miss} = p_{ord} + p_{coh}$ $t_{miss} = (1 - f_{c 2 c}) t_{DRAM} + f_{c 2 c} t_{c2c}$ Given: $t_{hit} = 1 ns$ , $p_{ord} = 0.02$ , $p_{coh} = 0.03$ , $f_{c 2 c} = 0.6$ , $t_{DRAM} = 100 ns$ , $t_{c2c} = 40 ns$ . Compute AMAT.

Recall Solution

First $t_{miss} = (1 - 0.6) (100) + (0.6) (40) = 40 + 24 = 64 ns$ . Then $p_{miss} = 0.02 + 0.03 = 0.05$ . $AMAT = 1 + 0.05 \times 64 = 1 + 3.2 = 4.2 ns$ Notice coherence misses ( $p_{coh} = 0.03$ ) contribute $0.03 \times 64 = 1.92$ ns — more than half the miss penalty here. That's the lesson: false sharing (which inflates $p_{coh}$ ), not raw DRAM latency, dominates.

Suppose the padding fix in 3.2 drops $p_{coh}$ from $0.03$ to $0.005$ . All else equal. New AMAT, and the speedup factor on memory access time?

Recall Solution

New $p_{miss} = 0.02 + 0.005 = 0.025$ . $AMAT_{new} = 1 + 0.025 \times 64 = 1 + 1.6 = 2.6 ns$ Speedup on AMAT $= 4.2/2.6 \approx 1.615 \times$ . A pure-software change (add padding) shrank average access time by ~38% because it slashed coherence misses.

Level 5 — Mastery

Exercise 5.1 — Coherence vs consistency

Core0 executes X=1; Y=1; (two different addresses, both start 0). Core1 spins while(Y==0){} print(X);. Under a system with perfect MESI coherence but a store buffer that reorders, can Core1 print X=0? Explain using the coherence-vs-consistency distinction, and name the fix.

Recall Solution

Yes, Core1 can print 0. MESI guarantees coherence per address: everyone agrees on the timeline of X, and separately on the timeline of Y. It says nothing about the relative order of a write to X versus a write to Y becoming visible. A store buffer can let Y=1 drain to the coherent cache/bus before X=1 does. So Core1 sees Y=1, exits the loop, and reads the still-old X=0. Fix: a memory fence / release-store on the writer and acquire-load on the reader (or atomic with the right ordering). See Memory consistency models and Atomics, locks, and the LL-SC / cmpxchg. Coherence ≠ consistency: coherence is cross-core agreement on one address; consistency is cross-address ordering.

Exercise 5.2 — Design tradeoff: snooping vs directory

Your chip grows from 4 cores to 64 cores. Broadcast-snooping BusRdX must be seen by every other cache. Argue why snooping stops scaling and what replaces it, in terms of the number of messages per write miss.

Recall Solution

With broadcast snooping, one write miss must reach all other caches: for $N$ cores that's $O (N)$ messages per coherence event, and every cache burns energy snooping even lines it doesn't hold. At $N = 64$ the shared bus/interconnect saturates — bandwidth is the scarce resource. Replacement: Directory-based coherence. A directory tracks which cores actually hold each line, so a write miss sends invalidations only to the (usually few) real sharers — $O (sharers)$ not $O (N)$ . You trade a directory storage/latency cost for message count that scales with actual sharing, not core count. Extensions like MOESI and MESIF extensions further reduce write-backs and pick a clean cache-to-cache supplier.

Exercise 5.3 — Full trace under directory intuition

Three cores. X=0 in DRAM, all I. Sequence:

C0 read, 2. C1 read, 3. C2 read, 4. C1 write X=9. How many caches must be invalidated at step 4, and what states result?

Recall Solution

After steps 1–3: C0, C1, C2 all hold X in S (three shared readers, value 0, DRAM clean). Step 4, C1 writes: it is in S, so it must become the single writer. It broadcasts BusUpgr/Invalidate. The other two sharers (C0 and C2) must be invalidated → 2 invalidations. Result: C1 = M (value 9, DRAM stale), C0 = I, C2 = I. Under a directory this is exactly the case where you message only the 2 real sharers, not all cores.