Basic Introduction
An introduction to cache coherency
Last updated
Was this helpful?
An introduction to cache coherency
Last updated
Was this helpful?
Consider the following diagram illustrating the coherence problem with multicore architectures.
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.
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.
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.
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.
