Think about how you study for an exam. The page you are reading right now is open on your desk. The few books you need this week are on the shelf next to you. The rest of your books are in a cupboard at home, and anything else is in the college library across town. You keep the things you use most closest to you, in the small but fast-to-reach places, and everything else further away, in big but slow places.
A computer stores data in exactly this way. No single kind of memory is fast, large and cheap all at once, so computers use several kinds of memory arranged in levels. This arrangement is called the memory hierarchy.
The memory hierarchy is the organization of a computer's storage into levels, from small, fast and expensive memory close to the CPU (registers, cache) to large, slow and cheap memory far from it (main memory, SSD, hard disk). Its goal is to give the CPU an average access time close to the fastest level at a cost per bit close to the cheapest level.
In this chapter we will see why a hierarchy is needed, what each level looks like in a real machine, why the idea works at all (locality of reference), and how to calculate average access time and average cost, which is the part exams love to ask.
Why Not Use Just One Kind of Memory?
Every memory technology sits somewhere on a three-way trade-off:
Speed (access time): how quickly a word can be read or written.
Capacity: how many bytes we can afford to have.
Cost per bit: how much each bit costs.
The rules of the trade-off are simple and always hold:
Faster memory costs more per bit.
Larger capacity means lower cost per bit.
Larger capacity also means slower access (signals travel further, decoders are bigger).
If we built all of a computer's memory from the fastest technology (the SRAM used in caches), a few gigabytes would be extremely expensive and would not even fit near the CPU. If we built it all from the cheapest technology (disk), the CPU would wait millions of cycles for every operand. The hierarchy is how we escape the trade-off.
There is a second reason. Processor speed improved much faster than DRAM latency for decades. A modern core can execute several instructions every nanosecond, but a trip to main memory takes tens of nanoseconds, which is hundreds of instruction slots. This growing difference is often called the processor–memory gap or the memory wall. Without fast levels in between, the CPU would spend most of its time waiting.
The Levels of the Hierarchy
/\
/ \ Registers fastest, smallest,
/----\ costliest per bit
/ L1 \ L1 cache (SRAM)
/--------\
/ L2 \ L2 cache (SRAM)
/------------\
/ L3 \ L3 cache (SRAM, shared)
/----------------\
/ Main memory \ DRAM
/--------------------\
/ SSD (flash) \ secondary storage
/------------------------\
/ Hard disk (HDD) \
/----------------------------\
/ Tape / archival / cloud \ slowest, largest,
/--------------------------------\ cheapest per bitThe table below gives typical orders of magnitude for a current desktop or laptop. Exact numbers vary from machine to machine; what matters is how many times bigger and slower each level is than the one above.
| Level | Technology | Typical size | Typical access time | Managed by |
|---|---|---|---|---|
| Registers | Flip-flops inside the CPU | Tens of registers (a few hundred bytes to a few KB) | Within one clock cycle (< 1 ns) | Compiler |
| L1 cache | SRAM, per core | 32–64 KB each for instructions and data | About 1 ns (a few cycles) | Hardware |
| L2 cache | SRAM, usually per core | 256 KB – 2 MB | A few ns (around 10–15 cycles) | Hardware |
| L3 cache | SRAM, shared by all cores | Several MB to tens of MB | About 10–20 ns | Hardware |
| Main memory | DRAM | 8–64 GB | About 50–100 ns | Operating system (with hardware) |
| SSD | NAND flash | 256 GB – a few TB | Tens of microseconds | OS / file system |
| Hard disk | Magnetic platters | 1 TB – 20+ TB | Several milliseconds | OS / file system |
| Tape / archive | Magnetic tape, cloud cold storage | Very large | Seconds to minutes | Backup software |
Look at the access times: from L1 to main memory is roughly 100 times slower, and from main memory to a hard disk is roughly 50,000 to 100,000 times slower. These huge ratios are why the hit ratio at each level matters so much, as we will calculate below.
For a concrete example, the machine used to run the C program in this chapter (an Intel Core i5-12400F with 6 cores) reports these caches on Linux with lscpu:
L1d cache: 288 KiB (6 instances) -> 48 KB of L1 data cache per core
L1i cache: 192 KiB (6 instances) -> 32 KB of L1 instruction cache per core
L2 cache: 7.5 MiB (6 instances) -> 1.25 MB of L2 per core
L3 cache: 18 MiB (1 instance) -> 18 MB shared by all coresNotice the pattern: small private caches close to each core, and one larger shared cache behind them.
Ways to Classify Memory
Exam questions often use these terms, so it is worth fixing them clearly.
| Basis | Types | Meaning |
|---|---|---|
| Location | Internal (primary) vs external (secondary) | Primary memory (registers, cache, main memory) is directly accessed by the CPU with load/store instructions. Secondary memory (SSD, disk) is accessed through I/O, and its data must be brought into main memory first. |
| Volatility | Volatile vs non-volatile | Volatile memory (SRAM, DRAM) loses its contents when power is removed. Non-volatile memory (ROM, flash, disk) keeps them. |
| Access method | Random, sequential, direct, associative | Random access: any location in the same time (RAM). Sequential: must pass through earlier data (tape). Direct: jump to a region, then search sequentially within it (disk: move to a track, then wait for the sector). Associative: locate data by comparing its content/tag with all entries at once (cache tags, TLB). |
| Changeability | Read-write vs read-only | RAM can be written as easily as it is read; ROM is written once or rarely. |
The details of RAM and ROM technologies are in RAM & ROM: SRAM, DRAM & Types of ROM, and disks and SSDs are covered in Secondary Storage: Magnetic Disks & SSDs.
Why the Hierarchy Works: Locality of Reference
A small fast memory only helps if the data the CPU wants next is usually already in it. Luckily, real programs behave very predictably.
Locality of reference is the tendency of a program to access a relatively small portion of its address space during any short period of time.
It comes in two main forms:
Temporal locality (locality in time): if an item is accessed now, it is likely to be accessed again soon. Examples: loop counters, a variable like
sumupdated every iteration, the instructions of a loop body, a function called repeatedly.Spatial locality (locality in space): if an item is accessed now, items at nearby addresses are likely to be accessed soon. Examples: walking through an array, executing instructions one after another, fields of the same struct.
(Some books also list sequential locality, the special case of spatial locality where addresses are accessed in increasing order, as in straight-line code.)
Look at a tiny loop:
int sum = 0;
for (int i = 0; i < 1000; i++)
sum += a[i];sumandiare used in every iteration: temporal locality. They will live in registers.The loop's instructions are executed 1000 times: temporal locality for instruction fetch.
a[0],a[1],a[2], … are at consecutive addresses: spatial locality.
The hierarchy exploits both:
To use temporal locality, keep recently used data in the faster level.
To use spatial locality, move data between levels in blocks (a cache line of, say, 64 bytes; a page of, say, 4 KB) instead of single words. One miss brings in the neighbours too.
Seeing Locality in Action
This C program adds up a 4096 × 4096 matrix of ints (64 MB, far larger than any cache) twice: once row by row and once column by column. Both loops do exactly the same additions.
#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 4096
static double seconds(void)
{
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec + ts.tv_nsec / 1e9;
}
int main(void)
{
int (*a)[N] = malloc(sizeof(int[N][N])); /* 4096 x 4096 ints = 64 MB */
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = 1;
long long sum = 0;
double t0 = seconds();
for (int i = 0; i < N; i++) /* row by row: consecutive addresses */
for (int j = 0; j < N; j++)
sum += a[i][j];
double t1 = seconds();
for (int j = 0; j < N; j++) /* column by column: jumps of 16 KB */
for (int i = 0; i < N; i++)
sum += a[i][j];
double t2 = seconds();
printf("sum = %lld\n", sum);
printf("row-major traversal: %.3f s\n", t1 - t0);
printf("column-major traversal: %.3f s\n", t2 - t1);
free(a);
return 0;
}Output on the i5-12400F machine (compiled with gcc -std=c17 -Wall -O1; your exact times will differ, but the gap will not):
sum = 33554432
row-major traversal: 0.006 s
column-major traversal: 0.216 sThe column-by-column loop is about 20 to 35 times slower (the exact factor changed from run to run on this machine), even though it does the same work. C stores a 2-D array row by row, so a[i][j] and a[i][j+1] are neighbours, but a[i][j] and a[i+1][j] are 4096 × 4 = 16 KB apart. The row-wise loop uses every byte of each 64-byte block it brings into the cache (good spatial locality). The column-wise loop uses just 4 bytes of each block before jumping away, so it keeps missing in the cache and waiting for main memory.
Properties of a Memory Hierarchy
Inclusion: data in a level is usually also present in the levels below it (whatever is in L1 is also in L2, in main memory and, for files, on disk). The lowest level holds everything. (Real multi-level caches may be designed as inclusive, exclusive or non-inclusive, so L2/L3 do not always hold a copy of everything in L1; the principle always holds for main memory and disk.)
Coherence: copies of the same data at different levels must be kept consistent. If the CPU changes a value in the cache, the lower levels must eventually be updated. How this is done is covered in Cache Replacement & Write Policies and, for multiple cores, in Multicore Processors & Cache Coherence.
Locality: as explained above, this is what makes the whole scheme effective.
Two more terms are used at every level:
Hit: the requested data is found in the level being checked. Hit ratio h = hits / total accesses.
Miss: it is not found, and must be fetched from a lower level. Miss ratio = 1 − h.
Average Access Time of a Two-Level Memory
Let level 1 (say, cache) have access time T1 and hit ratio h, and level 2 (say, main memory) have access time T2. There are two standard ways the levels can be accessed, and they give different formulas. Exam questions usually say which one to use; if they say nothing, read the question carefully, and state your assumption.
1. Hierarchical (Sequential, Look-Through) Access
The CPU first checks level 1. Only on a miss does it go to level 2. So a miss costs T1 (time wasted discovering the miss) plus T2.
T_avg = h x T1 + (1 - h) x (T1 + T2)
= T1 + (1 - h) x T22. Simultaneous (Parallel, Look-Aside) Access
The CPU sends the request to both levels at the same time. On a hit, level 1 answers in T1; on a miss, the answer arrives from level 2 in T2.
T_avg = h x T1 + (1 - h) x T2The simultaneous formula is always a little smaller, because it does not add T1 on a miss. Most modern cache hierarchies are effectively hierarchical (and the miss also includes transferring a whole block), which is what the "miss penalty" view in Cache Performance & Multi-level Caches builds on.
Worked Example 1
Cache access time = 10 ns, main memory access time = 100 ns, hit ratio = 0.9. Find the average access time.
Hierarchical: T = 10 + (1 - 0.9) x 100 = 10 + 10 = 20 ns
Simultaneous: T = 0.9 x 10 + 0.1 x 100 = 9 + 10 = 19 nsWithout a cache every access would take 100 ns. A cache that hits 90% of the time makes memory look about 5 times faster.
Worked Example 2: Required Hit Ratio
Same cache (10 ns) and memory (100 ns). What hit ratio is needed for an average access time of 15 ns?
Hierarchical: 10 + (1 - h) x 100 = 15
(1 - h) = 0.05 -> h = 0.95
Simultaneous: 10h + 100(1 - h) = 15
100 - 90h = 15 -> h = 85/90 = 0.944 (approx.)Access Efficiency
A handy measure of how well the hierarchy hides the slow level is the access efficiency:
e = T1 / T_avgIn Example 1 (hierarchical), e = 10 / 20 = 0.5: on average, memory behaves at half the speed of the cache. An efficiency close to 1 needs a hit ratio close to 1, especially when T2 is much larger than T1.
Why the Hit Ratio Must Be So High
Apply the same formula to main memory (100 ns) backed by a hard disk (5 ms = 5,000,000 ns), with a hit ratio in main memory of 99.9%:
T = 100 + 0.001 x 5,000,000 = 100 + 5000 = 5100 nsEven one miss in a thousand makes memory look 51 times slower. The bigger the speed ratio between two levels, the closer to 100% the hit ratio must be. That is why page faults must be extremely rare (see the Operating Systems tutorial's chapter on virtual memory).
Three or More Levels
The same reasoning extends to any number of levels. With hierarchical access, each level is checked only when all higher levels have missed. Let h1 be the hit ratio of L1 and h2 the hit ratio of L2 for the accesses that reach L2 (the local hit ratio), and let the last level always hit.
Hierarchical: T = T1 + (1 - h1) x [ T2 + (1 - h2) x T3 ]
Simultaneous: T = h1 x T1 + (1 - h1) x h2 x T2 + (1 - h1)(1 - h2) x T3Worked Example 3
L1: 1 ns, hit ratio 0.95. L2: 10 ns, hit ratio 0.9 (of the accesses that reach it). Main memory: 100 ns. Find the average access time.
Hierarchical:
T = 1 + 0.05 x [ 10 + 0.1 x 100 ]
= 1 + 0.05 x 20
= 2 ns
Simultaneous:
T = 0.95 x 1 + 0.05 x 0.9 x 10 + 0.05 x 0.1 x 100
= 0.95 + 0.45 + 0.5
= 1.9 nsOnly 0.05 × 0.1 = 0.5% of all accesses go to main memory. The CPU sees a memory that is almost as fast as L1 (2 ns) and almost as big as main memory.
Be careful with the wording "hit ratio of L2". If a question gives a global hit ratio (fraction of all CPU accesses that hit in L2), convert it before using the formulas above. Multi-level cache formulas and local vs global miss rates are treated in depth in Cache Performance & Multi-level Caches.
Average Cost per Bit
The other half of the bargain is cost. If level i has size Si and cost per unit size Ci, the average cost per unit size of the whole system is:
C_avg = (C1 x S1 + C2 x S2) / (S1 + S2)Worked Example 4
A two-level memory has 512 KB of fast memory costing 20 units per KB and 16 MB (16,384 KB) of slow memory costing 0.5 units per KB. Find the average cost per KB.
Total cost = 512 x 20 + 16384 x 0.5 = 10240 + 8192 = 18432 units
Total size = 512 + 16384 = 16896 KB
C_avg = 18432 / 16896 = 1.09 units per KB (approx.)The average cost (1.09) is very close to the cheap memory's cost (0.5) and far from the fast memory's cost (20), because S2 is much larger than S1. Combine this with Example 1 (speed close to the fast memory) and you have the whole point of a memory hierarchy: speed of the top, cost of the bottom.
Who Moves Data Between Levels?
| Between | Unit transferred | Typical size | Decided by |
|---|---|---|---|
| Registers ↔ cache | Word | 4–8 bytes | Compiler (load/store instructions, register allocation) |
| Cache ↔ main memory | Block (cache line) | 32–128 bytes, commonly 64 | Cache controller hardware |
| Main memory ↔ disk/SSD | Page | Commonly 4 KB | Operating system (virtual memory), with MMU/TLB hardware support |
| Disk ↔ tape/archive | File | Any size | User / backup software |
Notice how the unit grows as we go down. Lower levels are slow to start an access but can then transfer many bytes quickly, so it pays to move bigger chunks, and spatial locality makes those extra bytes useful. The hardware view of pages is covered in Virtual Memory & TLB (Hardware View).
Common Mistakes
Mixing up the two access-time formulas. Hierarchical: T1 + (1 − h)T2. Simultaneous: hT1 + (1 − h)T2. Read whether levels are searched one after another or in parallel.
Using a global hit ratio as a local one (or the other way round) in three-level problems.
Thinking "faster" means "bigger". Going up the hierarchy, memory gets faster but smaller and costlier per bit.
Confusing temporal and spatial locality. Same item again = temporal. Nearby item = spatial.
Calling cache "secondary memory". Cache and main memory are both primary (internal) memory; secondary memory is disk/SSD.
Assuming a small miss rate is harmless. With a 1:50,000 speed ratio, even 0.1% misses can dominate the average time.
GATE / Interview Questions
Why do computers use a memory hierarchy instead of one large fast memory?
Fast memory is expensive per bit and cannot be made large and still fast; large memory is cheap but slow. A hierarchy, combined with locality of reference, gives an average access time close to the fastest level at an average cost close to the cheapest level.
Define temporal and spatial locality with one example each.
Temporal: a recently accessed item is likely to be accessed again soon (a loop counter, a loop's instructions). Spatial: items near a recently accessed address are likely to be accessed soon (consecutive array elements, sequential instructions).
A cache has access time 20 ns and main memory 120 ns. With a hit ratio of 0.8 and hierarchical access, what is the average access time?
T = 20 + (1 − 0.8) × 120 = 20 + 24 = 44 ns. (With simultaneous access it would be 0.8 × 20 + 0.2 × 120 = 16 + 24 = 40 ns.)
With cache 10 ns and memory 100 ns (hierarchical access), what hit ratio gives an average of 15 ns?
10 + (1 − h) × 100 = 15, so 1 − h = 0.05 and h = 0.95.
Which access method does a hard disk use, and which does a cache tag lookup use?
A hard disk uses direct access (move to the track, then wait sequentially for the sector). Cache tag lookup (in an associative cache) and the TLB use associative access, comparing the tag with many entries in parallel.
Why does the unit of transfer get bigger at lower levels of the hierarchy?
Lower levels have a high fixed cost to start an access (latency) but good transfer rates afterwards, so moving larger chunks amortizes the latency. Spatial locality makes it likely that the extra data will be used.
Why is column-wise traversal of a large C array much slower than row-wise traversal?
C uses row-major order. Row-wise traversal touches consecutive addresses, so each cache block brought in is fully used. Column-wise traversal jumps by a whole row each time, using only one element per block, so it misses in the cache far more often.
Summary
No memory is fast, large and cheap at once, so computers use a hierarchy: registers, L1/L2/L3 cache (SRAM), main memory (DRAM), SSD/disk, archive.
Going down: larger, slower, cheaper per bit, and larger transfer units (word, block, page, file).
It works because of locality of reference: temporal (reuse soon) and spatial (neighbours soon). Our C test showed a 20–35× slowdown when spatial locality was destroyed.
Two-level average access time: hierarchical T = T1 + (1 − h)T2; simultaneous T = hT1 + (1 − h)T2. For 10 ns / 100 ns / h = 0.9: 20 ns and 19 ns.
For three levels, nest the formula: T = T1 + (1 − h1)[T2 + (1 − h2)T3] with local hit ratios.
Average cost per bit = ΣCiSi / ΣSi, which stays close to the cheapest level's cost.
Key properties: inclusion, coherence, locality.
Next, in RAM & ROM: SRAM, DRAM & Types of ROM, we open up the memory chips themselves and see why SRAM is fast and DRAM is dense.