Multilevel caches: L1 and L2, local vs global miss rate, inclusion

0 · Recall Warm-up

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

• CPI with base 1, m_I 2%, m_D 4%, 36% loads/stores, P = 100? from Lesson 4.3.2
• Three-level hierarchical AMAT? from Lesson 4.1.2
• Write-through vs write-back in one line? from Lesson 4.3.1

1 · The Hook

🎣

L1 must be tiny to be fast; a tiny cache misses often. Put a bigger, slower L2 behind it, and most L1 misses are caught before reaching DRAM. The catch is in the wording: "L2 miss rate 25%" can mean 25% of L2's own accesses or 25% of all accesses. GATE exploits that ambiguity.

2 · Predict First

🤔

1,000 memory references: 40 miss in L1, and 10 of those also miss in L2. What fraction of L2's accesses miss? What fraction of all references go all the way to memory?

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

3 · Core Concept

💡

Predict First — the answer

L2 sees only L1's misses: 10 / 40 = 25% (local). Of all references: 10 / 1000 = 1% (global).

Local and global miss rates

• Local miss rate of a level = its misses ÷ the accesses it receives. For L2: L2 misses ÷ L1 misses.
• Global miss rate of a level = its misses ÷ all CPU references. For L2: m₁ × m₂(local).
• L1's local and global rates are the same.

AMAT with two levels (hierarchical)

AMAT = t₁ + m₁ × (t₂ + m₂ × t_mem), with m₂ the local L2 miss rate.

Predict numbers with t₁ = 1, t₂ = 10, t_mem = 100 cycles: 1 + 0.04 × (10 + 0.25 × 100) = 1 + 0.04 × 35 = 2.4 cycles.

Stall cycles per instruction

Stalls = (memory accesses per instruction) × m₁ × (t₂ + m₂ × t_mem) (counting t₂ as the L1 miss cost).

Example: base CPI 1; 1.3 accesses per instruction; m₁ = 5%; L2 hit 12 cycles, m₂ = 20% local; memory 100 cycles.

• With L2: 1.3 × 0.05 × (12 + 0.2 × 100) = 1.3 × 0.05 × 32 = 2.08 → CPI = 3.08.
• Without L2: 1.3 × 0.05 × 100 = 6.5 → CPI = 7.5.
• L2 speeds the machine up by 7.5 / 3.08 ≈ 2.44.

Inclusion

• Inclusive hierarchy: everything in L1 is also in L2 (simple to manage).
• Exclusive: a block is in L1 or L2, not both; total capacity = L1 + L2.

Design view

L1: small, fast, often split into instruction and data caches. L2/L3: larger, unified, more associative; their job is to cut the trips to DRAM.

4 · Visual

1000 references
   |
  L1  --- 960 hits
   | 40 misses  (L1 miss rate 4%)
  L2  --- 30 hits
   | 10 misses  (L2 local miss rate 10/40 = 25%;  global 10/1000 = 1%)
 memory

5 · Worked Examples

Example 1 Easy

L1 miss rate 8%; L2 local miss rate 30%. Global L2 miss rate?

Solution

0.08 × 0.3 = 2.4%.

Example 2 Medium

t₁ = 2 cycles, m₁ = 10%; t₂ = 15 cycles, m₂ (local) = 20%; memory 150 cycles. AMAT?

Solution

2 + 0.1 × (15 + 0.2 × 150) = 2 + 0.1 × 45 = 6.5 cycles.

Example 3 GATE

A two-level hierarchy: L1 access 1 ns, L2 access 10 ns, memory 100 ns. 2,000 references: 100 L1 misses, 20 of which miss in L2. Hierarchical AMAT (ns)?

Solution

m₁ = 0.05; m₂ = 20/100 = 0.2. AMAT = 1 + 0.05 × (10 + 0.2 × 100) = 1 + 1.5 = 2.5 ns.

6 · GATE Traps

⚠️

• Local L2 rate divides by L1 misses; global divides by all references.
• If a question gives a global L2 rate, local = global ÷ m₁.
• In the AMAT formula, m₂ is local.
• An exclusive hierarchy's capacity is L1 + L2; inclusive's is effectively L2.

7 · Memory Hook

🧠

"Local looks at what reached it; global looks at everything." Global = m₁ × m₂(local).

8 · Connect the Dots

Lessons 4.3.1–4.3.3 priced misses. The last lesson of Phase 4 asks why they happen in real code: array layout and loop order can change the miss count by a factor of 16.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markGlobal rate

L1 miss rate 5%, L2 local miss rate 40%. Global L2 miss rate in percent?

Numerical answer: ________

Q2NAT2 marksLocal from counts

5,000 references; 250 miss in L1; 50 miss in L2. L2 local miss rate in percent?

Numerical answer: ________

Q3NAT2 marksTwo-level AMAT

t₁ = 1, m₁ = 6%; t₂ = 12, local m₂ = 25%; memory 200 (all in cycles). AMAT in cycles?

Numerical answer: ________

Q4NAT2 marksCPI with L2

Base CPI 1.1; 1.5 memory accesses per instruction; m₁ = 4%; L2 hit 10 cycles; L2 local miss rate 25%; memory 160 cycles. Effective CPI?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true?

• (A) L2's global miss rate is never larger than its local miss rate.
• (B) Adding L2 reduces the average cost of an L1 miss.
• (C) The AMAT formula t₁ + m₁(t₂ + m₂ t_mem) uses L2's local miss rate.
• (D) In an exclusive hierarchy a block can be in both L1 and L2.

10 · Rule Card

• Local miss rate = misses ÷ accesses reaching that level; global = misses ÷ all references = m₁·m₂.
• AMAT = t₁ + m₁(t₂ + m₂·t_mem) (m₂ local).
• Stalls/instr = accesses/instr × m₁ × (t₂ + m₂·t_mem).
• Inclusive vs exclusive.

11 · Concept Ledger

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

L1, L2, L3 cachessplit vs unified cachelocal miss rateglobal miss ratetwo-level AMATinclusive vs exclusive hierarchy

12 · Answer Vault