Cache memory is small, fast memory storing frequently accessed data.
Speed ↑ Cost ↑ Size ↓
Registers (1 cycle)
↓
L1 Cache (2-5 cycles)
↓
L2 Cache (10-20 cycles)
↓
L3 Cache (20-50 cycles)
↓
Main Memory (50-100 cycles)
↓
Disk Storage (100K+ cycles)
Temporal Locality: Recently accessed items likely accessed again
Spatial Locality: Items near recently accessed items likely accessed
AMAT = Hit_Time + (Miss_Rate × Miss_Penalty)
Each block maps to exactly one cache line.
Cache_Line = Block_Address mod Number_of_Cache_Lines
Address: | Tag (31-10) | Index (9-5) | Offset (4-0) |
Pros: Simple, fast Cons: Conflict misses
Any block can go in any cache line.
Address: | Tag (31-4) | Offset (3-0) |
Pros: Minimum conflict misses Cons: Complex hardware, slow
Block maps to specific set, can go in any line of that set.
Set_Number = Block_Address mod Number_of_Sets
Address: | Tag (31-10) | Set_Index (9-4) | Offset (3-0) |
Common: 2-way, 4-way, 8-way
- Compulsory Miss - First access (cold start)
- Capacity Miss - Cache too small
- Conflict Miss - Multiple blocks map to same location
Write Through:
- Write to cache AND memory
- Simple, consistent, slow
Write Back:
- Write only to cache
- Update memory when replaced
- Fast, needs dirty bit
- Random - Simple, unpredictable
- FIFO - Replace oldest
- LRU - Replace least recently used (best)
- LFU - Replace least frequently used
CPU → L1 → L2 → L3 → Memory
AMAT = L1_Hit + L1_Miss × (L2_Hit + L2_Miss × L3_Hit + ...)
Given:
- L1 hit: 1 cycle, miss: 10%
- L2 hit: 10 cycles, miss: 2%
- Memory: 100 cycles
AMAT = 1 + 0.10 × (10 + 0.02 × 100)
= 1 + 0.10 × 12
= 2.2 cycles