Fewer misses: size, blocks, ways, victims, prediction, prefetching and the compiler

One metric, three terms: what a knob really buys

Every technique in this lesson is judged by the formula of lesson 22, the first line under "Memory Hierarchy" on the example formula sheet of the course page:

The notes sort the ways to improve it into three families, one per term (p. 321): fewer misses (this lesson, pages 323–341), cheaper misses (lesson 26), faster hits (lesson 28). Most knobs here aim at one of the three C's of lesson 24: compulsory misses (the first touch of a block), capacity misses (the cache cannot hold the working set), conflict misses (too many busy blocks share one set).

Turning a knob lowers the miss rate and almost always pushes up another cost — the hit time, the penalty or the memory bandwidth. So the question is never "does it cut misses?" but "does it cut AMAT?".

A knob that lowers the miss rate pays only if the misses it saves, times the penalty, outweigh what it adds to the other terms.

The first knob: a bigger cache

A bigger cache holds more blocks, so fewer of them are thrown out and fetched again: it removes capacity misses (p. 323). It does nothing for compulsory misses — the first touch of a block misses in any cache — and the returns diminish: "doubling the cache size doesn't halve the miss rate" (p. 323). In the textbook's measurements a direct-mapped cache misses 9.8 % of its accesses at 4 KB and 4.2 % at 32 KB: eight times the capacity, the miss rate divided by 2.3.

The price is in the first term. A bigger array has longer wires, a bigger decoder and a bigger tag store, so the hit time grows, and so do area, power and cost (the table on p. 323). Every access pays the hit time, only the misses pay the penalty — so the L1 stays small and fast, one or two cycles at the processor's clock, and the capacity goes into the second and third levels, which "absorb the remaining misses" (p. 323).

Bigger blocks: fewer first touches, then a U-turn

Start with Example 9 of the notes (p. 324), taking a as 100 four-byte integers that begin at a block boundary:

for (i = 0; i < 100; i++)
    sum += a[i];

Every element is touched once, so every miss is compulsory, and the misses are simply the blocks the array spans: 25 with 16-byte blocks, 7 with 64-byte blocks. A bigger block preloads the neighbours of the word you asked for: spatial locality, turned into fewer misses.

Now hold the cache size fixed and keep growing the block. A 4 KB cache has 256 lines of 16 bytes, but only 16 lines of 256 bytes. With so few lines, blocks that are still needed are thrown out to make room: conflict and capacity misses rise, and the curve of miss rate against block size turns upward — the U-shaped curve of p. 325. Large blocks also carry bytes nobody uses, wasting bandwidth and energy when spatial locality is weak (the table on p. 324). In practice 16 to 64 bytes are common, and instruction caches, fetched in sequence, tolerate larger blocks than data caches (p. 325).

The penalty grows with the block, so AMAT turns earlier

A miss costs a fixed latency before the first bytes arrive, plus the transfer of the whole block. The textbook's model: 80 cycles, then 16 bytes every 2 cycles.

Put it next to the miss rates the textbook measured for a 4 KB cache, with a 1-cycle hit time:

That is fact one of the hook: from 32 to 64 bytes the miss rate drops by 0.24 points, but every remaining miss costs 4 cycles more. It is not an accident of these numbers — the optimum for AMAT can never lie to the right of the optimum for the miss rate:

1. Only two terms depend on the block size \(B\); the hit time does not:

   \[ \begin{aligned} \text{AMAT}(B) &= \text{HT} \\ &+ \text{MR}(B) \times \text{MP}(B) \end{aligned} \]

2. Call \(B^*\) the block with the lowest miss rate, and take any larger block \(B \gt B^*\). Its miss rate is not lower, by the choice of \(B^*\):

   \[ \text{MR}(B) \ge \text{MR}(B^*) \]

3. Its penalty is higher, because more bytes must travel:

   \[ \text{MP}(B) \gt \text{MP}(B^*) \]

4. Neither factor shrank and the penalty grew, so the product grew, and with it AMAT. No block larger than \(B^*\) beats \(B^*\): the AMAT optimum is \(B^*\) or smaller.

   \[ \text{AMAT}(B) \gt \text{AMAT}(B^*) \]

5. How much smaller depends on the memory: when the latency dominates, the penalty hardly grows with the block and the two optima meet; when the transfer dominates, small blocks win. Move that balance in the widget of the next section.

More ways: conflict misses out, hit time up

Example 10 (p. 327): a loop reads a[i], b[i] and c[i], and the three blocks map to the same set 5. In a direct-mapped cache each evicts the one read before it — three misses per iteration, while the rest of the cache may sit empty. In a 4-way set-associative cache (three ways would do) the three live in set 5 together and stop evicting each other.

Associativity is the number of places a block may occupy: 1 for direct-mapped, n for n-way, every line for fully associative (placement is lesson 23). Raising it removes conflict misses and nothing else: compulsory and capacity misses stay the same (p. 326), and a fully associative cache has, by definition, no conflict misses at all.

Two rules of thumb

The 2:1 cache rule (p. 327): a direct-mapped cache of size N has about the same miss rate as a 2-way set-associative cache of size N/2 — associativity can be traded for size. And the gain flattens fast. The textbook's 4 KB cache misses 9.8 % direct-mapped, 7.6 % 2-way, 7.1 % 4-way and 7.1 % 8-way: most of the gain comes with the first doubling — the notes' sweet spot is 2- or 4-way (p. 327) — and 8-way is, for practical purposes, as good as fully associative.

The price is paid at the multiplexer

A direct-mapped cache has one candidate line, so it can send the data towards the processor while the tag comparison is still running; if the comparison fails, the data is simply dropped. An n-way cache reads n candidates and compares n tags in parallel — but it can pick the data only after a comparator has said which way hit. That way-select multiplexer sits on the path of every hit, and reading n ways at once costs power on every access (the table on p. 327).

The textbook prices it as a slower clock: × 1.36 for 2-way, × 1.44 for 4-way, × 1.52 for 8-way, with a 25-cycle penalty. For a 4 KB cache the saved misses win: AMAT falls from 3.45 cycles direct-mapped to 3.22 at 4-way. For a 512 KB cache there are almost no conflicts left to remove, and the hit time wins: 1.20 cycles direct-mapped, 1.54 for 2-way — fact two of the hook.

Associativity on the cheap: a tray, a guess, a second address

Associativity removes conflict misses but slows every hit. Three tricks get most of the benefit without slowing the normal hit.

The victim cache: catch the block on its way out

Take an 8-line direct-mapped cache and a loop that alternates between blocks 5 and 13. Both map to line 5 (5 mod 8 = 13 mod 8 = 5), so each access throws out the block the next access needs — a ping-pong of conflict misses, with seven lines standing empty.

A victim cache (p. 328) is a small buffer of 4 to 16 entries, fully associative, placed between the cache and the next level. Every block evicted from the cache goes into it. On a miss the cache looks there: if the block is found, the two are swapped — the requested block returns to its line, the block it displaces takes its seat in the tray; if not, the block comes from the next level as usual (the flow on p. 329).

Two choices carry the idea. The tray is fully associative because its job is to hold blocks whose index collided: indexed the same way, they would collide again. And it is consulted only after a miss, so the hit path of the cache does not change — "No Change to Main Cache Hit Time" (p. 328).

Way prediction: knock on one door first

The notes' analogy (p. 332) is a hotel: floors are sets, rooms are ways. Without way prediction, staff knock on every door of the floor at once — quick, but noisy and costly. With it, the receptionist's notebook says where the guest was last time, and you knock there first.

The notebook is the way predictor table (WPT, p. 330): indexed by the set index, one entry per set, holding the way of the last hit (or of the last fill) — \(\lceil \log_2 n \rceil\) bits per entry. A 4-way cache with 1024 sets needs 1024 × 2 = 2048 bits, 256 bytes (p. 331). An access reads the predicted way only. If its tag matches, it is a correct-prediction hit in 1 cycle; if not, the other n − 1 ways are checked: found there, it is a misprediction-hit one cycle later; found nowhere, it is a miss. Example 11 of the notes (pp. 331–332), set 12 of a 4-way cache:

The pay-off: most hits are as fast and as cheap as in a direct-mapped cache, with the miss rate of the set-associative one. With prediction accuracy \(p\) and \(t_m\) extra cycles per wrong guess:

The notes quote 80–95 % accuracy (p. 332); at 90 % with one extra cycle, a 1-cycle hit becomes 1.1 cycles on average. What way prediction does not do is remove a miss: it changes how a hit is found, not what the cache holds. The notes' own p. 334 says so — it "reduces hit time", the family of lesson 28.

Pseudo-associativity: a second chance for a direct-mapped cache

A pseudo-associative (column-associative) cache stays direct-mapped but gives every block a second possible line, typically the index with its most significant bit flipped (p. 333). An access checks the primary line first — a hit there takes 1 cycle; then the secondary line — a hit there is a slow hit, one cycle more; then it is a miss. Take blocks 5 and 13 of the ping-pong above: both have line 5 as first choice and line 1 as second, so one can sit in each line instead of throwing the other out. Lines 1 and 5 together behave like one 2-way set, and most conflict misses disappear with little hardware (p. 334).

The price is a hit time with two values, which the pipeline must be able to absorb. Not in the notes, but standard: after a slow hit the two blocks are usually swapped, so that the block in use sits in the fast place next time. Memorise the notes' "Key Difference" box (p. 334): way prediction works on set-associative caches and cuts the hit time; pseudo-associativity works on direct-mapped caches and cuts conflict misses.

Fetching before the miss: stream buffers and prefetch instructions

Size, ways and trays leave one kind of miss untouched: the compulsory one. A block that has never been touched is nowhere above memory. The only way around it is to fetch the block before it is asked for, overlapping the fetch with useful work (p. 335).

In hardware: the stream buffer

Instructions run mostly in sequence, which makes instruction prefetching simple: on an instruction-cache miss, fetch the requested block into the cache and the next sequential block into an instruction stream buffer; when the next fetch hits in the buffer, that block moves into the cache and the one after it is requested (pp. 335–336). The notes' Example 13, the Alpha AXP 21064, is the textbook's case of exactly this.

Data prefetching works the same way for sequential or strided streams such as A[0], A[1], A[2] … (p. 336), with a D-stream buffer beside the cache (Fig. 3).

Why a separate buffer, and not straight into the cache? Because a guess can be wrong: a prefetched block that is never used would have evicted a useful one — cache pollution (p. 337). In the notes' picture, the waiter puts the next dish on a side tray; if nobody wants it, it goes back without touching your plate. What remains is the bandwidth spent on wrong guesses, and the need for a prefetch to arrive in time.

In software: the compiler issues the fetch

A hardware prefetcher sees only past addresses; the compiler sees the loop. It can insert prefetch instructions ahead of the use (p. 338): a register prefetch is a normal load done early (the notes cite HP PA-RISC), a cache prefetch an instruction that only brings the block into the cache (MIPS IV, PowerPC, SPARC v9). Example 15 prefetches eight elements ahead:

for (i = 0; i < N; i++) {
    __prefetch(&A[i+8]);  // 8 ahead
    sum += A[i];
}

The same loop in the papers' mnemonics, with 8-byte elements, so that eight elements ahead is 64 bytes. PREF stands for a cache-prefetch instruction (MIPS IV has one under that name; the papers have none):

LOOP: PREF  64(R1)       ; block of A[i+8]: cache only
      LD    F2, 0(R1)    ; F2 = A[i]
      FADD  F0, F0, F2   ; sum += A[i]
      ADDUI R1, R1, 8
      BNE   R1, R2, LOOP

Two conditions, not in the notes, make the idea work. The prefetch must be non-faulting: in the last iterations A[i+8] runs past the end of the array, and a prefetch to a bad address must quietly do nothing instead of raising an exception. And the cache must be non-blocking — able to keep serving the loop's loads while the prefetched block is on its way (lesson 26); a cache that stalls on a prefetch gains nothing.

The hard part is the prefetch distance (p. 339): too close, and the block arrives after the load that needed it — the penalty is still paid; too far, and it may be evicted before use. The usual rule: prefetch as many iterations ahead as one miss lasts,

— with a 100-cycle miss and a 12-cycle iteration, 9 iterations ahead. The costs (p. 339): issue slots for the extra instructions, less of a problem on a superscalar; bandwidth for blocks never used; and in Example 15 plain redundancy — with eight elements per 64-byte block, seven prefetches in eight ask for a block already requested, so a compiler unrolls the loop by eight and issues one per block (unrolling is lesson 15).

The compiler reorders the accesses

The last knob moves no hardware at all. The compiler rearranges the data or the loops so that the program's order of accesses fits the cache — related data together for spatial locality, reused data reused soon for temporal locality (p. 340). Four transformations.

Merging arrays

int val[SIZE];
int key[SIZE];

struct {
    int val;
    int key;
} merged_array[SIZE];

If val[i] and key[i] are always used together, two arrays keep them in two different blocks — a visit to some i can cost two misses — and two arrays of the same size can even map onto the same sets and evict each other. Merged into one array of structures, both fields sit in the same block (p. 340): one miss serves the pair, and the conflict between the arrays is gone.

Loop interchange

for (j = 0; j < 100; j++)
  for (i = 0; i < 5000; i++)
    x[i][j] = 2 * x[i][j];

for (i = 0; i < 5000; i++)
  for (j = 0; j < 100; j++)
    x[i][j] = 2 * x[i][j];

C stores arrays row by row: x[i][j] and x[i][j+1] are neighbours, while x[i][j] and x[i+1][j] are 100 words apart. The "before" loop walks down a column. With 4-byte words and 64-byte blocks, every access lands in a new block, and the loop comes back to that block only after visiting the other 4999 rows — 320 KB of blocks later. In a smaller cache the block is gone by then, and every one of the 500 000 elements misses. Interchanged, the loop walks along the rows and uses all 16 words of a block before moving on: 31 250 misses, sixteen times fewer — fact three of the hook. In Fortran, which stores arrays column by column, the good order is the other one; and the swap is legal only if no dependence between iterations forbids it.

Loop fusion

for (i = 0; i < N; i++)
  A[i] = B[i] + 1;
for (i = 0; i < N; i++)
  C[i] = A[i] * 2;

for (i = 0; i < N; i++) {
  A[i] = B[i] + 1;
  C[i] = A[i] * 2;
}

The first loop writes all of A; when A is larger than the cache, the second loop finds A[0] long evicted and misses on it again. Fused, each A[i] is used right after it was written, while still in the cache — temporal locality (p. 341). The cost is a longer loop body that needs more registers.

Blocking

In x = y × z with N × N matrices, every element of z is used N times — once for each row of y. Blocking computes on B × B sub-matrices, so that a tile of z is reused while it is still in the cache. The textbook's version, with the blocking factor B:

for (jj = 0; jj < N; jj += B)
  for (kk = 0; kk < N; kk += B)
    for (i = 0; i < N; i++)
      for (j = jj; j < min(jj+B, N); j++) {
        r = 0;
        for (k = kk; k < min(kk+B, N); k++)
          r = r + y[i][k] * z[k][j];
        x[i][j] = x[i][j] + r;
      }

The arithmetic is the same N³ multiply-adds; what changes is how many words travel from memory:

1. Unblocked, in the worst case — the cache keeps neither a row of y nor a column of z between uses — each of the N² results reads a row of y and a column of z and writes one word of x:

   \[ N^2 \cdot 2N + N^2 = 2N^3 + N^2 \]

2. Blocked: for one pair (jj, kk) the B × B tile of z is loaded once and then used by all N rows i. There are (N/B)² pairs:

   \[ \left(\frac{N}{B}\right)^{2} B^2 = N^2 \]

3. For each pair and each row i, a strip of B words of y is loaded and reused for the B values of j; x likewise, read and written:

   \[ \left(\frac{N}{B}\right)^{2} N \cdot B = \frac{N^3}{B} \]

4. Add z, y and x: about B times fewer words, as long as the tile and its two strips fit in the cache — about B² + 2B words:

   \[ \frac{2N^3}{B} + N^2 \]

The eight knobs side by side

Back to the three facts

Fact one: 64-byte blocks miss less, but each miss costs 4 cycles more — 7.00 % × 88 = 6.16 cycles of misses per access against 7.24 % × 84 = 6.08. Fact two: the 2-way 512 KB cache saves 0.1 % × 25 = 0.025 cycles of misses per access and adds 0.36 cycles to every hit. Fact three: same cache, same 500 000 elements, but each 64-byte block now serves 16 of them instead of one.

The metric is AMAT, not the miss rate: the plain hardware knobs cut misses but push up another term, and the compiler cuts misses by changing only the order of the accesses.