Worked examples — Set-associative and fully associative caches

This page is a drill hall. The parent note gave you the machinery — how an address splits into tag, set index and block offset, and how direct-mapped, set-associative, and fully associative caches differ. Here we throw every kind of question at that machinery so no exam scenario surprises you.

Before we start, one promise: every symbol is re-explained the moment it appears, and every number below is machine-checked in the verify block.

---

The symbols we will reuse

Keep these five letters in mind — every example plugs numbers into exactly these.

---

The scenario matrix

Think of a cache-mapping problem as a machine with three input dials:

• Associativity dial $N$ — how many places a block may go: $N=1$ (direct-mapped), $N=$ some middle number (set-associative), or $N=$ every line (fully associative).
• Address dial — a specific memory address, which may land anywhere, including on a boundary (offset $=0$) or right at the last byte of a block.
• Question type dial — "decode the fields", "which set?", "hit or miss?", "how many bits?", or a real-world word problem.

The table below lists every case class this topic can throw. Each later example is tagged with the cell it covers.

Cell	Case class	What is stressed
A	$N=1$ (direct-mapped) field decode	the degenerate low end of associativity
B	$N=$ middle (4-way) field decode	the normal set-associative case
C	$N=$ all lines (fully associative)	the degenerate high end — no index field
D	Two addresses colliding in a direct-mapped cache	conflict-miss birth
E	The same two addresses in a 2-way cache	conflict avoided by associativity
F	Offset = 0 (block boundary) vs offset = max (last byte)	degenerate / limiting offsets
G	A hit/miss trace with a replacement policy	temporal behaviour over time
H	Word problem — pick associativity under a bit budget	design decision
I	Exam twist — change block size, watch every field move	sensitivity to one dial

---

Quick vocabulary refresh (so nothing is unearned)

Recall Why

${\log }_2$ and not plain division? ${\log }_2(S)$ answers "how many yes/no bits do I need to name one of $S$ things?" ::: Because each bit doubles the count you can name: $k$ bits name $2^k$ things, so to name $S$ things you need the $k$ with $2^k=S$, i.e. $k={\log }_2(S)$.

The field ruler below shows this split drawn to scale (using Example B's widths). In every example that follows, mentally lay your address on this ruler: the orange slab on the right eats the low bits (offset), the teal slab in the middle eats the next bits (index), and the plum slab on the left keeps the rest (tag). Notice the caption's reminder that the three widths always sum to $A$.

---

Example A — Direct-mapped decode (cell A)

Forecast: Guess first — with $N=1$, how many sets are there? (Hint: as many as there are lines.)

1. Lines $L=C/B=32768/32=1024$ (here $C=32\text{ KB}=32768$ bytes, $B=32$ bytes). Why this step? Each line holds one $B$-byte block; $C$ bytes hold $C/B$ blocks, so that's the line count.
2. Sets $S=L/N=1024/1=1024$. Why this step? Direct-mapped means one line per set, so sets $=$ lines. This is the degenerate low end of the matrix.
3. Fields: offset $b={\log }_{2}32=5$; index $i={\log }_{2}1024=10$; tag $t=32-10-5=17$. Why this step? Fields must sum to the address width; whatever isn't offset or index is tag.
4. Decode 0x0000ABCD $=00000000000000001010101111001101_2$.
   • Offset = low 5 bits $=01101_2=13$.
   • Index = next 10 bits, i.e. bits $[14:5]$ $=0101011110_2=350$.
   • Tag = remaining high 17 bits (bits $[31:15]$) $=1$. Why this step? We slice from the right so each field keeps its numeric meaning: shift the address right by $b$ then mask $i$ bits for the index, shift right by $b+i$ for the tag.

Verify: $17+10+5=32$ ✓. Offset $13$ is a valid byte index ($0\le 13<32$) ✓. Line/set $=350$ is in range $[0,1023]$ ✓. (Numeric split checked in Verify block.)

---

Example B — 4-way set-associative decode (cell B)

Forecast: More ways than Example A — do you expect more or fewer index bits?

1. Lines $L=65536/64=1024$ (here $C=64\text{ KB}=65536$ bytes, $B=64$ bytes). Why this step? Same rule as before — capacity divided by block size gives how many blocks fit.
2. Sets $S=L/N=1024/4=256$. Why this step? Four lines share each set, so we need a quarter as many sets as lines. Fewer sets than the direct-mapped case with the same size — index bits shrink, tag bits grow.
3. Fields: $b={\log }_{2}64=6$, $i={\log }_{2}256=8$, $t=32-8-6=18$. Why this step? Offset covers the $64$ bytes in a block, index names one of $256$ sets, tag is the leftover.
4. Decode 0x00DEAD00 $=00000000110111101010110100000000_2$.
   • Offset = low 6 bits $=000000_2=0$.
   • Index = next 8 bits, bits $[13:6]$ $=10110100_2=180$.
   • Tag = high 18 bits (bits $[31:14]$) $=890$. Why this step? Same right-to-left slicing; only the field widths changed.

Verify: $18+8+6=32$ ✓. Set $180\in [0,255]$ ✓. Offset $0$ means the address sits on a block boundary — a cell F limiting case that also happens here (checked below).

---

Example C — Fully associative decode (cell C)

Forecast: With a block allowed anywhere, what happens to the index field?

1. Lines $L=16384/64=256$ (here $C=16\text{ KB}=16384$ bytes, $B=64$ bytes). Why this step? The capacity-over-block rule again; these 256 lines are the total parking spots.
2. Sets $S=1$ (all lines in one giant set). Why this step? Fully associative $=$ the degenerate high end: no partitioning, so index bits $={\log }_{2}1=0$. The index field vanishes.
3. Fields: $b={\log }_{2}64=6$, $i=0$, $t=32-0-6=26$. Why this step? Everything above the offset is tag now — the tag must uniquely name the block among all of memory's blocks, because there's no set to narrow the search.
4. Decode 0x00DEAD00: offset $=0$; tag $=$ address $\gg 6=228020$.

Verify: $26+0+6=32$ ✓. Compare with Example B on the same address: the 4-way tag was $890$ with an 8-bit index $=180$. Here the tag swallows those 8 index bits, so the fully-associative tag equals $890\times 256+180=228020$ — checked in Verify. This is the story "index bits migrate into the tag."

---

Example D — Two colliding addresses, direct-mapped (cell D)

Forecast: Two different addresses, same line — good or bad?

1. Config: $L=1024/16=64$ lines, $S=64$, $b={\log }_{2}16=4$, $i={\log }_{2}64=6$, $t=16-6-4=6$. Why this step? We need the field widths before we can slice either address; capacity/block gives 64 lines, direct-mapped makes 64 sets, so index is 6 bits.
2. Index of 0x0120: bits $[9:4]$. 0x0120 $=0000000100100000_2$; low 4 bits are offset, next 6 bits $=010010_2=18$. Why this step? We shift right past the 4 offset bits and read the next 6 bits — that names the set.
3. Index of 0x0520: bits $[9:4]$. 0x0520 $=0000010100100000_2$; next 6 bits $=010010_2=18$ as well. Why this step? Same slice on the second address; both give $18$ → they map to the same and only line for that set.
4. Tags differ: 0x0120 tag = bits $[15:10]$ $=0$; 0x0520 tag $=1$. Why this step? Same set, different tag = the two blocks fight for one line.

Result: Accessing them alternately causes each to evict the other every time → an endless string of conflict misses, even though 63 other lines sit empty. This is the parking-lot pain the parent note warned about.

Verify: both indices $=18$ ✓, tags $0$ and $1$ (distinct) ✓.

The picture below draws exactly this: a column of 64 lines, only line $18$ highlighted, with both address arrows pointing at that single orange slot. The red caption says out loud why the other 63 lines cannot help.

---

Example E — Same two addresses, now 2-way (cell E)

Forecast: We doubled the choices per set. Does the ping-pong stop?

1. Config: $L=64$, $S=L/N=64/2=32$ sets, $b=4$, $i={\log }_{2}32=5$, $t=16-5-4=7$. Why this step? Halving the sets shifts the index window: index is now 5 bits (bits $[8:4]$), not 6, and the freed bit joins the tag.
2. Index of 0x0120: bits $[8:4]$. From 0000\,0001\,0010\,0000_2, dropping the 4 offset bits and reading 5 bits gives $10010_2=18$. Why this step? Same slicing idea, but the window is now 5 bits wide, so we read one bit fewer at the top of the field.
3. Index of 0x0520: bits $[8:4]$. From 0000\,0101\,0010\,0000_2, the 5-bit slice is $10010_2=18$. Why this step? Bit $9$ (which differed between the two addresses) is now part of the tag, not the index — so both still share set $18$.
4. But each set has 2 lines. Both blocks fit side by side: one in way 0, one in way 1. No eviction. Why this step? Associativity gives a second parking spot in the same set, so a shared index no longer forces a fight.

Result: The alternating accesses now both hit after the first two loads. Associativity converted a stream of conflict misses into hits — exactly the sweet-spot argument.

Verify: both indices $=18$ ✓; two ways available so both resident simultaneously ✓.

---

Example F — Offset extremes: boundary vs last byte (cell F)

Forecast: Two addresses $63$ apart — same block or neighbours?

1. $b={\log }_{2}64=6$, so offset $=$ low 6 bits. Why this step? We only need the offset width to test the extremes; six bits count the 64 bytes inside a block.
2. 0x1000: low 6 bits $=0$ → first byte of its block (the degenerate zero-offset boundary case). Why this step? Offset $0$ is the smallest possible offset — the block's starting byte.
3. 0x103F: low 6 bits $=63$ → last byte of the same block (the maximum-offset limiting case). Why this step? Offset $63=B-1$ is the largest offset, and the bits above bit 5 match 0x1000, so tag+index are identical → one line.
4. Block base address $=$ 0x1000; block spans 0x1000–0x103F. Why this step? Masking off the low 6 bits of either address gives the same base, confirming a shared block.

Result: A single cache miss on 0x1000 brings in all 64 bytes, so the later access to 0x103F is a hit — this is spatial locality made concrete, and it shows both offset limits ($0$ and $B-1$) inside one block.

Verify: offsets $0$ and $63$ ✓; identical block base (address AND $\neg (B-1)$) ✓.

---

Example G — Hit/miss trace with LRU (cell G)

Forecast: Five accesses, two homes, LRU deciding evictions. How many hits?

We track the set as [MRU ... LRU] (most-recently-used first).

1. A → set empty → MISS, load A. Set: [A]. Why this step? Cold start — nothing is cached yet, so the first touch of A cannot hit.
2. B → not present, spare way free → MISS, load B. Set: [B, A]. Why this step? B is a new block and the set still has a free way, so we load without evicting; B becomes most-recent.
3. A → present → HIT. Move A to front. Set: [A, B]. Why this step? A is still resident from step 1; temporal locality pays off, and LRU order updates so A is now most-recent.
4. C → not present, set full → MISS. LRU is B (at the back) → evict B, load C. Set: [C, A]. Why this step? Both ways are full, so we must evict the coldest; LRU marks B as least-recently used.
5. B → not present (we just evicted it!) → MISS, evict LRU = A, load B. Set: [B, C]. Why this step? B returned one access too late — it was thrown out in step 4, so this is a fresh miss; A is now coldest and gets evicted.

Result: hits $=1$ (only step 3), misses $=4$. Final set [B, C].

Verify: hit count $=1$, miss count $=4$, final $=\{B,C\}$ (checked by a small LRU simulator).

The figure walks these five snapshots left to right, colouring HIT green and MISS orange, with the top box always the most-recently-used way — watch B fall to the back and get evicted.

---

Example H — Word problem: choose associativity under a bit budget (cell H)

Forecast: More associativity → bigger tags. Where does the tag cross 20 bits?

1. Lines $L=32768/64=512$. Offset $b=6$. Why this step? We need the line count to know how index bits split among sets; capacity/block gives 512 lines.
2. Tag as a function of $N$: sets $S=512/N$, index $i={\log }_2(512/N)=9-{\log }_{2}N$, so $t=32-i-b=32-(9-{\log }_{2}N)-6=17+{\log }_{2}N.$ Why this step? Each doubling of $N$ halves the sets, removing one index bit and adding it to the tag — so tag grows by exactly $1$ bit per doubling.
3. Evaluate:
   • $N=1$: $t=17$. ✓
   • $N=2$: $t=18$. ✓
   • $N=4$: $t=19$. ✓
   • $N=8$: $t=20$. ✓ (exactly at budget)
   • $N=16$: $t=21$. ✗ (over budget) Why this step? We plug each associativity into $t=17+{\log }_{2}N$ and compare against the 20-bit ceiling.
4. Answer: 8-way is the highest associativity within the 20-bit tag budget.

Verify: $t(8)=20\le 20$ ✓ and $t(16)=21>20$ ✗ (both checked).

---

Example I — Exam twist: change block size, watch every field (cell I)

Forecast: Doubling the block — which fields grow, which shrink?

1. Block 64 B: $b=6$; $L=65536/64=1024$; $S=1024/4=256$; $i=8$; $t=32-8-6=18$. Why this step? Baseline case: standard field computation for the smaller block.
2. Block 128 B: $b={\log }_{2}128=7$; $L=65536/128=512$; $S=512/4=128$; $i=7$; $t=32-7-7=18$. Why this step? Doubling $B$ adds one offset bit (each block covers twice the bytes) and halves the line count, removing one index bit. Those two changes are equal and opposite on the tag — so the tag stays put at 18.
3. Interpretation:
   • Offset: $6\to 7$ (bigger blocks need one more byte-selector bit).
   • Index: $8\to 7$ (fewer, larger blocks → fewer sets).
   • Tag: $18\to 18$ (unchanged — the shifts cancel).

Result: With cache size and associativity fixed, doubling block size trades one index bit for one offset bit; the tag is invariant. A tidy fact examiners love to test.

Verify: both tag values equal $18$ ✓; offset $6\to 7$, index $8\to 7$ ✓.

The last figure stacks the two field rulers so you can see the boundary between index and offset slide left by one bit while the tag edge stays frozen — the arrow marks the single migrating bit.

---

Wrap-up recall

Recall As associativity rises with size fixed, what happens to index and tag bits?

Index bits shrink by 1 per doubling of $N$; tag bits grow by 1 per doubling of $N$; offset unchanged. ::: Because $S=L/N$ so ${\log }_{2}S={\log }_{2}L-{\log }_{2}N$, and the bit lost from the index is added to the tag.

Recall In Example G, why did B miss on its second appearance?

Because between B's two accesses, block C forced an eviction and LRU chose B (the coldest). ::: B returned one access too late — a textbook LRU thrash.

Related deeper dives: Cache performance metrics (turn these hit/miss traces into AMAT), Write policies (what a store miss does), Cache coherence (multiple caches racing), and the Translation Lookaside Buffer (TLB) which is itself a small fully associative cache.