Set associative mapping

Set associative mapping divides the cache into sets, each with k lines (k-way). It combines direct mapping (a block maps to one fixed set, found by index) with associative mapping (inside the set the block may go to any of the k lines).

How it combines the two

   Address (16 bits)
   +-----------+---------+--------+
   | Tag  11b  | Set  3b | Word 2b|
   +-----------+----+----+--------+
                    |
          +---------v---------+
          | Set i: way0 way1  |  2-way: compare 2 tags
          +---------+---------+
                    v
                hit / miss

Example (2-way): 16 lines in 8 sets of 2. Blocks 0, 8 and 16 all map to set 0, but two of them can be present together; the third needs a replacement (LRU/FIFO) within that set.

• Merits: fewer conflict misses than direct mapping, cheaper than fully associative (only k comparators).
• Demerits: more complex than direct mapping, and a replacement algorithm is needed inside each set.

Special cases: k = 1 gives direct mapping, and k = number of lines (one set) gives fully associative mapping. A 2-way or 4-way cache gives most of the hit ratio of associative mapping at a cost near direct mapping.