Discuss the different mapping techniques used in cache memories and their relative merits and demerits.

Direct mapping

Each main memory block can go to exactly one cache line, given by $\text{line} = \text{block number} \bmod \text{number of lines}$. The address is split into tag, line (index) and word fields. The line field picks the cache line, and the tag is compared with the stored tag to check for a hit. For example, with a 16-bit address, 4-word blocks and 256 cache lines, the fields are tag 6, line 8 and word 2 bits.

Merits: it is simple, cheap, fast, and needs only one comparator. No replacement rule is needed. Demerits: two blocks that map to the same line keep throwing each other out, even if other lines are empty. The hit ratio can fall badly.

Associative (fully associative) mapping

A block can be placed in any cache line. The address has only a tag and a word field. In the same example the tag is 14 bits and the word is 2 bits. The tag is compared with all stored tags at the same time, using associative (content addressable) memory.

Merits: it is the most flexible. Conflict misses do not occur, and the hit ratio is the highest. Demerits: it needs one comparator per line, so the hardware is costly and slower. A replacement algorithm such as LRU or FIFO is needed.

Set-associative mapping

The cache lines are grouped into sets. A block maps to one particular set, but it can go to any line inside that set. With $k$ lines per set it is called $k$-way. In the example, a 4-way cache has $256/4 = 64$ sets, so the fields are tag 8, set 6 and word 2 bits. Only the $k$ tags of one set are compared.

Merits: it is a good middle path. It removes most conflict misses and needs only $k$ comparators. Demerits: it needs more hardware than direct mapping, and a replacement rule is still required inside each set.

Comparison

A good mapping keeps useful blocks together and avoids needless replacement. It also keeps the tag comparison cheap, because the cache must answer in one or two clock cycles.

Direct mapping is the special case of 1-way set associative, and associative mapping is the case where one set holds all the lines.

In practice, most modern processors use set-associative caches with 2, 4 or 8 ways, because this gives a hit ratio close to full associativity at a much lower hardware cost.