Cache memory mapping techniques

Cache memory is a small, fast memory placed between the processor and the main memory that holds copies of frequently used data/instructions, using the principle of locality. A hit gives data in one cache access; a miss goes to main memory. Because the cache is much smaller than main memory, a rule is needed to decide where each memory block may be placed. This rule is the mapping technique.

Memory address splits into tag | index | offset. The offset selects the byte within a block, the index selects the cache line or set, and the tag identifies which memory block is stored there.

Basic mapping techniques

1. Direct mapping: each main-memory block can go into exactly one cache line: line = (block address) mod (number of lines).
2. Fully associative mapping: a block can be placed in any cache line. The tag is the whole block address, compared with all line tags in parallel.
3. Set-associative mapping: the cache is divided into sets. A block maps to one set and can be in any line (way) of that set, e.g. 2-way or 4-way.

 Direct:  address = | tag | index | offset |
          index -> one line -> compare 1 tag
 Assoc.:  address = | tag (block no.) | offset |
          compare tag with ALL lines at once

Direct versus fully associative mapping