3.4k-way set associative
The idea
A k-way set-associative cache is the compromise: the block maps to one set, but can sit in any of the k lines of that set.
Think of it like this: Parking lot divided into sections: your ticket picks the section, then you can park in any bay of it.
Why it exists
Gets most of the hit-rate benefit of full associativity with only k comparators.
How it works
- sets = lines ÷ k.
- Set number = block mod sets.
- Compare tags of the k lines in that set in parallel.
- k = 1 is direct-mapped; k = number of lines is fully associative.
Worked example: 4 lines, 2-way
2 sets. Even blocks (0, 2, 4...) go to set 0, odd blocks to set 1. Blocks 0 and 4 now share set 0 without evicting each other.
Now play with it
- →On the 2-way tab click 0, 4, 0, 4: both hit. Now try 0, 2, 4 and see an eviction.
Main memory blocks (click one to access it)
Cache lines (4) · sets: {0,1} and {2,3}
Click memory blocks below. Try 0, 4, 0, 4 in direct mapped.
Hover a block to see which lines it is allowed to use. Block b → set b mod 2, either way (LRU).
Check yourself
A 16-line cache is 4-way set associative. How many sets does it have?
Exam notes (the dense version)
Block j → set (j mod #sets), any of k ways inside. Compromise. Address = tag + set + 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.