Direct cache mapping

Cache memory is a small, very fast memory placed between the CPU and main memory. It holds copies of the most recently used blocks of main memory, so that most CPU accesses are served at cache speed. It works because of locality of reference (temporal and spatial).

Example system used below: main memory = 64K words (16-bit address), block size = 4 words, cache = 16 lines (64 words). Main memory has 16384 blocks.

Direct mapping

Each main-memory block can go to exactly one cache line: line number = (block number) mod (number of lines). The address is split into Tag | Line | Word.

   Address (16 bits)
   +-----------+---------+--------+
   | Tag  10b  | Line 4b | Word 2b|
   +-----+-----+----+----+--------+
         |          |
         |    +-----v------+
         |    | line 0     | tag | data
         |    | line 1     | tag | data
         |    |  ...       |
         |    | line 15    | tag | data
         |    +-----+------+
         v          v
      +--------------------+
      | compare tag = ?    |--> hit / miss
      +--------------------+

Working: the line field selects one line, and the tag stored there is compared with the tag of the address. If the tags are equal (and the valid bit is set), it is a hit, and the word field picks the word. Otherwise it is a miss: the block is read from memory into that line, and the line's tag is updated.

Example: blocks 0, 16, 32 of main memory all map to line 0 (block mod 16); block 5 maps to line 5; block 21 also maps to line 5.

• Merits: simple and cheap hardware (only one comparator), fast lookup, no replacement algorithm needed.
• Demerits: fixed location for each block, so two blocks that map to the same line keep replacing each other (thrashing) even when other lines are empty; lower hit ratio.