Cache Design and Associativity
A cache holds recently used data close to the processor; associativity decides how freely a memory block may be placed within it.
Why Caches Exist
Main memory is far slower than a processor's clock. A cache is a small, fast memory that keeps recently and nearby-used data close, exploiting two patterns real programs show: temporal locality (recently used data is used again soon) and spatial locality (data near recently used data is used soon).
Data moves between cache and memory in fixed-size blocks (or lines), typically 64 bytes. A memory address is split into a tag, an index that selects a set, and an offset within the block.
Placement and Associativity
Associativity defines where a block may live. A direct-mapped cache gives each block exactly one possible slot: simple and fast, but two hot blocks that map to the same slot keep evicting each other (conflict misses). A fully associative cache lets a block go anywhere: fewest conflict misses, but every entry's tag must be searched. Set-associative caches compromise: the cache is divided into sets of N ways, and a block may occupy any way within its set.
- Direct-mapped: one slot per block, cheap, conflict-prone
- N-way set-associative: N candidate slots, tags compared in parallel
- Fully associative: any slot, needs a CAM-style search
Misses and Replacement
Cache misses fall into three classes: compulsory (first-ever access to a block), capacity (the working set exceeds the cache), and conflict (too many blocks map to one set). When a set is full, a replacement policy such as least-recently-used or an approximation of it chooses the victim.
Writes
On a write, a write-through cache updates memory immediately; a write-back cache marks the line dirty and defers the memory update until eviction, saving bandwidth. A write-allocate policy fetches a block into cache on a write miss. These choices interact directly with coherence protocols in multiprocessors.
Real machines stack multiple cache levels (L1, L2, L3), each larger and slower than the last, to balance latency against capacity.