Cache Memory
How CPU caches map addresses to fast local storage using tag, index, and offset bits.
Problem
A modern CPU can execute an instruction every ~0.3ns, but reading from main memory (DRAM) takes ~50–100ns: a 200× gap. Without a fast intermediary, the processor stalls waiting for data on almost every load. How does hardware bridge this speed gap?
How it works
The cache is a small, fast SRAM buffer between the CPU and main memory. When the processor reads address A, it checks the cache first. If the data is there (a hit), it returns in 1–4 cycles. If not (a miss), it fetches a whole block of data from memory and stores it in the cache for next time.
Address breakdown: Every memory address is split into three fields: tag | index | offset. The index bits select which set (row) in the cache to check. The tag bits identify which memory block is stored there. The offset bits select the byte within the block. This is the core of cache lookup: it's just bit slicing.
Direct-mapped: Each address maps to exactly one cache line (1 way per set). Simple and fast, but two addresses that map to the same set evict each other: this is a conflict miss.
Set-associative: Each set has multiple ways (slots). A 2-way cache checks 2 tags per lookup. More ways = fewer conflict misses, but more comparators and slower lookup. Fully associative (1 set, N ways) eliminates all conflict misses but requires checking every tag in parallel.
Replacement: When all ways in a set are occupied, the cache must evict one. LRU (Least Recently Used) evicts the way that hasn't been accessed the longest: betting that recently used data will be used again soon.
Locality: Caches exploit two patterns: spatial locality (if you accessed address A, you'll likely access A+1 soon: that's why blocks are bigger than 1 byte) and temporal locality (if you accessed A recently, you'll likely access it again: that's why eviction picks the least-recently-used entry).
Address breakdown: Every memory address is split into three fields: tag | index | offset. The index bits select which set (row) in the cache to check. The tag bits identify which memory block is stored there. The offset bits select the byte within the block. This is the core of cache lookup: it's just bit slicing.
Direct-mapped: Each address maps to exactly one cache line (1 way per set). Simple and fast, but two addresses that map to the same set evict each other: this is a conflict miss.
Set-associative: Each set has multiple ways (slots). A 2-way cache checks 2 tags per lookup. More ways = fewer conflict misses, but more comparators and slower lookup. Fully associative (1 set, N ways) eliminates all conflict misses but requires checking every tag in parallel.
Replacement: When all ways in a set are occupied, the cache must evict one. LRU (Least Recently Used) evicts the way that hasn't been accessed the longest: betting that recently used data will be used again soon.
Locality: Caches exploit two patterns: spatial locality (if you accessed address A, you'll likely access A+1 soon: that's why blocks are bigger than 1 byte) and temporal locality (if you accessed A recently, you'll likely access it again: that's why eviction picks the least-recently-used entry).
Key insightA cache is just a hardware hash table. The index bits are the hash, the tag bits are the key, and associativity is the number of slots per bucket. Thrashing: when two addresses keep evicting each other from the same set: is the cache equivalent of a hash collision with no room to resolve it. Understanding this mapping is how you write code that runs 10× faster without changing the algorithm.