Cache organization (direct-mapped): Worked examples

You already met the parking-garage picture in Cache organization (direct-mapped): every memory address has one cache line it is allowed to live in. This page does the boring-but-essential work: we take that one rule and hit it with every kind of input until nothing can surprise you in an exam.

Before we start, the three words we will use constantly, each earned from the address itself.

See the address being sliced:

Figure — Cache organization (direct-mapped)

If any word here feels shaky, the parent note derives each field from scratch; and Memory Addressing explains why addresses are counted in bytes at all.

The scenario matrix

A direct-mapped cache is small, so the list of qualitatively different things that can happen is finite. Here it is — every worked example below is tagged with the cell(s) it covers.

Cell	What makes it different	Covered by
A. Cold access	First-ever touch, valid bit = 0	Ex 1
B. Hit	Line valid, tag matches	Ex 1, Ex 2
C. Same block, different offset	Two addresses, same index+tag, different byte	Ex 2
D. Conflict miss / thrash	Same index, different tag, alternating	Ex 3
E. Degenerate: block size = 1	$b = 0$ , no offset field at all	Ex 4
F. Degenerate: one line	$c = 0$ , everything maps to line 0	Ex 4
G. Boundary: block-crossing access	A read straddling two blocks	Ex 5
H. Wrap-around of index	Block $2^{c}$ landing back on line 0	Ex 6
I. Parameter derivation	Given sizes → find $b, c, tag$	Ex 7
J. Real-world word problem	Loop over an array, count misses	Ex 8
K. Exam twist	Change one parameter, predict effect	Ex 9

We keep the same tiny cache for Examples 1–3 and 5–6 so the numbers stay familiar.

The worked examples

Example 1 — Cold access, then a hit (cells A, B)

Worked example Access address

0x2D, twice Setup: reference cache, all valid bits start at 0 (cache is empty).

Forecast: guess now — is the first access a hit or a miss? Is the second? Why?

Write the address in binary. $0x2D = 0010110 1_{2}$ . Why this step? Every field is read straight off the bits; we cannot slice decimal.
Slice TTTT | II | OO: tag $= 001 0_{2} = 2$ , index $= 1 1_{2} = 3$ , offset $= 0 1_{2} = 1$ . Why this step? The index alone tells us the one line to look at — no searching.
Go to line 3, read its valid bit. It is 0 (empty cache). Why this step? A tag comparison on garbage is meaningless; the valid bit is the gate.
Valid = 0 ⇒ MISS (a cold/compulsory miss). Fetch the 4-byte block, store data, set tag $= 0010$ , valid $= 1$ . Why this step? Nothing was ever loaded here, so no eviction is needed — this is the cheapest kind of miss to explain.
Second access to 0x2D: same index 3, valid now $= 1$ , stored tag $0010$ = address tag $0010$ . HIT. Return byte 1 of the block (offset $= 1$ ). Why this step? Shows the hit condition $Valid = 1 \land Tag_{cache} = Tag_{addr}$ actually firing.

Verify: index should equal (block address) mod 4. Block address $= ⌊ 0 x 2 D /4 ⌋ = ⌊ 45/4 ⌋ = 11$ ; $11 mod 4 = 3$ . ✓ Offset $= 45 mod 4 = 1$ . ✓

Example 2 — Same block, different offset (cells B, C)

Example 3 — Conflict miss and thrashing (cell D)

Worked example Alternate

0x0D and 0x4D forever Forecast: they are different addresses — but do they land on different lines? What is the hit rate of the alternating stream?

Binary: 0x0D $= 00001101$ , 0x4D $= 01001101$ . Why? To read out tag and index.
Fields: both have index $= 1 1_{2} = 3$ . Tags differ: $0000$ vs $0100$ . Why? Same index = same line (they must share spot 3). Different tag = different block. That is the exact recipe for a conflict.
Trace the stream on line 3:
- 0x0D: empty → MISS, store tag $0000$ .
- 0x4D: line has tag $0000$ , need $0100$ → mismatch → MISS, evict, store $0100$ .
- 0x0D: line has $0100$ , need $0000$ → MISS, evict again… Why? Each access evicts the block the next access wants — the definition of thrashing.
Every access is a miss even though the cache has 3 other empty lines. Why? Direct-mapping forbids using those lines; this is precisely the weakness that Set-Associative Caches fixes by giving each index more than one home.

Verify: index of both $= (⌊ 13/4 ⌋ mod 4)$ and $(⌊ 77/4 ⌋ mod 4)$ . $⌊ 13/4 ⌋ = 3, 3 mod 4 = 3$ ; $⌊ 77/4 ⌋ = 19, 19 mod 4 = 3$ . Same index. Tags $⌊ 13/16 ⌋ = 0 \neq = ⌊ 77/16 ⌋ = 4$ . Conflict confirmed. ✓

Example 4 — Two degenerate caches (cells E, F)

Worked example What happens when a field

vanishes? Forecast: can $b = 0$ happen? Can $c = 0$ ? What does the address split look like then?

Case E — block size = 1 byte ( $b = 0$ ).

Offset field is $0$ bits wide → there is no offset. Every address is its own block. Why? $2^{0} = 1$ byte per block; there is only one byte, nothing to index inside it.
With our $m = 8$ , $c = 2$ : split becomes TTTTTT | II (tag $= 6$ bits, index $= 2$ ). Why? Bits are conserved: $8 = 6 + 2 + 0$ .
Consequence: zero spatial locality — fetching one byte never pre-loads neighbours. Word problems that loop through an array (Ex 8) get much worse here.

Case F — one cache line ( $c = 0$ ).

Index field is $0$ bits wide → every block maps to the single line 0. Why? $2^{0} = 1$ line; modulo-1 of anything is 0.
Split (keeping $b = 2$ ): TTTTTT | OO.
Consequence: any two blocks with different tags collide — this is Ex 3's thrashing turned up to maximum. A "cache" with one line is basically a single-block buffer.

Verify: bit budgets. Case E: $6 + 2 + 0 = 8 = m$ . ✓ Case F: $6 + 0 + 2 = 8 = m$ . ✓ For Case F, index of every address $= blockaddr mod 1 = 0$ . ✓

Example 5 — Block-crossing access (cell G)

Worked example Read a 4-byte word starting at

0x1F Setup: reference cache (4-byte blocks). A 4-byte read wants bytes 0x1F, 0x20, 0x21, 0x22.

Forecast: these 4 bytes — do they all live in one cache block?

Which block is each byte in? Block address = byte address $\div 4$ (floor). 0x1F $= 31 \to ⌊ 31/4 ⌋ = 7$ ; 0x20 $= 32 \to 8$ ; 0x21,0x22 $\to 8$ . Why? A block boundary sits every 4 bytes; we must find where our read straddles it.
Two different blocks (7 and 8) ⇒ two cache lookups. Byte 31 comes from block 7; bytes 32–34 from block 8. Why? The offset field wraps at 4; address 0x20 has offset $00$ , meaning "start of a new block."
Index of each block: $7 mod 4 = 3$ , $8 mod 4 = 0$ . Different lines — this particular crossing does not even self-conflict. Why? Shows the crossing is a two-access event, handled by hardware as two block fetches.

Verify: offsets $31 mod 4 = 3$ (last byte of its block) and $32 mod 4 = 0$ (first of next). ✓ Indices $7 mod 4 = 3$ , $8 mod 4 = 0$ . ✓

Example 6 — Index wrap-around (cell H)

Example 7 — Parameter derivation (cell I)

Example 8 — Real-world word problem (cell J)

Worked example Summing a 64-int array (each int = 4 bytes) in the reference cache

Setup: array of 64 ints, laid out contiguously from address 0x00. Reference cache: 4-byte blocks, 4 lines. One int fits exactly in one block. We read every element once, in order.

Forecast: with 64 reads, how many are misses? Guess a number before computing.

How many bytes per block, ints per block? Block $= 4$ bytes $= 1$ int. So each int is its own block — no spatial locality benefit here. Why? Block size equals element size, the worst case for streaming.
Miss pattern: the first touch of each new block is a compulsory MISS. Since every int is a new block and we never revisit, all 64 accesses are compulsory misses. Why? Sequential, single-pass, no reuse ⇒ conflicts and capacity are irrelevant; only cold misses occur.
Miss rate $= 64/64 = 100%$ . Hit rate $= 0%$ . Why? Highlights that block size, not line count, drives streaming performance.
Fix: use 16-byte blocks (4 ints each). Then only every 4th access misses ⇒ 16 misses ⇒ hit rate $= 48/64 = 75%$ . Why? Bigger blocks amortise one fetch over 4 uses — spatial locality, quantified.

Verify: 4-byte block: misses $= 64$ , hit rate $0$ . 16-byte block: misses $= 64/4 = 16$ , hits $= 48$ , hit rate $48/64 = 0.75$ . ✓

Example 9 — Exam twist: change one knob (cell K)

Worked example "Double the block size but keep total cache size fixed. What happens to the number of index bits and the tag?"

Setup: start from Ex 7 (32-bit addr, 64 KB, 32-byte blocks → $b = 5, c = 11, tag = 16$ ). Now block size $\to 64$ bytes, cache size stays 64 KB.

Forecast: will the tag grow, shrink, or stay the same?

New offset bits: $64 = 2^{6}$ ⇒ $b = 6$ (was 5). Gained 1 offset bit. Why? Bigger block = more bytes to address inside it.
New line count: $64 KB /64 B = 1024 = 2^{10}$ ⇒ $c = 10$ (was 11). Lost 1 index bit. Why? Same total size, fatter blocks ⇒ fewer blocks ⇒ fewer lines.
New tag: $32 - 10 - 6 = 16$ . Unchanged! Why? The offset stole a bit and the index gave one back; the tag is the leftover and nets zero. This is the trap the exam is testing — students expect the tag to move.
Performance side-effect: fewer lines ⇒ more potential conflict misses, but bigger blocks ⇒ better spatial locality. It's a trade-off, not a strict win — connects to Cache Performance Metrics.

Verify: old $5 + 11 + 16 = 32$ ; new $6 + 10 + 16 = 32$ ; tag identical at 16. ✓

Recall Quick self-test on the whole matrix

Which field decides hit vs miss? ::: Tag and Index together (with the valid bit); the offset never does. Why can a cache with empty lines still miss every time? ::: Direct-mapping forces colliding blocks onto one line (conflict/thrash), ignoring free lines — cell D. If block size $= 1$ byte, which field disappears? ::: The offset ( $b = 0$ ) — cell E. Double block size, hold cache size fixed: what happens to the tag? ::: It stays the same; offset $+ 1$ , index $- 1$ cancel — cell K. A 4-byte word read at 0x1F needs how many block fetches? ::: Two — it straddles a block boundary (cell G).

Related deeper dives: Cache Replacement Policies (what to evict when lines are shared — trivial for direct-mapped, only one candidate!), Cache Write Policies (what happens on a write hit/miss), and Set-Associative Caches (the cure for the thrashing in Example 3).