Cache organization (direct-mapped): Exercises — Hardware deep dive

Intuition How to use this page

These problems build from "read off the bits" up to "design and defend a cache." Each is graded L1 → L5. Try each one before you open its collapsible solution. The parent note is Cache organization (direct-mapped) — if a symbol here feels unearned, that note built it first.

Throughout, we reuse the three address fields from the parent: $Tag m - c - b bits Index c bits Offset b bits$ where $m$ = address width, $2^{c}$ = number of cache lines, $2^{b}$ = block size in bytes.

One notation note: wherever a final numerical answer appears, it is wrapped in ==double equals==. In this vault that marks a cloze — the term or number you should be able to recall on your own; when you review, it is the blank you fill in. It carries no mathematical meaning; it is just a "remember this" highlight.

Before you start, look at Figure 1 (s01). It is the map every problem uses: it draws a single address as a horizontal bar split into three coloured boxes — a lavender Tag box on the left (the most-significant bits), a mint Index box in the middle ( $c$ bits), and a butter-yellow Offset box on the right (the least-significant $b$ bits). An arrow drops from each box to the job it does: Tag → "identifies WHICH memory block," Index → "picks WHICH cache line (no search!)," Offset → "picks WHICH byte in the block." At the bottom it states the hit rule (compare tag AND valid = 1) and reminds you the offset never causes a miss.

Figure — Cache organization (direct-mapped)

Level 1 — Recognition

"Can you read the fields straight off the address?"

Exercise 1.1

A cache has $b = 4$ (16-byte blocks) and $c = 6$ (64 lines), with $m = 16$ -bit addresses. (a) How many tag bits? (b) For address 0xB3A7, give (tag, index, offset) in binary and decimal.

Recall Solution 1.1

(a) Tag bits $= m - c - b = 16 - 6 - 4 === 6 ==$ bits.

(b) Write 0xB3A7 in binary (16 bits): $1011 0011 1010 0111$ Split from the right (exactly the box order in Figure 1) — offset is the lowest, then index, then tag:

Offset = lowest $b = 4$ bits = 0111 = $7$ .
Index = next $c = 6$ bits. The low 4 are offset, so index is bits $[9 : 4]$ . Group them: bits ...11 1010 0... → index bits are 111010 = $58$ .
Tag = top $6$ bits = bits $[15 : 10]$ = 101100 = $44$ .

Check: $44 \cdot 2^{10} + 58 \cdot 2^{4} + 7 = 45056 + 928 + 7 = 45991 = 0xB3A7$ . ✅

Exercise 1.2

Same cache as 1.1. What is the block address of 0xB3A7 (the address with offset bits stripped)?

Recall Solution 1.2

Block address $= ⌊ \frac{Address}{2 ^{b}} ⌋ = ⌊ \frac{45991}{16} ⌋ === 2874 ==$ . Sanity: block address in binary is just "tag ∥ index" = 101100 111010 = $2874$ . ✅

Level 2 — Application

"Given an address, do the hit/miss decision."

Exercise 2.1

A cache is 16 bytes of data with 4-byte blocks and 8-bit addresses. First derive its field widths yourself, then: line 3 currently holds valid data with stored tag = 0010 (=2), and you access 0x2E. (a) Derive $b$ , $c$ , and the tag width. (b) Compute (tag, index, offset) for 0x2E. (c) Hit or miss? Why?

Recall Solution 2.1

(a) Derive the fields (self-contained):

Block size $= 4 = 2^{2}$ bytes → $b = 2$ (offset bits).
Number of lines $= \frac{cache size}{block size} = \frac{16}{4} = 4 = 2^{2}$ → $c = 2$ (index bits). So there are exactly 4 lines, numbered 0–3.
Tag width $= m - c - b = 8 - 2 - 2 = 4$ bits.

(b) 0x2E = 0010 1110 (8 bits).

Offset = low 2 bits = 10 = $2$ .
Index = next 2 bits = 11 = $3$ .
Tag = top 4 bits = 0010 = $2$ .

(c) Go to line 3 (index tells us instantly, no search). Valid = 1 ✅ and stored tag 0010 matches address tag 0010 ✅. By the hit condition $Hit = (Valid = 1) \land (Tag_{cache} = Tag_{addr}),$ this is a HIT. Return byte $2$ of the block in line 3.

Exercise 2.2

Same 16-byte / 4-byte-block / 8-bit cache ( $b = 2$ , $c = 2$ , 4 lines). Trace this stream on a cold (all-invalid) cache and label each access H (hit) or M (miss): $0x00, 0x01, 0x04, 0x00$

Recall Solution 2.2

Decode each (offset = low 2 bits, index = next 2 bits, tag = top 4):

Addr	binary	index	offset	block addr $= ⌊ a /4 ⌋$
0x00	0000 0000	0	0	0
0x01	0000 0001	0	1	0
0x04	0000 0100	1	0	1
0x00	0000 0000	0	0	0

0x00: line 0 invalid → M (cold). Load block 0, tag 0.
0x01: line 0 now valid, tag 0 matches → H (same block, different byte).
0x04: line 1 invalid → M (cold). Different index!
0x00: line 0 still holds block 0, tag matches → H.

Result: M H M H → 2 hits, 2 misses. Hit rate $= 2/4 === 0.5 ==$ .

Level 3 — Analysis

"Explain and quantify collisions and thrashing."

Exercise 3.1

16-byte cache, 4-byte blocks, 8-bit addresses (so $b = 2$ , $c = 2$ , 4 lines). List all three other addresses in $[0, 255]$ that (a) map to the same line as 0x0D and (b) belong to a different block (would cause a conflict). Give the smallest such addresses.

Recall Solution 3.1

0x0D = 0000 1101: index = 11 = 3, tag = 0000.

Why does "block address $mod 4$ " give the index? Start from the definitions. Strip the offset: the block address is $B = ⌊ a / 2^{b} ⌋$ . Its binary form is exactly the address with the low $b$ bits removed — that is, the bits "tag ∥ index" glued together. The index occupies the lowest $c$ bits of $B$ . Taking any integer modulo $2^{c}$ keeps precisely its lowest $c$ bits and discards the rest (that is the definition of $mod 2^{c}$ in binary). Those lowest $c$ bits of $B$ are the index field. Hence $Index = B mod 2^{c} = ⌊ \frac{a}{2 ^{b}} ⌋ mod 2^{c},$ and here with $c = 2$ , that is $B mod 4$ . This is why blocks $3, 7, 11, 15, \dots$ (all $\equiv 3 (mod 4)$ ) land on line 3.

Distinct blocks conflicting with block 3 (block address of 0x0D is $⌊ 13/4 ⌋ = 3$ ):

block 7 → base address $7 \cdot 4 = 28 = 0x1C$ , tag = 0001
block 11 → $11 \cdot 4 = 44 = 0x2C$ , tag = 0010
block 15 → $15 \cdot 4 = 60 = 0x3C$ , tag = 0011

So 0x1C, 0x2C, 0x3C all fight over line 3 with 0x0D. Every tag differs, so any interleaving thrashes.

Exercise 3.2

On the same cold cache, the loop below runs 3 iterations: $(0x0D, 0x4D) \times 3$ 0x4D = 0100 1101 → index 3, tag 0100. Count total misses and give the miss rate. Classify each miss (cold vs conflict).

Recall Solution 3.2

Both map to line 3, tags 0000 vs 0100 differ → they collide.

#	access	line 3 before	result	line 3 after
1	0x0D	invalid	M (cold)	tag 0000
2	0x4D	tag 0000	M (conflict)	tag 0100
3	0x0D	tag 0100	M (conflict)	tag 0000
4	0x4D	tag 0000	M (conflict)	tag 0100
5	0x0D	tag 0100	M (conflict)	tag 0000
6	0x4D	tag 0000	M (conflict)	tag 0100

Total accesses = 6, misses = 6. Miss rate = $6/6 === 1.0 ==$ (100% — pure thrashing): 1 cold + 5 conflict.

Figure 2 (s02) draws this ping-pong: on the left a stack of the 4 cache lines with only line 3 coloured coral (lines 0–2 sit empty); on the right the two blocks 0x0D (tag 0000) and 0x4D (tag 0100). Curved arrows show each block being loaded into line 3 and immediately evicting the other, and the result panel reads "M M M M M M, miss rate = 100%," with the cure ("set-associativity") boxed at the bottom.

Level 4 — Synthesis

"Design the fields; account for every bit."

Exercise 4.1

Design a direct-mapped cache: 32-bit addresses, 32 KB data, 64-byte blocks. Compute $b$ , $c$ , tag bits, and the total SRAM bits including 1 valid bit per line.

Recall Solution 4.1

Block size $= 64 = 2^{6}$ → $b === 6 ==$ .
Number of lines $= \frac{32 KB}{64 B} = \frac{32768}{64} = 512 = 2^{9}$ → $c === 9 ==$ .
Tag $= m - c - b = 32 - 9 - 6 === 17 ==$ bits.

Bits per line = data $64 \times 8 +$ tag $17 +$ valid $1 = 512 + 17 + 1 = 530$ bits. Total = $512 lines \times 530 === 271360 ==$ bits $= 33920$ bytes $\approx 33.1$ KB. Overhead over the 32 KB of data: $\frac{17 + 1}{512} \approx== 3.52% ==$ .

Exercise 4.2

For the cache of 4.1 ( $m = 32$ , $b = 6$ , $c = 9$ , tag $= 17$ ), is address 0xDEADBEEF a hit if the line at its index holds valid data with stored tag 0x1BD45? Decode the index and tag explicitly and decide.

Recall Solution 4.2

0xDEADBEEF $= 3735928559$ . Peel the fields with the standard formulas.

Offset $= a mod 2^{b} = a mod 64$ . Low 6 bits of …EF = 101111 = $47$ .

Index $= ⌊ \frac{a}{2 ^{b}} ⌋ mod 2^{c} = ⌊ \frac{a}{64} ⌋ mod 512$ . $⌊ 3735928559/64 ⌋ = 58373883$ , and $58373883 mod 512 = 315$ . So 0xDEADBEEF maps to line 315 (binary 100111011). Since the problem says the resident line is the one at this index, both the address and the stored line share index 315 — the index does not decide the outcome here; the tag does.

Tag $= ⌊ \frac{a}{2 ^{b + c}} ⌋ = ⌊ \frac{a}{2 ^{15}} ⌋ = ⌊ \frac{3735928559}{32768} ⌋ = 113989 = 0x1BD45$ .

The stored tag is 0x1BD45 = $113989$ — equal to the address tag, and the line is valid. By the hit condition this is a HIT. (If the stored tag had been any other value, it would be a conflict miss, regardless of the matching index.)

Level 5 — Mastery

"Reason about trade-offs, prove behaviour, choose designs."

Exercise 5.1

Two direct-mapped caches have the same total data size of 8 KB.

Cache A: 32-byte blocks. Cache B: 64-byte blocks. Compute $(b, c)$ for each. A workload strides through memory reading 1 byte every 48 bytes (so consecutive reads are 48 B apart). Which cache captures more spatial locality per fetched block for this stride, and why?

Recall Solution 5.1

A: block $32 = 2^{5}$ → $b = 5$ ; lines $= 8192/32 = 256 = 2^{8}$ → $c = 8$ .
B: block $64 = 2^{6}$ → $b = 6$ ; lines $= 8192/64 = 128 = 2^{7}$ → $c = 7$ .

Stride = 48 B. In A (32-B blocks) two accesses 48 B apart never land in the same block (48 > 32), so every access is a fresh block — spatial locality wins 0 extra bytes reuse. In B (64-B blocks), an access at byte $x$ and the next at $x + 48$ can share a block (48 < 64) whenever $x mod 64 \leq 15$ . So Cache B captures more spatial locality on this stride. Trade-off: B has fewer lines (128 vs 256), raising conflict-miss risk elsewhere. Bigger blocks help spatial locality but cost line count — no free lunch.

Exercise 5.2

Prove: in any direct-mapped cache, two addresses $x$ and $y$ can never both be resident and hit at the same time if they share the same index but have different tags. Then state the one architectural change that breaks this limitation.

Recall Solution 5.2

A line is a single slot: it stores exactly one (valid, tag, block) triple. Suppose $x$ and $y$ share index $i$ but have tags $t_{x} \neq = t_{y}$ . Both map to line $i$ . The line's tag field can equal $t_{x}$ or $t_{y}$ , never both simultaneously (it is one register). So at any instant at most one of $x, y$ satisfies $Tag_{cache} = Tag_{addr}$ . Therefore they cannot both hit; loading one evicts the other. ∎

The fix: allow a set to hold more than one line — i.e. set-associativity (a set of $n$ ways lets up to $n$ colliding blocks coexist). With $n \geq 2$ , $x$ and $y$ can both reside.

Exercise 5.3

The parent's thrashing loop (0x0D, 0x4D)×N had 100% miss rate on a direct-mapped cache. If we upgrade to a 2-way set-associative cache of the same total size with LRU replacement, what is the steady-state miss rate for large $N$ ? (Just reason it out.)

Recall Solution 5.3

Both blocks map to the same set, but a 2-way set has two ways — both blocks fit, one per way. First two accesses are cold misses; after that each block stays resident (nothing else evicts it), so every subsequent access hits. Miss rate $= \frac{2}{2 N} = \frac{1}{N} \to== 0 ==$ as $N \to \infty$ . Thrashing eliminated. This is why associativity is the standard cure — details in Cache Replacement Policies and Cache Write Policies for the write side.

Recall One-line self-test dump

Read off tag/index/offset of any address ::: peel offset (low $b$ ), then index (next $c$ ), rest is tag. Number of index bits ::: $c = lo g_{2} (cache size / block size)$ . Why block-address mod $2^{c}$ equals the index ::: modulo $2^{c}$ keeps the lowest $c$ bits, which are exactly the index field of the block address. Two addresses, same index, different tag ::: conflict — cannot coexist in a direct-mapped cache. Cure for pure thrashing at 100% miss ::: set-associativity (a set holds several ways). Does offset ever cause a miss ::: no — it only selects a byte inside an already-chosen line.