These are the notes for CS Fundamentals for Placements, episode 8. Last episode the CPU learned its language: instructions and addressing modes. Nearly every instruction reaches into memory, so here you design that memory yourself, one problem at a time: why no single memory can be fast, big and cheap, the memory hierarchy pyramid (registers, cache, main memory, secondary and tertiary storage), access time, capacity and cost per bit, volatile vs non-volatile memory, temporal and spatial locality, hit ratio and the hierarchical access time numericals, SRAM vs DRAM and DRAM refresh, ROM, PROM, EPROM, EEPROM and flash, HDD vs SSD, latency vs bandwidth, byte- vs word-addressable memory and memory interleaving. Every term is explained in plain words, and there is a full glossary at the end. All outputs below are real: every program was run with Python 3.13. Prices and timings in the demos are made-up round numbers chosen to show the shape of the problem, not real product figures.
A quick refresher: a bit is one 0 or 1, a byte is 8 bits, a word is a fixed group of bytes a CPU handles at once (say 4 or 8). An address is the number of a memory box. A GiB (gibibyte) is 2³⁰ bytes. The CPU reads and writes memory on almost every instruction (episodes 6 and 7).
The seven problems
| Problem | What it teaches |
|---|---|
| One memory that is fast, big and cheap? | Access time, capacity, cost per bit, the memory hierarchy, volatile vs non-volatile |
| Why does a tiny memory help? | Temporal and spatial locality, loop order |
| How fast is it on average? | Hit, miss, hit ratio, simultaneous vs hierarchical access time, 3-level numericals |
| What is a bit made of? | SRAM vs DRAM, transistor, capacitor, DRAM refresh |
| Memory that survives power off | ROM, PROM, EPROM, EEPROM, flash, firmware |
| Disks and links | HDD vs SSD, seek time, rotational latency, latency vs bandwidth |
| A busy memory chip | Byte- vs word-addressable memory, memory interleaving (low- and high-order) |
Problem 1: fast, big and cheap? (the memory hierarchy)
You are designing a computer. From its memory you want three things:
| Want | Plain meaning | Example |
|---|---|---|
| Short access time | How long one read or one write takes | 1 ns (nanosecond = 10⁻⁹ s, a billionth of a second) |
| Big capacity | How much it holds | 64 GiB |
| Low cost per bit | Price ÷ number of bits stored | Rs 300 per GiB is cheaper per bit than Rs 5000 per GiB |
The failing attempt: one kind of memory everywhere
The obvious plan: pick the single best memory and use only that. Made-up round numbers with the right shape:
# build a computer from ONE kind of memory
# made-up round numbers, just to show the shape
kinds = { # name: (ns per access, rupees per GiB)
"SRAM": (1, 5000),
"DRAM": (60, 300),
"disk": (5_000_000, 3)}
need_gib, accesses = 64, 1_000_000_000
for name, (ns, rs) in kinds.items():
cost = need_gib * rs
secs = accesses * ns / 1e9
print(f"all {name:4}: Rs {cost:>7,} time {secs:>9,.0f} s")
Output:
all SRAM: Rs 320,000 time 1 s
all DRAM: Rs 19,200 time 60 s
all disk: Rs 192 time 5,000,000 s
- All SRAM (the fast kind): 1 second, but Rs 3.2 lakh for the memory.
- All disk: Rs 192, but 5,000,000 seconds, about 58 days for one program.
- Why it fails: fast memory is expensive per bit and cheap memory is slow. No single technology is fast, big and cheap at the same time.
The fix: stack several memories (the pyramid)
Real-life example: studying for an exam.
| Your study | A computer |
|---|---|
| The pen in your hand: instant, holds almost nothing | Registers: tiny storage boxes inside the CPU (episode 6), fastest of all |
| Books open on your desk: a few, within reach | Cache: a small, very fast memory holding copies of the data in use right now |
| The shelf in your room: many books, a walk away | Main memory (RAM): where running programs and their data live |
| The city library: everything, a bus ride away | Secondary storage: SSD or hard disk, files kept for good |
| The state archive warehouse: rarely visited | Tertiary storage: tape libraries and optical discs for backups and archives |
/\ registers fastest, smallest, costliest per bit
/ \ cache (L1, L2, L3)
/ \ main memory (DRAM)
/ \ secondary storage (SSD, hard disk)
/________\ tertiary storage (tape, optical) slowest, biggest, cheapest per bit
- This stack is the memory hierarchy. Going down: bigger, slower, cheaper per bit. Going up: smaller, faster, costlier per bit.
- Cache usually comes in levels: L1 (smallest, fastest, closest to the CPU), then L2, then L3.
- The CPU only talks to the top; data is copied between neighbouring levels as needed.
- Volatile memory loses its data when power goes: registers, cache, RAM (that's why an unsaved file is lost in a power cut). Non-volatile memory keeps it: SSD, hard disk, tape, ROM, flash.
- Goal: feel almost as fast as the top, cost almost as little as the bottom. Problem 2 shows why that works; Problem 3 measures it.
- RAM stands for random-access memory: any address can be read in about the same time, unlike a tape that must be wound to the right place.
Problem 2: why does a tiny memory help? (locality)
Real-life example: what you reach for while studying.
| You... | Name |
|---|---|
| Look up the same formula 20 times, so that book stays on the desk | Temporal locality |
| Read page 41, then 42, then 43, so you bring the whole chapter | Spatial locality |
| Need a random library book every minute: the desk doesn't help | No locality |
A tiny cache that counts hits
Our "desk" holds 4 blocks; a block is 4 neighbouring memory words. If the needed block is already there, it's a hit; if not, a miss: bring the block in and throw out the oldest one.
import random
def hits(addresses, slots=4, block=4):
desk, hit = [], 0 # a tiny cache: 4 blocks
for a in addresses:
b = a // block # which block of 4 words
if b in desk: hit += 1; desk.remove(b)
elif len(desk) == slots: desk.pop(0)
desk.append(b) # most recent at the end
return f"{hit}/{len(addresses)} hits"
rng = random.Random(7)
same = [500, 501] * 32 # the same two variables
seq = list(range(64)) # a[0], a[1], ... a[63]
rand = [rng.randrange(4096) for _ in range(64)]
print("same vars :", hits(same))
print("sequential:", hits(seq))
print("random :", hits(rand))
Output:
same vars : 63/64 hits
sequential: 48/64 hits
random : 0/64 hits
- Same two variables: only the very first access misses: 63/64.
- Sequential array: each miss brings 4 neighbours, so 3 of every 4 accesses hit: 48/64.
- Random addresses: 0/64. A small cache can't help a program with no pattern. Real programs are not random.
Temporal and spatial locality
| Kind | Plain meaning | Examples in code |
|---|---|---|
| Temporal locality (locality in time) | Data used now will likely be used again soon | loop counter i, a running total, the instructions of a loop body |
| Spatial locality (locality in space) | If you use one address, you'll likely use its neighbours soon | a[0], a[1], a[2]..., instructions running one after another |
Together this is locality of reference. Caches exploit both: keep recently used data (temporal) and fetch whole blocks of neighbours (spatial).
The trap: walking a 2D array the wrong way
An 8 × 8 grid (a 2D array) is stored row by row (row-major order, as in C, C++, Java and Python lists of rows): a[r][c] is at address r*8 + c. First, adding it up column by column:
def hits(addresses, slots=4, block=4):
desk, hit = [], 0
for a in addresses:
b = a // block
if b in desk: hit += 1; desk.remove(b)
elif len(desk) == slots: desk.pop(0)
desk.append(b)
return f"{hit}/{len(addresses)} hits"
N = 8 # 8 x 8 grid stored row by row: a[r][c] at r*8 + c
col = [r * N + c for c in range(N) for r in range(N)]
print("column by column:", hits(col))
Output:
column by column: 0/64 hits
Going down a column jumps 8 addresses each step, so each access lands in a different block and the 4-block desk is full before we come back. The fix is to swap the loops and walk in storage order:
def hits(addresses, slots=4, block=4):
desk, hit = [], 0
for a in addresses:
b = a // block
if b in desk: hit += 1; desk.remove(b)
elif len(desk) == slots: desk.pop(0)
desk.append(b)
return f"{hit}/{len(addresses)} hits"
N = 8 # 8 x 8 grid stored row by row: a[r][c] at r*8 + c
col = [r * N + c for c in range(N) for r in range(N)]
print("column by column:", hits(col))
row = [r * N + c for r in range(N) for c in range(N)]
print("row by row :", hits(row))
Output:
column by column: 0/64 hits
row by row : 48/64 hits
Same grid, same sum, 48 hits instead of 0. In C:
for (int r = 0; r < N; r++) // good: row by row, matches storage
for (int c = 0; c < N; c++)
total += a[r][c];
Problem 3: how fast is it on average? (hit ratio and access time)
- Hit: the data is found in the cache. Miss: it isn't, so a lower level must be used.
- Hit ratio H = hits ÷ total accesses. 48 hits out of 64 → H = 0.75. Miss ratio = 1 − H.
- Let t1 = cache access time, t2 = main memory access time.
| Access style | Plain meaning | Average access time |
|---|---|---|
| Simultaneous | Both levels are searched at the same time; a miss costs only t2 | T = H·t1 + (1 − H)·t2 |
| Hierarchical (sequential, look-through) | The cache is checked first; only on a miss go to memory, so a miss costs t1 + t2 | T = H·t1 + (1 − H)·(t1 + t2) = t1 + (1 − H)·t2 |
Exam questions state which one they mean ("the cache is checked first" = hierarchical). If they don't say, hierarchical is the usual reading in most textbooks, but write your assumption.
For three levels (L1, L2, RAM), hierarchical, with h1 = L1 hit ratio and h2 = L2 hit ratio among L1 misses (a local hit ratio):
T = h1·t1 + (1 − h1)·h2·(t1 + t2) + (1 − h1)·(1 − h2)·(t1 + t2 + t3)
# two levels: cache 2 ns, main memory 100 ns
t1, t2 = 2, 100
for h in [0.80, 0.90, 0.95, 0.99]:
sim = h * t1 + (1 - h) * t2 # both at once
hier = h * t1 + (1 - h) * (t1 + t2) # cache, then RAM
print(f"H={h:.2f} simultaneous={sim:5.1f} ns "
f"hierarchical={hier:5.1f} ns")
# three levels: L1 1 ns, L2 10 ns, RAM 100 ns, hierarchical
h1, h2 = 0.90, 0.80 # h2 = L2 hits among L1 misses
t = h1 * 1 + (1 - h1) * h2 * (1 + 10) \
+ (1 - h1) * (1 - h2) * (1 + 10 + 100)
print(f"3 levels: average = {t:.2f} ns")
Output:
H=0.80 simultaneous= 21.6 ns hierarchical= 22.0 ns
H=0.90 simultaneous= 11.8 ns hierarchical= 12.0 ns
H=0.95 simultaneous= 6.9 ns hierarchical= 7.0 ns
H=0.99 simultaneous= 3.0 ns hierarchical= 3.0 ns
3 levels: average = 4.00 ns
- With memory 50 times slower than the cache (100 ns vs 2 ns), 99% hits give an average of 3 ns. That is the pyramid working.
- 3 levels: 0.9 × 1 + 0.1 × 0.8 × 11 + 0.1 × 0.2 × 111 = 0.9 + 0.88 + 2.22 = 4.00 ns.
- Average cost per bit of a hierarchy works the same way, weighted by size: (c1·S1 + c2·S2) ÷ (S1 + S2). With the made-up prices of Problem 1, 1 GiB of SRAM + 63 GiB of DRAM costs (5000 + 63 × 300) ÷ 64 = Rs 373.4 per GiB, close to DRAM's price.
Problem 4: what is a bit made of? (SRAM, DRAM, refresh)
Real-life example: two ways to remember a 1.
| At home | In a memory chip |
|---|---|
| A light switch: stays on until you flip it | SRAM (static RAM): each bit is a flip-flop (episode 5), typically six transistors. Holds its value as long as power is on, no refresh |
| A leaky bucket: full = 1, empty = 0, slowly drains | DRAM (dynamic RAM): each bit is one transistor + one capacitor. The charge leaks, so it must be refreshed |
- A transistor is a tiny electronic switch. A capacitor is a part that stores electric charge, like a tiny bucket for electricity.
- Fewer parts per bit make DRAM denser (more bits per chip) and cheaper per bit, but slower than SRAM.
The failing attempt: DRAM with no refresh
A pretend DRAM where 20% of each capacitor's charge leaks every millisecond (made-up rate); above half full reads as 1:
# DRAM: each bit is charge in a tiny leaky capacitor
# made-up leak: 20% of the charge escapes every ms
def read(bits, ms, refresh_every=None):
charge = [1.0 if b else 0.0 for b in bits]
for t in range(1, ms + 1):
charge = [c * 0.8 for c in charge] # leak
if refresh_every and t % refresh_every == 0:
charge = [1.0 if c > 0.5 else 0.0
for c in charge] # refresh
return [1 if c > 0.5 else 0 for c in charge]
stored = [1, 0, 1, 1, 0, 1, 0, 1]
print("stored :", stored)
print("after 1 ms :", read(stored, 1))
print("after 10 ms :", read(stored, 10))
Output:
stored : [1, 0, 1, 1, 0, 1, 0, 1]
after 1 ms : [1, 0, 1, 1, 0, 1, 0, 1]
after 10 ms : [0, 0, 0, 0, 0, 0, 0, 0]
After 10 ms every bit reads 0. The data is gone even though the power never went off. The fix: read each cell before it fades and write it back full:
# DRAM: each bit is charge in a tiny leaky capacitor
# made-up leak: 20% of the charge escapes every ms
def read(bits, ms, refresh_every=None):
charge = [1.0 if b else 0.0 for b in bits]
for t in range(1, ms + 1):
charge = [c * 0.8 for c in charge] # leak
if refresh_every and t % refresh_every == 0:
charge = [1.0 if c > 0.5 else 0.0
for c in charge] # refresh
return [1 if c > 0.5 else 0 for c in charge]
stored = [1, 0, 1, 1, 0, 1, 0, 1]
print("stored :", stored)
print("after 1 ms :", read(stored, 1))
print("after 10 ms :", read(stored, 10))
print("10 ms, refresh:", read(stored, 10, refresh_every=2))
Output:
stored : [1, 0, 1, 1, 0, 1, 0, 1]
after 1 ms : [1, 0, 1, 1, 0, 1, 0, 1]
after 10 ms : [0, 0, 0, 0, 0, 0, 0, 0]
10 ms, refresh: [1, 0, 1, 1, 0, 1, 0, 1]
- Reading every cell and writing it back before it fades is DRAM refresh. Real DRAM must refresh every cell once per refresh window, which is typically 64 ms (32 ms in DDR5), according to the HiRA paper (arXiv 2209.10198). That need is the "dynamic" in dynamic RAM.
- While a row is being refreshed it can't be read, so refresh steals a little time.
| SRAM | DRAM | |
|---|---|---|
| Cell | flip-flop, typically 6 transistors | 1 transistor + 1 capacitor |
| Refresh | not needed | needed (typically every 64 ms) |
| Speed | very fast | slower |
| Density, cost per bit | low density, costly | high density, cheap |
| Volatile? | yes | yes |
| Used for | cache | main memory |
Problem 5: memory that survives power off (the ROM family and flash)
When a computer switches on, RAM is empty. The first program it runs, the firmware (a small built-in program that starts a computer, or runs a washing machine or a TV remote), must sit in non-volatile memory.
Real-life example: writing that stays.
| On paper | Memory | How it's written and erased |
|---|---|---|
| A printed newspaper | ROM (read-only memory) | Contents fixed when the chip is made; never changed |
| A form filled in ink | PROM (programmable ROM) | Leaves the factory blank; the user programs it once |
| A sheet you take to a special lamp to wipe completely | EPROM (erasable PROM) | Erased by ultraviolet light through a quartz window on the chip, the whole chip at once; then reprogrammed |
| A whiteboard: wipe any one word | EEPROM (electrically erasable PROM) | Erased and rewritten electrically, byte by byte |
| A board you wipe a whole section at a time | Flash memory | Erased electrically in whole blocks before rewriting; simpler, denser, cheaper. Inside SSDs, pen drives, phones |
All of these are non-volatile. "Read-only" today really means "read-mostly": writing is slow or limited compared to reading.
Problem 6: disks and links (HDD vs SSD, latency vs bandwidth)
Hard disk access time
A hard disk drive (HDD) stores bits as magnetism on spinning platters; a read/write head on an arm moves across them, like a record player. One access has three parts:
| Part | Plain meaning |
|---|---|
| Seek time | Moving the head to the right track (a circle on the platter) |
| Rotational latency | Waiting for the right sector (a piece of the track) to spin under the head. On average half a rotation |
| Transfer time | Reading the bytes as they pass: size ÷ transfer rate |
Numerical (made-up numbers): a disk spins at 6000 RPM (rotations per minute), average seek 4 ms, reading 4 KB at 100 MB/s.
one rotation = 60 s ÷ 6000 = 10 ms
rotational latency = 10 ÷ 2 = 5 ms
transfer = 4 KB ÷ 100 MB/s = 0.04 ms
access time = 4 + 5 + 0.04 = 9.04 ms
About 9 ms per read: millions of times slower than a cache access of a nanosecond or two.
HDD vs SSD
A solid-state drive (SSD) stores data in flash chips: no moving parts, so no seek and no rotation (Lenovo's glossary on seek time says SSDs have "no moving parts" and far shorter access times).
| HDD | SSD | |
|---|---|---|
| Stores data in | magnetic spinning platters | flash memory chips |
| Moving parts | yes: platters, arm, head | none |
| Access time | seek + rotational latency + transfer | no seek, no rotation: much faster, especially random access |
| Cost per bit | cheapest | higher |
| Other | moving parts can wear out; noise | silent, shock-resistant; flash is erased in blocks |
| Volatile? | no | no |
Latency vs bandwidth
Real-life example: a bike courier leaves now but carries one bag; a loaded truck is slow to start but carries tonnes.
- Latency: the delay before the first byte arrives.
- Bandwidth: how many bytes move per second once data is flowing (MB/s).
- Transfer time = latency + size ÷ bandwidth.
# time = latency + size / bandwidth (made-up links)
links = {"A: low latency ": (0.001, 100), # s, MB/s
"B: big bandwidth": (0.5, 2000)}
for mb in [0.01, 1, 1000]:
for name, (lat, bw) in links.items():
print(f"{mb:>7} MB via {name}: "
f"{lat + mb / bw:7.3f} s")
Output:
0.01 MB via A: low latency : 0.001 s
0.01 MB via B: big bandwidth: 0.500 s
1 MB via A: low latency : 0.011 s
1 MB via B: big bandwidth: 0.500 s
1000 MB via A: low latency : 10.001 s
1000 MB via B: big bandwidth: 1.000 s
Small, scattered accesses care about latency; big transfers care about bandwidth. "High bandwidth" is not the same as "fast" for a tiny request.
Problem 7: a busy memory chip (addressing and interleaving)
Byte-addressable vs word-addressable
| Plain meaning | 4 GiB of memory needs | |
|---|---|---|
| Byte-addressable | Every byte has its own address (almost all modern computers) | 2³² addresses → 32-bit address |
| Word-addressable | One address names a whole word (say 4 bytes) | 2³² ÷ 4 = 2³⁰ words → 30-bit address |
Address bits = log₂(number of addressable units).
Memory interleaving
Real-life example: a bank with one counter, where each customer takes 4 minutes, has a crawling queue. Open 4 counters and send token 1 to counter 1, token 2 to counter 2, and so on: while one counter is busy, the next is already serving.
After a DRAM chip answers one request it stays busy for a while (its cycle time). Memory interleaving splits memory into several modules (independent banks of chips) and spreads neighbouring addresses across them, so their busy times overlap.
# read 8 consecutive words; a module needs 4 cycles
# per access and is busy until it finishes
def cycles(modules, words=8, busy=4):
free = [0] * modules # when each module is free
t = 0 # CPU sends 1 request/cycle
for addr in range(words):
m = addr % modules # low-order interleaving
start = max(t, free[m])
free[m] = start + busy
t = start + 1
return max(free)
for k in [1, 2, 4]:
print(f"{k} module(s): {cycles(k):2} cycles")
Output:
1 module(s): 32 cycles
2 module(s): 17 cycles
4 module(s): 11 cycles
One module: 32 cycles. Four modules: 11 cycles, nearly 3× faster with the same chips.
| Kind | Module chosen by | 4 modules | Good for |
|---|---|---|---|
| Low-order interleaving | lowest address bits: address mod k | 0, 4, 8 → M0; 1, 5, 9 → M1; 2, 6 → M2 ... | consecutive words in parallel |
| High-order interleaving | highest address bits: address ÷ module size | M0 = 0-255, M1 = 256-511 ... | easy to add memory; one module per program region |
The whole chain
- Fast + big + cheap fails → the memory hierarchy.
- Why a tiny cache works → temporal + spatial locality.
- How fast on average → hit ratio, access time formulas.
- Bits leak → SRAM vs DRAM, refresh.
- Survive power off → ROM, PROM, EPROM, EEPROM, flash.
- Moving parts → HDD vs SSD; latency vs bandwidth.
- A busy chip → interleaving.
Next question: when a block comes into the cache, where does it go and how do we find it again? That's cache mapping (episode 9).
Common mistakes (and the real output)
| Mistake | Real output | Fix |
|---|---|---|
| Summing a row-major 2D array column by column | column by column: 0/64 hits |
Loop in storage order: row by row : 48/64 hits |
| Hierarchical miss costing only t2 | H=0.80 simultaneous= 21.6 ns hierarchical= 22.0 ns |
Miss = t1 + t2 when the cache is checked first |
| DRAM without refresh | after 10 ms : [0, 0, 0, 0, 0, 0, 0, 0] |
Refresh every cell within the refresh window |
| "High bandwidth is always faster" | 0.01 MB via B: big bandwidth: 0.500 s vs 0.001 s |
time = latency + size ÷ bandwidth |
| High-order interleaving for sequential reads | high-order (addr // 256): 32 cycles vs 11 cycles |
Use low-order interleaving for consecutive words |
| "SRAM needs refresh", "cache is DRAM" | (interview) | SRAM = flip-flop, no refresh, used for cache; DRAM = capacitor, refresh, main memory |
| "ROM is volatile" / "RAM keeps data when off" | (interview) | RAM (SRAM, DRAM) is volatile; ROM family, flash, disks are non-volatile |
| Counting bytes in word-addressable memory | 4 GiB, 4-byte words: 30 bits, not 32 | Address bits = log₂(number of words) |
The program behind the interleaving row:
# high-order interleaving with sequential reads
def cycles(module_of, words=8, modules=4, busy=4):
free = [0] * modules
t = 0
for addr in range(words):
m = module_of(addr)
start = max(t, free[m])
free[m] = start + busy
t = start + 1
return max(free)
print("low-order (addr % 4) :", cycles(lambda a: a % 4), "cycles")
print("high-order (addr // 256):", cycles(lambda a: a // 256), "cycles")
Output:
low-order (addr % 4) : 11 cycles
high-order (addr // 256): 32 cycles
With high-order interleaving, addresses 0-7 all live in module 0, so the requests queue up exactly like one module.
Mini project: a 3-level memory hierarchy simulator
L1 holds 4 blocks, L2 holds 16, RAM holds everything; a block is 4 words; both caches evict the least recently used block (the one untouched for the longest). Times: L1 1 ns, L2 10 ns, RAM 100 ns, hierarchical.
# mini project: a 3-level memory hierarchy simulator
# L1 holds 4 blocks, L2 holds 16 blocks, RAM holds everything.
# A block is 4 words. Both caches throw out the least recently used block.
import random
class Cache:
def __init__(self, name, slots):
self.name, self.slots, self.blocks = name, slots, []
self.hits = self.misses = 0
def lookup(self, block):
if block in self.blocks:
self.hits += 1
self.blocks.remove(block); self.blocks.append(block)
return True
self.misses += 1
if len(self.blocks) == self.slots:
self.blocks.pop(0) # least recently used
self.blocks.append(block)
return False
def run(name, addresses, t=(1, 10, 100)):
l1, l2 = Cache("L1", 4), Cache("L2", 16)
total_ns = 0
for a in addresses:
b = a // 4
total_ns += t[0] # always check L1
if l1.lookup(b): continue
total_ns += t[1] # L1 missed: check L2
if l2.lookup(b): continue
total_ns += t[2] # L2 missed: go to RAM
n = len(addresses)
print(f"{name:13} L1 hit {l1.hits / n:6.1%} "
f"L2 hit {l2.hits / max(1, l2.hits + l2.misses):6.1%} "
f"average {total_ns / n:6.2f} ns")
N = 16 # 16 x 16 grid, stored by rows
row = [r * N + c for r in range(N) for c in range(N)]
col = [r * N + c for c in range(N) for r in range(N)]
small = list(range(32)) * 4 # a 32-word array, read 4 times
rng = random.Random(1)
rand = [rng.randrange(1 << 16) for _ in range(N * N)]
run("row order", row)
run("column order", col)
run("small x4", small)
run("random", rand)
Output:
row order L1 hit 75.0% L2 hit 0.0% average 28.50 ns
column order L1 hit 0.0% L2 hit 75.0% average 36.00 ns
small x4 L1 hit 75.0% L2 hit 75.0% average 9.75 ns
random L1 hit 0.0% L2 hit 0.0% average 111.00 ns
- Row order: spatial locality gives 75% L1 hits, but the 256-word grid (64 blocks) never fits in L2, so L2 never hits on the first pass.
- Column order: 0% L1 hits; but a column touches 16 blocks, which L2 can hold, so L2 catches 75% of L1's misses. A bigger level rescues some locality the small one lost.
- Small × 4: a 32-word array (8 blocks) read 4 times fits in L2: temporal locality pays, average 9.75 ns.
- Random: no locality, every access goes to RAM: 1 + 10 + 100 = 111 ns.
- Try it: change L1 to 8 blocks, the block size to 8 words, or the times; add a third cache level.
Practice
- H = 0.95, t1 = 5 ns, t2 = 80 ns. Average time, simultaneous and hierarchical?
- Hierarchical, t1 = 10 ns, t2 = 100 ns. What hit ratio gives an average of 15 ns?
- Hierarchical, L1 2 ns (h1 = 0.8), L2 20 ns (h2 = 0.9 of L1 misses), RAM 200 ns. Average?
- A 7200 RPM disk: one rotation? Average rotational latency?
- 10,000 RPM, average seek 5 ms, read 1 MB at 200 MB/s. Access time?
- 8 modules, low-order: which module holds address 29? High-order with 1,024 words per module: addresses 29 and 5000?
- 16 consecutive words, each module busy 4 cycles, one request per cycle. Cycles with 1, 4 and 8 modules?
- 1 GiB memory: address bits if byte-addressable? If word-addressable with 8-byte words?
- A link has 20 ms latency and 50 MB/s bandwidth. Time to send 100 MB? 10 KB?
- 940 hits in 1,000 accesses. Hit ratio and miss ratio?
- 1 GiB at Rs 5000/GiB and 63 GiB at Rs 300/GiB (made-up). Average cost per GiB?
- Classify: (a) a loop counter, (b) reading
a[0..999]in order, (c) a function called in a loop. - Why does SRAM not need refresh but DRAM does?
- Which of ROM, PROM, EPROM, EEPROM, flash can be erased one byte at a time? Which needs UV light?
- Why is cache made of SRAM and main memory of DRAM?
Solutions
Numbers computed with a Python 3.13 script; its output:
Q1 simultaneous = 8.75 ns hierarchical = 9.00 ns
Q2 10 + (1-H)*100 = 15 -> H = 0.95
Q3 3 levels: 10.00 ns
Q4 7200 RPM: one turn 8.33 ms, average rotational latency 4.17 ms
Q5 seek 5 + rotate 3.0 + transfer 5.0 = 13.0 ms
Q6 low-order, 8 modules: address 29 -> M5; high-order, 1024 words each: 29 -> M0, 5000 -> M4
Q7 16 words, busy 4: 1 module 64, 4 modules 19, 8 modules 19 cycles
Q8 1 GiB: byte-addressable 30 bits, 8-byte words 27 bits
Q9 100 MB: 2.020 s 10 KB: 0.0202 s
Q10 hit ratio 0.94, miss ratio 0.06
Q11 average Rs per GiB = 373.4
- Simultaneous 0.95 × 5 + 0.05 × 80 = 8.75 ns; hierarchical 0.95 × 5 + 0.05 × 85 = 9.00 ns.
- T = t1 + (1 − H)·t2: 10 + (1 − H)·100 = 15 → H = 0.95.
- 0.8 × 2 + 0.2 × 0.9 × 22 + 0.2 × 0.1 × 222 = 1.6 + 3.96 + 4.44 = 10 ns.
- 60 ÷ 7200 s = 8.33 ms per turn; average latency 4.17 ms.
- Rotation 6 ms, so 3 ms average; transfer 1 ÷ 200 s = 5 ms; total 5 + 3 + 5 = 13 ms.
- Low-order: 29 mod 8 = M5. High-order: 29 ÷ 1024 → M0, 5000 ÷ 1024 → M4.
- 64, 19, 19 cycles. Once there are as many modules as busy cycles (4), more modules don't help: the CPU only sends one request per cycle.
- 30 bits; 2³⁰ ÷ 8 = 2²⁷ words → 27 bits.
- 0.02 + 100 ÷ 50 = 2.02 s; 0.02 + 0.01 ÷ 50 = 0.0202 s (latency dominates).
- 0.94 and 0.06.
- (5000 + 18,900) ÷ 64 = Rs 373.4 per GiB.
- (a) temporal, (b) spatial, (c) temporal (the same instructions again), and spatial within its body.
- An SRAM cell is a flip-flop that actively holds its state while powered; a DRAM cell is charge on a capacitor that leaks away.
- EEPROM erases byte by byte (flash erases blocks). EPROM is erased with ultraviolet light.
- The cache is small and must be as fast as possible (SRAM); main memory must be big and cheap (DRAM is denser and cheaper per bit).
Quick quiz
The cache takes 10 ns, main memory 100 ns, the hit ratio is 0.9, access is hierarchical. Average access time?
- A. 11 ns
- B. 19 ns
- C. 20 ns
- D. 110 ns
Answer
C, 20 ns. 0.9 × 10 + 0.1 × (10 + 100) = 9 + 11 = 20. B (19 ns) is the simultaneous formula: it forgets the cache check on a miss.
Interview questions
- What is the memory hierarchy and why do we need it? A stack of memories from registers to tape, each level bigger, slower and cheaper per bit. No single technology is fast, big and cheap, and locality lets a small fast level serve most accesses.
- What is locality of reference? Temporal: recently used data is used again soon. Spatial: neighbours of used data are used soon. Caches keep recent data and fetch whole blocks.
- Why is traversing a 2D array by columns slow in C? C stores arrays row-major; column order jumps a whole row per step, so each access touches a new cache block.
- Simultaneous vs hierarchical access time? H·t1 + (1 − H)·t2 vs H·t1 + (1 − H)·(t1 + t2).
- SRAM vs DRAM? SRAM: flip-flop (~6 transistors), fast, no refresh, costly, used for cache. DRAM: 1 transistor + 1 capacitor, dense, cheap, needs refresh, used for main memory.
- Why does DRAM need refresh, and how often? Capacitor charge leaks; each cell is refreshed within a refresh window, typically 64 ms.
- ROM vs PROM vs EPROM vs EEPROM vs flash? Factory-written; user-written once; UV-erasable; electrically erasable by byte; electrically erasable by block.
- Is flash RAM or ROM? It's non-volatile, electrically erasable memory descended from EEPROM, erased in blocks; used as storage, not as main memory.
- HDD vs SSD? HDD: platters and a moving head, seek + rotational latency, cheap per bit. SSD: flash, no moving parts, much faster random access.
- Latency vs bandwidth? Delay to the first byte vs bytes per second; time = latency + size ÷ bandwidth.
- What is memory interleaving? Splitting memory into modules and spreading consecutive addresses across them (low-order) so accesses overlap.
- Byte- vs word-addressable? One address per byte vs one per word; word addressing needs fewer address bits.
Glossary
| Term | Plain meaning | Example |
|---|---|---|
| Memory hierarchy | Stack of memories, each bigger, slower, cheaper per bit going down | registers → cache → RAM → SSD → tape |
| Memory hierarchy pyramid | The usual picture of the hierarchy: narrow fast top, wide cheap bottom | registers at the tip |
| Registers | Tiny storage boxes inside the CPU; the fastest memory | ACC, PC (episode 6) |
| Cache | Small, very fast memory holding copies of data in use | the books on your desk |
| L1 / L2 / L3 cache | Cache levels: L1 smallest and fastest, L3 biggest and slowest | L1 1 ns, L2 10 ns (made-up) |
| Main memory (RAM) | Memory where running programs and their data live | 16 GiB of DRAM |
| Random-access memory | Any address can be reached in about the same time | RAM vs tape |
| Secondary storage | Large non-volatile storage for files | SSD, hard disk |
| Tertiary storage | Very large, slow storage for backups and archives | tape libraries, optical discs |
| Access time | Time for one read or write | 2 ns, 100 ns, 9 ms |
| Nanosecond (ns) / millisecond (ms) | 10⁻⁹ s / 10⁻³ s | 1 ms = 1,000,000 ns |
| Capacity | How much a memory holds | 64 GiB |
| Cost per bit | Price ÷ number of bits | SRAM costly, disk cheap |
| Volatile | Loses data when power goes | RAM, cache |
| Non-volatile | Keeps data with power off | SSD, ROM, flash |
| Locality of reference | Programs reuse data and use neighbours | loops, arrays |
| Temporal locality | Used now → used again soon | loop counter i |
| Spatial locality | Used now → neighbours used soon | a[0], a[1], a[2] |
| Block (cache line) | Group of neighbouring words moved together | 4 words |
| Hit / miss | Found in the cache / not found | 48 hits, 16 misses |
| Hit ratio (H) | Hits ÷ total accesses | 48/64 = 0.75 |
| Miss ratio | 1 − H | 0.25 |
| Simultaneous access | Levels searched at once; miss costs t2 | H·t1 + (1 − H)·t2 |
| Hierarchical access | Cache checked first; miss costs t1 + t2 | H·t1 + (1 − H)·(t1 + t2) |
| Average memory access time | Expected time per access over hits and misses | 20 ns in the quiz |
| Local hit ratio | Hit ratio of a level among the accesses that reach it | h2 = 0.8 of L1 misses |
| Row-major order | 2D array stored row after row | a[r][c] at r·N + c |
| Least recently used (LRU) | Evict the block untouched for longest | mini project |
| Transistor | Tiny electronic switch | 6 per SRAM bit |
| Capacitor | Part that stores electric charge | 1 per DRAM bit |
| SRAM (static RAM) | Bits held by flip-flops; fast, no refresh, costly | cache |
| DRAM (dynamic RAM) | Bits held as capacitor charge; dense, cheap, needs refresh | main memory |
| DRAM refresh | Read each cell and write it back before it fades | within ~64 ms |
| Refresh window | Time within which every DRAM cell must be refreshed | typically 64 ms |
| Density | Bits per chip area | DRAM > SRAM |
| Firmware | Small built-in program stored in non-volatile memory | the startup program |
| ROM | Read-only memory, written at the factory | a printed newspaper |
| PROM | Programmable ROM, written once by the user | a form in ink |
| EPROM | Erasable PROM, erased by UV light through a quartz window | whole chip wiped |
| EEPROM | Electrically erasable PROM, byte by byte | a whiteboard |
| Flash memory | Electrically erasable in blocks; dense, cheap | SSDs, pen drives |
| HDD (hard disk drive) | Magnetic spinning platters read by a moving head | backups |
| SSD (solid-state drive) | Storage built from flash chips, no moving parts | laptop drive |
| Platter / track / sector | Spinning disk / a circle on it / a piece of a track | sector of 512 bytes |
| Read/write head | Part that reads and writes a platter | on a moving arm |
| Seek time | Time to move the head to the track | 4 ms (made-up) |
| Rotational latency | Wait for the sector to spin under the head; average half a turn | 5 ms at 6000 RPM |
| RPM | Rotations per minute | 6000 RPM → 10 ms per turn |
| Transfer time | Size ÷ transfer rate | 4 KB at 100 MB/s = 0.04 ms |
| Latency | Delay before the first byte arrives | 0.5 s link |
| Bandwidth | Bytes per second once flowing | 2000 MB/s |
| Byte-addressable | Each address names one byte | 4 GiB → 32 bits |
| Word-addressable | Each address names one word | 4 GiB, 4-byte words → 30 bits |
| Memory module (bank) | Independent group of memory chips | M0 ... M3 |
| Cycle time (busy time) | Time a module stays busy after an access | 4 cycles |
| Memory interleaving | Spreading addresses across modules so accesses overlap | 32 → 11 cycles |
| Low-order interleaving | Module = lowest address bits (address mod k) | 5 → M1 |
| High-order interleaving | Module = highest bits (continuous chunks) | 0-255 in M0 |
Summary
- No memory is fast, big and cheap, so computers stack a hierarchy: registers, cache (L1/L2/L3), main memory, secondary storage, tertiary storage. Down = bigger, slower, cheaper per bit.
- Volatile memory (registers, cache, RAM) forgets on power off; non-volatile (ROM family, flash, SSD, HDD, tape) keeps data.
- Locality makes a small cache work: temporal (reuse) and spatial (neighbours). Walk arrays in storage order.
- Hit ratio H = hits ÷ accesses. Simultaneous: H·t1 + (1 − H)·t2. Hierarchical: H·t1 + (1 − H)·(t1 + t2). Each level adds its time on a miss.
- SRAM (flip-flop, ~6 transistors, no refresh) makes caches; DRAM (1 transistor + 1 capacitor) makes main memory and needs refresh (typically every 64 ms).
- ROM → PROM (once) → EPROM (UV) → EEPROM (electrically, by byte) → flash (electrically, by block).
- HDD access = seek + rotational latency (half a turn) + transfer; SSD has no moving parts.
- Latency = delay to the first byte, bandwidth = bytes per second; time = latency + size ÷ bandwidth.
- Byte- vs word-addressable: address bits = log₂(units). Low-order interleaving overlaps busy modules for consecutive words.
Next episode: Cache memory 1: mapping techniques with numericals. Direct-mapped, fully associative and set-associative caches, and splitting an address into tag, index and offset.