Skip to main content

Associative cache mapping

Short answer

Fully associative mapping allows any main memory block to be placed in any cache line. Address has tag and offset; tag compared with all lines simultaneously. Merits: no conflict misses, highest hit ratio. Demerits: expensive due to one comparator per line, slower, requires replacement policy, and feasible only for small caches.

Explain associative cache mapping technique (with its merits and demerits).

In associative (fully associative) mapping, a main-memory block can be placed in any line of the cache. The memory address is divided into a tag (the block number) and an offset (word within the block). There is no index field.

 Address:  | Tag (block no.) | Offset |
              |
      compare in parallel with every line's tag
 +------+-----+------+   +------+
 | tag0 | data|valid |-> |  =?  |--+
 | tag1 | data|valid |-> |  =?  |--+--> hit / select line
 | ...                                 |
 +------------------+                  v
                                      data

Operation: the CPU sends the address; the tag is compared with the tags of all lines at the same time (using content-addressable memory). If one matches (and valid), it is a hit and the offset selects the word. Otherwise it is a miss: the block is fetched from main memory and put into any free line, or, if the cache is full, a replacement algorithm (LRU, FIFO, random) chooses a line to evict.

Merits

  • Most flexible placement, so there are no conflict misses and the highest hit ratio for a given size.
  • Cache space is fully used.

Demerits

  • Needs a comparator for every line, making it costly and complex.
  • Slower search and higher power use.
  • Needs a replacement algorithm.
  • Practical only for small caches (e.g. TLB).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Embedded System chapter 4 questions →