Miss penalty and block transfer; memory-stall cycles; CPI with cache misses

0 · Recall Warm-up

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

• Write-back AMAT with dirty fraction d? from Lesson 4.3.1
• Block fetch time with k-way low-order interleaving? from Lesson 4.1.5
• CPU time formula? from Lesson 0.1.2

1 · The Hook

🎣

"A miss costs 100 ns" hides how that number arises: wait for memory, then move a 64-byte block over an 8-byte bus, piece by piece. And a processor that runs one instruction per cycle on hits can run four times slower once misses are counted. This lesson computes the miss penalty from the hardware and folds it into CPI.

2 · Predict First

🤔

A 64-byte block moves over an 8-byte-wide bus. Memory needs 40 ns before the first transfer, and each bus transfer takes 5 ns. How long does the miss take?

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

3 · Core Concept

💡

Predict First — the answer

64 / 8 = 8 transfers: 40 + 8 × 5 = 80 ns.

Miss penalty from the hardware

Miss penalty = memory latency + (block size ÷ bus width) × time per transfer

• 64 B block, 8 B bus, latency 40 ns, 5 ns per transfer → 40 + 8 × 5 = 80 ns.
• Without interleaving, if each word needs a full memory access t_a plus transfer t_b: (B/w) × (t_a + t_b).
• With k-way low-order interleaving (Lesson 4.1.5): t_a + k × t_b.

In cycles: penalty (ns) ÷ cycle time. At 2 GHz (0.5 ns), 80 ns = 160 cycles.

Refinements (named only): early restart (resume when the needed word arrives), critical word first (fetch the needed word first).

Memory-stall cycles and CPI

Memory-stall cycles = memory accesses × miss rate × miss penalty (cycles)

Per instruction, with separate instruction and data caches: CPI = CPI_base + (1 × m_I × P) + (f_mem × m_D × P)

• 1 instruction fetch per instruction,
• f_mem = loads and stores per instruction,
• m_I, m_D = instruction and data miss rates,
• P = miss penalty in cycles.

Example: CPI_base = 1, m_I = 2%, m_D = 4%, 36% of instructions are loads/stores, P = 100: CPI = 1 + 0.02 × 100 + 0.36 × 0.04 × 100 = 1 + 2 + 1.44 = 4.44. A perfect cache would make the machine 4.44 times faster.

Average memory access time in cycles

AMAT = hit time + miss rate × miss penalty (the hierarchical form, Lesson 4.1.2, with the penalty in place of t_m).

4 · Visual

Miss on a 64-byte block, 8-byte bus

|---- latency 40 ns ----|5|5|5|5|5|5|5|5|      = 40 + 8 x 5 = 80 ns
                         1 2 3 4 5 6 7 8 transfers

CPI = 1 (base)  +  0.02 x 100 (instruction misses)  +  0.36 x 0.04 x 100 (data misses)
    = 1 + 2 + 1.44 = 4.44

5 · Worked Examples

Example 1 Easy

A 32-byte block, a 4-byte bus, 2 ns per bus transfer, no latency beyond the transfers. Miss penalty?

Solution

8 transfers × 2 = 16 ns.

Example 2 Medium

1 GHz processor. Miss penalty: 30 ns latency + a 64-byte block over a 16-byte bus at 4 ns per transfer. Penalty in cycles?

Solution

30 + 4 × 4 = 46 ns = 46 cycles.

Example 3 GATE

CPI_base = 1.2; 1.4 memory accesses per instruction (including the fetch); overall miss rate 3%; miss penalty 80 cycles. Effective CPI?

Solution

1.2 + 1.4 × 0.03 × 80 = 1.2 + 3.36 = 4.56.

6 · GATE Traps

⚠️

• Count transfers = block ÷ bus width, then add the latency once (unless each word pays its own access).
• Convert the penalty to cycles before using it in CPI.
• Every instruction makes one instruction fetch; only loads/stores make data accesses.
• Speedup of a perfect cache = effective CPI ÷ base CPI (same IC and clock).

7 · Memory Hook

🧠

"Penalty = wait + pieces × piece time." Then stalls = accesses × miss rate × penalty.

8 · Connect the Dots

Lesson 4.3.1 priced writes; this lesson priced a miss from the hardware and put it into the CPI. Next: two levels of cache, and the local vs global miss rates that make multi-level questions tricky.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markPenalty

A 128-byte block, a 16-byte bus, 50 ns latency, 4 ns per transfer. Miss penalty (ns)?

Numerical answer: ________

Q2NAT2 marksPenalty in cycles

A 2.5 GHz processor; miss penalty 20 ns latency + a 64-byte block over an 8-byte bus at 2.5 ns per transfer. Penalty in cycles?

Numerical answer: ________

Q3NAT2 marksEffective CPI

CPI_base = 1; I-cache miss rate 1%; D-cache miss rate 5%; 30% loads/stores; penalty 120 cycles. Effective CPI?

Numerical answer: ________

Q4NAT2 marksPerfect-cache speedup

With the CPI from the previous question, how many times faster would the processor be with a perfect cache?

Numerical answer: ________

Q5MCQ1 markInterleaving

Which change reduces the miss penalty for a multi-word block without changing the memory chips' access time?

• (A) Write-through instead of write-back
• (B) A higher associativity
• (C) Low-order interleaving of memory modules
• (D) A larger block size

10 · Rule Card

• Miss penalty = latency + (B / bus width) × transfer time (or interleaving formulas).
• Stall cycles = accesses × miss rate × penalty.
• CPI = CPI_base + m_I·P + f_mem·m_D·P.
• Perfect-cache speedup = CPI_eff / CPI_base.

11 · Concept Ledger

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

miss penalty from latency and transfersbus transfers per blockearly restartcritical word firstmemory-stall cycleseffective CPI with cache missesperfect-cache speedup

12 · Answer Vault