Multi-level cache hierarchy (L1 - L2 - L3): Foundations

This page assumes you know nothing. Before you can read the parent note and follow every line of the AMAT derivation (we spell that acronym out in section 7), you must be able to read every symbol in it. We build them one at a time, each on top of the last.

1. The CPU and memory — the two characters

Figure — Multi-level cache hierarchy (L1 - L2 - L3)

Look at the figure. The CPU is on the left, the warehouse on the right. The red arrow is one trip to fetch a fact. That trip is long. If the CPU had to make that long trip for every single fact it needs, it would spend nearly all its time waiting and almost none working. That waiting is the whole problem this topic exists to solve.

2. The clock cycle — our unit of time

When the parent note says "L1 hits in 4 cycles" and "DRAM costs 200 cycles", it means: fetching from the far warehouse takes 50 times more ticks than fetching from the nearby notebook. That ratio is the enemy.

3. The cache — the notebook

How the cache is internally arranged (rows, ways, sets) is the subject of Cache Organization — here we only need the black-box behaviour: you ask it for a fact, and it either has it or doesn't.

4. Hit and miss — the two outcomes

Look at the figure. Two paths leave the CPU. The short path (a hit) stays inside the fast notebook. The red long path (a miss) is forced to travel onward to the next level. Every access takes exactly one of these two paths. There is no third option — this is why hit and miss rates always add to 1 (we'll see that next).

5. Hit rate $h$ and miss rate $m$ — counting the outcomes

6. Hit time and miss penalty — the two costs

Definition Level-specific hit times, and

$T_{mem}$ Just like the rates, the generic hit time $T_{hit}$ gets a subscript to say which level:

$T_{L1}$ = hit time of L1 (the generic $T_{hit}$ specialized to L1) — e.g. 4 cycles.
$T_{L2}$ = hit time of L2 — e.g. 12 cycles. $T_{L3}$ = hit time of L3 — e.g. 40 cycles.
$T_{mem}$ = the time to fetch from main memory (DRAM) once every cache has missed — e.g. 100–200 cycles. Main memory is not a cache, so it has no hit/miss of its own; $T_{mem}$ is simply "the cost of the final, unavoidable warehouse trip."

Resolving $T_{miss}$ vs. $T_{mem}$ : $T_{miss}$ is the general idea "extra cost on a miss." In the single-level formula there is only one place to go on a miss — DRAM — so the miss penalty equals $T_{mem}$ . With more levels, a level's miss penalty is instead the average access time of the next level, and only the very last miss pays $T_{mem}$ .

7. Weighted average — the tool that ties it together

The parent note's central formula for a single-level cache is: $AMAT = T_{L1} + m_{L1} \cdot T_{mem}$

Read it with the symbols we just built: $T_{L1}$ is the L1 hit time (always paid), $m_{L1}$ is the L1 miss rate, and $T_{mem}$ is the DRAM fetch cost paid only on a miss.

Look at the bar in the figure. Every access pays the black base ( $T_{L1}$ ). Only the miss fraction stacks the red extra on top, and because it's a fraction, the red block is shrunk by $m$ . The height of the whole bar is the AMAT. Making $m$ small (a good cache) squashes the red block toward zero.

Recall Why can't we just add

$T_{L1} + T_{mem}$ ? Because that would assume every access goes to DRAM, which is false ::: only the miss fraction $m$ does, so we weight the DRAM cost by $m$ .

Multiplication and nesting

The formula uses two operations you already know:

Multiply ( $\cdot$ ): "how often" × "how much" = average cost of that penalty.
Nest (parentheses inside parentheses): the miss penalty of one level is itself an AMAT of the next level. Compute the innermost parentheses first, then work outward. That's why the parent solves the 3-level example inside-out: L3+mem gives 60, then L2 wraps it to 24, then L1 wraps it to 5.2.

8. Size vs. speed — why there are several notebooks

This size/speed tradeoff is why the hierarchy exists, and it's what the parent note's whole "Why Each Level Is Designed Differently" section explains.

9. The prerequisite map

Everything on this page flows downward into the parent topic. Related paths you'll meet later: what happens on a write (Write Policies), how the cache decides what to throw out (Cache Replacement Policies), keeping shared caches consistent (Cache Coherence), and address translation (TLB and Virtual Memory). How caches sit inside the instruction flow is CPU Pipeline.

Equipment checklist

Test yourself — you're ready for the parent note only if you can answer each without peeking.

What does the acronym AMAT stand for?

Average Memory Access Time — the typical cycles one memory access costs, averaged over all accesses.

What is a cycle and why do we count in cycles instead of seconds?

One tick of the CPU clock; cycles are independent of clock speed so designs compare fairly.

What is the difference between a hit and a miss?

A hit means the data is in this cache (fast); a miss means it isn't, so we go to the next slower level.

If the hit rate is

h = 0.90

, what is the miss rate

m

m = 1 - h = 0.10

What do the symbols

T_{L1}

and

T_{mem}

mean, and how do they relate to

T_{hit}

and

T_{miss}

T_{L1}

is the generic hit time

T_{hit}

specialized to L1;

T_{mem}

is the DRAM fetch cost, which equals the miss penalty

T_{miss}

in a single-level cache.

Why is the miss penalty multiplied by the miss rate in the AMAT formula?

Because we only pay the penalty on the fraction of accesses that miss; it's a weighted average of extra cost per access.

Does the miss penalty include the next level's access time?

Yes — it's the full time to fetch the data back, which contains the next level's own (possibly nested) access time.

Why can't one single cache be both huge and blazing-fast?

SRAM is expensive per bit (cost) and bigger caches have longer internal wires (physics), so size and speed trade off.

In the nested AMAT formula, which parentheses do you evaluate first?

The innermost — work inside-out (L3+mem first, then L2, then L1).