Exercises — Multicore coherence protocols

WHAT we look for: three clues — clean, read-only, may be elsewhere.

• "clean" rules out M (M is dirty).
• "read-only" rules out M and E (both allow writing).
• "may be in other caches" rules out E (E means only copy).
• "no valid data" would be I — but we do have the block.

Every clue points to one survivor: ==S (Shared)==.

• (a) Read miss from I → we only need a readable copy → issue ==BusRd==. Ends in S.
• (b) Write miss from I → we need the only writable copy, so everyone else must drop theirs → issue ==BusRdX== (read-exclusive). Ends in M.

Mnemonic: the X in BusRdX = "eXclusive = kick everyone else out."

True. Both E and M are exclusive — no other cache has a copy. The difference is cleanliness: E is clean (memory is current), M is dirty (memory is stale, write-back required on eviction). Ownership count is identical; only the memory's freshness differs.

Track it as a table. "—" means no bus message needed.

Why each step:

• Step 1: I→S needs a readable copy → BusRd.
• Step 2: P0 already S (clean), so it can stay S while P1 also loads S. No conflict.
• Step 3: P1 is already in S, so it holds a valid copy and needs only exclusivity, not data → it issues BusUpgr (invalidate the other sharer). This is exactly the S→M transition the parent note's derivation lists ("S → M: issue BusUpgr, no data fetch needed"). P0 snoops the BusUpgr → I. P1 → M.
• Step 4: P0 read-misses (it's I now) → BusRd. P1 is in M, snoops the BusRd, supplies the dirty data, writes back to memory, and downgrades M→S (a second reader now exists). Final: S/S.

Final state pair: (S, S).

(Aside on terminology: some textbook MSI variants do not include BusUpgr and instead use BusRdX even from S — fetching data it already has, which is wasteful. The parent note's protocol does include BusUpgr, so we follow that; if your course omits it, replace step 3's BusUpgr with BusRdX and the states are identical.)

First, the piece of hardware this exercise turns on — the shared line.

What the shared line is: the snooping bus carries, alongside the address, one extra wire called the shared signal (sometimes labelled S or HITM/SHR). When any cache broadcasts a BusRd, every other cache checks its own tags and, if it holds that block, asserts (drives high) this one shared wire. The requester then reads the wire:

• shared wire low = "nobody else answered" = I am the sole owner → load as E.
• shared wire high = "someone else has a copy" = load as S.

That single OR-ed wire is exactly how MESI distinguishes E from S at load time — without it, E could not exist.

Why:

• Step 1: the shared wire comes back low (P1 holds nothing) → load as E, not S.
• Step 2: E means clean and exclusive → we may silently promote E→M with no bus transaction. This is the payoff of MESI.
• Step 3: P1 read-misses → BusRd; P1's cache asserts nothing but P0 now holds the block, so the shared wire goes high. P0 in M supplies data, writes back, downgrades M→S. Both end S.

Total bus transactions = 2 (steps 1 and 3). In plain MSI the write in step 2 would have cost a BusUpgr → 3 transactions. MESI saved one.

Look at the ping-pong figure below.

Trace it (line state shown as who owns M):

• Write 1 (P0): P0 I→M, BusRdX. P1 stays I. 1st transfer (fetch line to P0).
• Write 2 (P1): line is in P0's M. P1 must BusRdX → P0 supplies + invalidates → P0 I, P1 M. 2nd transfer.
• Write 3 (P0): P0 is I → BusRdX → grabs from P1. 3rd.
• Write 4 (P1): grabs back from P0. 4th.
• Writes 5,6,7,8: same pattern → 4 more transfers.

Total = 8 line transfers. Every single write forces a full line bounce, even though a and b never truly share data. This is false sharing — see False sharing and padding.

Contrast: if a and b were on separate lines (padded with alignas(64)), P0 keeps its line in M for all 4 writes and P1 keeps its line in M — 0 cross-core transfers after the first fetch each. The count drops from 8 to essentially 2 initial fetches.

(a) Write-invalidate:

• First write: 1 BusUpgr invalidates all 3 readers. Writes 2–10 hit the writer's own M copy → no bus traffic.
• Invalidate broadcasts = 1.
• After the burst, 3 readers each read-miss → 3 refetches. Refetches = 3.
• Total bus events = 1 + 3 = 4.

(b) Write-update:

• Every write must push the new value to all copies → 1 update broadcast per write.
• Update broadcasts = W = 10 (each reaching all 3 caches).

Verdict: invalidate = 4 bus events; update = 10 bus events. Invalidate wins because it amortizes the whole 10-write burst behind a single invalidate. This is exactly why real chips are invalidate-based.

This is the O (Owned) state of MOESI.

Definition: O = "I hold the dirty master copy, I am responsible for supplying it to sharers cache-to-cache, and memory is still stale." Read-only for the owner in the sense that it stays the write-back authority; other cores may hold clean S copies fed by the owner.

New transition: M-owner snoops a BusRd →

• without O: owner writes back to memory, M→S, reader→S. (2 memory touches over time.)
• with O: owner supplies data cache-to-cache, M→O, reader→S, no memory write-back. Memory stays stale but the O-owner is on the hook to write it back only when evicted.

Who ends where: owner → O, new reader → S.

Payoff: the costly DRAM write-back is deferred (possibly avoided if the line is overwritten again first), and sharers get fresh data straight from cache. This is precisely why AMD uses MOESI. Cross-check with Snooping vs Directory protocols — the "who supplies the data" question is the heart of both.

Weakest to strongest: I, then S, then O, then E, then M.

Justification, rung by rung:

• I: no data, no rights — bottom.
• S: clean, read-only, may share — must broadcast to write.
• O: like S you're still read-serving and must broadcast to write, but you additionally own the dirty master and supply data — strictly more responsibility/rights than plain S, yet still not writable silently → sits just above S.
• E: exclusive and clean — can upgrade to M with zero broadcast → above O.
• M: exclusive, dirty, full read/write, zero broadcasts — top.

(Note: the O-vs-E ordering is a modelling choice — here we rank by "how close to a silent write." E can silently become M; O cannot. So E ranks above O.)

The claim is WRONG.

• Coherence guarantees that for each single location, P1 eventually sees P0's latest write: P1 will see ready==1, and will see data==42 for those locations individually.
• What coherence does NOT guarantee is the relative ordering between the two different locations data and ready. Under a relaxed memory consistency model, the hardware (via store buffers) or the compiler (via reordering) may make P1 observe ready=1 before data=42 is visible — so print(data) may output 0.

Why the intuition fails: coherence = ordering within one address; consistency = ordering across addresses. They are different axes.

The concrete fix (three equivalent levels of remedy — see Atomic operations and fences):

1. Release/acquire atomics. Make the publish a release-store and the flag-read an acquire-load:

   // P0:  data = 42;
   //      ready.store(1, memory_order_release);
   // P1:  while (ready.load(memory_order_acquire) == 0) {}
   //      print(data);   // now guaranteed 42
   

   The release forbids data = 42 from moving after the store; the acquire forbids print(data) from moving before the load. Together they create a happens-before edge: everything before the release is visible after the matching acquire.
2. Explicit fences. Keep plain writes but insert a store-release fence (atomic_thread_fence(memory_order_release)) before setting ready, and an acquire fence after reading it — same ordering, coarser granularity.
3. A mutex. Guard both variables with the same lock; lock/unlock imply the release/acquire fences for you.

Any one of these is sufficient; a bare volatile is not (it forbids compiler reordering but not the hardware store-buffer reordering).

• (a) Read from M: the block is valid and the core owns it → stay M, no bus traffic. A read never downgrades your own copy.
• (b) Evict E: E is clean → memory already current → silently drop, no write-back. Zero bus cost.
• (c) Evict M: M is dirty → memory stale → must write back to memory before dropping. This is the eviction cost that E avoids.
• (d) Simultaneous BusRdX: the bus arbiter serializes them — only one transaction wins the bus at a time (see Bus arbitration). One core gets exclusivity first (→M), the second's BusRdX then finds the line in the winner's M, forcing supply + invalidate, and the second core ends M. Coherence's write-serialization property is implemented precisely by this arbitration: the bus imposes a single global order on conflicting accesses.

The takeaway: there is no "tie." The shared medium (or directory) always picks a winner, which is how write serialization is physically realised.

L1 name the states/messages → L2 run the protocol (and see how the shared line separates E from S) → L3 count the traffic and spot false sharing → L4 design O/E to cut specific waste → L5 separate coherence (one address) from consistency (many addresses) and handle every degenerate case.