David Kroft, of Control Data Canada, described a "lockup-free" instruction fetch and prefetch cache at ISCA 1981. It kept accepting requests while misses were outstanding and recorded each in miss information/status holding registers: the MSHRs of the notes.
Cheaper misses: reads first, the critical word, caches that do not block, the second level
After this lesson you will explain six ways to make a cache miss cheaper or to hide it, compute the stall of early restart and critical word first and the two-level AMAT of the formula sheet, and sort any cache technique into miss rate, miss penalty or hit time.
The paper of 8 January 2026, as the notes transcribe it (pp. 503–504), has a multiple-answer quiz: "Which of the following cache improvements are effective in reducing the miss penalty?" The four options, shortened: (1) higher associativity, to reduce collisions; (2) avoiding address translation during indexing of the cache; (3) a small, fast L1 combined with a larger, slower L2; (4) giving priority to read misses over writes.
The notes' worked solution ticks 2 and 3. Two of its four verdicts are wrong. Tick your own answer now and keep it. By the end of the lesson you will know which two are wrong, and you will have a one-sentence rule that sorts any cache technique.
What a miss costs once it has happened
Lesson 22 split the average access into three terms, \(\text{AMAT} = HT + MR \times MP\). Lesson 25 attacked the middle one. This lesson does not try to lower the miss rate: each miss gets cheaper, or stops holding the processor up. The notes collect six such techniques under "Reducing Miss Penalty" (§6.9.2, pp. 342–355).
Miss penalty — "the additional time required to service a cache miss, i.e. the time to fetch the block from the lower level (or memory) and make it usable by the processor" (notes, p. 504). Only the accesses that miss pay it.
Picture a mechanic who orders a part from a warehouse across town. The wait has four pieces: the van may first be busy taking back earlier returns; the drive takes time; the crates come off one at a time, the one with the part perhaps last; and all the while the mechanic stands idle. A read miss has the same four pieces, and each technique of this lesson attacks one of them (Fig. 1).
Sections 2 to 5 take the pieces in turn; section 6 sorts all fourteen techniques of the chapter and settles the quiz.
Miss-penalty techniques do not reduce how many misses happen: they make each miss cheaper, or hide it from the processor.
Reads first, writes later
A load that misses holds the processor up: the instructions after it need its value (p. 342). A store has nobody waiting for it; it can sit in the write buffer of lesson 23 and reach memory later. So when a read miss and pending writes compete for memory, which in the notes' model serves one miss at a time per port, the controller serves the read first. Competing does not mean the same cycle: a load misses in cycle 10, a store in cycle 12, and both are pending when memory becomes free.
Write-through: bypass the buffer, but look into it first
Take a direct-mapped, write-through cache in which addresses 512 and 1024 fall on the same line. This classic case is from Hennessy & Patterson, rewritten in the papers' mnemonics (registers without the dollar sign, as the 2026 paper writes them; older papers write $F2):
I0: SD F2, 512(R0) ; store
I1: LD F4, 1024(R0) ; miss
I2: LD F6, 512(R0) ; missI0 updates the cache line and drops the pair (512, F2) into the write buffer. I1 misses, and its block replaces the block of 512. I2 misses too. If the controller sends I2's read to memory ahead of the buffered write, it reads the old M[512]: the new value is still in the buffer. The notes call this a RAW hazard through memory (p. 344).
The fix costs a comparison (pp. 342–343). Before going to memory, the controller compares the read address with every address in the write buffer. On a match it takes the data from the buffer; without one it sends the read miss to memory at once, ahead of the buffered writes. The other safe option, draining the whole buffer first, adds every pending write to the read-miss penalty.
Write-back: park the dirty victim
In a write-back cache the conflict comes from the victim (p. 343). A read miss must bring a block Y into a line that holds a block X. A clean X is simply overwritten. A dirty X, in the naive order, is written back first and Y fetched after: the processor waits for two block transfers. With read priority, X is copied into the write buffer, Y is fetched at once, and X goes to memory in the background (Fig. 2).
Before: write back, then fetch
After: fetch first, write back later
The price (p. 344): a comparison against every buffer entry, logic that tracks which reads depend on which writes, and no help once the buffer fills up. The gain: as many misses as before, but each read miss stops paying for writes nobody waits for. That is a shorter miss penalty.
The merging write buffer: fewer, fuller writes
With write-through, every store goes to memory through the write buffer, and stores come in runs: A[i], then A[i+1], in the same block. Without merging, each store is a separate memory transaction; the bus is busy, and a read miss that needs it waits (p. 353). A merging write buffer folds writes to the same block into one entry, sent as one transaction. An entry holds the block address, aligned to the block size; a data field as large as a block; and a byte-valid mask, one bit per byte (or per word), marking the bytes that hold new data.
The procedure (pp. 353–354), for 32-byte blocks and 8-byte stores: align the address to its block (0x1048 belongs to the block at 0x1040); if the buffer has an entry for that block, write the 8 bytes at their offset and set their mask bits, with no memory transaction yet; otherwise allocate an entry. At the flush a full mask becomes one full-block write, a partial mask a partial write with byte enables (if the bus has them) or a read-merge-write. The notes' Example 17 stores 8 bytes at 0x1000, 0x1008 and 0x1010: one entry, 24 of 32 bytes valid.
The price of merging (p. 355): matching logic and masks on every entry, room for a whole block per entry, and no escape from a full buffer. It pays most with write-through caches, and also helps a write-back cache that evicts dirty lines in pieces.
A load has a consumer waiting, a store has none: let read misses overtake buffered writes, check the buffer's addresses first, and pack the writes into whole blocks.
Fetch less, hand it over sooner
Next in Fig. 1 comes the transfer: a normal miss fetches the whole block, say 64 bytes, and the processor waits for the last byte (p. 345). Three techniques shorten that wait: move less data, or hand over the word before the rest arrives.
Sub-block placement: one tag, several valid bits
Divide each block into sub-blocks, each with its own valid bit, under a single tag (p. 345). On a miss only the requested sub-block is fetched; the others are marked invalid until they are needed. A hit now needs a matching tag and the valid bit of the right sub-block. Fig. 3 compares three ways to hold the same 32 bytes.
The gain: a shorter transfer and no bandwidth spent on words nobody asked for, useful when spatial locality is weak, bandwidth is limited or blocks are large (p. 345). The price: neighbouring words now miss later, so the miss rate creeps up a little, and valid bits and control logic grow. One term of AMAT is traded for another.
Early restart and critical word first
Take the notes' block of four words, W0 to W3, and a processor that asks for W2 (pp. 346–347). With early restart the memory sends the block in normal order, W0, W1, W2, W3; the cache forwards W2 the moment it arrives, and the processor resumes while W3 is still coming. With critical word first, or wrapped fetch, the memory starts at the requested word and wraps around: W2, W3, W0, W1. The requested word is fetched first, not just delivered first. The stepper turns the two orders into penalties.
The model: after a request the memory needs \(L\) cycles before it starts sending, then sends one word per cycle. A block has \(n\) words, numbered from 0; the processor wants word \(k\).
The word sent \(p\)-th, counting from 0, arrives at the end of cycle
\[ t(p) = L + p + 1 . \]That is \(L\) cycles of latency plus \(p + 1\) transfer cycles.
Waiting for the whole block, the processor resumes after the last word, \(p = n - 1\):
\[ MP_{\text{block}} = L + n . \]Early restart keeps the normal order, so word \(k\) is sent \(k\)-th, \(p = k\):
\[ MP_{\text{ER}} = L + k + 1 . \]Critical word first sends the requested word first, \(p = 0\), whatever \(k\) is:
\[ MP_{\text{CWF}} = L + 1 . \]The savings over the whole block: early restart saves \(n - k - 1\) cycles, from \(n - 1\) for the first word down to 0 for the last, \((n - 1)/2\) on average; critical word first always saves \(n - 1\). For the notes' block (\(n = 4\), \(k = 2\)) with \(L = 10\): 14, 13 and 11 cycles.
The price is in the controller and the memory (p. 347): critical word first needs wrap-around addressing and a memory that can start a burst mid-block; early restart only changes when the cache forwards a word. Both gain less when the processor needs another word of the block right away: it stalls again until that word arrives. Hennessy & Patterson add that both pay mainly with large blocks, as the third task shows.
Write the three penalties as one line on the A4 sheet: \(L + n\), \(L + k + 1\), \(L + 1\). Count \(k\) from 0, and check whether "latency" in the exam text already includes the first word.
Early restart forwards the requested word when it arrives; critical word first makes it arrive first: \(L + n \to L + k + 1 \to L + 1\).
Caches that keep working during a miss
So far the processor has stood still during every miss. The notes show why that is wasteful with two lines of C, sum += A[i] and sum += B[0] (p. 348). In the papers' mnemonics:
I0: LD F2, 0(R1) ; A[i]: miss
I1: LD F4, 0(R2) ; B[0]: hitA blocking cache stalls the processor until the miss of I0 is resolved, even though B[0] is already in the cache. A non-blocking cache (also called lockup-free) keeps serving accesses while a miss is outstanding. The processor keeps executing instructions that do not depend on the missing data, and the cache may have several memory transactions in flight. It tracks each outstanding miss in a Miss Status Holding Register (MSHR) (p. 348), which records which block is coming and which instruction waits for it.
There are two levels of capability (pp. 348–349). Hit under miss: while one miss is outstanding, hits to other addresses are served; a second miss must wait for the first. Miss under miss (multiple outstanding misses): a second miss starts while the first is still being serviced. That needs several MSHRs, a memory controller that accepts several requests, and logic that matches each returning block to its MSHR, in whatever order the blocks come back.
The widget runs the three cases on six instructions. I0 always misses, and so does a second load, I3 by default; pick I1 or I4 instead and I5 adds F4 or F10 rather than F8.
I0: LD F2, 0(R1)
I1: LD F4, 0(R2)
I2: LD F6, 8(R2)
I3: LD F8, 0(R3)
I4: LD F10, 16(R2)
I5: FADD F12, F2, F8Each orange bar has the same length in every mode: a non-blocking cache does not shorten a miss, it overlaps it with hits and with other misses. That is why the notes say it reduces the effective miss penalty (p. 349). It also breaks the bookkeeping of AMAT: \(MR \times MP\) charges every miss its full penalty, true only of a blocking cache. With overlap the real stall is smaller, and it has to be measured, not added up.
"A non-blocking cache makes misses faster." No: memory is exactly as slow. The gain needs independent work: an in-order pipeline has it only up to the first use of the missing value, I5 in the widget; an out-of-order core with reservation stations and a reorder buffer (lesson 11, lesson 17) finds much more, and a prefetch (lesson 25) is a miss nobody waits for.
The price (p. 349): tracking several misses is hard, MSHRs cost area and energy, and memory-ordering rules must hold when fills return out of order. The benefit grows with memory latency and with the number of cores: it maximises memory-level parallelism (MLP), the number of misses serviced at once.
A non-blocking cache does not shorten a miss, it overlaps it: hit under miss lets hits through, miss under miss overlaps misses in several MSHRs.
A second level: a storeroom downstairs
The last piece of Fig. 1 is the latency. Even with every trick so far, an L1 miss that goes to main memory costs "tens to hundreds of CPU cycles" (p. 350). The notes' answer is a second-level cache, L2: larger and slower than L1, much faster than DRAM; an L3 may follow, larger still and often shared between cores. The path is CPU → L1 → L2 → L3 → main memory.
Count before you average, with the notes' Example 16 (p. 351): 5% of the accesses miss in L1, the L2 hits 90% of the accesses that reach it, an L2 hit takes 10 cycles and a trip to main memory 100. Send 1000 accesses through it (Fig. 4).
The same count with letters is eq. (79) of the notes, the two-level formula of the example A4 sheet on the course page; lesson 24 derives it and defines local and global miss rates.
\[ \begin{aligned} & \text{AMAT}_{L1,L2} = \text{L1 Hit Time} \\ & + \text{L1 Miss Rate} \times (\text{L2 Hit Time} \\ & + \text{L2 Miss Rate} \times \text{L2 Miss Penalty}) \end{aligned} \]
- L1 Hit Time
- paid by every access
- L1 Miss Rate
- the fraction of accesses that miss in L1 and go to L2
- L2 Hit Time
- paid by every L1 miss
- L2 Miss Rate
- local: L2 misses over the accesses that reach L2; the product L1 Miss Rate × L2 Miss Rate is the global miss rate, here 0.05 × 0.10 = 0.5%
- L2 Miss Penalty
- the trip to main memory; the notes write "Main Memory Penalty"
The bracket is the L1 miss penalty: one L2 access always, a trip to memory sometimes. For Example 16 it is 20 cycles, so AMAT = L1 Hit Time + 0.05 × 20 = L1 Hit Time + 1; without the L2 the misses would add 0.05 × 100 = 5. As many L1 misses as before, each costing 20 cycles instead of 100: that is how an L2 reduces the miss penalty.
"An L2 lowers the L1 miss rate." No: L1 misses exactly as often as before. The L2 lowers what each of those misses costs, and how many accesses reach main memory, the global miss rate.
How the second level is built
The notes list four design choices (pp. 350–351). Size: much larger than L1, hundreds of KB to MBs, against capacity misses; the slower hit is acceptable because L2 sits only on the path of L1 misses, not on the processor's critical cycle. Associativity: higher, often 8-way or 16-way, against conflict misses. Shared or private: a private L2 per core reduces contention, a shared L3 helps sharing and coherence. Inclusion, in Fig. 5: an inclusive L2 holds everything L1 holds, which simplifies coherence in multiprocessors; an exclusive L2 holds only blocks that are not in L1, which maximises the total capacity; a non-inclusive non-exclusive (NINE) hierarchy keeps no strict relation. Hennessy & Patterson add that the second level is almost always write-back: a write-through L2 would pass every store on to memory.
The price (p. 351): every L1 miss pays the L2 lookup before it can go to memory, and the extra level costs area, power and complexity. The gain: a much lower average miss penalty and less demand on memory bandwidth; the notes (p. 352) call multi-level caches latency buffers.
An L2 does not touch the L1 miss rate: it turns the L1 miss penalty into L2 Hit Time + L2 Miss Rate × L2 Miss Penalty.
The answer key: three terms, fourteen techniques
Sections 6.9.1 and 6.9.2 of the notes hold fourteen named techniques, and one question sorts them: what does the technique change? How many misses happen: miss rate. What a miss costs once it has happened: miss penalty. What every access pays, even a hit: hit time. The table is the answer key for "which of these reduce the miss penalty?" quizzes.
| Technique (notes §) | Term it lowers | How | Main price |
|---|---|---|---|
| Fewer misses: lesson 25 | |||
| Larger cache (6.9.1.1) | miss rate | fewer capacity misses | longer hit time, area, power |
| Larger blocks (6.9.1.2) | miss rate | fewer compulsory misses | larger miss penalty; fewer blocks, more conflicts |
| Higher associativity (6.9.1.3) | miss rate | fewer conflict misses | longer hit time, power |
| Victim cache (6.9.1.4) | miss rate (p. 321: miss penalty) | keeps the blocks just evicted | a small fully associative buffer |
| Way prediction, pseudo-associativity (6.9.1.5) | hit time; miss rate | guess the way; a second index | extra cycles on a wrong guess |
| Hardware prefetching (6.9.1.6) | miss rate | fetch the next blocks early | bandwidth; pollution if wrong |
| Software prefetching (6.9.1.7) | miss rate | prefetch instructions from the compiler | extra instructions |
| Compiler optimisations (6.9.1.8) | miss rate | better locality: merging, interchange, fusion, blocking | compiler effort |
| Cheaper misses: this lesson | |||
| Read priority over writes (6.9.2.1) | miss penalty | a read miss does not wait for writes | address checks on the write buffer |
| Sub-block placement (6.9.2.2) | miss penalty | fetch one sub-block, not the whole block | valid bits; slightly more misses |
| Early restart, critical word first (6.9.2.3) | miss penalty | resume on the requested word | wrap-around fetch logic |
| Non-blocking caches (6.9.2.4) | effective miss penalty | overlap misses with hits and misses | MSHRs, complexity, ordering |
| Second-level caches (6.9.2.5) | miss penalty of L1 | most L1 misses are served by L2 | L2 lookup on every L1 miss; area |
| Merging write buffer (6.9.2.6) | miss penalty | fewer write transactions | masks and matching logic |
| Faster hits: lessons 27 and 28 | |||
| Small and simple L1 (6.9.3.1) | hit time | short wires, fast lookup | more misses |
| Avoiding address translation during indexing (6.9.3.2) | hit time | lookup starts before the TLB answers | size of one way limited by the page size |
| Pipelined writes (6.9.3.3) | hit time | overlap successive writes | pipeline control |
| Small sub-blocks for write-through caches (6.9.3.4) | hit time | a write updates and sends only its sub-block | valid and dirty bits per sub-block |
Two rows need care. The victim cache sits in the notes' miss-rate section (p. 328) but in the miss-penalty list of p. 321: a hit there is a main-cache miss that costs a few cycles, so at the exam name the mechanism and both effects. Way prediction only speeds up finding a hit; pseudo-associativity, beside it in the notes, removes conflict misses.
Back to the quiz of the hook. Answer 1, higher associativity, removes conflict misses: miss rate. Answer 2 lets the cache index while the TLB translates, which shortens every hit: hit time, the subject of lesson 27. Answers 3 and 4 are sections 5 and 2: miss penalty. The correct answers are 3 and 4.
Sort a cache technique by what it changes: how many misses (miss rate), what one miss costs (miss penalty), or what every hit costs (hit time).
Exam-style questions
The questions follow the forms of the papers: an open question with eight sub-points as in June 2026, quizzes with single and multiple answers and a true/false, and exercises answered with every intermediate number. The model answers are computed here; there are no official solutions.
Explain the main concepts and benefits of each one of the following techniques used to reduce the cache miss penalty: 1. Giving priority to read misses over writes; 2. Sub-block placement; 3. Early restart; 4. Critical word first; 5. Non-blocking caches (hit under miss, miss under miss); 6. Second-level caches; 7. Inclusive and exclusive multilevel caches; 8. Merging write buffer. (Five lines each.)
Show model answer
1. A read miss soon stalls the processor, because the following instructions need the data; a write can wait in the write buffer. So when a read miss competes with pending writes, the read is served first. In a write-through cache the read miss first compares its address with those in the write buffer: on a match it takes the data from the buffer, because memory still holds the old value (a RAW hazard through memory); with no match it goes to memory ahead of the buffered writes. In a write-back cache a dirty victim is copied into the write buffer, the new block is fetched at once and the victim is written back afterwards. Benefit: the read-miss penalty no longer includes writes nobody waits for. Cost: comparators on the buffer; a full buffer still stalls.
2. Each block is divided into sub-blocks, each with its own valid bit, under a single tag. On a miss only the requested sub-block is fetched; the others stay invalid until needed, and a hit requires both the tag match and the sub-block's valid bit. Benefit: the tag storage of a large block with the transfer time of a small one, so a lower miss penalty and less bandwidth, useful with large blocks or weak spatial locality. Cost: extra valid bits and control; less spatial locality exploited, so neighbouring words may miss later.
3. The block is fetched in normal order, but the requested word is sent to the processor as soon as it arrives and the processor resumes while the rest of the block is filled in the background. With a latency L before the first word, one word per cycle, n words per block and the requested word at position k (from 0), the stall falls from L + n to L + k + 1 cycles. Benefit: no change to the memory; the gain is larger when the word is early in the block.
4. Critical word first (wrapped fetch) asks the memory for the requested word first and then for the rest of the block, wrapping around (W2, W3, W0, W1). The stall is L + 1 cycles whatever the position of the word. Benefit: the largest gain when the word is late in the block. Cost: wrap-around fetch logic and a memory that supports it. Both 3 and 4 pay mainly with large blocks, where the transfer is a large part of the penalty, and both gain less when the processor soon needs another word of the block.
5. A blocking cache stalls the processor on a miss even if the next accesses would hit. A non-blocking (lockup-free) cache keeps serving accesses while misses are outstanding, each tracked in a Miss Status Holding Register (MSHR). Hit under miss: hits proceed while one miss is pending. Miss under miss: several misses are serviced in parallel (memory-level parallelism), with several MSHRs and a memory that accepts several requests. Benefit: the miss penalty is overlapped with useful work and with other misses, so the effective miss penalty drops; each miss itself is not shorter. It needs a processor with independent work, such as an out-of-order core. Cost: MSHRs, complexity, memory ordering.
6. An L2, larger and slower than L1 but much faster than main memory, catches most L1 misses: AMAT = L1 Hit Time + L1 Miss Rate × (L2 Hit Time + L2 Miss Rate × L2 Miss Penalty), with the local L2 miss rate; the bracket is the new L1 miss penalty. Example: 0.05 × (10 + 0.10 × 100) adds 1 cycle per access instead of 0.05 × 100 = 5. Design: much larger (hundreds of KB to MBs), more associative (8 to 16 ways), usually write-back, its slower hit time acceptable because it is not on the processor's critical cycle. Cost: every L1 miss pays the L2 lookup; area and power.
7. Inclusive: L2 holds a copy of every block in L1, so a coherence check in a multiprocessor can rely on L2 alone; the price is duplicated capacity. Exclusive: a block is either in L1 or in L2, never in both, so the total capacity is the sum of the two. Non-inclusive non-exclusive (NINE): no strict relation. In multicores a private L2 per core reduces contention and a shared L3 helps sharing and coherence.
8. In a write-through cache every store goes to memory through the write buffer; without merging, stores to adjacent addresses each become a memory transaction. A merging write buffer keeps block-sized entries with the aligned block address, a data field and a byte-valid mask; a store to a block already in the buffer is written into its entry instead of taking a new one. Benefit: fewer and larger transactions, less bus contention, so read misses wait less for the bus and the buffer fills less often. Cost: matching logic and masks; a partial entry needs a byte-enabled write or a read-merge-write; a full buffer still stalls.
The form is the June 2026 question: eight sub-points, about five lines each. Give three things in each: the mechanism, the term of AMAT it attacks, and its cost. Sub-points 3 and 4 are best answered with the three penalties; sub-point 6 with the formula from the A4 sheet; sub-point 5 with the sentence "it overlaps the miss, it does not shorten it".
(MULTIPLE ANSWERS) Which of the following cache improvements are effective in reducing the miss penalty?
Show model answer
Answers 3 and 4. Answer 1 reduces the miss rate (conflict misses); Answer 2 reduces the hit time; Answer 3 replaces most trips to main memory with an L2 access; Answer 4 lets a read miss start its fetch without waiting for pending writes.
This is the quiz of the 8 January 2026 paper as the notes transcribe it (pp. 503–504), with the options verbatim; the notes' worked solution picks 2 and 3 (red pen in section 6). If the paper asks you to motivate the answer, one line per option with the term of AMAT is enough.
(SINGLE ANSWER) A cache has blocks of 8 words. On a miss, main memory needs an access latency of 30 clock cycles before the transfer starts, then transfers one word per clock cycle. The CPU requests word 5 (words are numbered from 0). How many stall cycles does the CPU pay with (i) a full-block fetch, (ii) early restart, (iii) critical word first?
Show model answer
Answer 1. Full block: L + n = 30 + 8 = 38. Early restart: L + k + 1 = 30 + 5 + 1 = 36. Critical word first: L + 1 = 31.
The whole question is in the off-by-one. Read how the text defines the latency, write \(t(p) = L + p + 1\) for the word sent \(p\)-th, and the three numbers follow.
(True/False) In a non-blocking cache with miss-under-miss support, each individual miss is serviced in fewer clock cycles than in a blocking cache.
Show model answer
False. A non-blocking cache keeps serving hits and starts further misses while one is outstanding (tracked in MSHRs). Each miss takes as long as before; the processor simply does other work, so the stall it sees, the effective miss penalty, is smaller.
The distinction between the miss penalty and the effective miss penalty is the point. The widget of section 4 shows it: the orange bars keep their length in every mode.
A cache has blocks of 16 words. On a miss, main memory needs an access latency of 40 clock cycles before the transfer starts, then transfers one word per clock cycle, in order from word 0. With early restart, how many clock cycles does the CPU stall when it requests word 9 (words numbered from 0)?
Show model answer
\[ L + k + 1 = 40 + 9 + 1 = 50 \text{ clock cycles} \]
For comparison: full-block fetch 40 + 16 = 56, critical word first 40 + 1 = 41.
Early restart does not change the order: words 0 to 9 must arrive, ten transfer cycles after the 40 of latency.
Let us consider a computer with L1 and L2 caches with the following parameters: Hit Time L1 = 1 clock cycle; Hit Rate L1 = 95%; Hit Time L2 = 10 clock cycles; Hit Rate L2 = 90%; Miss Penalty L2 = 100 clock cycles.
1. How much is the miss penalty of L1? 2. How much is the AMAT? 3. How much is the Global Miss Rate for the Last Level Cache? 4. How much would the AMAT be without L2, if the L1 misses were served by main memory in 100 clock cycles? 5. How much is the speed-up of the average memory access due to L2?
Show model answer
Miss Rate L1 = 1 − 0.95 = 0.05; Miss Rate L2 (local) = 1 − 0.90 = 0.10.
1. The L1 miss penalty, in clock cycles:
\[ MP_{L1} = 10 + 0.10 \times 100 = 20 \]2. The AMAT, in clock cycles:
\[ \text{AMAT} = 1 + 0.05 \times 20 = 2 \]3. The global miss rate of L2, the last-level cache:
\[ 0.05 \times 0.10 = 0.005 = 0.5\% \]4. Without L2, in clock cycles:
\[ \text{AMAT} = 1 + 0.05 \times 100 = 6 \]5. Speed-up of the average access: 6 / 2 = 3.
These are the notes' Example 16 (p. 351) with an L1 hit time of 1 cycle, written in the form of the January 2026 quiz. The trap is item 1: the notes call the 10 cycles the L1 miss penalty, but they are the L2 hit time (red pen in section 5). Turn every hit rate into a miss rate before you substitute.
A write-through cache has a merging write buffer of 4 entries; each entry holds a 32-byte block with a byte-valid mask. With R1 = 0x1000 and R2 = 0x2000, the CPU executes the following stores (8 bytes each) before the bus becomes free:
SD F2, 0(R1)
SD F4, 8(R1)
SD F6, 0(R2)
SD F8, 16(R1)
SD F10, 24(R1)
SD F12, 8(R2)Complete a table with the columns Store | Address | Block base | Action | Valid bytes of the entry after the store. How many write transactions reach memory with and without merging, and of which kind?
Show model answer
| Store | Address | Block base | Action | Valid bytes after |
|---|---|---|---|---|
| SD F2, 0(R1) | 0x1000 | 0x1000 | allocate E0 | E0: 0–7 |
| SD F4, 8(R1) | 0x1008 | 0x1000 | merge into E0 | E0: 0–15 |
| SD F6, 0(R2) | 0x2000 | 0x2000 | allocate E1 | E1: 0–7 |
| SD F8, 16(R1) | 0x1010 | 0x1000 | merge into E0 | E0: 0–23 |
| SD F10, 24(R1) | 0x1018 | 0x1000 | merge into E0 | E0: 0–31 (full) |
| SD F12, 8(R2) | 0x2008 | 0x2000 | merge into E1 | E1: 0–15 (partial) |
With merging: 2 entries and 2 transactions, one full 32-byte write for E0 and one partial 16-byte write for E1 (with byte enables, or a read-merge-write if the bus has none). Without merging: 6 transactions, one per store; the 4-entry buffer is full after the fourth store, so the fifth and the sixth store stall the CPU until an entry has been written to memory.
The block base is the address with its 5 low bits cleared (32-byte blocks). Three points to get right: the alignment, the merge into an existing entry even when another block came in between (the third store), and the difference between a full and a partial flush. The widget of section 2 replays this stream ("two blocks, interleaved").
Check yourself
A write-through cache with a write buffer. A load misses while three stores wait in the buffer, none of them to the load's block. What does read priority do?
In the three-instruction example of section 2 (SD to 512, LD of 1024, LD of 512), why must the controller compare the read address with the write buffer before sending the read to memory?
A block of n words, the processor wants word k. For which k do early restart and critical word first give the same stall?
Which statements about non-blocking caches are true? Select all that apply.
An L2 has a local miss rate of 50%. What does that tell you?
Which inclusion policy gives the largest total capacity with the same L1 and L2?
A merging write buffer with 32-byte entries. The CPU stores 8-byte values at 0x1000, 0x1008, 0x1010, 0x1018 and 0x1020 before the buffer is flushed. How many write transactions reach memory?
Key take-aways
- The six techniques of this lesson do not reduce the number of misses: they make each miss cheaper, or hide it from the processor.
- Read misses go first: in write-through they bypass the buffered writes after an address check that guards against the RAW hazard through memory; in write-back a dirty victim waits in the write buffer while the new block is fetched.
- Sub-block placement fetches one sub-block under one tag; early restart resumes on the requested word, critical word first fetches it first: \(L + n\), \(L + k + 1\), \(L + 1\), worth it with large blocks.
- A non-blocking cache does not shorten a miss, it overlaps it: hits go on under one miss, several misses run in parallel in several MSHRs, and the additive AMAT is no longer exact.
- An L2 turns the L1 miss penalty into L2 Hit Time + L2 Miss Rate × L2 Miss Penalty; it is large, highly associative, and inclusive, exclusive or NINE.
- A merging write buffer folds the stores to one block into one transaction, so reads wait less for the bus.
- Sort any technique by what it changes: how many misses, what a miss costs, or what every hit costs.
What to watch and read
-
Miss Under Miss Support in Caches
Milos Prvulovic, Georgia Tech HPCA (Udacity)a few minutes
Watch it next to the widget of section 4: a short clip with a drawn example of a cache that keeps accepting requests while misses are pending.
-
What Every Programmer Should Know About Memory
Ulrich Drepper, 2007section 3.5.2
Section 3.5.2, "Critical Word Load", measures on a real machine the effect of where the requested word sits in its cache line: the second task of the widget in section 3, with data.
-
Lockup-Free Instruction Fetch/Prefetch Cache Organization
David Kroft, ISCA 19817 pages
The paper that introduced the non-blocking cache and the miss status registers of section 4. Look at how a returning block is matched to the requests waiting for it.
-
Cache Write Policies and Performance
Norman P. Jouppi, DEC WRL report 91/1248 pages
For the write buffer of section 2: write-through against write-back, and a small write cache that gathers writes behind a write-through L1, measured.