What the animation shows

The same address trace goes into three L1 caches of the same size at once: a direct-mapped cache, a 2-way set-associative cache and a fully associative cache, each with 4 lines of 16 bytes (64 B). For every access you see the address cut into tag / index / offset (differently for each cache), the set being searched, one tag comparator per way, hit or miss, and on a miss which line is thrown out and whether it must be written back. Under the caches a two-level hierarchy (L1 → L2 → RAM) turns the hits and misses into cycles and AMAT, the average memory access time.

Press Step Access to watch one access in steps, Run Trace for the rest of the trace, and Run Trace Again to run it once more with the caches warm. The trace list on the left keeps one letter per cache and access: H hit, M miss, with the kind of miss as a small suffix: c cold, k capacity, f conflict.

The memory wall

A register is read in about 0.3 ns, a word from main memory (DRAM) takes about 80 ns: some 250 cycles of a 3 GHz core. If every load went to DRAM, the processor would spend almost all its time waiting. A cache is a small, fast memory next to the core that keeps copies of recently used memory: an L1 cache answers in about 1 ns (4–5 cycles), an L2 in about 4 ns, a shared L3 in 10–15 ns. It works because programs have locality:

  • Temporal locality: a word used now is likely to be used again soon (a loop counter, a sum, the loop's own code).
  • Spatial locality: a word near one used now is likely to be used soon (the next element of an array, the next instruction).
Access time on a log scale: registers 0.3 ns, L1 cache 1 ns (4 to 5 cycles), L2 4 ns, shared L3 10 to 15 ns, DRAM main memory 80 ns (about 250 cycles)
Each level down the hierarchy is bigger and slower; DRAM is about 250 cycles away, which is why caches exist.

Blocks and how an address is split

A cache does not store single words but blocks (lines) of consecutive bytes: 16 B here, 64 B in real CPUs. A miss brings the whole block in, which is how spatial locality pays: in Array walk the first access to a[0] misses and brings a[0..3], so the next three hit. One miss per 4 words is a 25 % miss rate in every organisation.

The address itself says where to look. Its low bits, the offset, pick the byte inside the block (log2(block size) bits). The next bits, the index, pick the set (index bits = log2(sets)). The rest is the tag, stored with the line and compared on every lookup, because many blocks share a set. The same 64 B cache, three ways:

Organisationsets × wayssplit of 12 bits0x1040x140comparators
Direct-mapped4 × 1tag 6 · index 2 · offset 4tag 0x04, set 0, offset 4tag 0x05, set 01
2-way set-associative2 × 2tag 7 · index 1 · offset 4tag 0x08, set 0, offset 4tag 0x0A, set 02
Fully associative1 × 4tag 8 · offset 4tag 0x10, offset 4tag 0x144

With the same size, every doubling of the ways halves the number of sets: one index bit fewer, one tag bit more, and twice the comparators. Each line also has a valid bit V: after power-on or a flush the tags hold garbage, and a comparator only reports a hit if V = 1 and the tags are equal.

Direct-mapped, set-associative, fully associative

  • Direct-mapped: each block has exactly one place. One comparator, and the data can be read out while the tag is still being compared: the fastest and cheapest, and the one real L1s cannot afford because of conflict misses.
  • N-way set-associative: a block may go in any of the N ways of its set. N comparators work in parallel, and a multiplexer picks the data of the way that hit, which adds a little to the hit time. Real L1 data caches use 8 to 12 ways, L2 and L3 8 to 16 or more.
  • Fully associative: one set, a block may go anywhere; every line needs its own comparator. Used only where there are few entries: TLBs, small victim caches.
Addresses 0x100 and 0x140 have the same index bits 00; in the direct-mapped cache both need set 0 and 0x140 evicts 0x100; the 2-way cache keeps both in the two ways of set 0; the fully associative cache keeps both in any line
Two blocks with the same index fight over one line in a direct-mapped cache; with two ways, or full associativity, both stay.

The three C's: why a miss happens

  • Compulsory (cold): the block was never in this cache. Even an infinite cache misses. Bigger blocks reduce them; a prefetcher hides them.
  • Capacity: the program uses more blocks than the cache holds, so a fully associative cache of the same size misses too. Only a bigger cache (or a program with a smaller working set) helps.
  • Conflict: the cache had room, but too many blocks mapped to the same set. A fully associative cache of the same size would have hit. More ways, or a different layout of the data, help.

A branch target buffer is a small cache indexed by the PC and has the same cold and conflict misses: see Branch Prediction on the MIPS Pipeline, where two loop branches evict each other in a 2-entry BTB.

The page classifies every miss the way Hill's classic definition does: next to each cache a hidden fully associative LRU cache of the same size and policy runs the same trace. A miss on a block never seen before is cold; otherwise, if the shadow cache also misses it is capacity, and if the shadow hits it is conflict. The fully associative column therefore never shows a conflict miss.

Stride 64 B is the textbook thrash: 0x100, 0x140, 0x180 and 0x1C0 are exactly the cache size apart, so their index bits are equal and all four compete for set 0, while three sets stay empty. The direct-mapped and 2-way caches miss 12 times out of 12 (4 cold + 8 conflict); the fully associative cache keeps all four blocks and misses only the first 4 times. Two arrays a[i] + b[i] is the same problem in real code: two arrays 64 B apart ping-pong in set 0 of the direct-mapped cache (16 misses), while 2 ways are enough. b padded +16 B moves the second array by one block, and the direct-mapped cache is fine too: 4 cold misses.

Replacement: LRU, and when it is the worst choice

On a miss in a full set, one line must go. LRU (least recently used) throws out the line unused for the longest time; each line on the canvas shows its rank in the set, 0 being the most recent. An empty (invalid) way is always used first. A direct-mapped cache has nothing to choose.

LRU is usually good, but Loop over 5 blocks shows its trap: a loop over 5 blocks in a 4-line fully associative cache. Every time, the block LRU throws out is exactly the one the loop needs next, so all 15 accesses miss (5 cold + 10 capacity). The direct-mapped cache, which cannot choose at all, keeps 0x110–0x130 in their own sets and misses only on 0x100 and 0x140 (9 misses). Random replacement would keep some blocks and beat LRU here.

Real chips rarely use true LRU beyond 2 ways: remembering the exact order of 8 or 16 ways costs too many bits and too much updating on every hit. They use pseudo-LRU (a binary tree of bits that points away from the recently used half), random replacement, or adaptive policies such as RRIP that resist loops and scans like this one.

Writes: write-back and write-through

  • Write-back: a write changes only the cache line and sets its dirty bit D. The block goes to the next level only when the dirty line is evicted (or flushed). Many writes to the same block cost one write-back. Usually paired with write-allocate: a write miss first fetches the block like a read, then writes into it, because more writes to that block are likely to follow.
  • Write-through: every write also goes to the next level, so the line is never dirty and memory is always up to date. To avoid waiting for L2 on every store, writes go into a write buffer that drains in the background. Usually paired with no-write-allocate: a write miss just sends the word on and does not bring the block in.

Sum into x reads a[i] and updates x 8 times. With write-back, x's line is dirty after the first write and the next 7 writes are silent: 0 B reach L2 until Write Back Dirty Lines sends one 16 B block. With write-through, 8 writes × 4 B = 32 B go to L2. The misses and the AMAT are the same, because the writes are buffered. Write then evict dirties the 0x100 block with 4 writes; then R 0x140 maps to the same direct-mapped set, the dirty line is the victim and is written back (16 B), and R 0x100 misses again (a conflict miss). In the 2-way and fully associative caches both blocks fit and nothing is written back. Switch to write-through and the 4 writes miss without allocating, so the final read of 0x100 is a cold miss everywhere.

Write-back vs write-through for 8 writes to x: write-back marks the L1 line dirty and sends nothing to L2 until the line is evicted, then one 16 B block; write-through sends every write, 32 B in all
Write-back collects all 8 writes in a dirty line and sends one block later; write-through sends every write to L2 at once.

Multi-level caches and AMAT

A miss in L1 goes to L2, a miss there to RAM. The page charges 1 cycle for an L1 hit, 1 + 10 for a miss that L2 answers and 1 + 10 + 100 for one that goes to RAM; write-through writes and write-backs go through the write buffer and cost nothing extra. The average is

AMAT = L1 time + L1 miss rate × (L2 time + L2 local miss rate × RAM time)

where the L1 miss rate counts the misses that fetch a block (a write-through write miss does not), and the local miss rate of L2 is its misses divided by the requests that reach it. The global miss rate, L2 misses divided by all CPU accesses, is the product of the two. For Stride 64 B in the direct-mapped cache: 1 + 12/12 × (10 + 4/12 × 100) = 44.33 cycles. The panel also prints the same run without L2 (1 + 100 per miss): a cold L2 adds its 10 cycles to every miss (28.5 instead of 26.0 cycles for Array walk), but once it is warm it turns a 111-cycle miss into 11 (press Run Trace Again: the stride trace drops to 11 cycles per access in the direct-mapped column and to 1 in the fully associative one).

Real hierarchies also choose between inclusive caches (everything in L1 is also in L2, which makes snooping easy), exclusive ones (a block is in one level only, so the total capacity is larger) and neither. Each column here has its own L2, 16 lines, 4-way, that is neither.

What a miss costs also depends on the processor: an out-of-order processor keeps issuing independent instructions while a load misses, until its reorder buffer fills.

The traces, cold caches, 4 lines × 16 B, write-back

TraceAccessesDM misses2-way missesFA missesAMAT DM / 2-way / FA
1. Array walkR a[0..15], a = 0x1004 cold4 cold4 cold28.5 for all (L1 → RAM 26.0)
2. Stride 64 BR 0x100, 0x140, 0x180, 0x1C0 × 312 (4 cold + 8 conflict)12 (4 + 8 conflict)4 cold44.33 / 44.33 / 37.67; again 11 / 11 / 1
3. Two arraysR a[i], R b[i], i = 0..7, b = 0x14016 (4 cold + 12 conflict)4 cold4 cold36.0 / 28.5 / 28.5; again 11 / 1 / 1
4. b padded +16 Bas 3 with b = 0x1504 cold4 cold4 cold28.5 for all
5. Loop over 5 blocksR 0x100 … 0x140 × 39 (5 cold + 4 capacity)11 (5 + 6 capacity)15 (5 + 10 capacity)40.33 / 41.67 / 44.33; again 5 / 7 / 11
6. Sum into xR a[i], R x, W x, i = 0..7, x = 0x2283 cold3 cold3 cold14.75 for all
7. Write then evictW 0x100 … 0x10C, R 0x140, R 0x1003 (2 cold + 1 conflict)2 cold2 cold39.33 / 37.67 / 37.67

Change lines to 8 or block to 8 B and run them again (each trace has a tab above the controls; it loads at once): 8 lines cure the 5-block loop and the two arrays, but not the 64 B stride (its four blocks still share sets in the direct-mapped and 2-way caches); 8 B blocks double the cold misses of the array walk (8 instead of 4). The Custom tab takes a trace of up to 48 accesses such as R 0x100, W 0x104, 0x140 (read by default, aligned addresses below 0x1000), and Access runs one typed access at the current point of the trace.

Programming for the cache

  • Walk memory in order. C and Java store a 2-D array row by row; a loop that runs along a row uses every word of each block, a loop down a column uses one word per block and may touch a new block every time.
  • Avoid power-of-two strides between things used together: arrays of size 4096, matrix rows of 1024 doubles, structures aligned to the same page offset all land in the same sets (Stride 64 B, Two arrays).
  • Pad such arrays by a block or so to move them to different sets (b padded +16 B).
  • Blocking (tiling): when the data does not fit, work on a tile that does (for matrix multiply, a sub-matrix of each operand), finish everything that tile is needed for, then move on. The same arithmetic, many fewer capacity misses.
  • Keep hot data small and together, and data written by different threads in different blocks (false sharing makes cores steal a block from each other on every write).

Real sizes

A current x86 or ARM core has a 32–48 KB L1 data cache (8 to 12 ways) and a separate 32–64 KB L1 instruction cache, a private L2 of 256 KB to 2 MB, and an L3 of several MB shared by all cores. Lines are 64 B everywhere (Apple's M-series use 128 B). With 32 KB, 8 ways and 64 B lines, a 48-bit address splits into 6 offset bits, 6 index bits (64 sets) and 36 tag bits. L1 is usually indexed with the virtual address and tagged with the physical one, so the TLB lookup runs in parallel with the cache lookup.

What the page leaves out

  • Tiny sizes (64 B L1, 256 B L2, 12-bit addresses) so that every line fits on screen; real L1s are about 500 times bigger with 64 B lines.
  • Word accesses only, always aligned; no data values are stored or shown: the page is about where a block lives, not what is in it. The block's words light up when one is accessed.
  • True LRU; real caches use pseudo-LRU or other policies.
  • One access at a time, blocking: no overlapping misses (MSHRs), no prefetcher (which would hide the array walk's misses), no critical-word-first.
  • A write buffer of unlimited size: write-through writes and write-backs never stall. The dirty victim is written to L2 before the new block is fetched.
  • L2 neither inclusive nor exclusive, and a separate L2 per column only so the three are comparable; L2 has the same block size as L1. No L3, no TLB or virtual addresses, no coherence between cores.
  • Fixed latencies (1 / 10 / 100 cycles), independent of the block size and the bus width.

The MIPS datapath page runs a program with 1-cycle memory; this page is what hides behind that cycle.

Below the cache, every address is first translated from virtual to physical: Virtual Memory in Hardware follows a load through the TLB and the page table, with the same vocabulary (a page is a block, a page fault a miss).

When a device writes to RAM by DMA, the cache can hold stale or dirty copies of those lines: Direct Memory Access (DMA) shows snooping on x86 and the cache cleans and invalidates a non-coherent ARM SoC needs.

The same write-through vs write-back choice, one level up: Cache Strategies puts Redis in front of a database (cache-aside, write-through, write-behind, refresh-ahead).