The Problem: Processor-Memory Bottleneck

• The Gap: CPU can execute an instruction in less than 1ns, but accessing main memory can take 100ns (100x slowdown)

• Small memories are fast and expensive, large memories are slow but cheap

  

• Solution → Caches: memory hierarchy is a pyramid of sotrage, each level is a cahce for the level below it

  • Registers (in CPU) ➔ L1 Cache (~32KB, 1-4 cycles) ➔ L2 Cache (~256KB, ~10 cycles) ➔ L3 Cache (Shared, ~8MB, ~40 cycles) ➔ Main Memory (GBs, ~100 cycles) ➔ Disk (TBs, millions of cycles)

How Caches Work

• Cache hit: data CPU needs is already in the cache, this is fast
• Cache miss: data is not in the cache, CPU must wait for it to be fetched from a lower level, this is slow
• Cache lines: data is transferred between memory and cache in fixed-size blocks called cache lined (typically 64B)
  • Exploits spatial locality- if you use one byte, you’ll likely use the nearby bytes soon

Why Caches Work: Locality

Caches are effective because most programs have good locality

• Temporal locality: recently accessed items are likely to be access again soon (i.e., loop counter)
• Spatial locality: if a memory location is accessed, nearby locations are likely to be access soon (through iterating through an array)

Cache Misses

1. Compulsory (cold) miss: first access to a block, unavoidable
2. Capacity miss: program’s working set (active data) is larger than the cache size
3. Conflict miss: in some cache designs, two frequency used data blocks map to the same cache slot and keep evicting each other

Cache Write Policies

Write-Hit

Data to be written is already in the cache