Core 0 and core 1 each have a private cache. Both read a flag from memory: it is 0, and each cache keeps a copy. Core 0 sets the flag to 1, in its own cache. Core 1 checks the flag again, finds its copy, and reads 0. It will keep reading 0 for as long as its copy survives. Nothing is broken in either cache; each is doing exactly what a cache does. The system as a whole is wrong.
When every core keeps its own copy of memory, how do all of them see one consistent value?
The obvious fixes are to not cache shared data, or to write every store straight to memory. Not caching shared data throws away the reason caches exist: shared data is often the most frequently used. Writing through to memory updates memory, but core 1's stale copy is still in core 1's cache, and core 1 never looks at memory again while it hits. The copies themselves must be kept in step, and that needs messages between the caches: a protocol.
Every coherence protocol enforces the same two rules for each memory location:
Single writer, multiple readers (SWMR): at any moment, either one cache may write the location, or any number may read it, never both.
Data value: a read returns the value of the most recent write, in the order the writes were made.
To enforce them, a cache that wants to write must first get rid of every other copy (or update them), and a cache that wants to read must get the latest value, even if it is only in another cache. Each cache line carries a state saying which permission this cache holds; the protocol is the set of messages that changes those states.
Cache wants to | Must first |
|---|---|
Read a line it does not have | Get the latest value: from memory, or from the cache that holds it dirty |
Write a line it shares | Make every other copy invalid (or send them the new value, lesson 13.2) |
Write a line it does not have | Both: get the value and remove the other copies |
Coherence works on whole cache lines, typically 64 bytes. Two variables that happen to share a line behave as one: if core 0 writes a and core 1 writes b in the same line, the line bounces between their caches on every write, although they share no data. This is false sharing, and it can make a parallel program slower than its serial version. Padding or aligning the data so each core's variables sit in their own lines removes it.
System | Coherence |
|---|---|
Multicore processors | Hardware coherence among all cores' caches, invisible to software |
AMBA ACE and CHI | Coherence built into the interconnect protocol, with snoop channels or snoop messages (fact A23) |
Many accelerators and DMA engines | Not coherent, or coherent only one way; software manages copies (lesson 13.7) |
A parallel counter (illustrative) gave each of eight threads its own counter in an array of eight 8-byte integers. All eight sat in one 64-byte line. The program ran slower on eight cores than on one, because every increment moved the line. Padding each counter to its own line gave a near-linear speed-up.
Memory is updated, but other caches still hold their old copies and keep hitting on them without looking at memory.
No correctness problem (coherence keeps both writes), but a performance one: the line bounces between caches on every write (false sharing).
Private caches create copies that go stale when another core writes.
Coherence enforces single-writer, multiple-reader and the latest-value rule, per location.
It works on whole lines: unrelated data in one line causes false sharing.