SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 8

CS Fundamentals for Placements · Lesson 8 of 90 · 18 min

Memory hierarchy and locality

memory hierarchy pyramidregisterscachemain memorysecondary storagetertiary storageSRAM vs DRAMDRAM refreshROMPROMEPROMEEPROMflash memoryHDD vs SSD

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.

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

  1. Fast + big + cheap fails → the memory hierarchy.
  2. Why a tiny cache works → temporal + spatial locality.
  3. How fast on average → hit ratio, access time formulas.
  4. Bits leak → SRAM vs DRAM, refresh.
  5. Survive power off → ROM, PROM, EPROM, EEPROM, flash.
  6. Moving parts → HDD vs SSD; latency vs bandwidth.
  7. 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

  1. H = 0.95, t1 = 5 ns, t2 = 80 ns. Average time, simultaneous and hierarchical?
  2. Hierarchical, t1 = 10 ns, t2 = 100 ns. What hit ratio gives an average of 15 ns?
  3. Hierarchical, L1 2 ns (h1 = 0.8), L2 20 ns (h2 = 0.9 of L1 misses), RAM 200 ns. Average?
  4. A 7200 RPM disk: one rotation? Average rotational latency?
  5. 10,000 RPM, average seek 5 ms, read 1 MB at 200 MB/s. Access time?
  6. 8 modules, low-order: which module holds address 29? High-order with 1,024 words per module: addresses 29 and 5000?
  7. 16 consecutive words, each module busy 4 cycles, one request per cycle. Cycles with 1, 4 and 8 modules?
  8. 1 GiB memory: address bits if byte-addressable? If word-addressable with 8-byte words?
  9. A link has 20 ms latency and 50 MB/s bandwidth. Time to send 100 MB? 10 KB?
  10. 940 hits in 1,000 accesses. Hit ratio and miss ratio?
  11. 1 GiB at Rs 5000/GiB and 63 GiB at Rs 300/GiB (made-up). Average cost per GiB?
  12. Classify: (a) a loop counter, (b) reading a[0..999] in order, (c) a function called in a loop.
  13. Why does SRAM not need refresh but DRAM does?
  14. Which of ROM, PROM, EPROM, EEPROM, flash can be erased one byte at a time? Which needs UV light?
  15. 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
  1. Simultaneous 0.95 × 5 + 0.05 × 80 = 8.75 ns; hierarchical 0.95 × 5 + 0.05 × 85 = 9.00 ns.
  2. T = t1 + (1 − H)·t2: 10 + (1 − H)·100 = 15 → H = 0.95.
  3. 0.8 × 2 + 0.2 × 0.9 × 22 + 0.2 × 0.1 × 222 = 1.6 + 3.96 + 4.44 = 10 ns.
  4. 60 ÷ 7200 s = 8.33 ms per turn; average latency 4.17 ms.
  5. Rotation 6 ms, so 3 ms average; transfer 1 ÷ 200 s = 5 ms; total 5 + 3 + 5 = 13 ms.
  6. Low-order: 29 mod 8 = M5. High-order: 29 ÷ 1024 → M0, 5000 ÷ 1024 → M4.
  7. 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.
  8. 30 bits; 2³⁰ ÷ 8 = 2²⁷ words → 27 bits.
  9. 0.02 + 100 ÷ 50 = 2.02 s; 0.02 + 0.01 ÷ 50 = 0.0202 s (latency dominates).
  10. 0.94 and 0.06.
  11. (5000 + 18,900) ÷ 64 = Rs 373.4 per GiB.
  12. (a) temporal, (b) spatial, (c) temporal (the same instructions again), and spatial within its body.
  13. 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.
  14. EEPROM erases byte by byte (flash erases blocks). EPROM is erased with ultraviolet light.
  15. 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.