Skip to main content

Cache read and direct-mapping demerits

Short answer

Cache read splits address into tag, line, and word; tag comparison yields hit (word from cache) or miss (block fetched from memory). Direct mapping forces each block to one fixed line, causing thrashing and conflict misses when multiple blocks map to the same line, lowering hit ratio and leaving other lines unused. Associative mapping solves this by allowing any block in any line, using parallel tag comparison and a replacement algorithm.

Explain the cache read operation. What are the demerits of the direct mapping technique used in cache design? Describe in detail any one of the mapping techniques that solves these problems.

Cache read operation

   CPU gives address
          |
   Is block in cache? (tag compare)
      /Yes           \No
 Hit: fetch word   Miss: read block from main memory
 from cache           and load it into a cache line
      |            (replace a line if needed)
      |            Deliver the word to the CPU
      v                 v
   Word delivered to CPU

The address is split into tag, line/set and word fields. The cache is checked first; on a hit the word is returned at cache speed, on a miss the whole block is brought from main memory (the word may be sent to the CPU as soon as it arrives) and the tag is updated.

Demerits of direct mapping

  • Each block has only one possible line, so blocks that map to the same line keep evicting each other (thrashing), even when other lines are empty.
  • This gives conflict misses and a lower hit ratio, for example when a loop alternates between two blocks whose numbers differ by a multiple of the number of lines.
  • Cache usage is not uniform, since some lines are used heavily and others hardly at all.

Associative mapping solves these problems

   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.

Associative mapping removes thrashing because a block may use any free line. Set associative mapping gives a similar benefit at lower cost.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 6 questions →