The memory wall and the illusion of a fast, big memory

The memory wall: fast or big, never both

Every programmer wants the same thing; the notes (p. 297) put it as "an unlimited amount of memory, as fast as the CPU". Physics and price say no: a memory can be fast or big, and the two qualities come from different technologies.

The fast one is SRAM, static RAM; the big one is DRAM, dynamic RAM. They differ already in how one bit is stored, and everything else follows from that:

The notes pair them this way on p. 301, after a slip four pages earlier:

The way out is a stack of memories, the memory hierarchy: each level faster and smaller than the one below, slower and larger than the one above, each holding a subset of the data of the level below (p. 297). The notes' Example 1 (p. 299) is a student's books: the most-used ones on the desk (L1), others on the shelf in the room (L2), the rest in the university library (main memory), the rarest in the city archive (disk). "If we're smart about what to keep close (using locality), we'll avoid most slow trips."

And the distance between the top and the bottom grew for decades. In Hennessy & Patterson's plot of the processor–memory gap, processor performance rises by about 50% a year from the mid-1980s to 2000, while DRAM latency improves by only about 7% a year.

The processor sees none of the pyramid. It has one address space and one LD instruction; whether the word comes from L1 in a cycle or from DRAM in a hundred is decided underneath it. That is the illusion of a large, fast memory (p. 297): almost as fast as the top, as large as the bottom.

Who keeps the illusion running? Not the programmer: "the hardware and compiler manage this automatically" (p. 298). Hennessy & Patterson split the work three ways. The compiler decides what lives in registers (register allocation); the hardware moves blocks between the caches and main memory, invisibly to the program; the operating system, with hardware help, moves pages between main memory and disk — virtual memory, lesson 27, the layer the notes' sentence leaves out.

Fast memory (SRAM) is small and expensive, big memory (DRAM) is slow and cheap; the hierarchy stacks them so that the processor sees one memory almost as fast as the top and as large as the bottom.

Why the illusion works: locality

The illusion is a bet on how programs behave. Take the loop the notes use on p. 298:

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

Compile it with sum kept in memory, as the notes' comment assumes ("sum is read and written many times in a short span"), and one iteration is six instructions in the papers' mnemonics:

I0  LOOP: LD    F2, 0(R1)      ; F2 ← a[i]
I1        LD    F0, SUM(R0)    ; F0 ← sum
I2        FADD  F0, F0, F2     ; F0 ← sum + a[i]
I3        SD    F0, SUM(R0)    ; sum ← F0
I4        ADDUI R1, R1, 8      ; R1 → a[i+1], 8 bytes on
I5        BNE   R1, R2, LOOP   ; until R1 = R2

Write down the addresses the loop sends to memory. Data: a[0], SUM, SUM, a[1], SUM, SUM, a[2], … Instructions: I0, I1, …, I5, then I0 again. Two patterns jump out, and the notes name both (pp. 298 and 300):

• Temporal locality, "time-based reuse": a location used now will probably be used again soon. SUM is read and written in every iteration; the six instructions are fetched again in every iteration.
• Spatial locality, "nearby reuse": after a location, its neighbours will probably be used soon. a[1] sits 8 bytes after a[0]; I1 sits right after I0.

Each kind is caught by its own mechanism (the table on p. 300). Temporal locality: keep what was used recently, and when something must leave, evict the block unused for the longest time — least recently used, LRU (lesson 23). Spatial locality: never move a single word; move a whole block, or line, "the smallest unit of data moved from main memory to cache", typically 32, 64 or 128 bytes. A 64-byte line holds eight of the loop's 8-byte elements: one trip to memory serves eight iterations.

Hennessy & Patterson put a number on the effect: a program spends about 90% of its execution time in about 10% of its code, a hot loop fetched again and again from a handful of cache lines. In the probe below, the first program is this loop; the other two remove one kind of locality, then both.

The probe's third program is the notes' warning made concrete (p. 298): "Without locality, caches would be useless: every access would go to slow memory." Locality belongs to the program, not to the cache, which is why "compiler optimizations and programming style matter" (p. 300).

Temporal locality is caught by keeping blocks and evicting the least recently used; spatial locality by moving whole blocks. Without locality, a cache only adds its hit time.

What a cache is: blocks, hits and misses

In a two-level picture the cache is the upper level, holding a subset of memory, and main memory the lower level, accessed only when the data is not in the cache: "a buffer between fast CPU and slow main memory". Everything moves in blocks, so the first thing to know is how many blocks a cache holds:

An access is a hit when the requested address is already in the cache, a miss when its block must be fetched from the level below. What does a miss cost? Follow the first load of the loop when the block holding a[4] is not in the cache; the notes (p. 301) list four consequences, numbered in Fig. 3:

1. Stall the CPU. The load cannot complete, so the pipeline freezes: the same stall as for a hazard (lesson 2), only tens to hundreds of cycles long.
2. Fetch the block that holds a[4] from memory, or from the next-level cache.
3. Write the block into the cache.
4. Retry the access, which now becomes a hit.

Two times describe the two outcomes (p. 302). The hit time is the time to access the cache, determine whether it is a hit and return the data. The miss penalty is the time to fetch the block from main memory or the next-level cache, update the cache and resume the CPU. A miss pays both, because the cache is looked up before it knows it missed:

The notes call the cost of a miss the miss time (eq. 49):

Counted over a run, hits and misses give two rates that add up to one (p. 257); HR and MR stand for the notes' Hit Rate and Miss Rate:

A hit costs the hit time; a miss costs the hit time plus the miss penalty, because the lookup is paid before the cache knows it missed.

AMAT: what one access costs on average

Count before you average. Take the notes' Example 3 (p. 302): hit time 1 cycle, miss rate 5%, miss penalty 100 cycles, and run 100 accesses. 95 hit and cost 1 cycle each: 95 cycles. 5 miss and cost 1 + 100 cycles each: 505 cycles. Together 600 cycles, 6 per access. That average is the average memory access time, AMAT, "the expected cost of accessing memory, accounting for both hits and misses". The derivation is the same count with letters (p. 303).

1. Every access is either a hit or a miss. Weight the time of each case by its probability; the notes call this "the most general formula" (eq. 70), with MT the miss time:

   \[ \text{AMAT} = HR \cdot HT + MR \cdot MT \]

2. A miss first checks the cache, exactly like a hit, then fetches the block (eq. 71):

   \[ MT = HT + MP \]

3. Substitute and multiply out:

   \[ \begin{aligned} \text{AMAT} = {} & HR \cdot HT + MR \cdot HT \\ + {} & MR \cdot MP \end{aligned} \]

4. The first two terms share the hit time. Factor it out:

   \[ \begin{aligned} \text{AMAT} = {} & HT\,(HR + MR) \\ + {} & MR \cdot MP \end{aligned} \]

5. Hit or miss, nothing else: \(HR + MR = 1\). The bracket disappears, and the formula of the notes (eq. 69, 72) and of the formula sheet is left:

   \[ \text{AMAT} = HT + MR \times MP \]

Read the formula the way the count went: every access pays the hit time, and the misses add MR × MP on average. At a 100-cycle penalty each percent of miss rate costs a whole cycle on every access — why the miss rate gets so much attention, and why it is not the whole story.

Three levers, and the map of the next lessons

The formula has three terms, so there are exactly three ways to make the average access faster. The notes list them twice (p. 258 and pp. 321–322), and they organise the rest of the memory part of this course:

The notes call the three strategies "orthogonal", one per term. In practice most techniques move two terms at once: a bigger cache misses less but answers more slowly, a bigger block catches more spatial locality but makes every miss longer. Weighing one term against another is the design space of lesson 24, and AMAT is the scale.

AMAT = HT + MR × MP: every access pays the hit time, and on average the misses add MR × MP.

Split or unified L1: the paradox of Example 6

The first-level cache can be built in two ways (p. 258). A unified cache holds instructions and data together. A split cache, separate instruction and data caches (the notes write I$ and D$), is also called the Harvard architecture.

The 5-stage pipeline of lesson 1 makes the choice concrete. In every cycle IF fetches an instruction while a load or store in MEM accesses data. A split L1 serves both at once; a unified cache with a single port serves one, and the other waits — a structural hazard of exactly the kind lesson 2 describes. Below, the load I0 reads memory in cycle 4, the cycle in which I3 should be fetched:

One data access, one lost cycle: 4 + 4 = 8 cycles with the split L1, 4 + 4 + 1 = 9 with the one-port unified cache (cycles = IC + 4 + stalls, lesson 3). Example 6 charges the cycle to the data access: "Data hit has 1 more stall for Unified cache (only one port)".

To average over all accesses, count how many are instruction fetches. Every instruction is fetched once, and a fraction d of the instructions are loads or stores with one data access each: 1 + d accesses per instruction, so

With d = 0.33, as in Example 6: 1 / 1.33 ≈ 0.75 and 0.33 / 1.33 ≈ 0.25. The notes print these two shares correctly, but their premise skips this very step:

Each stream then gets its own AMAT, and the two are weighted by their shares. This is the Harvard formula of the notes (eq. 51), also on the example formula sheet that the course page shows:

Now Example 6 (pp. 258–259): 16 KB instruction and data caches missing 0.64% and 6.47% of their accesses, against a 32 KB unified cache missing 1.99%; hit time 1 cycle, miss penalty 50 cycles.

Read the last two columns together. The unified cache misses less, because 32 KB shared between code and data adapt to whichever needs more room: on misses alone it would gain (2.10% − 1.99%) × 50 ≈ 0.05 cycles per access. But one access in four is a data access that waits a cycle for the port: 0.25 cycles per access. A quarter of a cycle lost against a twentieth gained: the unified cache ends up 0.2 cycles slower, 2.245 against 2.05 (the notes round 2.245 to 2.24).

Back to the two puzzles

The 94 cycles of the first puzzle were never spent: 95 accesses in 100 find their block in the cache, because the program reuses data and walks through neighbours, and pay one cycle; only 5 pay the trip. The illusion is an average that only locality keeps alive — the probe's random program pays 101 cycles per access. In the second puzzle the unified cache wins on miss rate and loses on AMAT, because its single port charges a cycle to every data access: the miss rate is one ingredient, the average access time is the measure.

Miss rate is not performance: compare AMATs. A split L1 misses a little more; a single-ported unified L1 pays a cycle on every data access.