A large cache holds a lot but is slow; a small one is fast but misses often. Since we can’t build a cache that’s both large and fast, what if we used several caches of different sizes?
Put a larger, slower cache below a small, fast one. Thanks to locality, most accesses end in the small, fast cache at the top, and we go down only when it isn’t there. On average, this finds values faster than one large cache.
Stacking stores in layers like this, small and fast near the CPU and large and slow farther away, is called the memory hierarchy.
The table below gives rough values for today’s desktop CPUs. A cycle is the time for the clock to go from 0 to 1 and back once.
| Layer | Capacity | Speed |
|---|---|---|
| Registers | Tens | 1 cycle |
| L1 cache | Tens of KB | ~5 cycles |
| L2 cache | Hundreds of KB to a few MB | ~15 cycles |
| L3 cache | Tens of MB | ~50 cycles |
| RAM | A few to tens of GB | ~400 cycles |
The CPU looks in L1 first; if it isn’t there, it goes down through L2 and L3 to RAM. A value found in a lower layer is also put into the upper layers it passed through.
The second read of an address is found in L1. An address evicted from an upper layer has to be found further down. The demo’s L1 has only 2 slots, so things are evicted quickly, but a real L1 holds tens of KB, so most accesses end there. So the CPU works as if it were using one large, fast memory.
Below RAM are storage devices like SSDs and HDDs. Going all the way down there, access time grows to hundreds of thousands of cycles for an SSD and tens of millions for an HDD.

Thanks to the memory hierarchy, the CPU waits less for memory. That’s the hardware that makes up a computer; from here on we look at the software that runs on top of it. In the next post, let’s start with how to write programs in a language closer to how people think than assembly.
There are setups A and B shown in the figure below. We look from the top layer down, the time taken is the sum of the cycles of every layer passed, a value found in a lower layer is also put into the upper layers passed, and when a layer is full it evicts the one used longest ago. Reading addresses 0, 1, …, k − 1 in order over and over, what is the smallest k for which, from the second round on, one access takes longer in A than in B? Answer with a number.
Loading…