Even when two programs perform the same number of additions, the order in which they read data can change their running time. A CPU can calculate much faster than it can bring values from a large memory. Caches bridge part of that gap by keeping copies of frequently used data close to the CPU.
A hierarchy of small, fast storage
A typical CPU uses registers, caches such as L1, L2, and L3, and main memory. Their capacities, access times, and sharing arrangements depend on the processor. The compiler and instructions specify which values use registers, while CPU caches are normally managed by hardware. The array address used by an application does not specify which level currently holds a copy.
Caches work because of locality. Temporal locality means using the same value again within a short time. Spatial locality means accessing values at nearby addresses in succession. A loop's accumulator often benefits from the former; a sequential array traversal often benefits from the latter.
Moving a cache line rather than one element
Suppose a cache line is 64 bytes and an integer occupies 4 bytes. Sixteen consecutive integers fit in one line. If accessing the first element causes a miss that brings in the line, later elements may be read from that same line. The following example illustrates access order. Actual measurements also depend on optimization, prefetching, array size, and other factors.
/* Read contiguous elements. */
for (size_t i = 0; i < n; ++i)
sum += a[i];
/* Skip 16 elements at a time. The total read count also differs. */
for (size_t i = 0; i < n; i += 16)
sum += a[i];The second loop uses just one element from each line before moving on. These loops perform different numbers of reads, so comparing their total times directly would not establish which access pattern is more efficient. Time per element and cache-miss counts help reveal how much of each transferred 64-byte line was actually used.
A small change in hit rate can add substantial delay
An access is a hit if the cache holds the required data and a miss otherwise. In a simple single-level model, average access time = hit time + miss rate × additional miss penalty. A 1 ns hit time, a 5% miss rate, and an additional 100 ns penalty give 6 ns. Reducing the miss rate to 1% gives 2 ns. A small fraction of slow accesses can dominate the average.
Real CPUs may service several misses concurrently and overlap computation with memory reads. This formula therefore cannot be used directly as the running time of an entire program. Use it as a model for identifying what contributes to access delay.
Conflicts can occur even when space remains
Unused capacity elsewhere in a cache does not necessarily provide a place for a particular block. In a direct-mapped cache, each memory block has one possible location. Two blocks mapped to the same location can repeatedly evict each other. In a set-associative cache, a block can occupy one of several locations within its set. A four-way set can hold four cache lines.
When every location in a set is occupied, the replacement policy selects a line to evict. Policies include least recently used (LRU) and approximations to it. Greater associativity can reduce conflicts but requires more comparison circuitry and other resources. Increasing capacity and increasing associativity are different changes.
When writes reach the next level
Write-through passes cache updates to the next level. Write-back marks a modified line and writes it back later, for example when it is evicted. With write-back, main memory may temporarily hold an older value while the CPU observes the newer value in the cache.
Whether to fetch a line on a write miss is a separate policy from when to propagate writes. Writing a CPU cache line back to memory is also different from making a file durable on an SSD. A value being written to memory does not imply that it will survive a loss of power.
Check your understanding
Question 1: Which kind of locality is involved when the same element is used repeatedly? Temporal locality. Accessing the next adjacent element instead exploits spatial locality.
Question 2: What is the average access time with a 2 ns hit time, a 2% miss rate, and an additional 80 ns penalty? It is 2 + 0.02 × 80 = 3.6 ns.
For shared-memory access by multiple cores and devices, continue to Interrupts, I/O, DMA, and Multicore Systems.