Cache Mapping: Direct, Associative and Set-Associative

A cache holds far fewer blocks than main memory, so many memory blocks must share each cache location. The mapping function decides where a memory block may be placed, and therefore how the cache finds it again. Direct mapping allows exactly one line per block; fully associative mapping allows any line; $k$-way set-associative mapping allows any of the $k$ lines of one set. The choice fixes how the address is split into tag, index and offset, how many tag comparators the hardware needs, how much tag storage the cache needs, and how many conflict misses a program suffers.

The calculations on this topic are address splits, tag-directory sizes, comparator counts, the line or set of a given address, and hit/miss traces. Policies (write, replacement) and the three Cs are in Cache Memory.

Notation and addressing convention used in all Gate CS Mastery notes. Memory is byte-addressable unless a question says word-addressable. $A$ is the number of physical address bits, $C$ the cache data capacity in bytes, $B$ the block size in bytes, $L = C/B$ the number of lines, $k$ the associativity and $S = L/k$ the number of sets. All of these are powers of 2. A memory block number is $b = \lfloor \text{address} / B \rfloor$.

Field widths:

Equivalently, the tag width is $\lg$ of the number of memory blocks that share one set: $\text{tag} = \lg\big(2^A / (B \cdot S)\big)$. Doubling the associativity halves the number of sets, removes one index bit and adds one tag bit.

Word-addressable memory. If each address names a word of $w$ bytes, measure $B$ and $C$ in words: offset $= \lg(B/w)$ when $B$ is given in bytes.

The tag directory (tag memory) holds one tag per line:

"Cache size" in a question normally means the data capacity $C$; the metadata is extra.

Figure 1 shows the three splits for one cache. Figure 2 shows a 2-way set-associative lookup.

With $B$ and $S$ powers of two, mod and floor are bit-field extractions: the offset is the low $\lg B$ bits, the index the next $\lg S$ bits, the tag the rest. Lookup time is one parallel comparison; hardware cost grows with $k$.

Why the tag has that width. All addresses with the same index and offset differ only in the tag. There are $2^A/(B \cdot S)$ memory blocks that map to one set, and the tag must tell them apart, so it needs $\lg(2^A/(B S)) = A - \lg B - \lg S$ bits.

Blocks per line or set. Each set is shared by $2^A/(B \cdot S)$ memory blocks; a direct-mapped line by $2^A/(B \cdot L)$.

Inverse problems. Given the tag width $t$, the block size and $k$: $\lg S = A - t - \lg B$, so $C = S \cdot k \cdot B$.

Comparator and multiplexer sizes. A $k$-way cache needs $k$ comparators of tag width and a $k$-to-1 multiplexer (as wide as the data returned). A direct-mapped cache needs one comparator and no way multiplexer.

Hit time. In a $k$-way cache the data of the hit way can leave only after the $k$ parallel tag comparisons and the $k$-to-1 multiplexer, so the hit latency is roughly one comparator delay plus one multiplexer delay. A direct-mapped cache can send its single line's data out while the tag is still being compared, which is why it hits fastest.

Replacement bits. A set-associative or fully associative cache adds replacement state per set: at least $\lceil \lg (k!) \rceil$ bits for exact LRU, or $k \lceil \lg k \rceil$ bits with an age counter per line (see Cache Memory). A direct-mapped cache needs none.

32-bit byte addresses, $C = 32$ KB $= 2^{15}$ bytes, $B = 64 = 2^6$ bytes, so $L = 2^{15}/2^6 = 512$ lines.

Adding a valid bit and a dirty bit per line to the direct-mapped cache gives $512 \times (17 + 2) = 9728$ metadata bits.

For the direct-mapped cache of Example 1, address 0x00001234: offset $=$ 0x34 $= 52$, block $=$ 0x1234 $/ 64 = 72$ (0x48), index $= 72 \bmod 512 = 72$, tag $= 0$. Address 0x00009234 has block 584, index $584 \bmod 512 = 72$ and tag 1. The two addresses compete for line 72: a program alternating between them misses every time in the direct-mapped cache, and hits after the first two misses in the 4-way cache, where both blocks fit in set $584 \bmod 128 = 72 \bmod 128 = 72$.

A cache with 4 one-block lines; block trace 0, 4, 1, 0, 5, 4, 1, 0; LRU where there is a choice.

Only four distinct blocks are used, so 4 misses are compulsory; the 4 extra direct-mapped misses are conflict misses. Two ways per set are already enough here.

An int array A[64][64] (4-byte elements, row-major, starting at address 0) is read once in full by a cache of 4 KB with 64-byte blocks (64 lines, each block holds 16 elements).

A 4-way set-associative cache with 32-byte blocks on 32-bit addresses has 20-bit tags. Then $\lg S = 32 - 20 - 5 = 7$, $S = 128$, and $C = 128 \times 4 \times 32 = 16$ KB. If the same cache were direct mapped, the index would be 9 bits and the tag 18 bits.

Take the 4-way cache of Example 1 (512 lines, 128 sets, 19-bit tags), write-back, with a 2-bit LRU age counter per line. Each line stores $19 + 1 + 1 + 2 = 23$ bits of metadata (tag, valid, dirty, age), so the directory holds $512 \times 23 = 11776$ bits. With the minimum exact LRU state of $\lceil \lg 24 \rceil = 5$ bits per set instead of counters, it holds $512 \times 21 + 128 \times 5 = 11392$ bits. Either way the data array itself is $2^{15} \times 8 = 262144$ bits.

A machine has 16-bit addresses, each naming a 32-bit (4-byte) word. A direct-mapped cache holds 2 KB of data in 16-byte blocks.

Using the byte offset $\lg 16 = 4$ would give a 5-bit tag: the wrong answer that a byte-addressing habit produces. Memory here is $2^{16}$ words $= 256$ KB.

A 2-way set-associative cache with 2 sets (set $= b \bmod 2$), block trace 0, 4, 1, 0, 8, 5, 0, 4, 1, 8.

Set 1 sees only 1, 5, 1 and behaves the same under both policies. The difference is in set 0 when block 8 arrives, holding 0 and 4. Block 0 has just hit, so LRU evicts 4 and the next 0 hits; FIFO ignores that hit, evicts 0 (loaded first) and the next 0 misses.