Course contentsShow
← Computer Science
Lesson 1133 of 2,87226. Memory Hierarchy and CachingFree lesson

Set-Associative Address Mapping

Learn how addresses map to sets and how blocks can occupy any way within their assigned set.

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:

  1. Tag bits – uniquely identify the block
  2. Set index bits – determine which set the block maps to
  3. 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:

  1. Use the set index to select one specific set
  2. Search all ways within that set (comparing tags in parallel)
  3. If any way's tag matches, it's a cache hit
  4. 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.