Fully Associative Caches
What You'll Learn
You'll learn how fully associative caches eliminate conflict misses by allowing any memory block to be stored in any cache line.
The Problem with Direct-Mapped Caches
Remember direct-mapped caches? Each memory block had exactly one possible cache line it could occupy. This caused conflict misses when different memory blocks competed for the same cache line, even if other lines sat empty.
How Fully Associative Caches Work
A fully associative cache takes the opposite approach: any memory block can be placed in any cache line. There are no restrictions or fixed mappings.
Analogy: Think of a parking lot. In direct-mapped caching, you have an assigned spot (like apartment parking). In fully associative caching, you can park in any available spot (like a public lot) — total freedom!
The Lookup Process
When the CPU requests data:
- Search all cache lines in parallel
- Compare the requested tag against every cache line's tag simultaneously
- If any line matches → cache hit
- If no line matches → cache miss
This requires parallel comparison hardware for every cache line, which is why fully associative caches are expensive and typically small.
Advantages and Tradeoffs
Advantages:
- No conflict misses — blocks never fight for the same spot
- Maximum flexibility in block placement
- Ideal hit rate for a given cache size
Disadvantages:
- Expensive hardware (need comparators for every line)
- Power-hungry (all comparisons happen simultaneously)
- Doesn't scale well to large cache sizes
Fully associative caches are typically used only for small, specialized caches like Translation Lookaside Buffers (TLBs) where the flexibility justifies the cost.
Key Takeaway: Fully associative caches eliminate conflict misses by allowing any memory block to occupy any cache line, but this flexibility requires expensive parallel search hardware.