Locality & the Memory Hierarchy

Fast memory is small and expensive; big memory is cheap and slow. A memory hierarchy gets us the illusion of “big, fast and cheap” — and it only works because of locality. Final Q3(a) is “explain the principle of locality” or “diagram the memory hierarchy.”

1. The principle of locality

Programs don't touch memory randomly. They reuse things, and they touch neighbours. Two flavours:

Temporal locality — in time
If an item is referenced, it will probably be referenced again soon.

Example: a loop counter or a variable used every iteration. Fix: keep recently-used items in the cache.

Spatial locality — in space
If an item is referenced, items near it will probably be referenced soon.

Example: stepping through an array, or the next instruction. Fix: move data in blocks, not single words.

Locality is why a hierarchy is a good idea: keep the small set of currently-hot data in fast memory and most accesses hit there.

2. The memory hierarchy

Multiple levels of memory: the closer to the CPU, the smaller, faster and costlier per bit. Each level acts as a cache for the level below it.

As distance from the CPU grows, both size and access time increase — the essence of a memory hierarchy.

3. Hit, miss & the vocabulary

Term	Meaning
Block (line)	The unit of data copied between levels (exploits spatial locality).
Hit	The requested data is in the upper level.
Miss	Not there — fetch the block from the level below (a penalty).
Hit rate	Fraction of accesses that hit: $\text{hits}/\text{accesses}$ .
Miss rate	$1 - \text{hit rate}$ .
Hit time	Time to access the upper level (including the hit/miss check).
Miss penalty	Extra time to fetch the block from below on a miss.

Average memory access time (AMAT):

\text{AMAT} = \text{Hit time} + \text{Miss rate}\times\text{Miss penalty}

Section checklist

Define temporal vs spatial locality with an example of each.
Draw the pyramid: registers → cache (SRAM) → main memory (DRAM) → disk, with the two trade-off arrows (speed/cost vs capacity).
Know hit, miss, hit rate, miss penalty, and AMAT.