Cache mapping techniques

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.

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.

Set associative mapping

The cache lines are grouped into sets. A block maps to one particular set (set number = block mod number of sets) but can be placed in any line of that set. The address is split into Tag | Set | Word.

   Address (16 bits)
   +-----------+---------+--------+
   | Tag  11b  | Set  3b | Word 2b|
   +-----------+----+----+--------+
                    |
          +---------v---------+
          | Set i: way0 way1  |  2-way: compare 2 tags
          +---------+---------+
                    v
                hit / miss

Example (2-way): 16 lines in 8 sets of 2. Blocks 0, 8 and 16 all map to set 0, but two of them can be present together; the third needs a replacement (LRU/FIFO) within that set.

• Merits: fewer conflict misses than direct mapping, cheaper than fully associative (only k comparators).
• Demerits: more complex than direct mapping, and a replacement algorithm is needed inside each set.

Comparison