Hit time is the critical path: small L1, pipelined writes, and the nineteen-technique scorecard

The one term that every access pays

Lesson 22 showed that every access pays the hit time, a miss included: the cache must be looked up before it knows that it missed (p. 303). Put a number on it with the L1 of the notes' Example 16 from lesson 26: 5 % misses, each costing 20 cycles on average behind the L2. With a 1-cycle hit, AMAT = 1 + 0.05 × 20 = 2 cycles. Add one cycle to the hit and AMAT becomes 3. To lose as much through the misses, the miss rate would have to double, to 10 %.

Now the hardware. In the five-stage pipeline of your first course, IF reads the instruction cache on every cycle and ME reads the data cache for every load and store, each in one clock cycle. The L1 sits on the critical path: the slowest stage sets the clock period \(T_{CLK}\). Suppose every stage needs 1 ns except the access to the L1 data cache, which needs 1.25 ns, and take the load-use pair of lesson 2:

I0   LD   R2, 0(R1)
I1   ADD  R3, R2, R4     # needs R2

The designer has two choices (Fig. 1). Stretch the clock: \(T_{CLK}\) = 1.25 ns, so \(f_{CLK}\) falls from 1 GHz to 800 MHz and every instruction runs 25 % slower, also the ones that never touch memory. In CPU time = IC × CPI × \(T_{CLK}\) the last factor grows. Or add a stage: the access is spread over two cycles, M1 and M2, and the clock stays at 1 GHz. The loaded value now arrives a cycle later, so the load-use pair stalls twice instead of once: CPI grows. Split the instruction cache in IF the same way and every mispredicted branch costs one more cycle too, because the branch is resolved one stage further from the fetch.

Either way the L1's access time ends up in the CPU time, cycle after cycle. The notes open the hit-time techniques with exactly this point, a hit "still lies on the critical path of every memory access" (p. 356), but their next sentence mixes up the two choices.

Every access pays the hit time, and the L1 is used on every cycle: a slower L1 lengthens the clock period, or adds a pipeline stage and its stalls.

Small and simple: short wires, one comparison

Back to Example 18. Why should a 16 KB direct-mapped cache answer in one cycle and a 32 KB 8-way cache need two or three? The notes give four reasons (p. 356):

• Shorter wires inside the cache array: a signal crosses a smaller array sooner.
• Fewer sets: a simpler decoder for the index.
• A smaller tag array: a faster tag comparison.
• Lower associativity: fewer tag comparators working in parallel.

The last reason hides the biggest gain. A hit is a chain of steps: decode the index, read the tag and the data, compare the tags and, in a set-associative cache, let the comparison drive the way-select multiplexer (Fig. 2). A direct-mapped cache has one candidate line, so it hands the data on while the comparison is still running; if the tags differ, the data is simply dropped. It is the multiplexer that lesson 25 drew for way prediction. "Simple" removes a whole step; "small" shortens the others.

A second reason, which the notes do not give, is power. The L1 is read on almost every cycle, so the energy of one access is paid about a billion times per second at 1 GHz, and in the CACTI data that Hennessy & Patterson show (5th edition) the energy of a read grows with both the size and the associativity of the cache.

When does the smaller cache win?

The price is in the notes' trade-off table (p. 356): a small cache has a low hit time and a high miss rate, a large one the reverse. AMAT decides which matters more. Write HT, MR and MP for the hit time, the miss rate and the miss penalty, with s for the small design and b for the big one. Both send their misses to the same next level, so they share the miss penalty.

1. The small design is the better one when its average access is shorter:

   \[ \text{AMAT}_s \lt \text{AMAT}_b \]

2. Write both with the formula of lesson 22, with the same MP on both sides:

   \[ \begin{aligned} & HT_s + MR_s \cdot MP \\ & \lt HT_b + MR_b \cdot MP \end{aligned} \]

3. Collect the miss terms on the left and the hit times on the right. Left: the extra misses of the small cache times the price of each. Right: the cycles it saves on every access.

   \[ (MR_s - MR_b)\, MP \lt HT_b - HT_s \]

4. When the small cache misses more, \(MR_s \gt MR_b\), divide: the two designs tie at the break-even miss penalty, and below it the small one wins.

   \[ MP^{*} = \frac{HT_b - HT_s}{MR_s - MR_b} \]

5. Or fix MP and solve for the highest miss rate the small cache may have before it loses:

   \[ MR_s^{*} = MR_b + \frac{HT_b - HT_s}{MP} \]

Put numbers on Example 18. The notes give no miss rates, so take 4 % for the small cache and 2.5 % for the big one, with 1 and 2 cycles of hit time. Behind the L1 put the L2 of Example 16, where an L1 miss costs 20 cycles: AMAT = 1 + 0.04 × 20 = 1.80 cycles for the small cache and 2 + 0.025 × 20 = 2.50 for the big one. The extra 1.5 % of misses costs 0.3 cycles per access; the faster hit saves 1. Now take the L2 away and send every L1 miss to memory, 100 cycles: 5.0 against 4.5, and the big cache wins. The two tie at MP* = 1 / 0.015 ≈ 67 cycles.

This is why the L1 is small and the L3 is huge. The L3 is reached only by accesses that missed in L1 and L2: its latency is part of a miss penalty, never of the hit that every access pays. Hence the design practice of p. 356: keep the L1 "small enough for 1-cycle accesses at CPU clock speed" and "use L2 and L3 caches to absorb most misses from L1".

One tension is left. The same page recommends associativity "often 2-4 way in L1", while p. 364 notes that "many modern CPUs use 32 KB, 8-way L1 caches". Hit time pulls the associativity down. The rule of lesson 27, cache size / associativity ≤ page size, pulls it up as soon as the L1 grows beyond one page per way. Hennessy & Patterson add two more upward pulls: many processors already take two or more cycles for an L1 hit, and several threads sharing one L1 cause more conflict misses. Way prediction gives designers both: the miss rate of an 8-way cache with, most of the time, the hit time of a direct-mapped one.

A small, simple L1 wins while its extra misses, times the miss penalty, cost fewer cycles than it saves on every hit.

Why a write hit is slower than a read hit

The notes say that the write path is slow, "due to checking tags, updating data arrays, handling dirty bits" (p. 366), but not why a write hit is slower than a read hit. The reason is the order of two steps. A read hit may read the tag array and the data array at the same moment and use the data only if the tags match: a mismatch costs nothing but a wasted read. A write cannot do that. Writing the data before the comparison would overwrite a word of whatever block sits in that line (Fig. 3). So a write checks the tag first and writes afterwards, two steps in a row where a read needs one. This is the textbook's reason (Hennessy & Patterson), and the first thing to say about pipelined writes.

Now a burst of stores, in the shape of the notes' Example 22, which splits a write into three one-cycle steps: address decode, tag check, data write. In the papers' mnemonics (the 2026 paper writes registers without the dollar sign; older papers write $F2):

SD   F2, 0(R1)
SD   F4, 8(R1)
SD   F6, 16(R1)
SD   F8, 24(R1)
SD   F10, 32(R1)

Without pipelining, the cache finishes one store before it starts the next: 3 cycles each, 15 for the five, "one write every three cycles" (p. 366). With pipelined writes a new store enters every cycle. While one store checks its tag, the store before it writes its data and the store after it decodes its address. The five stores need 7 cycles. In general, N stores through a k-stage write path take kN cycles without pipelining and k + N − 1 with it.

Notice what did not change: each store still spends 3 cycles from decode to data write, "latency still 3, but overlapped" (p. 366). Pipelining raises the throughput, one write per cycle instead of one every three, which is what store-heavy code on a superscalar core needs. It does not make a single write faster. The notes' "reduced average hit time" means exactly this: the processor no longer waits for each write to finish before it issues the next.

A real cache adds a detail that the notes leave out (Hennessy & Patterson, 2nd edition, describe it on the Alpha 21064). Loads need the data array too, so after its tag check a store's data waits in a small delayed-write buffer and enters the array in a later cycle in which the data array is idle, such as the tag check of the next store, which needs only the tag array. The ticker below writes it in the first idle cycle. The buffer creates the hazard the notes name, "reads don't bypass pending writes to the same address" (p. 366). A load must compare its address with the buffer and, on a match, take the data from there. That check is the first of the three costs the notes list; the others are more complex control and the area and power of the buffers and pipeline registers.

Pipelining is not limited to writes. Hennessy & Patterson's 5th edition counts pipelined cache access among its advanced optimisations: the whole L1 access is spread over several stages so that the clock can run fast. An instruction-cache access took 1 cycle on the Intel Pentium, 2 on the Pentium Pro to Pentium III, and 4 on the Pentium 4 and the Core i7. It is the "add a stage" choice of Fig. 1: a faster clock and more bandwidth, paid with a longer load-use latency and a costlier mispredicted branch.

Pipelined writes overlap the data write of one store with the tag check of the next: one write per cycle, the same latency per write, and every load must look into the delayed-write buffer.

Small sub-blocks: write first, check later

The fourth hit-time technique of the notes (p. 367) attacks the same two-step write from the other side: instead of overlapping the steps, it makes the early write harmless. Take a write-through cache (lesson 23) whose 32-byte blocks hold four 8-byte words, and give every word its own valid bit, the key ingredient: each word is now a sub-block. In Fig. 4 the line holds block A, all four words valid. The store SD F2, 8(R1) writes word 1 of block B, which maps to the same line.

The cache does not wait for the comparison. In the same cycle in which it compares the tags, it writes F2 into word 1 and B's tag into the tag field. Then it looks at the outcome:

Every outcome is either right or repaired at once, so a store never waits for the tag check, and a write hit costs no more than a read hit. As a bonus, a write miss fetches nothing. Two conditions make it work. The sub-block must be one word, so that a one-word store fills it completely and its valid bit can be set with nothing fetched. And the cache must be write-through: case 3 overwrites a word of block A, which is harmless only because memory already holds A's current data. The price is a valid bit per word, and after case 3 the line holds a single valid word of B: a later read of B's other words misses, the notes' "spatial locality underused" (p. 367). This is the mechanism in Hennessy & Patterson (2nd edition); the notes explain the technique differently, and two of their sentences need the red pen.

The hardware is that of sub-block placement (p. 345, lesson 26), one valid bit per sub-block under one tag, put to another use: there to fetch less on a miss (miss penalty), here to write without waiting (hit time). And it is the twin of pipelined writes. Both attack the same rule, "check the tag before you write": one overlaps the two steps, the other makes the early write safe.

With a valid bit per word, a write-through cache can write first and check the tag later: a hit was right, a missing valid bit is set, a mismatch is repaired because memory still holds the old block.

Nineteen rows, three terms: the scorecard of the chapter

The notes close the chapter with three lists, one per term of AMAT, each technique with the page where it starts (pp. 368–369), and with Table 29 (p. 370). Before you look at either, test your memory: the lists are the skeleton of any open question on cache optimisations.

From memory: the eight techniques the notes file under "Reducing Miss Rate", with their pages.

The six under "Reducing Miss Penalty".

The four under "Reducing Hit Time".

The lists hold 18 entries. Table 29 has 19 rows, because early restart and critical word first get one each. The scorecard widget below has 20 cards: it also splits the row "Pseudo-Associativity / Way Prediction", since, as lesson 25 showed, way prediction lowers the hit time and pseudo-associativity the miss rate.

Most rows say what lessons 25 and 26 said. Six cells need a second look:

• a, block size, hit time ↑: there is no hit-time effect (red pen below).
• b, victim cache, miss penalty ↓ (slightly): a valid second reading. Seen from the L1 alone a victim-cache hit is a short miss; seen from the L1 and its buffer it is no miss at all.
• c, one row, two techniques: the ↓ under miss rate is pseudo-associativity's; way prediction removes no miss, it shortens the hit.
• d, software prefetching, hit time ↑ (extra instr.): the extra instructions raise the instruction count IC of lesson 3, not the time of a hit.
• e, second level, miss rate ↓: the L1 misses as often as before; what falls is the global miss rate of lesson 24.
• f, second level, hit time ↑ (extra level): the L1 hit is untouched; the L2 lookup is paid by L1 misses, inside the L1 miss penalty.

The scorecard below keys all twenty cards with these corrections and the prices found in lessons 25 and 26, and a pattern appears: only six cards push a second term the wrong way. A bigger cache, more ways and pseudo-associativity lengthen the hit, bigger blocks raise the miss penalty, sub-block placement and the small L1 add misses. The other fourteen pay in hardware, bandwidth or complexity.

The textbook's version adds bandwidth and power

Background, not in the notes. The 5th edition of Hennessy & Patterson sums up its advanced optimisations in a table (Fig. 2.11) that adds two columns to the three terms: bandwidth and power. Small and simple caches score on hit time and power; way prediction on hit time; pipelined cache access and multibanked caches (split into banks that serve independent accesses in parallel) on bandwidth, the first at the price of a longer hit; non-blocking caches on bandwidth and miss penalty; critical word first and the merging write buffer on miss penalty; compiler techniques on miss rate; prefetching on miss penalty and miss rate. A quiz that follows the book may therefore count prefetching as a miss-penalty technique too.

Back to the two L1 designs

The cache that Example 18 does not mention is the L2. With the L2 of Example 16 behind it, an L1 miss costs 20 cycles and the small, simple L1 wins, 1.80 cycles per access against 2.50. Without it every miss costs 100 cycles and the 32 KB 8-way L1 wins, 4.5 against 5.0. Generations of small L1 caches rest on the large, fast levels behind them. The notes' "use L2 and L3 caches to absorb most misses from L1" (p. 356) is not a detail of the design; it is its condition.

Sort any technique by what it changes (how many misses, what one miss costs, what every access costs), then name its price: the term it pushes the wrong way, if any, or the hardware it adds.