Cache lines, tags, index, offset

WHY does a cache need to slice the address?

Main memory (DRAM) is huge but slow (~100 ns). The CPU runs at ~0.3 ns/cycle. If every load waited for DRAM, the CPU would idle 99% of the time. So we keep a tiny copy of hot data near the CPU.

But the cache is much smaller than memory, so many memory addresses must share the same cache slot. The hardware needs a fast, wiring-only way (no arithmetic, no search) to:

1. Pick which slot a given address maps to → index.
2. Confirm that the data sitting in that slot is actually the address we want → tag.
3. Select the exact byte(s) inside the fetched block → offset.

Slicing bits is free in hardware (just wires), which is why this scheme wins.

WHAT is a cache line / block?

HOW to derive the three fields from scratch

Assume a byte-addressable memory with $n$-bit addresses, a cache holding $S$ sets (rows), each line of size $B$ bytes.

Step 1 — Offset bits. Inside a block of $B$ bytes we must name each byte. Number of distinct bytes $= B$, so we need $\text{offset bits} = \log_2 B.$ Why this step? It takes exactly $\log_2 B$ bits to count from $0$ to $B-1$.

Step 2 — Index bits. After removing the offset, the block number is $\lfloor A / B \rfloor$. We must map each block number to one of $S$ sets. The hardware uses the low bits of the block number (so consecutive blocks spread across sets): $\text{index bits} = \log_2 S.$ Why this step? $\log_2 S$ bits address $S$ rows; low bits are used so adjacent blocks don't collide.

Step 3 — Tag bits. Whatever address bits are left over uniquely identify which of the many blocks that map to this set is currently stored: $\text{tag bits} = n - \log_2 S - \log_2 B.$ Why this step? All address bits not used for index/offset must be stored & compared to verify identity.

Associativity (where $S$ comes from)

A cache stores $L$ total lines. Group them into ways:

• Direct-mapped ($1$-way): each set holds $1$ line, so $S = L$.
• $w$-way set-associative: each set holds $w$ lines, so $S = L / w$.
• Fully associative: one giant set, $S = 1$ ⇒ 0 index bits, everything is tag.

Worked Example 1 — Direct-mapped

Cache: $L = 256$ lines, $B = 64$ B, direct-mapped, 32-bit addresses.

• Offset $= \log_2 64 = 6$ bits. Why? 64 bytes per line.
• Sets $S = L = 256$ (direct-mapped) ⇒ index $= \log_2 256 = 8$ bits. Why? 1 line per set.
• Tag $= 32 - 8 - 6 = 18$ bits. Why? leftover bits.

Address 0xDEADBEEF = 1101 1110 1010 1101 1011 1110 1110 1111.

Carefully peel the low 14 bits (= 8 index + 6 offset). The last 14 bits of the address are 11 1110 1110 1111:

• Offset = low 6 bits = 101111 = 0x2F (byte 47 in the line). Why? lowest $\log_2 B$ bits.
• Index = next 8 bits = 11111011 = 0xFB = set 251. Why? next $\log_2 S$ bits. (Watch the boundary: the offset eats the bottom 6 bits, so the index is bits 13..6, which read 11111011, not 10111011.)
• Tag = top 18 bits, compared against what's stored in set 251.

Worked Example 2 — 4-way set-associative

Same numbers but 4-way: $L=256$, $w=4$, $B=64$, 32-bit.

• Offset $=6$ (unchanged — depends only on $B$).
• Sets $S = L/w = 256/4 = 64$ ⇒ index $=\log_2 64 = 6$ bits. Why? fewer sets now.
• Tag $= 32 - 6 - 6 = 20$ bits. Why? index lost 2 bits, tag gained 2 bits.

Worked Example 3 — total bits stored

For the 4-way cache: each line also stores a valid bit and the tag. Bits per line $= \text{data}(64\times8) + \text{tag}(20) + \text{valid}(1) = 512 + 21 = 533$ bits. Total = $256 \times 533 = 136{,}448$ bits of SRAM. Why? overhead (tag+valid) is real silicon cost — bigger lines amortize overhead but waste bandwidth if locality is poor.

Common mistakes (Steel-manned)

Flashcards

Connections

• Cache associativity & replacement policies
• Spatial and temporal locality
• Memory hierarchy and latency numbers
• Virtual vs physical addressing (VIPT/PIPT)
• Cache coherence (MESI)
• TLB and page tables — same "split the address, look up, verify" pattern

Concept Map

Hinglish (regional understanding)