The Multi-Core Problem

Module 1 · Chapter 1.2 · Cache Coherency Foundations

Project thread — same running example as 1.1: two CPUs (CPU0, CPU1), each with a private L1 cache, sharing one memory with one shared line A. Here we make the two cores race on the same line and watch the outcome depend on the interleaving.

1. Learning Outcomes

By the end of this lesson you will be able to:

• Explain why concurrent access to one line makes correctness depend on the interleaving of two cores' loads and stores.
• Trace the four-way interleaving of two cores' read-modify-write on one line and identify which orders are correct and which lose an update.
• Identify the lost-update signature: two private copies moving in lockstep to the same value because neither observed the other's write.
• Explain why the bug is timing-dependent — passing repeatedly, then failing once — and invisible in single-core testing.

2. Why Should I Learn This?

Chapter 1.1 established the contract: private caches hold independent copies of a line, and a lock orders access but never reconciles those copies. This chapter shows the concrete consequence — put two cores on the same line at the same time and program correctness now depends on the exact interleaving of their loads and stores.

• The bug is timing-dependent. The same code passes a thousand times, then fails once, because failure needs a specific overlap of two cores' operations. That is what makes multi-core bugs terrifying — they escape directed tests and survive to the field.
• Read-modify-write is the trap. Two cores that each do load, add, store on one line can lose an increment — the classic lost update — because both computed from the same starting value. A real dual-core boot once hung intermittently for exactly this reason: one core's flag write updated only its own L1, so the waiter kept hitting its stale copy.
• This is CHI's concrete job. Snoops, home nodes, and directories exist precisely to make these interleavings safe. See the race clearly and CHI stops being abstract.

3. Core Concept — the four-way interleaving of one line

Take the running project: CPU0 and CPU1, each with a private L1, over one shared memory holding line A. Both do the same read-modify-write: load A, add 1, store the result. (From 1.1: each core works from its own cached copy, and nothing in the code reconciles the two.)

On one core, load, add, store runs to completion before the next such sequence starts — one copy, always current, no race. With two cores the sequences overlap in time, so the visible result depends on when each core reads and writes relative to the other. Picture two cashiers each updating a notepad copy of the same balance: both read $100, both write $110, and two $10 deposits raise the balance by only $10.

There are four representative interleavings of "CPU0 load/store" against "CPU1 load/store" on the same line:

• Serial 0-then-1: CPU0 completes load then store, then CPU1 loads. Correct only if CPU0's store is visible to CPU1.
• Serial 1-then-0: the mirror image — CPU1 completes, then CPU0. Same condition, other direction.
• Overlap, both read first: both cores load A before either stores. Both compute from the same old value, both store — one increment is lost.
• Overlap, interleaved store: CPU0 stores, then CPU1 — but CPU1 already read the old value, so its store is again based on stale data.

Only the two serial orders can be correct, and even they are correct only if the write becomes visible to the other core. The two overlapping orders are wrong regardless. With no coherency, nothing forces the serial, visible orderings — so the wrong interleavings happen, and only sometimes, which is why the bug is intermittent.

4. Engineering Diagram

5. Worked Example — two cores race a shared counter

Trace both cores doing load A, add 1, store A with A = 5, no coherency. Watch the overlapping interleaving lose an increment:

# Two private caches over one shared memory. Initial: A = 5 everywhere.
# Both cores execute: load A -> add 1 -> store A.  (No coherency mechanism.)
 
Cycle  CPU0                 CPU1                 L1(CPU0)  L1(CPU1)  Memory  Note
-----  -------------------  -------------------  --------  --------  ------  -----------------------------
  1    load A (miss->5)     .                    A=5       -         A=5     CPU0 caches copy of A
  2    .                    load A (miss->5)     A=5       A=5       A=5     CPU1 caches its OWN copy of A
  3    add 1 -> 6           add 1 -> 6           A=5       A=5       A=5     BOTH computed 6 from the same 5
  4    store A=6            .                     A=6       A=5       A=5     CPU0 writes its copy only
  5    .                    store A=6            A=6       A=6       A=5     CPU1 writes its copy only  <-- BUG
# Expected after two +1 on 5 = 7.  Actual visible result = 6.  One increment LOST.

Both cores read 5 at cycles 1-2, both computed 6 at cycle 3, and both stored 6. Two increments should give 7; the system shows 6. Nothing forced CPU1 to see CPU0's store before it read — the two operations raced, and the wrong interleaving won. The missing layer is coherency, which would make CPU1's load at cycle 2 (or its store at cycle 5) observe CPU0's value. Reorder the cycles so the two accesses fall far apart and the same code is correct — which is exactly why the failure is intermittent.

6. Protocol Transaction Walkthrough — the store that arrived too late

Frame the race as CHI later will — two requesters on one line, and the serialisation/invalidate action that is missing:

The one missing message — a serialise-and-invalidate between the two caches on a write — is the entire multi-core problem. It must force one core's read-modify-write to observe the other's before completing. Every CHI mechanism exists to make that dashed arrow real, correct, and cheap enough to run on every shared write.

7. Timing Diagram — the two copies race to the same wrong value

Track each core's cached value for line A across the race. Both start at 5, both climb to 6, and memory never sees 7:

The visual signature of the multi-core race: two cached copies of one address moving in lockstep to the same value because neither observed the other's update. If a coherency point existed, an invalidate pulse would fire between the two stores and force CPU1 to refetch; here that action never happens, so both copies settle on the wrong value.

8. DebugLab — "two cores increment, the counter only moves once"

9. Common Mistakes

• Calling it a software race. The code is correct; the caches raced. The fix is a hardware coherency point, not rewriting the loop.
• Reaching for a memory barrier. Barriers order writes across different addresses (consistency). They do not reconcile two copies of one address — that is coherency.
• Assuming "I wrote it" means "they can see it." A store updates the writer's copy; visibility to another core is a separate guarantee that only coherency provides.
• Testing only single-core. Single-core has one copy and cannot expose the race. The bug needs two concurrent copies and a specific interleaving.
• Thinking a lock alone is enough. As 1.1 showed, a lock serialises access but cannot reconcile diverging copies — the released write may still be invisible in the next core's cache. Lock and coherency are different layers, both required.

10. Interview Questions

11. Engineering Checklist

• I can enumerate the four interleavings of two cores' load/store on one line and say which are correct and why.
• I can show the exact cycles where both cores read the same old value and one store overwrites the other.
• I can explain why the failure is intermittent and invisible single-core.
• I can name the missing action — serialise the requests and invalidate the loser's copy on write — that a coherency protocol must add.
• I can explain why a barrier is the wrong fix and coherency is the right one.

12. Key Takeaways

• Concurrency turns copies into a race. Two cores on one line make the result depend on the interleaving of their loads and stores.
• The overlapping orders lose an update regardless. Both read before either writes, so both compute from the same stale value and one store silently overwrites the other.
• The bug is timing-dependent. It needs a specific overlap, so it passes repeatedly then fails once, and never appears single-core.
• Invariant to hold: once both cores hold a copy of a line, the two copies must agree, and the agreed value must equal the starting value plus every committed increment — a coherent system upholds this, the incoherent one violates it.
• This is why CHI exists. A per-line serialise-and-invalidate point makes the race safe; a lock orders access and a barrier orders addresses, but neither reconciles copies.

13. Quick Revision

The multi-core problem. Two cores, two private copies, one line — the visible result depends on the interleaving. Concurrent read-modify-write: both load the same old value, both store their own copy -> one update lost (5 +1 +1 = 6, not 7). The bad interleaving is rare, so the bug is timing-dependent — passing repeatedly, then failing once, never single-core. This is coherency + visibility on one address — not ordering (cross-address, Module 12) and not just locking (orders access, cannot reconcile copies). The fix = a per-line serialise-and-invalidate point that forces the overlap into a safe serial order; at SoC scale that machinery is AMBA CHI (Home Node + snoops). Barriers are the wrong tool.

14. Coming Next

Next — 1.3 Shared Memory Systems. You will add:

• how the shared-memory model promises every core a single view of one address space, and why private caches quietly break that promise;
• the memory hierarchy the coherency point must sit within — private L1/L2, shared LLC, and backing memory;
• where the point of coherence lives, and why "which copy is the truth" becomes the central question.

We keep the same project — CPU0, CPU1, private L1s, one shared line — and zoom out from "here is exactly how two cores racing lose a write" (this lesson) into "here is the shared-memory system that must make one address look like one value to every core."