Associative mapping and replacement algorithms

Associative mapping

A main-memory block can be placed in any cache line. The address is split into Tag | Word; the tag is the full block number.

   Address (16 bits)
   +----------------------+--------+
   |   Tag  14b          | Word 2b|
   +----------+-----------+--------+
              |
      compare with ALL tags in parallel
   +------+-----------+------+
   | line0| tag0      | data |--= ?
   | line1| tag1      | data |--= ?
   |  ... | ...       | ...  |--= ?
   +------+-----------+------+--> hit / miss

Working: the tag is compared with the tags of all lines at the same time (associative or content-addressable memory). A match is a hit. On a miss the block is loaded into any free line; if the cache is full, a replacement algorithm (LRU, FIFO, LFU, random) chooses the line to remove.

Example: with 16 lines, blocks 0, 16, 32 and 5 can all stay in the cache together, because any line can hold any block.

• Merits: most flexible, best hit ratio, no thrashing.
• Demerits: needs one comparator per line (costly, slow, more power), long tag, and a replacement algorithm.

Why a replacement algorithm is required

• In associative mapping any block can go to any line, so when a miss occurs and all lines are full, the hardware must choose which existing block to remove. There is no fixed line for the new block as in direct mapping.
• A good choice keeps blocks that will be used soon. Common algorithms:
  • LRU: replace the block unused for the longest time (best, uses locality).
  • FIFO: replace the oldest block loaded.
  • LFU: replace the block with the fewest references.
  • Random: replace any line.
• The algorithm must be implemented in hardware to keep the cache fast. A poor choice reduces the hit ratio.