Exercises — Cache lines, tags, index, offset

The offset must be able to name every byte inside one line. A line has $B=64$ bytes, numbered $0$ to $63$. To count that many distinct positions you need ${\log }_{2}64$ bits. ${\log }_{2}64=6\text{ bits}.$ Answer: 6 offset bits. Notice this used only the line size — nothing about how big the whole cache is.

The index picks one row (set) out of $S$. To address $128$ distinct rows you need ${\log }_{2}128=7\text{ bits}.$ Answer: 7 index bits.

The tag. The index already chose the row and the offset picks a byte; only the tag is stored next to the data and compared to verify identity. Answer: the tag.

Peel from the right:

• Offset $={\log }_{2}64=6$ bits.
• Index $={\log }_{2}512=9$ bits.
• Tag $=32-9-6=17$ bits.

Answer: tag 17 / index 9 / offset 6. Check they sum: $17+9+6=32$. ✓

Direct-mapped means 1 line per set, so $S=L=1024$.

• Offset $={\log }_{2}32=5$ bits.
• Index $={\log }_{2}1024=10$ bits.
• Tag $=32-10-5=17$ bits.

Answer: tag 17 / index 10 / offset 5. Sum $=32$. ✓

• Offset $={\log }_{2}16=4$ bits.
• Index $={\log }_{2}64=6$ bits.
• Tag $=16-6-4=6$ bits.

Answer: tag 6 / index 6 / offset 4. Sum $=16$. ✓

Widths: offset $={\log }_{2}64=6$, index $={\log }_{2}256=8$, tag $=32-8-6=18$.

Write the address in binary (0xCAFEF00D): $\text{1100 1010 1111 1110 1111 0000 0000 1101}$ We need the low $14$ bits (bits $13\dots 0$ = $8$ index $+6$ offset). The low 14 bits are 01 1111 0000 1101 — read them off the last three-and-a-bit hex digits F00D: the byte 0x0D = 0000 1101 and the nibble above it (from F00D) contributes the higher index bits. Let's be exact by masking:

• Offset = low $6$ bits = $\text{0xCAFEF00D}\mathrm{mod}64$. Since 0x0D = $13$ and bit 6 above it comes from 0x00, the low 6 bits are 001101 $=13$. So byte $13$ inside the line.
• Index = next $8$ bits (bits $13\dots 6$). Shift the address right by $6$ and keep $8$ bits: $(\text{0xCAFEF00D}\gg 6)\&\text{0xFF}$. Working it out gives 11000000 $=192$, i.e. set 192 (0xC0).
• Tag = top $18$ bits (compared, not "computed as a nice number" here).

Answer: offset $=13$, index $=$ set $192$, tag $=18$ bits. The picture below shows the peel line landing inside the last hex nibble, not on its edge — the mint INDEX box straddles a coral nibble tick, which is exactly why the naive "grab a hex byte" shortcut fails here.

Binary of 0xDEADBEEF: $\text{1101 1110 1010 1101 1011 1110 1110 1111}$ Low $14$ bits (bits $13\dots 0$) = 11 1110 1110 1111.

• Offset = low $6$ (bits $5\dots 0$) = 101111 $=47$ (0x2F).
• Index = next $8$ (bits $13\dots 6$) = 11111011 $=251$ (0xFB).

Answer: set $251$, offset byte $47$. Note the index is 11111011, not the nibble-looking 10111011 — the $6$-bit offset shifts the boundary off the hex grid.

Before (direct-mapped): $S=L=512$.

• Offset $=6$, index $={\log }_{2}512=9$, tag $=32-9-6=17$.

After (8-way): $S=L/w=512/8=64$.

• Offset $=6$ (unchanged, still $B=64$).
• Index $={\log }_{2}64=6$.
• Tag $=32-6-6=20$.

Tag grew by $20-17=3$ bits $={\log }_{2}8={\log }_{2}w$. ✓ Answer: tag grows by $3$ bits; new split = tag 20 / index 6 / offset 6.

Offset $={\log }_{2}64=6$. From the tag formula: $\text{tag}=n-{\log }_{2}S-{\log }_{2}B⟹12=32-{\log }_{2}S-6.$ Solve: ${\log }_{2}S=32-6-12=14$, so $S=2^{14}=16384$ sets. If $2$-way: $L=S\times w=16384\times 2=32768$ lines.

Answer: $16384$ sets; $32768$ lines if $2$-way.

Fully associative means one giant set: $S=1$, so index $={\log }_{2}1=0$ bits.

• Offset $={\log }_{2}128=7$ bits.
• Index $=0$ bits.
• Tag $=40-0-7=33$ bits.

Answer: tag 33 / index 0 / offset 7. Every non-offset bit is tag, because any line can live in any slot — you must compare the tag of every slot.

(a) Tag: $S=L/w=512/4=128$, so index $={\log }_{2}128=7$, offset $=6$, tag $=32-7-6=19$ bits.

(b) Bits per line $=$ data $+$ tag $+$ valid: $(64\times 8)+19+1=512+20=532\text{ bits}.$ Total over all lines: $512\times 532=272384\text{ bits}.$ Answer: tag 19 bits; total $272384$ bits of SRAM. The $20$ overhead bits per line are real silicon you pay for on every line — this is why tiny lines are expensive per byte of useful data.

Index is ${\log }_{2}256=8$ for both.

• A: offset $={\log }_{2}32=5$, tag $=32-8-5=19$.
• B: offset $={\log }_{2}128=7$, tag $=32-8-7=17$.

Answer: A tag $=19$, B tag $=17$. Bigger lines consume more offset bits (more bytes to name inside a line). With index fixed, those extra offset bits come out of the tag, so the tag shrinks as line size grows. Bigger lines also lean harder on spatial locality.

• Offset $={\log }_{2}1=0$ bits (a "line" is a single byte — nothing to index inside it).
• Index $={\log }_{2}1=0$ bits (one set — no row to choose).
• Tag $=16-0-0=16$ bits (the entire address is the tag).

Answer: tag 16 / index 0 / offset 0. With a single one-byte slot and a full-address tag, it is a degenerate fully-associative cache of exactly one byte — it can hold one byte at a time and must compare all $16$ address bits to decide a hit. Both degenerate logs (${\log }_{2}1=0$) collapse two whole fields to zero width — a good reminder that ${\log }_{2}1=0$ is not a bug (and that $S=1,B=1$ are still powers of two, so the split stays integer).

The page offset is the low $12$ bits (unchanged by translation). VIPT wants index $+$ offset $\le$ page-offset bits so the index is taken from bits that virtual and physical addresses share. Offset $={\log }_{2}64=6$. So: $\text{index}\le 12-6=6\text{ bits}⟹S\le 2^6=64\text{ sets}.$ Answer: at most $64$ sets. Beyond that the index would reach into translated bits and risk aliasing — see Virtual vs physical addressing (VIPT/PIPT) and TLB and page tables.