yeolyi.comSeongyeol's CS

The Memory Hierarchy

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?

The memory hierarchy

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.

LayerCapacitySpeed
RegistersTens1 cycle
L1 cacheTens of KB~5 cycles
L2 cacheHundreds of KB to a few MB~15 cycles
L3 cacheTens of MB~50 cycles
RAMA 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.

Address to read
L1
··
~5 cycles
L2
····
~15 cycles
L3
········
~50 cycles
RAM
Holds every address
~400 cycles
  1. Press the same address twice.
  2. Press several different addresses.

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.

An HDD with its cover off. The platter spins, and the head at the end of the arm has to move into place before it can read (photo: Evan-Amos · CC BY-SA 3.0, background removed)
An HDD with its cover off. The platter spins, and the head at the end of the arm has to move into place before it can read (photo: Evan-Amos · CC BY-SA 3.0, background removed)

Wrapping up

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.

Challenge

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…