Memory Hierarchy & Cache

The Memory Speed Gap

Analogy: The CPU is like a formula racing car — incredibly fast. Main memory (RAM) is like a regular road. If the CPU had to wait every time it needed data from RAM, it would be like a race car constantly stopping at traffic lights. Cache is the VIP lane — a small, ultra-fast memory right next to the CPU.

Memory Hierarchy (top = fastest, smallest, most expensive):

Registers    : 1 cycle,    ~1KB,    $$$$$   (inside CPU)
L1 Cache     : 4 cycles,   ~64KB,   $$$$    (inside CPU chip)
L2 Cache     : 10 cycles,  ~256KB,  $$$
L3 Cache     : 30 cycles,  ~8MB,    $$
RAM          : 100 cycles, ~16GB,   $
SSD          : 10,000 cycles, ~512GB, ¢
HDD          : 5,000,000 cycles, ~4TB, ¢¢

Locality principles that make caching work:

Temporal locality:  if you use data now, you will likely use it AGAIN SOON
  (variables in loops accessed repeatedly)

Spatial locality:   if you use data at address X, you will likely use addresses
  near X soon (arrays, sequential code execution)

---

Cache Mapping — Where Does a Block Go?

Direct-Mapped Cache

Analogy: Each book in the library has exactly ONE shelf it belongs to (based on its last digit). Fast to find, but if two popular books share a shelf, they keep kicking each other out.

Cache line = (block_number) mod (total_cache_lines)

Example: 8 cache lines, block 5 → line 5, block 13 → line 5 (13 mod 8 = 5)
         These two CONFLICT — loading block 13 evicts block 5!

Address split:
  |────── Tag ──────|── Index ──|── Block Offset ──|

Tag:    identifies WHICH block is in this cache line
Index:  which cache line to look in
Offset: which byte within the block

Fully Associative Cache

Analogy: Books can go on ANY shelf. Maximum flexibility, but to find a book you must check ALL shelves simultaneously (expensive!).

Block can be placed in ANY cache line.
Hardware: comparators for ALL cache lines (Content Addressable Memory)

No conflict misses!
But: expensive hardware, slower for large caches.

Address split:
  |────────────── Tag ──────────────|── Block Offset ──|

k-Way Set Associative Cache

The compromise: Cache divided into S sets, each with k lines. Block maps to one SET (like direct-mapped), then can go to any of k lines within that set.

Set index = (block_number) mod S

Address split:
  |────── Tag ──────|── Set Index ──|── Block Offset ──|

Popular choices: 2-way, 4-way, 8-way (modern L1/L2/L3 caches)
Higher k → fewer conflict misses, more hardware

---

Address Calculation Example

Given:
  Cache size = 16KB
  Block size = 64 bytes
  4-way set associative

Calculate:
  Block offset bits = log₂(64) = 6 bits
  Number of sets S = 16KB / (4 × 64) = 16384 / 256 = 64 sets
  Set index bits = log₂(64) = 6 bits
  Tag bits = (total address bits) − 6 − 6 = 32 − 12 = 20 bits (for 32-bit system)

Address breakdown (32-bit):
  [bits 31-12: Tag (20 bits)] [bits 11-6: Set Index (6 bits)] [bits 5-0: Offset (6 bits)]

---

Cache Miss Types (3Cs)

Compulsory miss (cold miss): first access to any block — unavoidable
  Fix: prefetching (load blocks before they are needed)

Capacity miss: working set larger than cache — even fully associative would miss
  Fix: increase cache size

Conflict miss: two blocks in direct-mapped cache fight for same line
  Fix: higher associativity (2-way, 4-way) or better mapping

---

AMAT — Average Memory Access Time

The most important formula in cache design:

AMAT = Hit_time + Miss_rate × Miss_penalty

Multi-level cache:
AMAT = L1_hit + L1_miss_rate × (L2_hit + L2_miss_rate × Mem_time)

Worked Example:

L1 cache: hit time = 2 cycles, miss rate = 5%
L2 cache: hit time = 10 cycles, miss rate = 20%
Memory:   access time = 200 cycles

AMAT = 2 + 0.05 × (10 + 0.20 × 200)
     = 2 + 0.05 × (10 + 40)
     = 2 + 0.05 × 50
     = 2 + 2.5
     = 4.5 cycles

Compare: without L2, AMAT = 2 + 0.05 × 200 = 12 cycles
L2 cache saved 12 - 4.5 = 7.5 cycles per access!

---

Write Policies

Write-Through:
  On write: update BOTH cache AND main memory simultaneously
  Pros: simple, always consistent (memory up-to-date)
  Cons: every write goes to slow memory → use write buffer to hide latency

Write-Back:
  On write: update cache only; set DIRTY BIT
  Write to memory ONLY when the dirty block is evicted
  Pros: much lower memory traffic (multiple writes batched)
  Cons: memory may be stale (inconsistency with DMA/multiprocessor)
  Common in practice: modern CPUs all use write-back + LRU

---

Replacement Policies (for associative caches)

LRU (Least Recently Used):
  Evict the block accessed LONGEST AGO
  Best performance, but expensive hardware (track access time for each line)

FIFO (First In First Out):
  Evict the OLDEST loaded block
  Simpler, but may evict frequently used blocks
  Suffers Belady's anomaly (more lines can mean more misses!)

Random:
  Evict a randomly chosen block
  Surprisingly competitive with LRU in practice
  Simple hardware

Pseudo-LRU (Clock):
  Approximate LRU using reference bits
  Good balance of performance and simplicity

---

Quick Check

Q1. Cache: 256 lines, block size = 32 bytes, direct-mapped. Which cache line does block 300 map to?

Cache line = 300 mod 256 = 44

Q2. AMAT = 1 + 0.1 × 50 = 6. What does this mean? Answer: L1 hit takes 1 cycle. But 10% of the time we miss, and a miss costs 50 cycles. Average time per access = 6 cycles.

Q3. Why does increasing associativity reduce conflict misses? Answer: Higher associativity means more "candidate" slots for a block. When two blocks map to the same set, both can reside in the cache simultaneously (in different ways), instead of evicting each other.