---
title: Cache Performance and Cache-Friendly Code
module: The Memory Hierarchy
moduleNumber: 6
lessonNumber: 5
order: 605
summary: >
  Turn the cache mechanism into a number. Hit time, miss rate, and miss penalty
  combine into the average memory access time; we compute AMAT for a two-level
  hierarchy with real numbers, weigh the design knobs against each other, and read
  the memory mountain. Then we write cache-friendly code — the matrix-multiply
  loop-order case study (ijk versus kij, misses counted per iteration) and loop
  blocking, where cache-sized tiles turn evicted reuse back into hits.
topics: [The Memory Hierarchy]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §6 The Memory Hierarchy"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §7–9 The Memory Hierarchy / The Cache / Main Memory"
---

We have a cache that exploits [locality](/computer-architecture/memory-hierarchy/locality)
through [set-associative placement and write policies](/computer-architecture/memory-hierarchy/set-associative-and-write-policies).
What we lack is a way to **measure** it: to say whether one cache, or one program,
is faster than another. This final lesson reduces cache behavior to a single number,
the average memory access time, shows how that number deteriorates as a program's
access pattern degrades, and then returns to the module's opening question: writing
code with locality the cache can exploit.

## The three numbers and AMAT

Cache performance rests on three quantities, measured against a stream of references.

> **Definition (Miss rate, hit time, miss penalty).** The **miss rate** is the
> fraction of references that miss (its complement is the **hit rate**). The **hit
> time** is the time to deliver a word that is in the cache — set selection, tag
> compare, byte select — typically a few cycles. The **miss penalty** is the
> _additional_ time a miss costs beyond a hit: fetching the block from the next level
> down.

They combine into one figure of merit, the **average memory access time**, by
weighting the penalty by how often it is actually paid:

$$
\text{AMAT} = \text{hit time} + \text{miss rate} \times \text{miss penalty}.
$$

The formula carries the whole intuition of the hierarchy. Because the **miss penalty**
is enormous (DRAM is roughly two orders of magnitude slower than an L1 hit), even a
small miss rate dominates the average. A cache with a 1 ns hit time, a 3 % miss rate,
and a 100 ns miss penalty has $\text{AMAT} = 1 + 0.03 \times 100 = 4$ ns: the misses,
though rare, contribute three-quarters of the time. This is why shaving the miss rate
matters far more than shaving the hit time, and why **the few misses you do take are
the thing to attack.**

$$
% caption: AMAT as a stacked quantity for hit time 1 ns, miss rate 3%, penalty 100 ns.
% caption: The hit time is paid on every access; the miss-rate-weighted penalty stacks
% caption: on top. Even a small miss rate adds a large slice because the penalty is so
% caption: large.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % hit time slice
  \fill[acc!8] (0.8,0) rectangle (2.2,1.0);
  \draw (0.8,0) rectangle (2.2,1.0);
  \node[anchor=west] at (2.4,0.5) {hit time = 1 ns};
  % miss penalty slice stacked above
  \fill[acc!25] (0.8,1.0) rectangle (2.2,4.0);
  \draw (0.8,1.0) rectangle (2.2,4.0);
  \node[anchor=west] at (2.4,2.5) {miss part: 0.03 x 100 = 3 ns};
  % total bracket at the left, label clear of the arrow
  \draw[<->] (0.45,0) -- (0.45,4.0);
  \node[anchor=east,text=acc,align=right] at (0.1,2.0) {AMAT\\4 ns};
\end{tikzpicture}
$$

A corollary: **small changes in hit rate are large changes in
speed.** With a 1-cycle hit and a 100-cycle penalty, a 97 % hit rate gives
$\text{AMAT} = 1 + 0.03 \times 100 = 4$ cycles while a 99 % hit rate gives
$1 + 0.01 \times 100 = 2$. Two percentage points of hit rate double the memory
performance, so 99 % and 97 % hit rates describe machines of very different speed.

The arithmetic is unforgiving because AMAT is a weighted average of two
numbers that differ by two orders of magnitude, and the weight on the large one is
the miss rate. Halving the miss rate (3 % to 1.5 %) does far more than halving the
hit time (1 cycle to 0.5), because the penalty is a hundred times the hit time.
Every optimization in this lesson therefore aims at making misses **rarer**, not
hits faster — the hardware already handles the latter.

## Two levels: AMAT composes

Real hierarchies have several cache levels, and the formula nests naturally: the
miss penalty of one level _is_ the AMAT of the level below it. Work one example.
L1 hits in 1 ns and misses 5 % of the time; L2 hits in 10 ns (beyond the L1 probe)
and misses 25 % of _its_ accesses; a DRAM access costs 100 ns beyond that.

$$
\text{AMAT} = 1 + 0.05 \times \bigl(10 + 0.25 \times 100\bigr)
            = 1 + 0.05 \times 35 = 2.75\ \text{ns}.
$$

Without the L2, the same L1 would give $1 + 0.05 \times 100 = 6$ ns: the middle
level more than halves the average, not by making hits faster but by making
**misses cheaper**. That is the design logic of the whole pyramid: each level
exists to shrink the penalty of the level above.

$$
% caption: The two-level AMAT as an expected value over access outcomes. Each edge
% caption: carries a probability, each leaf a total latency; the products sum to
% caption: 0.95 + 0.41 + 1.39 = 2.75 ns. The rare DRAM leaf still contributes half
% caption: the total, which is why the deep misses are the ones to attack.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  ev/.style={draw, minimum width=17mm, minimum height=7mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[ev, fill=acc!8] (root) at (0,0) {access};
  \node[ev] (l1h) at (3.6,1.2) {L1 hit: 1 ns};
  \node[ev] (l1m) at (3.6,-1.2) {L1 miss};
  \node[ev] (l2h) at (7.4,-0.2) {L2 hit: 11 ns};
  \node[ev] (l2m) at (7.4,-2.2) {DRAM: 111 ns};
  \draw[->] (root.east) -- (l1h.west) node[midway,above,black] {0.95};
  \draw[->] (root.east) -- (l1m.west) node[midway,below,black] {0.05};
  \draw[->] (l1m.east) -- (l2h.west) node[midway,above,black] {0.75};
  \draw[->] (l1m.east) -- (l2m.west) node[midway,below,black] {0.25};
  \node[anchor=west,text=acc] at (9.2,-0.2) {0.41 ns expected};
  \node[anchor=west,text=acc] at (9.2,-2.2) {1.39 ns expected};
  \node[anchor=west,text=acc] at (5.5,1.2) {0.95 ns expected};
\end{tikzpicture}
$$

(The leaf latencies are cumulative: an L2 hit pays the L1 probe plus the L2
access, $1 + 10 = 11$ ns; a DRAM access pays all three, $111$ ns. Weighting each
leaf by its path probability and summing gives $0.95 \times 1 + 0.0375 \times 11 +
0.0125 \times 111 = 2.75$ ns.)

## The knobs, and what they cost

A cache designer controls the three AMAT terms through the geometry of the
[last two lessons](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped),
and every knob that improves one term leans on another:

- **Bigger cache ($C$).** Lower miss rate (more of the working set fits), but a
  larger SRAM array is slower to search, so the hit time creeps up. This is why L1
  stays small and fast while L2 and L3 grow large and slower.
- **Bigger blocks ($B$).** Better spatial locality per miss, but for fixed $C$
  fewer lines, so more conflict and capacity evictions; and each miss now moves
  more data, raising the penalty. Block sizes settle in the middle: 32–64 bytes.
- **More ways ($E$).** Fewer conflict misses, but more comparators and muxing in
  the hit path: the hit time rises with associativity, which is why L1 caches are
  moderately associative rather than fully.
- **Cheaper misses.** Add a level below (the two-level computation above), or
  overlap the miss with useful work, which is the pipeline's
  [stall game](/computer-architecture/pipelining/data-hazards-stalling-and-forwarding)
  played against memory.

The programmer controls none of these. What the programmer controls is the **miss
rate term of their own program**, the access pattern, and that is where the rest
of the lesson lives.

## The memory mountain

AMAT treats the miss rate as given, but the miss rate is not a constant: it depends
on the program's access pattern, and that pattern has two knobs: the **size** of the
data being swept (the working set, which decides _which level_ of the hierarchy holds
it) and the **stride** of the sweep (which decides how much of each fetched block is
used). Plotting read throughput against both knobs produces the **memory mountain**: a
surface high where data fits a fast level and is read stride-1, falling away into a
slow plain as the working set spills to a lower level and the stride grows.

$$
% caption: The memory mountain, schematically. Throughput is highest at small working
% caption: sets and stride 1 (data in L1, every block fully used) and falls off as the
% caption: working set spills to slower levels and as the stride wastes more of each
% caption: block. Labels sit beside the axes, off the surface.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % two axes in a faux-3D base
  \draw[->] (0,0) -- (5.4,0) node[anchor=north] {stride (1 $\to$ large)};
  \draw[->] (0,0) -- (-2.4,1.8) node[anchor=south east] {working set (small $\to$ large)};
  \draw[->] (0,0) -- (0,4.4) node[anchor=south east] {read throughput};
  % a high ridge near the origin (small set, stride 1) sloping down
  \draw[acc,very thick] (0.2,3.9) .. controls (1.8,3.2) and (3.2,1.4) .. (5.0,0.8);
  \draw[black,very thick] (-0.9,2.6) .. controls (0.6,2.1) and (2.4,1.0) .. (4.2,0.55);
  \draw[black,very thick] (-1.7,1.6) .. controls (-0.4,1.3) and (1.4,0.7) .. (3.2,0.4);
  % label the peak and the plain, off the curves
  \node[anchor=south west,text=acc] at (0.2,3.9) {peak: L1, stride 1};
  \node[anchor=west] at (3.4,0.4) {slow plain};
\end{tikzpicture}
$$

Read the mountain along each axis separately. Fix stride 1 and grow the working
set: throughput descends a staircase of **plateaus**, one per level. A sweep that
fits in L1 might stream at 12 GB/s; spill into L2 and it settles around 5; spill
into L3, 2–3; spill into DRAM and it flattens below 1. The cliff edges _are_ the
cache capacities — you can read a machine's cache sizes off its mountain. Now fix
a DRAM-sized working set and grow the stride: throughput slides downhill as each
fetched block contributes fewer useful words, bottoming out when stride reaches
the block size and every reference misses — the $\min(1, kw/B)$ law from the
[locality lesson](/computer-architecture/memory-hierarchy/locality), drawn as
terrain. The mountain is the whole module in one picture: ascend it by shrinking
the working set (temporal locality) and by shrinking the stride (spatial
locality). Both are things the programmer controls.

For a numeric traverse of the mountain, fix
stride 1 and read throughput as the working set grows past each level's capacity
(the figures below are representative of a desktop core, not a specific chip):

| Working set | Resident level | Read throughput | Effective AMAT |
| --- | --- | --- | --- |
| 16 KB | L1 (32 KB) | ~14 GB/s | ~1 ns |
| 256 KB | L2 (512 KB) | ~7 GB/s | ~2 ns |
| 4 MB | L3 (8 MB) | ~4 GB/s | ~4 ns |
| 64 MB | DRAM | ~2 GB/s | ~8 ns |

Each row-to-row drop is a cache capacity being exceeded — the working set spilled
out of one level into the next, slower one, and the miss rate for that level jumped
from near zero to near one. The throughput does not decay smoothly; it steps, and
the step edges sit exactly at 32 KB, 512 KB, and 8 MB, which is why a mountain
measured on real silicon _reports the cache sizes_. Notice the throughput never
falls as far as the raw latency ratio would suggest (DRAM's ~8 ns AMAT is 8x L1's,
but the bandwidth only falls ~7x): the hardware prefetcher of the
[locality lesson](/computer-architecture/memory-hierarchy/locality) is running ahead
of the stride-1 sweep, hiding much of the DRAM latency behind streamed blocks. That
prefetch help evaporates the moment the stride goes irregular — the mountain's other
slope.

## Cache-friendly code: stride-1

The first rule follows directly from spatial locality and the row-major layout: make
the **innermost loop stride-1**. We saw this in the locality lesson; here is the
payoff stated as a rule. When a cache miss brings in a block of, say, sixteen `int`s,
a stride-1 inner loop uses all sixteen before triggering the next miss, so the miss
rate is roughly $1/16$. A stride-16 inner loop uses one `int` per block and misses on
nearly every access. Same data, same instruction count, a 16x difference in misses.

## Case study: loop order in matrix multiply

Matrix multiplication is the classic example, because its triple loop can be
permuted six ways that all compute the same $C = AB$, with wildly different miss
counts. Take $N \times N$ matrices of `double`s (8 bytes) and 32-byte blocks, so a
block holds **four** doubles. The natural **ijk** order:

```c [matmul_ijk.c]
/* ijk: inner loop k sweeps a row of A (stride-1) and a column of B (stride-N). */
void matmul_ijk(double A[N][N], double B[N][N], double C[N][N]) {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      double sum = 0.0;
      for (int k = 0; k < N; k++)
        sum += A[i][k] * B[k][j];
      C[i][j] = sum;
    }
}
```

Count the memory behavior **per innermost iteration**, assuming the matrices are
much larger than the cache. `A[i][k]` walks a row: stride-1, one miss per four
iterations, $0.25$ misses. `B[k][j]` walks a **column**: stride-$N$, a different
block every iteration, $1.0$ misses. `sum` lives in a register: $0$. Total:
**1.25 misses per iteration**. Now permute to **kij**, hoisting `A[i][k]` into a
scalar:

```c [matmul_kij.c]
/* kij: r = A[i][k] is loop-invariant; inner loop j streams rows of B and C. */
void matmul_kij(double A[N][N], double B[N][N], double C[N][N]) {
  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++) {
      double r = A[i][k];
      for (int j = 0; j < N; j++)
        C[i][j] += r * B[k][j];
    }
}
```

Per inner iteration: `r` is a register, $0$ misses. `B[k][j]` walks a row:
stride-1, $0.25$. `C[i][j]` walks a row: stride-1, $0.25$ (it is both loaded and
stored, but the block is resident after the first touch). Total: **0.5 misses per
iteration**: a 2.5x reduction, even though kij executes _more_ memory operations
per iteration (an extra store to `C`). The third family, **jki**, is the worst
case: its inner loop walks columns of both `A` and `C` for $2.0$ misses per
iteration, four times worse than kij.

| Order (inner loop) | Loads | Stores | A misses | B misses | C misses | Total / iter |
| --- | --- | --- | --- | --- | --- | --- |
| ijk (k) | 2 | 0 | 0.25 | 1.00 | 0.00 | 1.25 |
| jki (i) | 2 | 1 | 1.00 | 0.00 | 1.00 | 2.00 |
| kij (j) | 2 | 1 | 0.00 | 0.25 | 0.25 | 0.50 |

$$
% caption: What the innermost loop touches, per order. In ijk (left), each iteration
% caption: walks a row of A (stride-1, cheap) against a column of B (stride-N, one
% caption: miss per step) while C stays f\/ixed in a register. In kij (right), A is
% caption: f\/ixed and the loop streams rows of B and C, all stride-1: 0.5 misses per
% caption: iteration versus 1.25.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % ---- ijk panel ----
  \node[text=acc] at (2.7,2.5) {ijk: 1.25 misses/iter};
  \foreach \m/\x in {A/0, B/2.0, C/4.0} {
    \draw (\x,0) rectangle ++(1.4,1.4);
    \foreach \g in {0.35,0.7,1.05} {
      \draw[black] (\x+\g,0) -- (\x+\g,1.4);
      \draw[black] (\x,\g) -- (\x+1.4,\g);
    }
    \node[anchor=south] at (\x+0.7,1.5) {\m};
  }
  % A: row sweep
  \fill[acc!12] (0,0.7) rectangle (1.4,1.05);
  \draw[->,acc,thick] (0.08,0.875) -- (1.32,0.875);
  \node[anchor=north,black] at (0.7,-0.12) {0.25};
  % B: column sweep
  \fill[acc!12] (2.7,0) rectangle (3.05,1.4);
  \draw[->,acc,thick] (2.875,1.32) -- (2.875,0.08);
  \node[anchor=north,black] at (2.7,-0.12) {1.00};
  % C: f\/ixed element
  \fill[acc] (4.7,0.7) circle (2.4pt);
  \node[anchor=north,black] at (4.7,-0.12) {0.00};
  % ---- kij panel ----
  \begin{scope}[xshift=7.4cm]
    \node[text=acc] at (2.7,2.5) {kij: 0.50 misses/iter};
    \foreach \m/\x in {A/0, B/2.0, C/4.0} {
      \draw (\x,0) rectangle ++(1.4,1.4);
      \foreach \g in {0.35,0.7,1.05} {
        \draw[black] (\x+\g,0) -- (\x+\g,1.4);
        \draw[black] (\x,\g) -- (\x+1.4,\g);
      }
      \node[anchor=south] at (\x+0.7,1.5) {\m};
    }
    % A: f\/ixed element
    \fill[acc] (0.7,0.7) circle (2.4pt);
    \node[anchor=north,black] at (0.7,-0.12) {0.00};
    % B: row sweep
    \fill[acc!12] (2.0,0.7) rectangle (3.4,1.05);
    \draw[->,acc,thick] (2.08,0.875) -- (3.32,0.875);
    \node[anchor=north,black] at (2.7,-0.12) {0.25};
    % C: row sweep
    \fill[acc!12] (4.0,0.7) rectangle (5.4,1.05);
    \draw[->,acc,thick] (4.08,0.875) -- (5.32,0.875);
    \node[anchor=north,black] at (4.7,-0.12) {0.25};
  \end{scope}
\end{tikzpicture}
$$

The same point again: all six orders run $2N^3$ floating-point
operations; only the **order of memory touches** differs, and on large matrices
kij outruns jki by roughly the ratio of their miss counts. Checking the loop order
of a hot kernel is minutes of work for integer-factor speedups.

## Cache-friendly code: blocking

Stride-1 fixes spatial locality, but some computations reuse data so heavily that the
working set, not the stride, is the problem. Matrix multiply is again the case in
point: the trouble is reuse across the whole matrix. By the time the loops come back
to a row of `A` or a column of `B`, it has long since been evicted, because between
two uses the loop streamed an entire $N \times N$ matrix through the cache: capacity
misses, in the vocabulary of the
[direct-mapped lesson](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped).
When `N` is large enough that a row plus a column no longer fits, **every** reuse is
a miss.

**Blocking** (also called **tiling**) restructures the computation to reuse data
while it is still resident. Instead of computing whole rows and columns, it carves the
matrices into small $\text{BLK} \times \text{BLK}$ **tiles** sized so that the tiles
in flight fit in the cache, and multiplies tile by tile. Within a tile-pair, every
loaded block is reused $\text{BLK}$ times before the tile moves on, so the misses are
amortized.

```c [matmul_blocked.c]
/* Blocked C = A * B with BLK x BLK tiles sized to fit in cache. */
void matmul_blocked(double A[N][N], double B[N][N], double C[N][N]) {
  for (int ii = 0; ii < N; ii += BLK)
    for (int jj = 0; jj < N; jj += BLK)
      for (int kk = 0; kk < N; kk += BLK)
        /* multiply one BLK x BLK tile of A by one of B into C */
        for (int i = ii; i < ii + BLK; i++)
          for (int j = jj; j < jj + BLK; j++) {
            double sum = C[i][j];
            for (int k = kk; k < kk + BLK; k++)
              sum += A[i][k] * B[k][j];
            C[i][j] = sum;
          }
}
```

The working-set argument fixes the tile size: the inner three loops touch one tile
of each matrix, $3 \cdot \text{BLK}^2 \cdot 8$ bytes of doubles, and that must fit
comfortably in the cache being targeted. For a 32 KB L1, $3 \cdot \text{BLK}^2
\cdot 8 \le 32768$ gives $\text{BLK} \le 36$, so tiles of 32 fit with room to
spare, and every element loaded into the cache is used $\text{BLK} = 32$ times
before eviction instead of once.

$$
% caption: Unblocked versus blocked matrix multiply. Unblocked (left) streams a whole
% caption: row of A and a whole column of B per output element — no reuse once the
% caption: working set exceeds the cache. Blocked (right) works on a tile that f\/its
% caption: in cache and sweeps it across the matrix, reusing each loaded block BLK
% caption: times.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % left matrix: a row and column highlighted
  \draw (0,0) rectangle (2.4,2.4);
  \foreach \x in {0.4,0.8,1.2,1.6,2.0} \draw[black] (\x,0) -- (\x,2.4);
  \foreach \y in {0.4,0.8,1.2,1.6,2.0} \draw[black] (0,\y) -- (2.4,\y);
  \fill[acc!12] (0,1.6) rectangle (2.4,2.0);   % a row
  \fill[acc!12] (1.2,0) rectangle (1.6,2.4);   % a column
  \node[anchor=north] at (1.2,-0.2) {unblocked: full row and column};
  % right matrix: a tile highlighted, with a sweep arrow
  \begin{scope}[xshift=5.6cm]
    \draw (0,0) rectangle (2.4,2.4);
    \foreach \x in {0.4,0.8,1.2,1.6,2.0} \draw[black] (\x,0) -- (\x,2.4);
    \foreach \y in {0.4,0.8,1.2,1.6,2.0} \draw[black] (0,\y) -- (2.4,\y);
    \fill[acc!18] (0,1.6) rectangle (0.8,2.4);   % a tile
    \draw[->,acc,thick] (0.4,2.0) -- (1.9,2.0);  % sweep right
    \draw[->,acc,thick] (0.4,2.0) -- (0.4,0.5);  % sweep down
    \node[anchor=north] at (1.2,-0.2) {blocked: tile sweeps the matrix};
  \end{scope}
\end{tikzpicture}
$$

Blocking does not change the arithmetic — the same $N^3$ multiply-adds run — but it
changes the **order**, and order determines the miss count. On large matrices it
turns a near-100 % miss rate back into something close to the tiny stride-1 rate, and
the speedup is often several-fold. Production linear-algebra libraries are blocked
for every level of the hierarchy at once, registers included.

## The miss you cannot avoid, and the tile you need not tune

AMAT and blocking are the classical account. Two developments refine it — one in
hardware that changes what a "miss penalty" even means, one in algorithms that
removes the tile-tuning the blocked kernel above still requires.

**Non-blocking caches make misses overlap.** The AMAT formula assumes a miss stalls
the processor for the full penalty. Modern cores do not stall: a **non-blocking**
(lockup-free) cache, using miss-status holding registers (MSHRs), keeps serving hits
and launching _further_ misses while an earlier miss is outstanding (Kroft,
"Lockup-free instruction fetch/prefetch cache organization," ISCA 1981).[^kroft] The
consequence for code is **memory-level parallelism**: if several independent misses
are in flight at once, their penalties overlap, and the effective cost is far below
the sum. This reframes the programmer's job — it is not only about _fewer_ misses but
about misses that can proceed _in parallel_, which is why a scatter of independent
loads can outrun a dependent chain that misses the same number of times. The AMAT
number becomes a ceiling that overlap sits below, not an exact prediction.

**Cache-oblivious algorithms block without knowing the cache.** The blocked matrix
multiply needed a tile size $\text{BLK}$ tuned to a specific cache — recompile for a
new machine, retune. **Cache-oblivious** algorithms reach near-optimal miss counts at
_every_ level of the hierarchy at once, with no cache parameters in the code, by
dividing the problem recursively until the subproblems are small enough to fit
whatever cache they happen to land in (Frigo, Leiserson, Prokop & Ramachandran,
"Cache-oblivious algorithms," FOCS 1999).[^cacheob] Recursive matrix multiply, for
instance, halves the matrices until a subproblem fits — and since the recursion
passes through _every_ size on the way down, it is automatically blocked for L1, L2,
L3, and registers simultaneously, with a single portable implementation. It is the
theoretical endpoint of this lesson's advice: locality engineered into the algorithm's
structure rather than tuned into its constants.

> **Takeaway.** Reduce cache behavior to $\text{AMAT} = \text{hit time} +
> \text{miss rate} \times \text{miss penalty}$; because the penalty is huge, small
> hit-rate changes are large speed changes (97 % vs 99 % hits is 4 vs 2 cycles), and
> levels compose — an L2 turns a 6 ns average into 2.75 ns by cheapening misses.
> The **memory mountain** maps throughput against working-set size (plateaus at each
> level) and stride (the block-waste slope). Climb it in code: keep the innermost
> loop **stride-1**, pick the loop order that streams rows (kij's 0.5 misses per
> iteration versus ijk's 1.25), and **block** reuse-heavy kernels into cache-sized
> tiles. The arithmetic never changes; only the access order — the thing that
> sets the cost — does.

This closes the Memory Hierarchy module. From the [latency gap](/computer-architecture/memory-hierarchy/storage-technologies-and-the-latency-gap)
that motivates a hierarchy, through the [locality](/computer-architecture/memory-hierarchy/locality)
that makes one work, to the [cache organization](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped)
that implements it — the payoff is code, and hardware, that keep the working set near
the top of the pyramid.

[^kroft]: **D. Kroft**, "Lockup-free instruction fetch/prefetch cache organization," _ISCA_ 1981 — introduces miss-status holding registers so a cache keeps serving accesses while misses are outstanding, enabling memory-level parallelism.
[^cacheob]: **M. Frigo, C. E. Leiserson, H. Prokop, S. Ramachandran**, "Cache-oblivious algorithms," _FOCS_ 1999 — recursive algorithms that achieve near-optimal cache performance at every level of the hierarchy without knowing any cache parameters.