Basic Introduction

An introduction to cache coherency

Illustrating Incoherency

Incoherence Illustration

Consider the following diagram illustrating the coherence problem with multicore architectures.

A Primer on Memory Consistency and Cache Coherence, (Sorin, Wood, and Hill 2011)

Explanation

In this simple example, the variable A is initialized to 42 at time 1 and is in Core 1's cache. During time 2, Core 2 loads the value of A into its cache; the cache's are coherent, both containing the updated value of A (42). At time 3, Core 1 increments A by 1 with an add instruction and stores in memory. Core 2's cache is now incoherent with Core 1 and does not contain an updated record.

Generally speaking, this is an imperfect and (partially) incorrect example of cache incoherency. It implies that a read by one core can happen simultaneously while another core is writing. This is generally not possible and therefore necessitates a more acurate definition of coherence.

Defining Cache Coherence

Foundation

Note the term single-writer-multiple-reader (SWMR) invariant, which means for any given memory location at a moment in time, there is a single core that may write it (and read it) or some number of cores that may read it.

This means it is not possible for one core to write to a memory location, while another core reads from the same location simultaneously.

Additionally, reads from multiple cores during a read-only time, must return the same value. Honoring the SWMR invariant while reading inconsistent values during a read-only time, does not achieve coherency. Therefore, value propagation must be correct.

Consider time measured in epochs, where by any epoch can support a read-write by a single core, or a read-only by many cores.

In this illustration above, you can see that the SWMR invariant is upheld; each epoch allows a read-write by a single core, or a read-only by multiple cores. To reiterate, this invariant alone does not guarantee coherency; the multiple cores reading during a read-only epoch could potentially read different values. Therefore, what is needed, is a guarantee that the value of a memory location at the start of an epoch is the same as the value of the memory location at the end of the its most recent read-write epoch.

Referring to the illustration above, if cores 1, 2, and 3 read from address 0x3EF during epoch 4, the value in the memory location 0x3EF must exactly match the value at the end of epoch 3. Assuming core 1 completed a write at 0x3EF the value was changed and the value read during the read-only epoch (epoch 4) must match the updated value stored during epoch 3.

This is invariant is known as the data-value invariant. This leaves us with a suitable definition of coherence.

Coherence Invariants

Single-write-multiple-read Invariant

For any given memory location A, at any given moment in time, there exists only a single core that may write to A (and can also read it) or some number of cores that may only read from A.

Data-value Invariant

The value of the memory location at the start of an epoch is the same as the value of the memory location at the end of its last read-write epoch.

Example

During read-only epoch, the cores reading a value can potentially read different values OR one core might fail to read the last value written during the most recent (last) read-write epoch. Both would be considered breaking the data-value invariant.

Important Notes

Coherency, in practice, is performed at a very granular level; many CPUs enforce coherency at the cache block level. This means SWMR invariant is applied on a cache block-by-block basis; allowing simultaneous writes to differing blocks, only.

Coherence invariants are maintained using invalidate protocols, that allow cores to use queues and to communicate with each other prior any read or write to ensure cached entries with updated values don't exists or to update and invalid block.