Cache

[toc]

1. Cache

There is a layer of high-speed cache between the CPU and memory, used to make up for the speed difference between them. In a typical set-associative cache, a memory address can be divided into index, tag, and offset. First use the index to select the cache set. Then use the tag to identify the cache line. Then use the offset to select a byte within that cache line. Finally use state such as the valid bit to determine whether the cache line is usable.

1.1. Problems Brought by Cache

Multiple processor cores may cache the same memory location. If Core A updates it, how do the other cores learn about the change? This requires introducing a cache-coherence protocol.

2. Cache Coherence

2.1. MESI Protocol

MESI divides a cache line into four states:

• Invalid The cache line is invalid.
• Shared Multiple processors may cache the same line, and the cached data is consistent with memory.
• Exclusive Only the current processor caches the line, and the cached data is consistent with memory.
• Modified The current processor has modified the cache line, so the copy in main memory may be stale.

2.1.1. Specific Implementation

• Processor0 needs to read data S and its state is I. Processor1’s state is M/E/S. Processor0 issues a Read request. If another processor holds the newest data in M state, the coherence protocol supplies that data and changes the relevant states; otherwise the data can be read from another cache or memory.
• Processor0 needs to write data S. If the state is M, it can write directly. If the state is E, it can write directly and change the state to M. If the state is S, it must first obtain exclusive ownership and invalidate other shared copies, then write and enter M. If the state is I, it must first obtain the cache line and exclusive ownership, then write and enter M.
• Summary MESI uses write-invalidate. Typical caches also use write-back, so a write does not have to be written to main memory immediately.

2.1.2. MESI Performance Problem

When a cache line is shared, a writer must first obtain exclusive ownership and invalidate other copies, which creates coherence traffic and waiting.

3. Write Buffer and Invalidation Queue

3.1. Write Buffer

A write buffer is temporary storage on the processor’s write path. When a write is still waiting for a cache-coherence transaction to complete, the data can first enter the write buffer while the processor continues executing later instructions.

Summary After a processor executes a write, other processors may not be able to observe that write immediately.

3.2. Invalidation Queue

After receiving an Invalid message, a processor may queue it for later processing; whether and when it can reply before applying the invalidation depends on the implementation.

3.3. Problems Brought by These Components

Visibility and reordering.

4. Reordering Problem

Write buffers, out-of-order execution, and related mechanisms can make other processors observe memory operations in an order different from program order.

4.1. Categories

StoreLoad A Load after a Store may be observed as taking effect before that Store.

StoreStore The observable order of two Stores may change.

LoadLoad The observable order of two Loads may change.

LoadStore The observable order of a Load and a later Store may change.

Which reorderings are allowed depends on the processor architecture and memory model.

5. Visibility Problem

If one processor has executed a write but the write has not yet become observable to another processor, the other processor may still read the old value. That is the visibility problem discussed here.

5.1. Solution

Use synchronization primitives or memory barriers to establish the required ordering of memory accesses.

6. Memory Barrier

A memory barrier constrains certain memory operations from crossing the barrier or being observed by other processors in an order that violates the required ordering. XY can be used to describe an ordering constraint: an X-type access before the barrier must not cross the barrier and be observed after a Y-type access that follows it.

6.1. Specific Implementation

Different processor architectures provide different Fence / Barrier instructions and guarantees. A memory barrier should not be understood simply as “clearing the invalidation queue” or “flushing the entire write buffer into cache or memory.”

7. References

• Introduction to Cache Coherency - Cao Zhiyuan - InfoQ