Skip to main content

Replacement algorithm in associative mapping

Short answer

In associative mapping any block can occupy any line, so when the cache is full a miss requires choosing which existing block to replace. A replacement algorithm (e.g., LRU) selects the victim to maximize hit ratio; without it the cache cannot accept new blocks once full. The algorithm is implemented in hardware for nanosecond decisions.

Why is a replacement algorithm necessary in associative mapping? Justify.

In associative mapping a block of main memory may be placed in any cache line. The cache is small, so after some time all lines are occupied. When a new block is requested and misses, there is no free line, and the new block is not tied to one fixed line as in direct mapping.

  • The hardware must therefore decide which of the existing blocks is to be replaced. This decision is made by a replacement algorithm.
  • A good algorithm (LRU, FIFO, LFU, random) removes the block least likely to be needed soon. A bad choice removes a useful block and causes extra misses, which lowers the hit ratio.
  • The algorithm is implemented in hardware, as the decision must be made in nanoseconds so that the cache stays fast.

Without such a rule the cache could not continue to take new blocks once it is full.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 6 questions →