3.3Fully associative
The idea
A fully associative cache lets a block go in any line, so there are no conflict misses.
Think of it like this: Open parking: park anywhere, but the attendant must check every space to find your car.
Why it exists
It removes conflicts, so it is the best for hit rate, but you must search all lines at once.
How it works
- No index bits: the address is just tag + offset.
- Every line has its own comparator, all checking in parallel.
- When full, a replacement policy (LRU, FIFO) picks a victim.
- Expensive in hardware, so used only for small caches such as the TLB.
Worked example: 4 lines, accesses 0, 4, 0, 4
Blocks 0 and 4 sit in different lines: after the first two misses, both accesses are hits.
Now play with it
- →On the Fully tab click 0, 4, 0, 4 and compare with direct-mapped.
Main memory blocks (click one to access it)
Cache lines (4)
Click memory blocks below. Try 0, 4, 0, 4 in direct mapped.
Hover a block to see which lines it is allowed to use. Any line (LRU).
Check yourself
A fully associative cache has 64 lines. How many tag comparators are needed to check in parallel?
Exam notes (the dense version)
Block can go anywhere. Many comparators (one per line), no conflict misses, expensive. Address = tag + offset.
Previous year questions: Cache Memory (22)
PYQs are grouped by topic, so this is the full set for Cache Memory; try the ones that match this subtopic. Open all 22 on the topic page.