Associative cache mapping with example

In 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.

Example with numbers

Cache has 4 lines; blocks requested in order: 12, 7, 40, 7, 25, 12.

Request  Result   Cache (line0..3 after request)
12       miss     12  -   -   -
7        miss     12  7   -   -
40       miss     12  7   40  -
7        hit      12  7   40  -
25       miss     12  7   40  25
12       hit      12  7   40  25

Every block was loaded in the first free line, and the tags (the block numbers) of all four lines are compared at once for each request. Blocks 12 and 40, which would clash in a direct-mapped cache of 4 lines (both map to line 0), stay together here.