The Memory Hierarchy

Computer Organization & Embedded System — Computer Arithmetic and Memory System, NEC licence examination syllabus (Nepal Engineering Council).

The Memory Hierarchy: why computers have so many kinds of memory

Fast memory is small and expensive. Big memory is slow and cheap. The hierarchy is the compromise.

AMAT = hit time + (miss rate × miss penalty) With mr = 10 %, pen = 80 ns, AMAT = 9, miss = 8.

At a 10% miss rate with an 80 ns penalty the average is 9 ns — nine times the 1 ns hit time, from misses alone.

No single memory technology is fast, huge, AND cheap all at once — so computers stack several kinds of memory in layers, fastest and smallest at the top, slowest and biggest at the bottom.

The whole hierarchy only works because of locality of reference — programs tend to reuse the same data and instructions repeatedly (temporal locality) and access nearby memory addresses together (spatial locality). This is why keeping recently/nearby-used data in fast memory actually helps.

💡 Be ready to define temporal vs spatial locality with a one-line example each: temporal = a loop variable reused every iteration; spatial = walking through an array element by element.

The numbers behind the pyramid

The shape only makes sense once you see how far apart the levels are. Taking one CPU cycle as roughly 1 ns:

Level Access time In CPU cycles ──────────────────────────────────────────────────────── Register 0.3 ns under 1 L1 cache 1 ns 1 L2 cache 4 ns 4 L3 cache 15 ns 15 Main memory (DRAM) 80 ns 80 SSD 100,000 ns 100,000 Hard disk 8,000,000 ns 8,000,000

The gaps are not incremental. Main memory is roughly 80 times slower than L1, and a hard disk is eight million times slower. A processor waiting on a disk read could have executed millions of instructions instead — which is why the hierarchy is not an optimisation but a necessity.

What a miss actually costs

The average access time is what the processor really experiences, and it is dominated by misses rather than hits.

AMAT = hit time + (miss rate × miss penalty) With a 1 ns hit and an 80 ns penalty: miss rate 1% AMAT = 1 + 0.01×80 = 1.80 ns miss rate 5% AMAT = 1 + 0.05×80 = 5.00 ns miss rate 10% AMAT = 1 + 0.10×80 = 9.00 ns miss rate 20% AMAT = 1 + 0.20×80 = 17.00 ns

A 10% miss rate makes memory nine times slower than the 1 ns hit time suggests. Ninety percent of accesses hit and the ten percent that miss dominate the average completely — which is why cache design is overwhelmingly about reducing the miss rate rather than shaving the hit time.

💡 It also explains why there are several cache levels rather than one. Each level exists to catch misses before they reach the next, so L2 turns an 80 ns penalty into a 4 ns one for most of them. Adding a level is worthwhile whenever it catches enough misses to pay for the delay it adds.

Why the hierarchy works at all

Keeping a small fast memory only helps if the data you need is likely to be in it. That it usually is comes down to locality.

📍 The two kinds of locality

TemporalData used recently is likely to be used again soon — a loop variable, a counter, the top of the stack.

SpatialData near what you just used is likely to be needed next — the following array element, the next instruction.

💡 Spatial locality is why a cache fetches a whole block rather than the single byte requested. It is also why walking an array is far faster than following a linked list of the same length: array elements arrive together in one block, while list nodes scattered across memory each cost their own miss — the cache-locality point from the linked-list topic, quantified here.

Syllabus points

Hierarchy levels; speed/cost/capacity tradeoff
Locality of reference (temporal, spatial)

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.