Average memory access time (AMAT)

WHY this exact formula? (Derivation from scratch)

We want the expected time per access. Let a single access take:

$T_{hit}$ if it hits (probability $= 1 - m$ , where $m$ = miss rate),
something longer if it misses (probability $= m$ ).

Key modeling decision: On every access we first look in the cache — so we always pay $T_{hit}$ . Only when we miss do we pay the extra trip to lower memory, $T_{penalty}$ .

So the two outcomes are:

Outcome	Probability	Time
Hit	$1-m$	$T_{hit}$
Miss	$m$	$T_{hit} + T_{penalty}$

Expected value (definition of average):

\text{AMAT} = (1-m)\,T_{hit} + m\,(T_{hit}+T_{penalty})

Expand and collect the $T_{hit}$ terms:

= T_{hit} - m\,T_{hit} + m\,T_{hit} + m\,T_{penalty} = \boxed{T_{hit} + m\cdot T_{penalty}}

Recursive / Multi-level AMAT (WHY caches are layered)

The "miss penalty" of L1 is itself just the AMAT of L2. Memory is a hierarchy, so we nest the formula:

\text{AMAT} = HT_{L1} + m_{L1}\big(HT_{L2} + m_{L2}\cdot MP_{L2}\big)

where $MP_{L2}$ is the time to reach main memory (or the next level).

Figure — Average memory access time (AMAT)

$HT_{L1}=1$ ns, $m_{L1}=10\%$ ; $HT_{L2}=10$ ns, $m_{L2}=20\%$ (local); DRAM penalty $MP_{L2}=200$ ns. Inner first (AMAT of L2 subsystem): $HT_{L2} + m_{L2}\cdot MP_{L2} = 10 + 0.2\times200 = 10 + 40 = 50\ \text{ns}$ Why? This is what an L1 miss actually costs — the effective L1 miss penalty. Now plug into L1: $\text{AMAT} = 1 + 0.10\times 50 = 1 + 5 = 6\ \text{ns}$ Why this step? The scary 200 ns DRAM cost got multiplied by $0.10\times0.20 = 0.02$ (global L2 miss rate), so it only adds $0.02\times200 = 4$ ns.

Common Mistakes

Active Recall

Recall Cover and answer

State the AMAT formula and why $HT$ isn't multiplied by miss rate.
Derive AMAT from the two-outcome expected value.
Why does adding L2 reduce AMAT even though DRAM is still slow?
Difference between local and global miss rate?
In Example 1, what fraction of AMAT came from misses?

Recall Feynman: explain to a 12-year-old

Imagine your school locker (fast) holds most of your books. Usually you grab a book instantly — that's a hit. But sometimes the book is in the far-away library (slow) — a miss. On average, how long to get a book? Almost always fast, but the rare library trips are so slow they pull the average up. AMAT is just that average waiting time. To make it small, we don't try to make the locker faster — we try to make library trips rarer (fewer misses) or add a nearer "shelf" (L2) so we rarely go all the way to the library.

Flashcards

AMAT formula (single level)

\text{AMAT} = HT + \text{MissRate}\times\text{MissPenalty}

Why is hit time not multiplied by miss rate?

You access the cache on every request, so you always pay

HT

; only the miss penalty is conditional on missing.

Derive AMAT from expected value

(1-m)HT + m(HT+MP) = HT + m\,MP

Two-level AMAT formula

HT_{L1} + m_{L1}(HT_{L2} + m_{L2}MP_{L2})

Local miss rate of L2

L2 misses ÷ accesses that reached L2.

Global miss rate of L2

L2 misses ÷ all CPU accesses

= m_{L1}\times m_{L2,local}

Which miss rate goes inside the recursive AMAT term?

The local miss rate of that level.

Miss penalty definition

The extra time to fetch the block from the next level, beyond the hit access.

Single-level: HT=1ns, m=5%, MP=100ns → AMAT?

1 + 0.05\times100 = 6

ns.

Why add an L2 cache if DRAM is still slow?

L1 misses mostly hit in L2, so the huge DRAM penalty is multiplied by the tiny product

m_{L1}\times m_{L2}

Connections

Cache Miss Rate & Miss Types (3 Cs)
Miss Penalty & Main Memory Latency
Multi-level Cache Hierarchy
Cache Associativity & Hit Time tradeoff
CPU Performance Equation (AMAT feeds memory-stall cycles)
Locality of Reference (why hit rates are high at all)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, memory hierarchy ka main funda ye hai ki cache bahut fast hoti hai lekin choti, aur main memory (DRAM) badi lekin slow. Har access pe pehle cache check karte ho — agar mil gaya to hit (fast), nahi mila to miss (DRAM tak jana padta hai, bahut slow). AMAT ka matlab hai: average me ek access me kitna time lagta hai. Formula: AMAT = Hit Time + Miss Rate × Miss Penalty.

Yaha sabse important baat: Hit Time hamesha lagti hai kyunki har baar cache to check karni hi padti hai. Isliye usko miss rate se multiply nahi karte — wo flat cost hai. Sirf Miss Penalty (DRAM ka extra time) tabhi lagta hai jab miss hota hai, isliye usko miss rate se multiply karte hain. Example: HT=1ns, miss rate 5%, penalty 100ns → AMAT = 1 + 0.05×100 = 6 ns. Dekho, 6 me se 5 ns to sirf misses ki wajah se aaya — matlab thode se misses hi average ko upar khींch dete hain!

Ab multi-level: L1 miss hone pe seedha DRAM mat jao — beech me L2 laga do. To L1 ka miss penalty ab L2 ka AMAT ban jaata hai. Formula nested ho jaata hai: AMAT = HT_L1 + m_L1(HT_L2 + m_L2 × MP_L2). Iska fayda ye ki DRAM ka bada 200ns penalty ab bahut kam baar lagta hai (m_L1 × m_L2, ek tiny number), isliye overall AMAT gir jaata hai.

Yaad rakho: performance improve karni hai to hit time se zyada miss rate kam karo — kyunki misses hi average ko dominate karte hain. Locality (spatial + temporal) isliye important hai, wo hit rate badhati hai.

WHAT is AMAT?

WHY this exact formula? (Derivation from scratch)

Recursive / Multi-level AMAT (WHY caches are layered)

Worked Examples

Common Mistakes

Active Recall

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Memory Hierarchy & Caches

Connections