Caches
Understand how cache hierarchies use locality, address mapping, blocks, associativity, and write policies to reduce average memory access time.
The memory hierarchy and caches
Memory systems balance memories that are small, expensive, and fast against memories that are large, inexpensive, and slow. The gap between registers and main memory is especially important: accessing a register takes roughly clock cycle, while accessing main memory can take several hundred cycles. DRAM access is also variable: the first value in an array can take many nanoseconds to access, while nearby values may be accessed faster afterward.
Using only DRAM would make a computer too slow, while using only registers would make it too expensive. A cache adds an intermediate-sized memory made from SRAM between registers and main memory, which is typically DRAM. Frequently accessed data is transferred automatically into the cache so that many accesses can be served there.
Cache levels and access outcomes
Every memory access in a system with a cache is either a or a . A hit means the requested data is already in the cache and can be supplied quickly; a miss means it is not there, so the request goes to DRAM or another lower level of the hierarchy. A cache aims to maximize its hit rate, or equivalently minimize its miss rate.
Modern computers commonly layer caches of different sizes and speeds. L1 is closest to the processor and is the smallest and fastest level; L2 and L3 provide additional levels. An L4 cache is also possible, but returns diminish as more levels are added, so the hierarchy does not continue indefinitely.
The L1 cache often separates instructions from data. Although instructions and data coexist in main memory, their patterns differ enough that separating them can help maximize performance. These separate caches are commonly called L1I and L1D.
in memory access
Caches rely on : the tendency for similar data to be accessed close together in time. Temporal means that after a program accesses a value, it is likely to access that same value again soon. Spatial means that after accessing a value, a program is likely to access nearby memory addresses soon.
In the loop below, repeated accesses to total exhibit temporal because the same variable is accessed on each iteration, with only a few instructions between accesses. The accesses to a[i] exhibit spatial : after loading one element, the program soon loads the nearby element a[i+1], whose address is only bytes away.
int total = 0;
for (int i = 1; i < n; i++) {
total += a[i];
}
return total;
is a general principle. Refrigerators, backpacks, and laundry hampers are examples of everyday mechanisms that exploit temporal or spatial .
Direct-mapped caches
A assigns every memory address to exactly one cache index. With entries, a cache cannot hold all possible -bit addresses, so many addresses map to each entry. A mapping function specifies the index for address ; the cache uses the same function to place data and to look it up. This is similar to using a hash function in a hash table.
Two possible mappings illustrate the choice. A chunk mapping assigns consecutive ranges of addresses to each index, using . A stripe mapping uses , distributing consecutive addresses across consecutive indices. Stripe mapping is chosen because nearby addresses can occupy different entries at the same time, which better serves spatial ; chunk mapping would send nearby addresses to the same index.
For stripe mapping, the least-significant address bits form the index, and the most-significant bits form the tag. The tag distinguishes which of the addresses mapped to an index is currently stored there.
Each direct-mapped entry stores a tag, a valid bit, and data. The index identifies the entry and does not change. A valid bit of means the entry has no meaningful cached data; a valid bit of means it does. Invalid entries are useful at startup, when all entries can be marked invalid. The tag identifies the address currently represented by the entry, and the data holds the value at that address.
To access address , split it into index and tag , then inspect entry . If the entry is invalid, the access misses. If it is valid but its tag does not equal , the access also misses. Only a valid entry with a matching tag is a hit, allowing the data to be used without accessing main memory.
On a load miss, fetch the data from main memory and fill entry . If the entry already contains valid data, that data is evicted. Then set the valid bit to , set the tag to , and store the fetched data. A later access to the same address can then hit, exploiting temporal .
For a -entry cache and -bit addresses, : the low bits are the index and the high bits are the tag. Starting with an empty cache, these loads have the following outcomes:
0xEEEEE14A: .0xEEEEE14B: .0x9999914A: and eviction.0xEEEEE14A: and eviction.
Blocks, offsets, and spatial
A cache entry can hold a whole block, also called a line, rather than just one memory address. With blocks of bytes, an address is divided, from most significant to least significant, into a tag, an -bit index, and a -bit block offset. Memory is divided into aligned blocks, and a cache fill transfers the entire block containing the requested address. The offset selects which byte within the block to return. Loading one byte therefore also brings in its neighbors, anticipating that spatial may make them useful soon.
For -bit addresses, a -entry cache, and -byte blocks, and . The low bits are the offset, the next bits are the index, and the remaining bits are the tag. For the same four loads used in the direct-mapped example, the outcomes are:
0xEEEEE14A: .0xEEEEE14B: hit, because it is in the block brought in by the first load.0x9999914A: and eviction.0xEEEEE14A: and eviction.
Comparisons between cache designs should hold total cache capacity constant. Changing from -byte blocks to -byte blocks while keeping the same number of entries makes the cache times larger in bytes and silicon, and times as expensive. To keep capacity constant when block size doubles, halve the number of entries.
Store policies and dirty data
Stores introduce choices about what to do on a store miss and when to update main memory. A policy fills the cache with a block on a store miss, relying on the hypothesis that a program that writes a location may read it again soon. A no- policy sends the write to memory without filling the cache.
With , every store updates the cache and is immediately sent to main memory. This policy is simple. With write-back, a store updates the cache without immediately sending the change to main memory. Write-back can avoid many costly main-memory stores and is popular, but it requires bookkeeping because the cache and main memory can become inconsistent.
A adds a to each entry. A clean entry agrees with main memory; a dirty entry might disagree. On a fill, set the to . Whenever a store updates an entry, set the bit to . On eviction, do nothing if the entry is clean; if it is dirty, write its data back to main memory.
For the -byte-block setup, the sequence load 0xEEEEE14A, store 0xEEEEE14B, load 0x9999914A, load 0xEEEEE14A produces a , a store hit, a with eviction, and a with eviction, respectively.
Fully associative caches and replacement
In a , each block has only one possible entry, so different blocks that map to the same entry can repeatedly evict one another even when other entries are available. A removes the index restriction: any memory block may use any cache entry. For addresses with -byte blocks, the address has a tag of bits and no index bits.
Because the desired block could be in any entry, a must search every entry on each access. For a four-entry cache with -byte blocks, all four entries are equally available to hold any address. On the sequence load 0xEEEEE14A, load 0xEEEEE14B, load 0x9999914A, load 0xEEEEE14A, the outcomes are a , a hit, a , and a hit.
When a is full, a chooses which block to evict. The goal is to estimate which block is least likely to be used again soon while making the decision efficiently.
Least-recently used (LRU): Track the last access time of every block and evict the block used least recently. The assumption is that a block left unused longer is less likely to be used soon. Tracking timestamps creates substantial overhead.
Not most-recently used (NMRU): Track only the most recently accessed block, then randomly choose a different block to evict. This can make worse choices than LRU but is cheaper to implement.
First-in first-out (FIFO): Track when each block was filled, not when it was read, and evict the block that was filled longest ago.
Associativity reduces evictions but costs hardware resources. Searching all entries requires a . CAMs are expensive, large, hot, and slow; their cost scales with the number of entries, making fully associative caches practical mainly when they are very small.
Set-associative caches
A balances the direct-mapped and fully associative designs. A memory block can occupy one of a small number of entries grouped into a set. If each set has entries, the cache has ways. With total entries, it has sets.
Direct-mapped and fully associative caches are special cases. In a , , so there is one way and sets. In a , , so there is one set with ways. In a set-associative design, entries can be pictured as a grid with one row per set and one column per way. The index has bits, and the tag grows correspondingly.
To access a , use the index to locate a set, then search all ways in that set for a valid entry with a matching tag. On a miss, choose a way within that set to evict using a .
For -bit addresses, -byte blocks, and a cache with entries and -way associativity, there are sets. The low bits are the block offset, the next bits are the index, and the remaining bits are the tag. With LRU replacement, the sequence load 0xEEEEE14A, load 0xEEEEE14B, load 0x9999914A, load 0xEEEEE14A results in a , a hit, a , and a hit.
The three categories of cache misses
Misses can be categorized by why they occur. Here, a means an aligned block-sized region of memory, not a particular storage entry in the cache. With block size bytes, the line containing address is an aligned range satisfying
A concerns the first access to that memory range, regardless of where it might be stored in the cache.
Cold or compulsory misses occur on the first access to a given .
Conflict misses occur when associativity is too low, so too many lines compete for the same set and one evicts a line needed later.
Capacity misses occur when the entire cache is too small for the working set; increasing associativity alone cannot help.
To classify a miss, first ask whether that was ever loaded before. If not, it is cold. If it was loaded before, ask whether the access would miss in a . If it would not, the miss is a ; if it would, it is a .
Cache performance and design trade-offs
(AMAT) summarizes average performance across memory accesses. It is calculated as
Here, is the time to access the cache. A hit takes this time, while a miss takes this time to check the cache and then additional time to reach lower memory. The miss rate is the fraction of accesses that miss. The miss penalty is the time to retrieve data from a lower memory structure, such as a lower-level cache or main memory.
For example, if cache access takes ns, main-memory access takes ns, and of accesses hit, the miss rate is , giving ns. In a hierarchy with L1 and L2, the L1 miss penalty is the time to access the rest of the hierarchy, including trying L2. The average access time at L2 can therefore be used as the miss penalty in the L1 calculation.
Cache design balances total cache size, block size, associativity, , write policy, number of cache levels, and whether instruction and data caches are unified. These choices affect hit time, miss rate, and miss penalty; improving performance requires decreasing one or more of those quantities.
With total cache size fixed in a , increasing block size gives fewer entries, each holding more data. This means fewer tags and less tag overhead, and it can reduce cold misses by bringing in neighboring data. A larger block may therefore reduce miss rate when many misses are cold. However, fewer entries can increase conflict misses, and if the program's working set does not fit in the cache, a block that is too large can increase miss rate. Larger blocks also increase miss penalty because more data takes longer to fetch from main memory.