Cache miss types (compulsory, capacity, conflict): Exercises

This page is a self-testing ladder. Each problem is a mini-simulation of a cache. Before you look at any solution, run the access trace by hand the way the parent note taught: for every access ask the question-chain — first touch? too small? mapping fight?

The vocabulary this whole page uses (defined before any symbol appears)

Everything below is bookkeeping with four numbers. Define them now, in plain words, before we ever put them in a formula:

Definition The four miss-counts (memorize these four names)

For one fixed access trace, we simulate it on different caches and count misses:

$M_{real}$ = misses in the real cache we actually build (limited associativity, e.g. direct-mapped). This is the number that hurts.
$M_{fa}$ = misses in a fully-associative cache of the same size, using LRU. "Fully-associative" means a block may sit in any slot — there is no mapping rule, so this cache can never suffer a conflict.
$M_{inf}$ = misses in an infinite cache (nothing is ever evicted). The only miss left here is a block's first ever touch.
A distinct block = a block number that appears in the trace, counted once no matter how many times it recurs.

Read the subscripts as words: real, fa = fully-associative, inf = infinite. We will use only these three symbols — never any other spelling — for the rest of the page.

Intuition Why three caches, and why subtraction gives each C (the WHY, drawn)

Each idealized cache switches off exactly one cause of a miss:

Infinite cache: no eviction at all ⇒ the misses that remain, $M_{inf}$ , are purely compulsory (cold, first-touch).
Fully-associative finite cache: eviction can happen (it is finite) but never because of mapping (there is no mapping) ⇒ its extra misses beyond $M_{inf}$ are purely capacity (ran out of room).
Real cache: adds the mapping rule back ⇒ its extra misses beyond $M_{fa}$ are purely conflict (two blocks forced to fight over one home slot).

Because each cache removes one cause, the differences peel the causes apart like layers: $M_{compulsory} = M_{inf} = (number of distinct blocks)$ $M_{capacity} = M_{fa} - M_{inf}$ $M_{conflict} = M_{real} - M_{fa}$ Look at the figure below: the total real bar is sliced into three stacked layers, and each subtraction is literally the height of one layer. That is the entire method of this page.

Figure — Cache miss types (compulsory, capacity, conflict)

Throughout, blocks are 1 word for simplicity, so "block number" = the number in the trace. The direct-mapped index of block $B$ is $index = B mod S$ , where $S$ = number of sets. (This is the mapping rule: the same value of $B mod S$ means two different blocks are sent to the same home slot and must evict each other.)

Level 1 — Recognition

Problem 1.1 (L1)

A program touches these distinct blocks for the very first time, each exactly once: 7, 3, 99, 3. The cache is infinitely large. How many misses, and of which type?

Recall Solution 1.1

An infinite cache never runs out of room and has no mapping rule, so the only possible miss is compulsory (first-ever touch), i.e. $M_{real} = M_{inf}$ here.

7 → first touch → compulsory.
3 → first touch → compulsory.
99 → first touch → compulsory.
3 → already seen → hit (it never got evicted; the cache is infinite).

Answer: 3 compulsory misses, 0 capacity, 0 conflict. Number of compulsory misses = number of distinct blocks = $∣ {7, 3, 99} ∣ = 3$ .

Problem 1.2 (L1)

Match the cure to the cause: (a) higher associativity, (b) larger cache, (c) prefetching. Each fixes which miss type?

Recall Solution 1.2

(a) higher associativity → fixes conflict (more slots per set means blocks stop fighting over one home). See Cache Associativity & Set Mapping.
(b) larger cache → fixes capacity (more room holds a bigger working set). See Working Set & Program Behavior.
(c) prefetching → fixes compulsory (fetch the block before its first use so the cold miss is hidden). See Prefetching.

Answer: a↔conflict, b↔capacity, c↔compulsory.

Level 2 — Application

Problem 2.1 (L2)

Direct-mapped, 4 lines ( $S = 4$ ). Trace: 0, 8, 0, 8. Classify every access.

Recall Solution 2.1

Index $= B mod 4$ : block 0 → $0 mod 4 = 0$ ; block 8 → $8 mod 4 = 0$ . Both live in set 0 only — a mapping collision.

#	Block	State before	Result	Why
1	0	empty	Compulsory	first touch of 0
2	8	{0}	Compulsory	first touch of 8, evicts 0
3	0	{8}	Conflict	0 seen before (not cold); only 2 blocks used ⇒ a fully-assoc 4-line cache would hold both ⇒ $M_{fa}$ hits here ⇒ the miss is caused purely by mapping
4	8	{0}	Conflict	same reasoning

Answer: 2 compulsory + 2 conflict + 0 capacity. Fix in hardware: just 2-way associativity lets 0 and 8 co-exist in set 0 → accesses 3 and 4 become hits.

Problem 2.2 (L2)

Fully-associative, 2 lines, LRU. Trace: 0, 1, 2, 0. Classify every access.

Recall Solution 2.2

Fully-associative ⇒ no mapping rule ⇒ no conflict misses are possible, ever (this cache is the $M_{fa}$ reference). Only compulsory and capacity remain. LRU evicts the least-recently-used block.

#	Block	Cache (LRU→MRU)	Result	Why
1	0	[0]	Compulsory	first touch
2	1	[0,1]	Compulsory	first touch
3	2	[1,2]	Compulsory	first touch; evicts 0 (LRU)
4	0	[2,0]	Capacity	0 was seen but evicted only because 3 distinct blocks don't fit in 2 slots

Answer: 3 compulsory + 1 capacity + 0 conflict. See LRU and Replacement Policies.

Level 3 — Analysis

Problem 3.1 (L3)

Direct-mapped, 2 lines ( $S = 2$ , index $= B mod 2$ ). Trace: 0, 1, 2, 0, 3, 0. Classify each access. This is the parent's Example 3 — the subtle one.

Recall Solution 3.1

The two sets each hold one block. I show one honest walk-through table with a WHY for every step, tracking both sets side by side. Index of 0=0, 1=1, 2=0, 3=1 (so 0 and 2 share set 0; 1 and 3 share set 1).

#	Block	idx	set0 before / set1 before	Result (real)	WHY this result
1	0	0	{} / {}	Compulsory	first ever touch of 0; place it in set 0
2	1	1	{0} / {}	Compulsory	first ever touch of 1; place it in set 1
3	2	0	{0} / {1}	Compulsory	first ever touch of 2; set 0 already holds 0 ⇒ evict 0, install 2
4	0	0	{2} / {1}	miss	0 was seen (not cold), but set 0 now holds 2 ⇒ miss; is it conflict or capacity? decided in Step B ⇒ capacity
5	3	1	{0} / {1}	Compulsory	first ever touch of 3; set 1 holds 1 ⇒ evict 1, install 3
6	0	0	{0} / {3}	Hit	access #4 already re-installed 0 into set 0, and nothing since touched set 0 ⇒ 0 is still there

Why the single table (not two): the only trap is access #6 — it is tempting to think 0 was evicted, but re-read step 4: 0 was re-installed into set 0 there, and steps 5 only touches set 1, so 0 survives. Tracking both sets in one row makes this visible, so there is no need to redo anything.

Real misses = 5 (accesses 1,2,3,4,5), i.e. $M_{real} = 5$ .

Step B — is access #4 conflict or capacity? Apply the rule from the definitions: simulate the 2-line fully-associative LRU ( $M_{fa}$ reference) on the same trace up to #4, 0,1,2,0:

0→[0] (compulsory), 1→[0,1] (compulsory), 2→[1,2] (compulsory, evicts 0 as LRU), 0→miss (0 is gone).
Because even the fully-associative cache also misses on 0 at #4, the mapping was not the culprit — the size was. So access #4 is a capacity miss, not conflict.

Step C — tally with the three formulas.

$M_{compulsory} = M_{inf} =$ distinct blocks first-touched $= {0, 1, 2, 3} = 4$ .
$M_{fa}$ on the full trace 0,1,2,0,3,0: 0c, 1c, 2c (evict 0), 0 capacity (had [1,2]), 3c (evict 1 → [0,3]), 0 hit (0 still there) ⇒ 5 misses, so $M_{fa} = 5$ .
$M_{capacity} = M_{fa} - M_{inf} = 5 - 4 = 1$ .
$M_{conflict} = M_{real} - M_{fa} = 5 - 5 = 0$ .
Check: $4 + 1 + 0 = 5 = M_{real}$ ✓.

Answer: 4 compulsory + 1 capacity + 0 conflict. Access #4 is the capacity miss.

The timeline below draws this trace step by step; follow the amber box at step 4 — it is the capacity miss that looks like a conflict but isn't.

Problem 3.2 (L3)

Same trace 0, 1, 2, 0, 3, 0, but now a direct-mapped, 4-line cache ( $S = 4$ ). Recompute the three C's and explain what changed versus Problem 3.1.

Recall Solution 3.2

Index $= B mod 4$ : 0→0, 1→1, 2→2, 3→3. Every block gets its own set — no two collide.

#	Block	idx	Result	WHY
1	0	0	Compulsory	first touch, set 0 empty
2	1	1	Compulsory	first touch, set 1 empty
3	2	2	Compulsory	first touch, set 2 empty (does NOT disturb 0)
4	0	0	Hit	0 still in set 2's neighbour set 0; nothing evicted it
5	3	3	Compulsory	first touch, set 3 empty
6	0	0	Hit	0 never disturbed

Real misses = 4, all first-touches. So $M_{real} = 4 = M_{inf}$ ⇒ $M_{compulsory} = 4$ , $M_{capacity} = M_{fa} - M_{inf} = 4 - 4 = 0$ , $M_{conflict} = M_{real} - M_{fa} = 4 - 4 = 0$ .

What changed: enlarging the cache from 2→4 lines removed the eviction that caused the capacity miss at access #4 in Problem 3.1. The 1 capacity miss is gone. Bigger cache cures capacity — matching the rule from Problem 1.2.

Level 4 — Synthesis

Problem 4.1 (L4)

Design a single trace that produces all three miss types in a direct-mapped, 2-line cache ( $S = 2$ ), then classify each access. (Build it, don't just find one.)

Recall Solution 4.1

Design goals:

Need compulsory → include first touches.
Need conflict → force two blocks into the same set while only a few distinct blocks are live (so the fully-assoc reference $M_{fa}$ would fit them and hit).
Need capacity → make the live set genuinely exceed 2 distinct blocks at some moment (so even $M_{fa}$ misses).

First attempt 0, 2, 0, 1, 3, 1 looked promising but on checking $M_{fa}$ the re-touch at the end still hit in fully-assoc, giving conflict rather than capacity — so it failed the capacity requirement. That failure teaches the fix: to force a capacity miss you must grow the distinct-block count, not just aim addresses at one set. So use:

Chosen trace: 0, 2, 0, 1, 2, 1. Index $= B mod 2$ : 0→0, 2→0, 1→1 (so 0,2 share set 0; 1 sits alone in set 1).

Real direct-mapped walk (with WHY each label):

#	Block	idx	set0 / set1 before	Result (real)	WHY this label
1	0	0	{} / {}	Compulsory	first ever touch of 0
2	2	0	{0} / {}	Compulsory	first ever touch of 2; set 0 held 0 ⇒ evict 0, install 2
3	0	0	{2} / {}	Conflict	0 seen before (not cold); only {0,2} live so far ⇒ $M_{fa}$ hits (checked below) ⇒ mapping caused this miss
4	1	1	{0} / {}	Compulsory	first ever touch of 1; set 1 was empty
5	2	0	{0} / {1}	Capacity	2 seen before, but by now {0,1,2} are all live ⇒ even $M_{fa}$ misses (checked below) ⇒ size, not mapping
6	1	1	{2} / {1}	Hit	1 was installed at #4 into set 1 and nothing has touched set 1 since ⇒ still present

Verify #3 is conflict — simulate $M_{fa}$ (2-line fully-assoc LRU) up to 0,2,0: 0→[0], 2→[0,2], 0→ present ⇒ hit. Fully-assoc hits but real missed ⇒ #3 is conflict. ✓

Verify #5 is capacity — continue $M_{fa}$ on the full trace 0,2,0,1,2,1: 0→[0], 2→[0,2], 0→[2,0] (hit, 0 now MRU), 1→[0,1] (evict 2 as LRU), 2→ miss (2 was evicted!) ⇒ compulsory? No — 2 was seen before, and this is the fully-assoc cache, so it is a genuine capacity-type miss of the size-limited fully-assoc cache. Because $M_{fa}$ also misses here, access #5 in the real cache is capacity, not conflict. ✓

Tally with the formulas.

$M_{real}$ : misses at #1,#2,#3,#4,#5 = 5; hit at #6.
$M_{inf} = M_{compulsory} =$ distinct blocks $= {0, 1, 2} = 3$ .
$M_{fa}$ on full trace above: misses at 0,2,1,2 = 4.
$M_{capacity} = M_{fa} - M_{inf} = 4 - 3 = 1$ (that is access #5).
$M_{conflict} = M_{real} - M_{fa} = 5 - 4 = 1$ (that is access #3).
Check: $3 + 1 + 1 = 5 = M_{real}$ ✓.

Answer: trace 0,2,0,1,2,1 gives 3 compulsory + 1 conflict + 1 capacity + 1 hit — all three C's present, exactly as required.

Level 5 — Mastery

Problem 5.1 (L5)

A trace runs on a real cache. You are given, by simulation (using the exact three counts defined at the top of this page): $M_{real} = 100$ , $M_{fa} = 70$ (same-size fully-associative, LRU), $M_{inf} = 45$ . (a) Compute compulsory, capacity, conflict counts. (b) If each miss costs a 100-cycle penalty and hits cost 0 extra, and there are 1000 total accesses with hit time 1 cycle, compute the Average Memory Access Time (AMAT) of the real cache. (c) Perfect Prefetching eliminates all compulsory misses; recompute AMAT.

Recall Solution 5.1

(a) Decomposition by subtraction — the same three formulas as the top of the page, each idealized cache removing exactly one cause: $M_{compulsory} = M_{inf} = 45$ $M_{capacity} = M_{fa} - M_{inf} = 70 - 45 = 25$ $M_{conflict} = M_{real} - M_{fa} = 100 - 70 = 30$ Check: $45 + 25 + 30 = 100 = M_{real}$ ✓

(b) AMAT. The formula (see Average Memory Access Time (AMAT)) is $AMAT = HitTime + MissRate \times MissPenalty .$ Miss rate $= 100/1000 = 0.1$ . So $AMAT = 1 + 0.1 \times 100 = 1 + 10 = 11 cycles.$

(c) With perfect prefetch the 45 compulsory misses vanish (capacity + conflict remain because prefetch does not add room or associativity): $M_{new} = 25 + 30 = 55, miss rate = 55/1000 = 0.055.$ $AMAT = 1 + 0.055 \times 100 = 1 + 5.5 = 6.5 cycles.$

Answer: (a) 45 / 25 / 30. (b) 11 cycles. (c) 6.5 cycles — a 40.9% AMAT reduction, and it targeted only the compulsory component, exactly as the cure-map predicts.

Problem 5.2 (L5)

Continuing Problem 5.1's trace: you may apply one upgrade. Option X = full associativity (removes all 30 conflict misses, adds +1 cycle to hit time). Option Y = double the cache size (empirically removes 60% of capacity misses, hit time unchanged). Which gives lower AMAT? Show the numbers.

Recall Solution 5.2

Option X (full associativity): conflicts → 0, so misses $= 45 + 25 + 0 = 70$ , miss rate $= 0.07$ , but hit time rises to 2. $AMAT_{X} = 2 + 0.07 \times 100 = 2 + 7 = 9 cycles.$

Option Y (double size): removes $0.6 \times 25 = 15$ capacity misses, so capacity $= 10$ ; misses $= 45 + 10 + 30 = 85$ , miss rate $= 0.085$ , hit time stays 1. $AMAT_{Y} = 1 + 0.085 \times 100 = 1 + 8.5 = 9.5 cycles.$

Answer: Option X wins (9 < 9.5 cycles) — even though it raises hit time, killing all 30 conflict misses saves more than the +1-cycle hit tax costs here. The lesson: an upgrade's value depends on how many misses of its target type exist; conflicts dominated this trace. See Cache Block Size Trade-offs for the analogous tension with block size.

Recall Final self-check (cover the answers)

Conflict formula ::: $M_{real} - M_{fa}$ Capacity formula ::: $M_{fa} - M_{inf}$ Compulsory count equals ::: number of distinct blocks touched (= $M_{inf}$ ) A miss that also misses in a same-size fully-assoc cache is ::: capacity (or compulsory), never conflict Prefetching targets which C ::: compulsory AMAT formula ::: $HitTime + MissRate \times MissPenalty$

Related depth: Spatial and Temporal Locality explains why re-references cluster (feeding capacity/conflict behavior), and Cache Associativity & Set Mapping details the $B mod S$ machinery behind every conflict above.