Associative mapping technique

Associative mapping is a cache mapping function in which any block of main memory can be stored in any line of the cache. 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.