Memory Hierarchy

Fundamentals of Computer Systems (8hrs) · Computer Fundamentals & Emerging Technologies

1. Why a Hierarchy is Needed

Three requirements pull in opposite directions:

Speed — the CPU must not wait long for data.
Capacity — the user wants to store huge programs and files.
Cost — fast memory is expensive (₹ per bit).

No single technology satisfies all three, so memory is built as a hierarchy: a few tiers of fast-but-small memory backed by slow-but-huge storage. As we move down the pyramid, capacity ↑, access time ↑, cost per bit ↓, frequency of CPU access ↓.

2. The Memory Pyramid

                      ▲ faster / smaller / costlier per bit
              ┌───────────────────┐
              │   REGISTERS  ← CPU│   hundreds of bytes, < 1 ns
              ├───────────────────┤
              │  L1 CACHE (SRAM)  │   32-64 KB per core, ~1 ns
              ├───────────────────┤
              │  L2 CACHE (SRAM)  │   256 KB - 2 MB, ~4 ns
              ├───────────────────┤
              │  L3 CACHE (SRAM)  │   8-32 MB shared, ~10-20 ns
              ├───────────────────┤
              │  MAIN MEMORY (DRAM)│  4-32 GB, ~50-100 ns
              ├───────────────────┤
              │  SSD (Flash)      │   256 GB - 1 TB, ~50-150 µs
              ├───────────────────┤
              │  HDD / TAPE       │   1-10 TB, ~5-10 ms
              └───────────────────┘
                      ▼ slower / larger / cheaper per bit

3. Level-by-Level Comparison

Level	Technology	Typical size	Access time	Managed by	Volatile?
Registers	Flip-flops in CPU	100s of bytes	< 1 ns (1 clock)	Compiler/programmer	Yes
L1 cache	SRAM	32-64 KB	1-2 ns	Hardware	Yes
L2 cache	SRAM	256 KB - 2 MB	3-10 ns	Hardware	Yes
L3 cache	SRAM	8-32 MB (shared)	10-30 ns	Hardware	Yes
Main memory	DRAM	4-32 GB	50-100 ns	OS (paging)	Yes
Secondary	SSD / HDD	256 GB - 10 TB	µs - ms	OS (file system)	No
Tertiary	Tape, optical jukebox	TB - PB	seconds	Operator/software	No

4. Design Principles of the Hierarchy

Inclusion — every level contains a copy of the data in the level above it (L1 ⊂ L2 ⊂ RAM ⊂ disk).
Block (line) transfer — data moves between adjacent levels in fixed blocks (typically 64 bytes), not one byte at a time.
Principle of locality — programs do not access memory uniformly:
- Temporal locality — a location accessed once is likely to be accessed again soon (loop body, counter).
- Spatial locality — neighbours of an accessed location are likely to be accessed soon (array traversal, sequential instructions).
Automatic movement — hardware moves blocks between cache levels; the OS moves pages between RAM and disk; the programmer only influences it (e.g. loop order).

5. Performance Measures

Hit — the requested block is found in the upper level; miss — it is not.
Hit ratio $h = \text{hits} / (\text{hits} + \text{misses})$ ; miss ratio $= 1 - h$ .
Hit time $T_1$ = time to access the fast level; miss penalty = time to fetch the block from the lower level.

Average access time for a two-level cache–memory system:

T_{ave} = h × T_1 + (1 - h) × T_2

Numerical: $h = 0.9$ , $T_1 = 5$ ns (cache), $T_2 = 50$ ns (DRAM):
$T_{ave} = 0.9 × 5 + 0.1 × 50 = 4.5 + 5 =$ 9.5 ns — versus 50 ns with no cache at all, i.e. a 5.3× improvement in average memory access time.

With an L2 in between (three levels):

T_{ave} = T_1 + (1 - h_1) × T_2 + (1 - h_1)(1 - h_2) × T_3

Adding a level helps only if the extra hit time it adds is smaller than the miss penalty it avoids.

6. Cache Basics (detail in the cache-impact topic)

Line/block size — 32-64 B typical; too small wastes locality, too large wastes bandwidth.
Mapping — direct, fully associative, set-associative (k-way).
Replacement — LRU, FIFO, random, LFU.
Write policy — write-through (simple, slow) vs write-back (fast, needs dirty bit).
Split caches — separate L1 instruction cache (I-cache) and data cache (D-cache) to avoid fetch/decode stalls.

7. Exam Points

Draw the memory hierarchy pyramid and explain each level with typical size and access time — 5-7 marks, very frequent.
Why is memory organised as a hierarchy? (speed-capacity-cost trade-off) — 3-5 marks.
Explain temporal and spatial locality with examples — 3-5 marks.
Numerical: given hit ratio and both access times, find average access time — 3-5 marks.
Compare SRAM, DRAM, SSD and HDD in one table — 5 marks.
Compare registers vs cache vs RAM vs disk in speed, cost and volatility — 5 marks.

Memory Hierarchy