Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 67 ยท Memory Hierarchy

The Memory Hierarchy and Locality

Understand why computers use layers of memory from registers to disk, how speed, size and cost trade off, and how to measure temporal and spatial locality.

Every instruction a CPU runs needs data, and the data has to live somewhere. The ideal memory would be as fast as a register, as big as a disk and as cheap as a disk. No such technology exists: fast memory is small and expensive, big memory is slow and cheap. Computer designers do not pick one compromise. They stack several, so that most of the time the program sees something that is almost as fast as the smallest layer and almost as large as the biggest one.

This trick works because of a property of programs called locality. In this lesson you will see the layers, the numbers that separate them, and measure locality in access traces with Python. The next lessons zoom into each layer, starting with RAM, ROM, SRAM, DRAM and Flash and cache memory.

The layers

From the CPU outwards, each layer is bigger, slower and cheaper per byte than the one before it:

flowchart TD
  R["Registers<br/>~1 KB, under 1 ns"] --> L1["L1 cache<br/>32-64 KB, ~1 ns"]
  L1 --> L2["L2 cache<br/>256 KB - 2 MB, ~4 ns"]
  L2 --> L3["L3 cache<br/>4-64+ MB, ~15 ns"]
  L3 --> M["Main memory (DRAM)<br/>GBs, ~80 ns"]
  M --> S["SSD<br/>100s of GB, ~80 us"]
  S --> H["Hard disk / network<br/>TBs, ~8 ms"]

The memory hierarchy: moving down the page, capacity grows and speed drops.

Typical figures for a desktop machine (they vary by model and year, so treat them as orders of magnitude):

Level Typical size Typical latency Managed by
Registers a few hundred bytes to a few KB under 1 ns compiler
L1 cache 32 to 64 KB per core about 1 ns hardware
L2 cache 256 KB to 2 MB per core about 4 ns hardware
L3 cache 4 to 64 MB or more, shared about 15 ns hardware
Main memory (DRAM) 8 to 128 GB about 80 ns OS and hardware
SSD 256 GB to several TB tens of microseconds OS
Hard disk 1 to 20 TB several milliseconds OS

Registers are named by the program. Caches are invisible: the hardware decides what to keep. Main memory and below are managed by the operating system, which also provides virtual memory.

The gaps between levels are huge. It helps to rescale time so that one nanosecond lasts one second.

Python Memory latency in human time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On that scale an L1 hit takes a second, a trip to main memory takes about a minute and a half, and a hard disk read takes three months. A program that waited for DRAM on every access would spend nearly all its time idle.

The principle of locality

Programs do not touch memory at random. Two patterns dominate, and the hierarchy is built to exploit both.

Temporal locality: an address used recently is likely to be used again soon. Loop counters, accumulators, the stack frame of the running function and hot functions called repeatedly are all examples. The response is to keep recently used data close: after the first access, put the value in a faster level.

Spatial locality: an address near a recently used one is likely to be used soon. Walking through an array, executing the next instruction, or reading the fields of a struct are all examples. The response is to move data in blocks: when you fetch one byte, bring in its neighbours too (a cache block is commonly 64 bytes).

A rule of thumb from measurements on real programs: about 90% of the execution time is spent in about 10% of the code, and the same skew applies to data. That is why a cache holding a tiny fraction of memory can still serve most accesses.

flowchart LR
  A["Access to address A"] --> T["Same address again soon<br/>= temporal locality"]
  A --> S["Nearby address soon<br/>= spatial locality"]
  T --> K["Keep it in a fast level"]
  S --> B["Fetch the whole block"]

Each kind of locality suggests a different hardware trick.

Measuring locality in a trace

An address trace is the list of memory addresses a program touched, in order. We can score a trace by looking at a sliding window of the last 16 accesses: an access is temporal if the exact address is in the window, and spatial if it is a different address in the same or a neighbouring 64-byte block as something in the window.

Python Score the locality of five access patterns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output separates the patterns cleanly:

  • Sequential ints have 100% spatial and 0% temporal locality: every address is new, but always next to the previous one. Block fetching turns 16 accesses into one memory transfer.
  • A stride of 256 bytes skips four blocks each step. It uses one int out of every 64 bytes fetched, so it has neither kind of locality in the window and wastes bandwidth.
  • Random addresses in 1 MB have almost none of either, and the hierarchy cannot help much.
  • The loop over 8 ints is almost purely temporal (99.8%): the same 8 words again and again.
  • Eight hot but scattered addresses are temporal (88.5%) even though they are far apart, because a window of 16 accesses usually contains the address being accessed. The rest of the time one of the eight addresses has not shown up recently.

Locality in your own code

The same array can be walked with very different locality, depending on loop order. Take a 64 x 64 matrix of 4-byte integers stored row by row (row-major, as in C, Java and NumPy's default). Walking it by rows touches consecutive addresses. Walking it by columns jumps 256 bytes each step.

Python Row order versus column order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Row order moves to a new block only once every 16 accesses (a 64-byte block holds sixteen 4-byte values), so the other 15 accesses are served from the block already fetched. Column order changes block on every single access. The second half of the output shows why that matters: with a 1 ns fast level and a 100 ns slow level, an 80% hit rate gives an average of 20.8 ns, while a 99% hit rate gives 1.99 ns. A few percent of hit rate changes performance by a factor of ten. You will turn this idea into a formula, the average memory access time, in Cache Memory Basics.

How the hierarchy behaves as a system

Three properties hold the design together:

  1. Inclusion: in many designs everything in a faster level also exists in the level below it, so data can be dropped from a cache without being lost. (Some CPUs make the L2 and L3 exclusive to save space.)
  2. Unit of transfer: caches move blocks (also called lines, typically 64 bytes), memory moves pages (typically 4 KB) to and from disk, and disks move sectors.
  3. Hit and miss: a hit is served by the current level; a miss sends the request one level down and brings the block back up, usually evicting something else.

When your program runs slowly although the CPU is not the bottleneck, the first suspect is almost always the hierarchy: too much data for the cache, or an access pattern without locality. Writing Cache- and CPU-Friendly Code returns to this with practical advice.

Memory units, magnetic disk and tape in the hierarchy

Every level of the hierarchy has a typical capacity, and exam questions expect you to know the order of magnitude. The binary units are powers of 1,024: 1 KiB = 2^10 bytes, 1 MiB = 2^20, 1 GiB = 2^30, 1 TiB = 2^40, 1 PiB = 2^50. Storage vendors often use powers of ten (1 GB = 10^9 bytes), which is why a "1 TB" disk shows as about 931 GiB in an operating system.

Level Typical capacity Typical access time Access method
Registers Tens to hundreds of bytes Under 1 ns Direct
L1 / L2 / L3 cache 32 KiB to tens of MiB 1 to 20 ns Direct (associative)
Main memory (DRAM) Gigabytes 50 to 100 ns Random
Solid-state drive Hundreds of GB to TB 10 to 100 microseconds Random, in blocks
Magnetic disk (HDD) Terabytes 5 to 10 ms Semi-random: seek, then rotate
Magnetic tape Many terabytes per cartridge Seconds to minutes Sequential

Magnetic disk

A hard disk keeps bits as magnetic regions on rotating platters. Reading a block takes seek time (moving the head to the right track) plus rotational latency (waiting for the sector to come under it, on average half a revolution) plus transfer time. The details, and SSDs and RAID, are in Disks, SSDs and RAID.

Magnetic tape

Tape is a long strip of magnetic film wound on reels or in a cartridge. It is sequentially accessed: to reach data in the middle, the drive must wind past everything before it, so the average access time is very long. But once the head is positioned, the streaming transfer rate is high, tape is cheap per terabyte, a cartridge can be stored offline for decades and is immune to online attacks. That makes it the medium of choice for archives and backups in data centres, while disks and SSDs serve data that must be reached quickly.

Python Access time: disk versus tape

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers are illustrative, but they show the pattern: a disk is far better for one random block, while for a long sequential read tape keeps up (sometimes beating a single disk) at a much lower cost per terabyte. This is the memory hierarchy principle again: the faster the level, the smaller and more expensive it is, and each slower level exists to hold what is too big or too rarely used for the level above. See The Memory Hierarchy and Locality for why the layering works at all.

Tertiary and offline memory

Below the disks the textbooks add two more levels.

  • Primary memory is what the CPU addresses directly: registers, cache and main memory.
  • Secondary memory is online mass storage the operating system can reach at any moment: HDDs and SSDs.
  • Tertiary memory is a large, slow level reached through a robot or an operator: a tape library or an optical-disc jukebox. Cartridges are mounted on demand, so access takes seconds to minutes.
  • Offline memory is removable media that sits on a shelf until someone connects it: tapes, optical discs, external drives and USB sticks. It is used for backups, transport and long-term archives.

One more detail explains how a machine starts. Main memory (DRAM) is volatile and empty at power-on, yet the CPU needs instructions at once. A small non-volatile ROM or flash chip therefore holds a bootstrap loader (the firmware). It tests the hardware, finds the operating system on secondary memory, copies the kernel into RAM and jumps to it. From then on, programs run from RAM and the disks supply the rest.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is a memory hierarchy used instead of one big fast memory?

    Speed, size and cost trade off against each other. Layers give most of the speed of the small level and most of the capacity of the large one.
  2. 2. Which of these is an example of spatial locality?

    Consecutive elements sit at neighbouring addresses. Reusing the same address is temporal locality.
  3. 3. How does hardware exploit temporal locality?

    If data was used recently it will probably be used again, so it is worth keeping close. Fetching whole blocks is the response to spatial locality.
  4. 4. A 64-byte block holds 4-byte integers. Walking a large array in order, how many accesses are served per block fetched from the next level?

    64 / 4 = 16 integers per block: one miss brings the block in and the next 15 accesses hit.
  5. 5. On the one-nanosecond-equals-one-second scale, roughly how long does a main-memory access of 80 ns take?

    80 ns becomes 80 seconds, which is about 1.3 minutes. A hard disk read is the one that takes months.

Summary

  • The memory hierarchy stacks small fast layers on top of large slow ones so that the program sees speed close to the top and capacity close to the bottom.
  • Latency steps are large: roughly 1 ns for L1, 80 ns for DRAM, tens of microseconds for SSD and milliseconds for a hard disk.
  • Temporal locality (reuse of the same address) is exploited by keeping data close; spatial locality (use of nearby addresses) is exploited by moving data in blocks.
  • Access patterns decide how well the hierarchy works: sequential access and small working sets are good, large strides and random access are bad.
  • A few percentage points of hit rate can change average access time by a large factor.

Next, look at how each layer stores its bits in RAM, ROM, SRAM, DRAM and Flash.