Misses, penalties and the design space: the second level, the 3 C’s, from misses to seconds

A second chance before memory: the L2 cache

The first-level cache has to answer at the speed of the pipeline, in a cycle or two, so it must be small — and, in the notes' words (p. 260), "small cache, relatively high miss rate". With one level of cache every L1 miss is a trip to DRAM.

The fix is a second-level cache, L2, between L1 and main memory, and its "main job is to catch L1 cache misses before they reach main memory" (p. 315). It is larger than L1 (hundreds of KB to several MB), slower than L1 but much faster than DRAM, usually unified (instructions and data together), built in SRAM like L1 and, in modern processors, on the same chip. An access now has three places to end:

1. L1 hit: the data comes back at once.
2. L1 miss, L2 hit: the block comes from L2 into L1 and to the CPU, after the L2 hit time.
3. L1 miss, L2 miss: the block comes from main memory, the slow trip.

It works because the small L1 has to evict blocks that are still useful, and the larger L2 still holds many of them: "a large fraction of L1 misses are 'saved' by L2" (p. 315).

Two levels, one formula: nest the AMAT

Start from the one-level formula of lesson 22 and ask only one new question: what does an L1 miss cost now?

1. The one-level formula, written for L1:

   \[ \text{AMAT} = HT_{L1} + MR_{L1} \times MP_{L1} \]

2. An L1 miss is served by the L2. Seen from L1, the L2 is just a slower memory with a hit time, a miss rate and a penalty of its own, so what one L1 miss costs is the average access time of the L2:

   \[ MP_{L1} = HT_{L2} + MR_{L2} \times MP_{L2} \]

3. Substitute. This is the notes' eq. 77 and the "Hierarchical (L1, L2)" line of the example formula sheet on the course page:

   \[ \begin{aligned} \text{AMAT} = {} & HT_{L1} + MR_{L1} \times {} \\ & (HT_{L2} + MR_{L2} \times MP_{L2}) \end{aligned} \]

4. Multiply out: three terms, one per level an access may have to visit (eq. 52):

   \[ \begin{aligned} \text{AMAT} = {} & HT_{L1} + MR_{L1}\, HT_{L2} \\ & + MR_{L1}\, MR_{L2}\, MP_{L2} \end{aligned} \]

5. Read the terms. Every access pays the L1 hit time; the fraction \(MR_{L1}\) that misses in L1 also pays the L2 hit time; the fraction \(MR_{L1} MR_{L2}\) that misses in both also pays the trip to memory. A third level repeats the move:

   \[ MP_{L2} = HT_{L3} + MR_{L3} \times MP_{L3} \]

The notes' Example 8 (p. 316) in numbers: \(HT_{L1} = 1\) cycle, \(MR_{L1} = 5\%\), \(HT_{L2} = 10\) cycles, \(MR_{L2} = 20\%\), \(MP_{L2} = 100\) cycles. An L1 miss now costs 10 + 0.2 × 100 = 30 cycles instead of 100, and the average access 1 + 0.05 × 30 = 2.5 cycles. Without the L2 the same misses go straight to memory: 1 + 0.05 × 100 = 6 cycles. (The notes assume, without saying so, that memory is 100 cycles away from L1 as well as from L2.)

An L2 does not make L1 miss less often; it makes every L1 miss cheaper: \(HT_{L2} + MR_{L2} \times MP_{L2}\) instead of the trip to memory.

Local and global miss rates

Back to Example 7 (p. 261): 1000 references, 40 misses in L1, 20 misses in L2. A miss rate is misses divided by accesses — but which accesses? The notes give two answers.

The global rate is "what really matters" (p. 261): it is the share of all accesses so unlucky that they pay the trip to memory — here 2%, half of the 4% that would pay it without an L2. The local rate of an L2 looks bad because L1 has already served the easy accesses, the ones with locality, so the L2 is asked only about the hard ones. A local miss rate of 50% at L2 is no failure, and it cannot be compared between machines: put a better L1 in front of the same L2 and the L2's local rate rises although nothing in the L2 changed. To compare hierarchies, compare global rates.

A paper may give the L2 as a hit rate, and that hit rate is local. Question 3 of the 8 January 2026 paper, as the notes reproduce it (p. 503): L1 hit rate 95%, L2 hit rate 90%, "How much is the Global Miss Rate for Last Level Cache?" The last-level cache is the lowest cache before memory, here L2: 0.05 × 0.10 = 0.005 = 0.5% of all accesses reach memory. The AMAT of the same machine is an exam question at the end of the lesson.

A local miss rate measures a level against what reaches it; only the global rate counts the accesses that pay the trip to memory.

From misses to seconds: memory stalls in the CPU time

AMAT is a cost per memory access. The exam asks for CPI and CPU time, costs per instruction, and lesson 3 gave the frame: CPU time = IC × CPI × \(T_{CLK}\). What is left is how the misses get into the CPI.

Count it first on the CPU3 of the June 2025 paper. With an ideal cache every instruction takes 8 cycles. Each instruction makes 3 memory accesses on average, half of them miss, and each miss stalls the processor for 3 more cycles. Two instructions make 6 accesses, 3 misses and 9 stall cycles: 16 + 9 = 25 cycles for 2 instructions, 12.5 per instruction.

The general form adds the two parts in the same way (p. 262). It is the Iron Law with the cycles split into work and waiting:

1. Split the cycles of the program into normal work and waiting for memory:

   \[ \begin{aligned} \text{CPU time} = {} & (\text{exec cycles} \\ & + \text{stall cycles}) \\ & \times T_{CLK} \end{aligned} \]

2. The work is the Iron Law with \(CPI_{exec}\), the CPI "without considering cache misses": every access a hit (eq. 55):

   \[ \text{exec cycles} = IC \times CPI_{exec} \]

3. The waiting is the number of misses times the price of one (eq. 56):

   \[ \begin{aligned} \text{stall cycles} = {} & IC \times \frac{\text{misses}}{\text{instruction}} \\ & \times MP \end{aligned} \]

4. Misses per instruction: chain two ratios so that the memory accesses cancel (eq. 57, corrected below):

   \[ \begin{aligned} \frac{\text{misses}}{IC} &= \frac{\text{accesses}}{IC} \times \frac{\text{misses}}{\text{accesses}} \\ &= MAPI \times MR \end{aligned} \]

5. Put the pieces together and take IC out of the bracket (eq. 58–59): the CPI grows by the stall cycles of each instruction.

   \[ \begin{aligned} CPI &= CPI_{exec} \\ &+ MAPI \times MR \times MP \end{aligned} \] \[ \text{CPU time} = IC \times CPI \times T_{CLK} \]

The three cases of the June 2025 exercise

The paper asks for CPU3 with an ideal cache, with the real cache and with no cache at all. "Ideal cache" is a miss rate of 0; "no cache" is treated, as on p. 263, as a cache that always misses (miss rate 1) with the same 3-cycle penalty.

It is the same program on the same CPU in all three cases: IC and \(T_{CLK}\) are equal and cancel, so the ratio of the CPU times is the ratio of the CPIs. With the real cache CPU3 takes 56.25% more time than with an ideal one; without a cache, 36% more than with the real one (2.125 times the ideal). Part 1 of the same exercise compares CPU1 and CPU2, which have different clocks, and there the CPI ratio is not the answer (lesson 3). If the pipeline also stalls for hazards, the two kinds of stall simply add (eq. 60):

Why a faster core suffers more

The 4.5 stall cycles per instruction belong to the memory system: at the same clock, the core does not appear in MAPI × MR × MP. What changes from core to core is what they are added to. On top of 8 cycles of work they add 56%. On top of 1 cycle, a core eight times better, they make the CPI 5.5, 5.5 times the ideal, and the better core finishes only 12.5 / 5.5 = 2.27 times sooner, not 8. A faster clock makes it worse: memory's latency in nanoseconds stays, so its penalty in cycles grows. The notes draw the moral on p. 263: "even if we build the fastest CPU core in the world, if our memory system is slow, our real performance will be bad!"

Two levels in the CPU time

With an L2 there are two kinds of stall (p. 264): every L1 miss waits for the L2 hit time, and an access that misses in both waits for the trip to memory on top. Count each kind per instruction with MAPI, and watch which rate it needs:

The L2 makes this machine 13 / 7.6 = 1.71 times faster. Look at the last row: the stall formula is the expanded AMAT without its first term, multiplied by MAPI. The L1 hit time is missing on purpose: \(CPI_{exec}\) already counts every access as an L1 hit, so a stall is only what comes on top of it.

CPI = \(CPI_{exec}\) + MAPI × MR × MP: misses per instruction times the price of one miss, added to the work of the core.

Why a miss happens: the three C's

Take the notes' own collision (p. 306): blocks 12 and 20 in a direct-mapped cache of 8 blocks. 12 mod 8 = 4 and 20 mod 8 = 4, so both may live only in line 4 (the placement rule of lesson 23). Read them in turn and every access misses. Is the cache too small? It has 8 lines and the program uses 2. Is it the cold start? Only for the first two accesses. The other four misses happen because the two blocks were given the same place.

Miss rate 6 / 6 = 100% in the direct-mapped cache, 2 / 6 = 33% in the fully associative one. The notes sort misses by cause into three kinds, plus a fourth for multiprocessors (pp. 319–320):

• Compulsory (cold-start) misses: the first access to a block, which cannot be in the cache yet. "These always occur, even with infinite cache." Reduced by prefetching or larger blocks.
• Capacity misses: "The cache is too small to hold all the data the program is working on", so useful blocks are evicted and missed again. Reduced by a larger cache.
• Conflict (collision, interference) misses: blocks that "map to the same cache set, and they overwrite each other, even if the cache is not full". Reduced by higher associativity or a victim cache.
• Coherence misses, in multiprocessors only: another processor writes a block this core holds, the copy is invalidated, and the next access misses (lesson 35).

"Too small" and "the same place" need a test you can apply to a trace. Hennessy & Patterson (background, not in the notes) define each C by comparing your cache with two imaginary caches that have the same block size:

Run the ping-pong through the tests. Infinite cache: 2 misses, the first touches, so 2 compulsory. Fully associative, 8 blocks: still 2 misses, so 0 capacity. Direct-mapped: 6 misses, so 6 − 2 = 4 conflict. In a 2-way cache of the same size both blocks go to set 0 (12 mod 4 = 20 mod 4 = 0) and fit in its two ways: 2 misses. So the C belongs to the access in a given cache, not to the block, and the totals add up: misses = compulsory + capacity + conflict (+ coherence).

The July 2024 table of lesson 23 has eight misses, all first touches, three of which evict a block: by the definitions all eight are Cold-start, since no bigger or more associative cache could have avoided any of them. No official solution settles how the paper labels a first touch that evicts, so write the reason next to the type, "Cold-start Miss (replaces LRU 14)", as lesson 23 does.

Compulsory: an infinite cache would miss too. Capacity: a fully associative cache of the same size would miss too. Conflict: only your organisation misses.

The design space: five knobs, three terms

"Changing one parameter usually impacts hit time, miss rate, and miss penalty, so it's always about trade-offs" (p. 317). The notes list five knobs: cache size, block size, associativity, replacement policy and write policy. The three C's tell you which misses each knob attacks, and AMAT tells you what it costs. Here is the notes' Table 27 (p. 318), read through the three terms:

A bigger cache misses less but answers more slowly. "We can't make L1 huge without slowing it down, that's why big caches are placed at L2 or L3" (p. 317): the second level exists because of this trade-off. Block size has a sweet spot, where fewer, larger blocks start to collide and every miss carries more bytes; lesson 25 measures it. For replacement, the notes' trend is LRU at 2–4 ways and pseudo-LRU or random above, where tracking the exact order of use costs too much. The write policy has no term of its own in AMAT: write-back saves memory traffic (lesson 23), and the dirty victim it may have to write back on a miss is handled in lesson 26.

Three strategies, and a quiz the notes got backwards

Sort the techniques by the term they attack and you get the notes' three strategies (pp. 321–322): reduce the miss rate, reduce the miss penalty, reduce the hit time. They are the map of the next four lessons, and they are exactly what Question 4 of the 8 January 2026 paper tests: "Which of the following cache improvements are effective in reducing the miss penalty?"

The L2 of this lesson is Answer 3. The other miss-penalty answer is 4: a read miss that would wait behind buffered writes, or behind the write-back of a dirty victim, is served first (lesson 26). Answer 2 shortens every hit: index bits that need no translation let the TLB and the cache look up in parallel (lesson 27). Answer 1 removes conflict misses: miss rate.

Back to the two puzzles

The L2 of Example 7 misses half of what it is asked, but it is asked only about the 40 accesses in 1000 that L1 could not serve. Against all accesses its misses are 2%, half of the 4% that went to memory without it: an L1 miss costs 110 cycles instead of 200, the average access 5.4 instead of 9. The 50% is a local rate; the global 2% is the one that matters.

The 4.5 stall cycles of CPU3 belong to the memory system. On top of 8 cycles of work they add 56%; on top of 1 cycle they multiply the time by 5.5. A faster core shrinks only its own part of the CPI, so memory's share grows — which is why the next four lessons attack the miss rate, the miss penalty and the hit time one by one.

Size, block and associativity each move two terms of AMAT: judge a knob by the sum, never by the miss rate alone.