4.2.4 Tracing references: hits and misses; compulsory, capacity and conflict misses

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Tag directory formula? from Lesson 4.2.3
How many comparators for a k-way set-associative cache? from Lesson 4.2.2
Hit ratio formula? from Lesson 4.1.1

1 · The Hook

🎣

"A 4-line cache receives block requests 0, 4, 8, 0, 4, 8, 1. How many misses?" The answer is 7, 7 or 4 depending on the mapping. Tracing small sequences by hand is the core skill of every cache question, and it shows exactly why associativity helps and when it does not.

2 · Predict First

🤔

A direct-mapped cache with 4 lines receives the block sequence 0, 4, 8, 0, 4, 8. Which line does each block use, and how many hits?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

0, 4 and 8 all map to line 0 (j mod 4 = 0). Each evicts the previous one: 0 hits, 6 misses, while lines 1–3 stay empty.

Tracing method

Convert byte addresses to block numbers: ⌊address / block size⌋.
For each reference, find its set (j mod S; S = 1 for fully associative, S = L for direct).
Hit if the block is in that set; otherwise miss, and place it (evicting by the policy if the set is full; LRU unless stated).
Keep a table: reference, set, hit/miss, set contents after.

Example: blocks 0, 4, 8, 0, 4, 8, 1 on three 4-line caches

Cache	Trace	Misses
Direct (4 sets × 1)	M M M M M M M	7
2-way (2 sets × 2), LRU	M M M M M M M	7
Fully associative (1 × 4), LRU	M M M H H H M	4

Direct: 0, 4, 8 all hit line 0. 2-way: 0, 4, 8 all go to set 0 (even blocks), which holds only 2: LRU always evicts the block needed next. Fully associative: all four distinct blocks fit.

The three Cs

Every miss is one of:

Compulsory (cold): the first reference to a block ever. Unavoidable (except by prefetching).
Capacity: the block was used before, but even a fully associative cache of the same size would have evicted it: the working set is bigger than the cache.
Conflict: a fully associative cache of the same size would have hit; the miss comes from the mapping restriction.

For the direct-mapped trace above: 4 compulsory (0, 4, 8, 1), 3 conflict, 0 capacity.

When associativity loses

Blocks 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 on a 4-line cache:

Fully associative LRU: 10 misses (the 5-block loop always evicts the next block needed: all after the first 5 are capacity misses).
Direct-mapped: 7 misses (blocks 1, 2, 3 survive in their own lines; only 0 and 4 fight over line 0).

More associativity removes conflict misses; it cannot remove capacity misses, and LRU can be beaten by a lucky mapping.

Byte addresses

16-byte blocks; addresses 0, 4, 8, 20, 64, 100, 128, 36, 68, 132 → blocks 0, 0, 0, 1, 4, 6, 8, 2, 4, 8. The first three addresses share block 0: spatial locality gives two immediate hits.

4 · Visual

Ref	Block	Direct line	Direct after	Hit?	2-way set	2-way after (LRU first)	Hit?
1	0	0	L0 = 0	M	0	{0}	M
2	4	0	L0 = 4	M	0	{0, 4}	M
3	8	0	L0 = 8	M	0	{4, 8}	M
4	0	0	L0 = 0	M	0	{8, 0}	M
5	4	0	L0 = 4	M	0	{0, 4}	M
6	8	0	L0 = 8	M	0	{4, 8}	M
7	1	1	L1 = 1	M	1	{1}	M

5 · Worked Examples

Example 1 Easy

A direct-mapped cache with 8 lines. Which line does block 27 use?

Solution

27 mod 8 = 3.

Example 2 Medium

A 4-line direct-mapped cache, blocks 1, 3, 5, 1, 3, 5. Misses?

Solution

1 → L1, 3 → L3, 5 → L1 (evicts 1), 1 → L1 (evicts 5), 3 hit, 5 → L1 (evicts 1): 5 misses, 1 hit.

Example 3 GATE

Same sequence 1, 3, 5, 1, 3, 5 on a 4-line 2-way set-associative cache with LRU. Misses?

Solution

2 sets; 1, 3, 5 are all odd → set 1, which holds 2. LRU evicts the block needed next every time: 6 misses. (Here 2-way does worse than direct-mapped.)

6 · GATE Traps

⚠️

Convert byte addresses to block numbers first.
Set = block mod number of sets, not mod number of lines (unless direct-mapped).
Classify a miss as capacity only if a same-size fully associative cache would also miss.
Higher associativity does not always mean fewer misses for a particular sequence.

7 · Memory Hook

🧠

"First time = compulsory; too small = capacity; bad placement = conflict."

8 · Connect the Dots

Traces so far used LRU without question. Next: the replacement policies themselves (LRU, FIFO, random, optimal), how they differ on the same sequence, and what each costs to implement.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markDirect trace

An 8-line direct-mapped cache receives blocks 0, 8, 16, 0, 8, 3, 11, 3. Number of misses?

Numerical answer: ________

Q2NAT2 marks2-way trace

The same sequence on an 8-line 2-way set-associative cache with LRU. Number of misses?

Numerical answer: ________

Q3NAT2 marksFully associative trace

The same sequence on an 8-line fully associative cache. Number of hits?

Numerical answer: ________

Q4NAT2 marksByte addresses

16-byte blocks, 4-line direct-mapped cache. Byte addresses 0, 4, 8, 20, 64, 100, 128, 36, 68, 132. How many hits?

Numerical answer: ________

Q5MSQ2 marksThree Cs

Which statements are true?

(A) A fully associative cache has no conflict misses.
(B) Compulsory misses happen on the first reference to a block.
(C) A larger cache can reduce capacity misses.
(D) Increasing associativity removes capacity misses.

10 · Rule Card

Trace: byte address → block → set (j mod S) → hit/miss → update (LRU unless stated).
Direct: S = L; fully associative: S = 1.
Compulsory (first use), capacity (fully associative of same size also misses), conflict (the rest).
Associativity cuts conflict misses; size cuts capacity misses; neither guarantees fewer misses on every sequence.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

reference traceblock-number conversiontrace tablecompulsory (cold) misscapacity missconflict missworking set

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

lines × (tag + valid + dirty + replacement bits).
k.
hits / total accesses.