Write policy; direct vs associative mapping

Write policy

When the CPU writes to a cached word, the cache and main memory may become different. The write policy decides when main memory is updated.

1. Write-through: every write goes to both the cache and main memory at once. Memory is always up to date and the design is simple, but write traffic is high and the CPU may wait for the slow memory (a write buffer reduces this).
2. Write-back (copy-back): a write updates only the cache and sets a dirty bit on the line. Main memory is updated only when the line is replaced. Writes are fast and the bus traffic is low, but memory is temporarily stale and the control is more complex (important in multiprocessors).
3. Write-once: the first write to a block is written through (to tell other caches), later writes are write-back. It is used for cache coherence in multiprocessor systems.

On a write miss the cache uses either write-allocate (load the block, then write) or no-write-allocate (write directly to memory).

Direct mapping

   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.

Associative (fully 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.

Difference between direct and associative mapping