Timedora

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 11 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 44 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 2n2^n entries, a cache cannot hold all 2642^{64} possible 6464-bit addresses, so many addresses map to each entry. A mapping function f(a)=if(a)=i specifies the index for address aa; 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 264−n2^{64-n} addresses to each index, using f(a)=⌊a264−n⌋f(a)=\left\lfloor \frac{a}{2^{64-n}}\right\rfloor. A stripe mapping uses f(a)=a mod 2nf(a)=a\bmod 2^n, 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 nn address bits form the index, and the most-significant 64−n64-n bits form the tag. The tag distinguishes which of the 264−n2^{64-n} 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 00 means the entry has no meaningful cached data; a valid bit of 11 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 aa, split it into index ii and tag tt, then inspect entry ii. If the entry is invalid, the access misses. If it is valid but its tag does not equal tt, 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 ii. If the entry already contains valid data, that data is evicted. Then set the valid bit to 11, set the tag to tt, and store the fetched data. A later access to the same address can then hit, exploiting temporal .

For a 256256-entry cache and 3232-bit addresses, n=8n=8: the low 88 bits are the index and the high 2424 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 2b2^b bytes, an address is divided, from most significant to least significant, into a tag, an nn-bit index, and a bb-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 3232-bit addresses, a 256256-entry cache, and 1616-byte blocks, n=8n=8 and b=4b=4. The low 44 bits are the offset, the next 88 bits are the index, and the remaining 2020 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 11-byte blocks to 1616-byte blocks while keeping the same number of entries makes the cache 1616 times larger in bytes and silicon, and 1616 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 00. Whenever a store updates an entry, set the bit to 11. On eviction, do nothing if the entry is clean; if it is dirty, write its data back to main memory.

For the 1616-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 2b2^b-byte blocks, the address has a tag of 64−b64-b 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 22-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 2w2^w entries, the cache has 2w2^w ways. With 2n2^n total entries, it has 2n−w2^{n-w} sets.

Direct-mapped and fully associative caches are special cases. In a , w=0w=0, so there is one way and 2n2^n sets. In a , w=nw=n, so there is one set with 2n2^n 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 n−wn-w 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 3232-bit addresses, 1616-byte blocks, and a cache with 512512 entries and 22-way associativity, there are 256256 sets. The low 44 bits are the block offset, the next 88 bits are the index, and the remaining 2020 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 2b2^b bytes, the line containing address aa is an aligned range satisfying

i×2b≤a<(i+1)×2b.i\times 2^b \le a < (i+1)\times 2^b.

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

tavg=thit+rmiss×tmiss.t_{\mathrm{avg}}=t_{\mathrm{hit}}+r_{\mathrm{miss}}\times t_{\mathrm{miss}}.

Here, thitt_{\mathrm{hit}} 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 rmissr_{\mathrm{miss}} is the fraction of accesses that miss. The miss penalty tmisst_{\mathrm{miss}} 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 11 ns, main-memory access takes 5050 ns, and 95%95\% of accesses hit, the miss rate is 0.050.05, giving 1+0.05×50=3.51+0.05\times 50=3.5 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.