CS149 L14 Cache Coherence: MSI, MESI, and False Sharing

🌏 中文版

This post is based on the Fall 2025 edition of CS149. It is part 19 of Reading Stanford CS149. It follows PA5, the fastest kernel on an H100 and covers Lecture 14, "Cache Coherence" (2025-11-11).

The official material is the L14 slide PDF (45 pages, also available slide by slide on the web). Fall 2025 recordings are Canvas-only; the course home page points to the 2023 Lecture 11 Cache Coherence video instead. This post follows the 2025 slides and lists the video only as a supplement. The access level is A3 (defined in the global AI/CS course map): the slides are fully public, and only the current recordings are missing.

Why the course returns to caches after AI kernels

That is the official order: L9 through L13, PA4, and PA5 cover AI systems, and L14 through L18 return to correctness in shared memory. The topic seems to break, but it connects back to two earlier places:

• L2 Modern multi-core processors drew each core with private L1 and L2 caches. This lecture answers how those private copies stay consistent.
• In PA2's thread pool, worker threads share task counters and queues. Part of their performance depends on the protocol in this lecture.

Multithreaded runtimes, locks, and lock-free data structures all sit on top of this layer. Part 5 doesn't talk about AI directly, but no parallel runtime gets around it.

Review: how a cache works

The slides open with two small examples: an 8-byte cache, 4-byte lines, LRU replacement. The first shows spatial locality (loading a line preloads its neighbors) and temporal locality (repeat accesses to one address hit). The second runs into a capacity miss.

Next come the five steps of a write miss in a uniprocessor write-allocate, write-back cache: pick a location (writing back any dirty line there), load the whole line from memory, update 32 bits, mark it dirty. The slides also show the Intel Skylake hierarchy: a private 32 KB L1 and 256 KB L2 per core, a shared 8 MB inclusive L3, and 64-byte lines.

What the coherence problem looks like

Four processors each have a cache. Variable foo sits at shared address X, starts at 0, and caches are write-back. The slides step through:

One address, and processors see 0, 1, and 2. The slide asks: is this a mutual exclusion problem? Can locks fix it? No. The hardware created the problem by replicating data in local caches. It has nothing to do with whether the program races.

The root cause is that the abstraction of one shared address space is implemented by global main memory plus per-processor local caches.

What does "last" mean in "last write"?

The intuitive rule is that reading X returns the last value any processor wrote to X. But what if two processors write at the same moment? What if P1 writes and P2 reads so soon after that the write can't reach P2 in time? In a sequential program, "last" means program order. Parallel programs need a different definition.

The formal definition on the slides: a memory system is coherent if, for each address, there exists a hypothetical serial order of all processors' operations on it that is consistent with the results, and:

1. Operations issued by one processor appear in the order that processor issued them
2. Each read returns the value of the last write to that address in the serial order

In an implementation, this becomes two invariants:

• SWMR (Single-Writer, Multiple-Read): in any period, either one processor may write (and read), or several processors may only read
• Data-value (write serialization): the value at the start of a period equals the value at the end of the last read-write period

Ways to implement coherence

The slides list three:

• Software, page-granularity: the OS propagates writes through page faults, which works across a cluster of workstations. Not covered in class, except to note its big problem is false sharing (see below).
• Hardware, cache-line granularity: snooping (the focus here) and directories (briefly).
• Share one cache: no replication, no coherence problem, but you lose what makes a cache local and fast, and you get interference and contention. The upside is that when working sets overlap, one processor's loads can prefetch for another. The example is SUN Niagara 2: eight cores connected through a crossbar to shared L2 banks, with the crossbar taking about as much area as one core.

Snooping, and the simplest version

In snooping, all coherence-related activity is broadcast to every cache controller, and each controller monitors ("snoops") it and reacts per the protocol. A controller now answers to two sides: loads and stores from its own processor, and messages broadcast on the interconnect.

The simplest version assumes write-through caches at cache-line granularity: on a write, broadcast an invalidation; other processors miss on their next read and fetch the new value from memory. The problem is that every write goes to memory, which needs a lot of bandwidth. Write-back caches absorb most writes as hits, but they need a more elaborate protocol.

MSI: get exclusive ownership before writing

With write-back caches, the dirty state means exclusive ownership. The cache holds the only valid copy and may write it; when someone else wants to read, this cache must supply the data, or the reader gets a stale copy from memory.

In MSI, each line has one of three states:

There are two processor operations, PrRd and PrWr, and three bus transactions:

• BusRd: get a copy with no intent to modify
• BusRdX: get a copy with intent to modify
• BusWB: write a dirty line back to memory

The key transitions:

• A read brings the line into S, even if it is the only copy
• Before writing, a cache must reach M by issuing BusRdX; other caches invalidate their copies, and any cache holding M writes back first
• Even a line already in S needs BusRdX to upgrade to M
• A cache in M that sees another cache's BusRd writes back and drops to S; on BusRdX it writes back and drops to I

The slides' worked example, with three processors operating on x:

How MSI satisfies the invariants: only one cache can be in M, and all others receive invalidations, which gives SWMR. On BusRd and BusRdX, data comes from the cache holding M, and the bus puts all transactions in one order, which gives write serialization.

MESI: skip the second transaction in read-then-write

MSI needs two transactions in the common case of reading an address and then writing it: BusRd from I to S, then BusRdX from S to M. The waste happens even when the program shares nothing.

MESI adds an E (exclusive clean) state: the line is unmodified, but only this cache has it. On a read, if no other cache asserts that it shares the line, the line goes straight to E, and a later write moves E to M with no bus transaction at all. E separates exclusivity from ownership: the line isn't dirty, so memory still holds a valid copy.

The slide's corner note: "MESI, not Messi!"

Directories: stop broadcasting

Snooping broadcasts to learn the state of a line in other caches, and that doesn't scale. A directory keeps the state of each line across all caches in one place. Caches look it up when needed, and coherence runs on point-to-point messages sent on a need-to-know basis. The SWMR and write-serialization invariants still apply.

The example is the Intel Core i7. Its L3 is inclusive, so every line in any L2 is also in L3, which lets L3 serve as the central directory and serialization point. The directory records which L2s hold a line and sends coherence messages only to them. The Core i7 interconnect is a ring, not a bus.

What it means for programmers

Communication hides inside memory latency

On a multiprocessor, communication is a key parallel overhead, and it shows up as a longer average memory access time (AMAT). The slides list rough latencies for the Core i7 Xeon 5500 series: about 4 cycles for an L1 hit; for an L3 hit, about 40 cycles when the line is unshared and about 75 cycles when another core has modified it; about 400 cycles for remote DRAM. The warning is that even a small fraction of these slow accesses can matter. The slides suggest Intel VTune to observe memory system behavior.

False sharing

The slide asks what the performance problem is in this per-thread accumulation:

// one counter per thread, packed into an array
int myPerThreadCounter[NUM_THREADS];

And why this version might be faster:

struct PerThreadState {
  int myPerThreadCounter;
  char padding[CACHE_LINE_SIZE - sizeof(int)];
};
PerThreadState myPerThreadCounter[NUM_THREADS];

The demo: 8 threads on a 4-core system, each incrementing its own counter many times. Unpadded, 14.2 seconds. Padded, 4.7 seconds.

The cause is false sharing. Two processors write different addresses in the same cache line. Under MSI, every write needs M first, so the line ping-pongs between the two caches and generates heavy coherence traffic. The program has no data to communicate. All of this is artifactual communication caused by cache lines being larger than 4 bytes.

The slides close the section with a simulation figure credited to Culler, Singh, and Gupta: a 1 MB cache, four applications, and line sizes from 8 to 256 bytes, with the miss rate split into cold, capacity/conflict, true sharing, false sharing, and upgrade misses. Bigger lines help and hurt, and false sharing is one of the costs.

Try this: open any thread pool or parallel accumulation code you've written (for example, the worker state in PA2). Find fields that are one-per-thread, packed in an array, and written often. Pad them to 64 bytes (the line size on Skylake and in the slides) and measure before and after.

Lecture summary

The summary slide makes three points:

1. The coherence problem exists because a single shared address space is not implemented by a single storage unit; data is replicated into local caches for performance
2. Snooping's main idea is that any cache operation that could affect coherence is broadcast to all other cache controllers. The hardware challenge is keeping the protocol's overhead low; the software challenge is watching for artifactual communication such as false sharing
3. Snooping scales only as far as broadcast does; directories are how coherence scales further

What this post can and cannot confirm

Confirmed: the L14 slide PDF, and the lecture date and description on the course home page ("Invalidation-based coherence using MSI and MESI, false sharing"). The first 20 pages of the Fall 2025 L15 slides repeat L14's MSI, MESI, directory, and false-sharing material almost verbatim, which suggests L14 ran over into the next lecture. That is an inference from the slides; there's no recording to confirm it.

Not confirmed: what was said in the Fall 2025 lecture, and the page-by-page differences between the 2023 video and the 2025 slides. This post was not written from the video.

Further reading: locks and synchronization from the operating-system side in CS111 Lecture 6: Implementing locks.

Series: previous PA5, the fastest kernel on an H100 | next L15 Memory consistency | Series overview

References

• Stanford CS149 Fall 2025 home page and lecture schedule
• Lecture 14: Cache Coherence (slide PDF)
• Lecture 14, slide-by-slide web version
• Lecture 15 slide PDF (opens by repeating L14)
• CS149 2023 Lecture 11 Cache Coherence video (supplement)
• CS149 2023 YouTube playlist
• Assignment 2 README (stanford-cs149/asst2)