Set-Associative Address Mapping
What you'll learn: How memory addresses are divided to locate data in a set-associative cache, and why blocks have flexibility within their assigned set.
The Hybrid Approach
Set-associative caches combine ideas from direct-mapped and fully associative designs. Instead of mapping each address to one specific location (direct-mapped) or allowing it to go anywhere (fully associative), we split the cache into sets, where each address maps to a specific set, but can occupy any way (position) within that set.
Think of a parking garage with numbered floors (sets). Your car type determines which floor you must park on, but once there, you can choose any available spot on that floor.
Address Breakdown
A memory address in a set-associative cache divides into three parts:
- Tag bits – uniquely identify the block
- Set index bits – determine which set the block maps to
- Block offset bits – locate the byte within the cache line
The number of set index bits depends on how many sets exist. For example, 64 sets need 6 index bits (2^6 = 64).
Lookup Process
When the CPU requests data:
- Use the set index to select one specific set
- Search all ways within that set (comparing tags in parallel)
- If any way's tag matches, it's a cache hit
- Use the offset to extract the exact byte
A 4-way set-associative cache means each set contains 4 blocks. The address maps to one set, then searches across those 4 blocks.
Why This Matters
Set-associative mapping reduces conflict misses compared to direct-mapped caches (more flexibility within a set) while being simpler and faster than fully associative designs (only search one set, not the entire cache).
Key Takeaway: Set-associative address mapping uses index bits to select a specific set, then allows the block to occupy any way within that set, balancing flexibility and hardware complexity.