CPU cache coherence simulator

Pick a workload and press Play or One round. In each round every core performs its part of the workload. The four columns show each core's private cache, with the state of every line it holds; the log lists each operation with its cost and the bus messages it caused. You can also issue a single read or write from any core with the controls on the right of the toolbar.

• False sharing: each core writes its own counter, but all four counters are in line 0. Every write has to take the line away from the core that wrote last.
• Padded counters: the same counters, each on its own line. After the first write, every write is an L1 hit with no bus traffic.
• Read-only sharing: all four cores read the same line. It ends up Shared in every cache and stays there.
• One shared counter and Producer and consumer show real sharing, where the traffic is unavoidable.

The protocol is tested on random sequences of reads and writes: every read returns the value most recently written, and a line is never held Modified or Exclusive by one core while another core holds any copy.

A CPU cache is a small, fast memory on the processor that holds copies of recently used data from main memory. Reading main memory takes hundreds of cycles; the closest cache, L1, answers in a few. Modern processors have several levels: each core usually has its own L1 and L2, and the cores share a larger, slower L3.

Caches do not store single bytes. They move memory in fixed blocks called cache lines, 64 bytes on current x86 processors from Intel and AMD, so reading one byte brings its neighbours along. That makes sequential access fast, and it is also the reason two unrelated variables can interfere with each other if they share a line.

If two cores both cache the same line and one of them writes it, the other core's copy is now stale. Without a protocol, it could go on reading the old value indefinitely, and two cores writing the same line could each lose the other's update. Cache coherence rules this out. The usual way to state it is single-writer, multiple-reader: at any moment a line may have one core that can write it, or any number of cores that can read it, but not both.

The hardware enforces this by having caches tell each other what they are doing. In a snooping design, every cache watches a shared bus or interconnect and reacts to the requests of the others; in a directory design, a central record tracks which caches hold each line and sends messages only to those.

MESI gives each line in each cache one of four states, named by their initials:

Coherence works on whole lines. When threads on different cores write different variables that share a line, every write invalidates the other cores' copies, and the line moves from cache to cache on almost every write, even though the threads never touch each other's data. This is false sharing. It shows up as multithreaded code that gets slower, not faster, as threads are added.

The simulator's workloads, 100 rounds each, with its example latencies:

The simulator uses a snooping bus: every request is seen by every cache. That is simple and fast with a few cores, but the traffic grows with the number of cores, since every miss must be checked by all of them. Larger processors use directories or snoop filters, which record which caches may hold each line so that requests go only to those. Multi-socket servers extend the same idea across sockets, where a transfer between caches costs considerably more than one within a chip.

MESI is the basis for most protocols in use, with extra states for efficiency. MOESI, used in AMD processors, adds an Owned state: a cache can share a modified line with others without first writing it back to memory, and stays responsible for writing it back later. MESIF, used by Intel, adds a Forward state that picks one of the sharers to answer requests for the line, so a request does not get a reply from every cache that holds it.

Coherence is about one memory location: all cores agree on the order of writes to it. It says nothing about the order in which a core's writes to different locations become visible to others. That is the job of the processor's memory consistency model. To go faster, cores buffer stores and reorder memory operations, so another core can observe them in a different order from the program. Concurrent code relies on atomic operations and memory fences, or on language-level atomics and locks that use them, to get the ordering it needs.

Multiprocessors with private caches needed coherence from the start. James Goodman described the write-once protocol in 1983, and Mark Papamarcos and Janak Patel of the University of Illinois published the protocol now called MESI in 1984, which is why it is also known as the Illinois protocol. Its key addition was the Exclusive state, which saves a bus transaction whenever a core writes data that no other core has read.