Multicore coherence protocols: Question bank — Coding deep dive

Prerequisites worth having open: Cache memory hierarchy, Memory consistency models, Snooping vs Directory protocols, Atomic operations and fences, False sharing and padding.

True or false — justify

A coherent system guarantees my two threads always observe operations in the order I wrote them.

False — coherence only orders writes to one location; cross-location order is decided by the consistency model plus your fences.

In MESI, a block in state E can be written without any bus transaction.

True — E means clean and the only copy, so the write silently becomes M with zero broadcast.

In MSI, a block in state S can be written without any bus transaction.

False — S may coexist in other caches, so a write must issue a BusUpgr to invalidate them first.

Two variables never shared between threads can still cause coherence traffic.

True — if they live in the same 64-byte line, false sharing ping-pongs the line even though no real data is shared.

Evicting an E-state block requires writing it back to memory.

False — E is clean and matches memory, so it is dropped silently; only M (dirty) needs write-back.

Write-update protocols eliminate the need for invalidation and are therefore superior.

False — most writes target data nobody else reads, so broadcasting every value floods the bus; invalidate amortizes a whole write-burst.

Adding the O (Owned) state changes the number of stalls a program sees but not its final values.

True — O only lets a dirty owner supply data cache-to-cache and defer write-back; the values observed are identical to MESI.

Coherence is only needed because caches exist.

True — with no private caches every read/write hits the single shared memory copy, so no duplication means no coherence problem.

Spot the error

"A read miss in MSI always loads the block as S, so read-only sharing is free."

Missing cost — if another cache holds the block in M, that owner must supply the data and downgrade M→S, which is a bus transaction, not free.

"E and M both mean 'only I have this copy,' so they're interchangeable."

The difference is cleanliness — E matches memory (no write-back on eviction) while M is dirty and must be written back.

"BusUpgr fetches the latest data before letting me write."

BusUpgr only invalidates other sharers; the writer already has the block (it was in S), so no data is fetched.

"Since coherence returns the most recent write, a spin-loop on a flag is safe without atomics."

Coherence handles that one flag correctly, but reordering of the flag versus the guarded data needs fences/atomics from the consistency model.

"MOESI removes write-backs entirely."

It only defers them — the owner still must write back eventually (e.g. on eviction of the O copy); it just avoids the immediate memory write on a read-share.

"With write-invalidate, the reader after an invalidation gets stale data."

The opposite — invalidation forces the next reader to miss and refetch the fresh value from the writer or memory, guaranteeing currency.

Why questions

Why is MSI's minimum set exactly three states and not two?

You need to distinguish "I can write freely" (M) from "I may only read" (S) from "I have nothing" (I); collapsing any pair loses either write-permission or presence information.

Why does a snooped BusRd force an M-state cache to downgrade to S rather than stay in M?

A second reader now exists, so the copy is no longer exclusive; the owner supplies data, writes back, and moves to S to keep them consistent.

Why does invalidate-based coherence usually beat update-based on real workloads?

Cores tend to write a block many times before another core reads it, so one invalidate covers the whole burst instead of one broadcast per write.

Why does the E state matter for single-threaded-feeling code on a multicore chip?

Such code touches data nobody else shares; E lets each write skip coherence traffic entirely, so the program pays effectively zero bus cost.

Why is coherence enforced on whole cache lines instead of individual bytes?

Tracking state per byte would multiply the metadata and bus signalling cost enormously; the line is the natural transfer/tracking unit, which is exactly why false sharing exists.

Why can a directory protocol scale past a shared bus?

A bus requires every cache to snoop every transaction (broadcast); a directory sends messages only to caches that hold the block, avoiding the shared-medium bottleneck.

Edge cases

What state does a block occupy when no core has ever touched it?

Effectively I (Invalid) in every cache — there is no valid cached copy, so the first access is a miss.

In MESI, two cores read the same fresh block back-to-back — what states result?

The first read lands as E (sole owner), then the second read's snoop drops it: both end in S since sharing now exists.

A core in M evicts its block with no other core interested — what must happen?

Because M is dirty, the line must be written back to memory before the frame is reused, unlike a clean E/S eviction.

Zero-writer case: a block only ever read by many cores — what traffic does coherence add?

After the initial misses it settles into S across caches with no further coherence traffic, since read-only sharing never invalidates.

What happens if two cores issue a write to the same S block "simultaneously"?

The bus arbiter serializes them — one BusUpgr wins first (→M), invalidating the other, whose write re-issues as a miss afterward.

Degenerate false-sharing case: variables in the same line but only ever read by both cores?

No ping-pong occurs — reads keep the line in S on both cores; false sharing only bites when at least one core writes.

Can a block be in M on two different cores at the same instant?

No — M asserts a single exclusive dirty owner; the protocol's invalidations make simultaneous M-ownership impossible by construction.

Recall One-line self-test

Coherence fixes ::: one location seeing the latest write, in a single agreed order across cores. Coherence does NOT fix ::: ordering across different locations — that's the consistency model plus your synchronization.