Explain the following cache mapping techniques: i. Direct Mapping ii. Associative Mapping iii. Set-Associative Mapping

i. Direct mapping

Each memory block goes to one fixed cache line:

$$\text{line} = \text{block number} \bmod 256$$

The address has three fields: tag, line and word. The word field has 2 bits, the line field has 8 bits and the tag has the remaining bits:

$$16 - 8 - 2 = 6 \text{ bits}$$

The line field selects the cache line, and its stored tag is compared with the tag of the address. If they are equal, it is a hit. This needs only one comparator and no replacement rule, so it is simple and fast. But blocks that map to the same line replace each other again and again, so the hit ratio can be poor.

ii. Associative mapping

A memory block can be placed in any cache line. The address has only a tag and a word field. Here the tag has $16 - 2 = 14$ bits and the word has 2 bits. The tag is compared with the tags of all 256 lines at the same time, using associative memory. This is the most flexible and gives the highest hit ratio, because there are no conflict misses. But it needs 256 comparators, so it is costly and slow, and it needs a replacement algorithm such as LRU or FIFO.

iii. Set-associative mapping

The lines are grouped into sets. A block maps to one fixed set, but it can go to any line in that set. For a 4-way cache, there are $256/4 = 64$ sets. The set field has 6 bits, the word field has 2 bits and the tag has

$$16 - 6 - 2 = 8 \text{ bits}$$

Only the 4 tags of one set are compared. It reduces conflict misses and costs less than the associative method. A replacement rule is needed only inside the set.