SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 10

CS Fundamentals for Placements · Lesson 10 of 90 · 16 min

Cache memory 2: replacement, writes, multilevel caches and coherence

cache replacement policies (LRU, FIFO, random, LFU)write-throughwrite-backdirty bitwrite-allocate vs no-write-allocatewrite buffermultilevel cache (L1, L2, L3)inclusive vs exclusive cachessplit instruction/data cachemultilevel AMAT numericalsmulticore processorshared cachecache coherence problemsnooping vs directory protocols

These are the notes for CS Fundamentals for Placements, episode 10. Last episode you decided where a block may sit in a cache (direct-mapped, set-associative, fully associative). Today three new problems arrive. The set is full: which block do we throw out? (replacement policies: LRU, FIFO, random, LFU, and the ideal OPT). The CPU writes: when does RAM find out? (write-through, write-back, the dirty bit, the write buffer, write-allocate vs no-write-allocate). One cache can't be both big and fast (multilevel caches L1, L2, L3, local vs global miss rate, multilevel AMAT numericals, split instruction/data caches, inclusive vs exclusive caches). And a chip with many cores has many copies of the same data (multicore processor, shared cache, the cache coherence problem, snooping vs directory protocols, the MESI protocol, and false sharing). 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. Every cache and timing in these notes is made up, to keep the numbers simple.

A quick refresher from earlier episodes: a cache is a small, fast memory next to the CPU that keeps copies of recently used blocks (fixed-size chunks of RAM, for example 64 bytes). A slot that holds one block is a line. A hit means the data is already in the cache; a miss means it must be fetched from RAM, which costs the miss penalty. In a k-way set-associative cache, a block may sit in any of the k lines (ways) of one set. AMAT (average memory access time) = hit time + miss rate × miss penalty. Temporal locality: data used recently will probably be used again soon. In Python, list.pop(0) removes the first item, list.remove(x) removes the item x, and append adds to the end.

The five problems

Problem What it teaches
The set is full Replacement policy, victim, FIFO, LRU, pseudo-LRU, random, LFU, Belady's OPT
The CPU writes Write-through, write-back, dirty bit, write buffer, write miss, write-allocate, no-write-allocate
Big and fast at once L1, L2, L3, local vs global miss rate, multilevel AMAT, split I/D caches, unified caches, inclusive vs exclusive
Many cores, many copies Multicore processor, shared cache, stale data, cache coherence, snooping, directory, MESI
Two counters, one line False sharing and padding

Problem 1: the set is full (replacement policies)

Your kitchen counter has room for only three jars: salt, chilli and turmeric are out. Now you need the garam masala, so one jar must go back to the shelf.

A kitchen counter A cache set
Room for only 3 jars A full set: all 3 ways of a 3-way set hold blocks
Deciding which jar goes back Replacement policy: the rule that picks which block to throw out
The jar that goes back The victim: the block that is evicted (thrown out)
Put back the jar you took out first FIFO (first in, first out): evict the block that came in earliest
Put back the jar untouched for longest LRU (least recently used): evict the block whose last use is oldest
Put back any jar at all Random: pick the victim at random

A direct-mapped cache never needs a policy: each block has exactly one possible line, so the old block in that line is always the victim. Replacement policies matter for set-associative and fully associative caches.

FIFO vs LRU, live

Both policies keep the set as a list and throw out the front. The only difference: LRU moves a block to the back every time it is used, so the front is always the least recently used block. A trace is the list of blocks a program asks for, in order.

# a full 3-line set: which block do we throw out?
def run(policy, trace, ways=3):
    cache, hits = [], 0
    for b in trace:
        if b in cache:
            hits += 1
            if policy == "LRU":   # move to the back
                cache.remove(b); cache.append(b)
        else:
            if len(cache) == ways:
                cache.pop(0)              # evict the front
            cache.append(b)
    print(f"{policy}: {hits}/{len(trace)} hits")

trace = list("ABACADABACAD")
run("FIFO", trace)
run("LRU", trace)

Output:

FIFO: 4/12 hits
LRU: 5/12 hits

Block A is used every other time. When D arrives, FIFO throws out A just because A came in first, even though A is the busiest block. LRU sees that A was just used and keeps it. LRU is a bet on temporal locality.

The cost of LRU, and pseudo-LRU

  • LRU must remember the use order of the blocks in every set, and update it on every hit.
  • 2-way: 1 bit per set is enough (which way is older).
  • k-way: there are k! (k factorial) possible orders, so you need ⌈log₂(k!)⌉ bits per set. 4-way: 4! = 24 orders → 5 bits. 8-way: 8! = 40,320 orders → 16 bits.
  • So larger caches use pseudo-LRU: a cheaper approximation (for example a small tree of bits that points roughly towards the oldest way). It usually evicts an old block, not always the very oldest.

LFU: least frequently used

LFU keeps a use counter per block and evicts the block with the smallest count. It sounds clever, but it remembers the past too well:

# LFU: evict the block used the FEWEST times
from collections import Counter
def run(policy, trace, ways=2):
    cache, uses, hits = [], Counter(), 0
    for b in trace:
        uses[b] += 1
        if b in cache:
            hits += 1
            cache.remove(b); cache.append(b)
        else:
            if len(cache) == ways:
                if policy == "LFU":
                    victim = min(cache,
                                 key=lambda x: uses[x])
                else:            # LRU: the front
                    victim = cache[0]
                cache.remove(victim)
            cache.append(b)
    return hits

old = ["A"] * 50          # A was hot an hour ago
new = ["B", "C"] * 5      # now only B and C are used
for p in ["LFU", "LRU"]:
    h = run(p, old + new) - run(p, old)
    print(f"{p}: {h}/{len(new)} hits in the new phase")

Output:

LFU: 0/10 hits in the new phase
LRU: 8/10 hits in the new phase

A has a count of 50, so LFU never evicts it; B and C keep fighting over the one remaining way. Real LFU designs age the counters (halve them now and then) to forget old popularity. MFU (most frequently used) is the opposite rule; it is mostly a textbook curiosity.

Random and OPT

  • Random needs no bookkeeping at all and can't be fooled by any one access pattern. With many ways it does nearly as well as LRU.
  • OPT (optimal, also called Belady's algorithm): evict the block that will be needed furthest in the future. It gives the fewest misses possible, but hardware can't see the future, so it can't be built. Exams and studies use it as the yardstick to judge other policies.
  • Belady's anomaly: with FIFO, more ways can give fewer hits. LRU and OPT never do this. (See the common-mistakes program below.)

Problem 2: the CPU writes (write policies)

So far the CPU only read. A class teacher writes marks quickly in her rough notebook (the cache copy); the official copy is the school register in the office (RAM).

A class teacher A cache on writes
Writes marks in her rough notebook The CPU writes to the cache copy
Walks to the office register after every change Write-through: every write updates the cache and RAM
Copies everything to the register once, at the end of the day Write-back: update RAM only when the line is evicted
Puts a star on every page she changed Dirty bit: 1 = this line was changed since it came from RAM

Write-through vs write-back, live

# a loop adds to a counter 1,000 times. How many RAM writes?
def run(policy):
    ram_writes, dirty = 0, False
    for i in range(1000):
        # the CPU writes the counter; it's in the cache
        if policy == "write-through":
            ram_writes += 1   # RAM too, every time
        else:                        # write-back
            dirty = True             # only mark the line
    if dirty:              # evicted at the end
        ram_writes += 1
    print(f"{policy}: {ram_writes} RAM writes")

run("write-through")
run("write-back")

Output:

write-through: 1000 RAM writes
write-back: 1 RAM writes
Write-through Write-back
RAM traffic Every write goes to RAM Only evicted dirty lines go to RAM
RAM up to date? Always Not until the line is written back
Extra bit per line None needed Dirty bit
Eviction Just drop the line A dirty victim must be written back first (slower miss)
Simplicity Simple More complex

Why the dirty bit? Without it, write-back would have to write every evicted line to RAM, even lines that were only read. With it, clean lines are simply dropped.

The write buffer

Write-through would make the CPU wait for RAM on every write. The fix is a write buffer: a small queue of pending RAM writes. The CPU drops the write into the buffer and carries on, like dropping a letter into a post box instead of walking to the post office. The buffer drains to RAM in the background; the CPU only waits if the buffer is full.

Write misses: write-allocate vs no-write-allocate

A write miss is a write to a block that isn't in the cache.

  • Write-allocate (fetch on write): bring the block into the cache, then write it there.
  • No-write-allocate (write-around): skip the cache and write straight to RAM.
# write a value, then read it 5 times
def run(allocate):
    cache, misses = set(), 0
    ops = [("W", "x")] + [("R", "x")] * 5
    for op, b in ops:
        if b not in cache:
            misses += 1
            if op == "R" or allocate:
                cache.add(b)         # bring the block in
    name = "write-allocate" if allocate \
        else "no-write-allocate"
    print(f"{name}: {misses} misses")

run(True)
run(False)

Output:

write-allocate: 1 misses
no-write-allocate: 2 misses

If written data is read again soon, write-allocate wins. If it is written once and never read (filling a big output buffer), no-write-allocate wins, because it doesn't fill the cache with junk.

Usual pairs: write-back + write-allocate (once the block is in, later writes hit and stay in the cache); write-through + no-write-allocate (RAM is written anyway, so bringing the block in buys little).

Problem 3: big and fast at once (multilevel caches)

A bigger memory is slower (signals travel further, more to search). We want both size and speed, so we do what we do with money: a little in the wallet, more in the almirah at home, most in the bank.

Where you keep money Levels of cache
Wallet: tiny, instant L1 cache: smallest and fastest, inside each core
Almirah: bigger, a short walk L2 cache: bigger, a bit slower
Bank locker: huge, a trip across town L3 cache: biggest cache, often shared by all cores; then RAM

A multilevel cache checks L1 first; an L1 miss checks L2; an L2 miss checks L3 (if any); only then RAM.

Multilevel AMAT, live

# AMAT with one level vs two levels of cache (ns)
l1_hit, l1_miss = 1, 0.10      # L1: 1 ns, misses 10%
l2_hit, l2_miss = 10, 0.20     # L2: 10 ns, local 20%
ram = 100

one = l1_hit + l1_miss * ram
two = l1_hit + l1_miss * (l2_hit + l2_miss * ram)
print(f"L1 only : {one:.0f} ns")
print(f"L1 + L2 : {two:.0f} ns")
print(f"global L2 miss rate = {l1_miss * l2_miss:.0%}")

Output:

L1 only : 11 ns
L1 + L2 : 4 ns
global L2 miss rate = 2%

The formulas

  • Two levels: AMAT = h₁ + m₁ × (h₂ + m₂ × T_RAM), where h = hit time and m = local miss rate. The miss penalty of L1 is simply the AMAT of L2.
  • Three levels: AMAT = h₁ + m₁ × (h₂ + m₂ × (h₃ + m₃ × T_RAM)).
  • Local miss rate of L2 = L2 misses ÷ accesses that reach L2.
  • Global miss rate of L2 = L2 misses ÷ all CPU accesses = m₁ × m₂. Here 0.10 × 0.20 = 0.02: only 2% of accesses go to RAM.
  • The formula needs the local rate. Given a global rate, divide by m₁ first: local = global ÷ m₁.

Worked example (three levels): L1 1 ns, misses 5%; L2 8 ns, local miss 30%; L3 30 ns, local miss 50%; RAM 200 ns. AMAT = 1 + 0.05 × (8 + 0.3 × (30 + 0.5 × 200)) = 1 + 0.05 × (8 + 0.3 × 130) = 1 + 0.05 × 47 = 3.35 ns.

Some textbooks state "L1 miss penalty" separately and count an L2 hit as costing (L1 time + L2 time). Read the question: if it gives the L2 access time, the nested formula above is the one to use.

Split vs unified, inclusive vs exclusive

  • Split L1 (instruction cache + data cache): the CPU fetches its next instruction (IF) and reads data (MEM) in the same clock cycle. Two separate caches never block each other. This is the Harvard architecture idea from episode 1, applied inside the cache. Often written L1i and L1d.
  • Unified cache: instructions and data share one cache. L2 and L3 are usually unified, so space goes wherever it's needed.
  • Inclusive cache: every block in L1 is also in L2 (or L3). To check whether any core has a block, look only in the outer level: simple. Cost: duplicated blocks waste some space, and evicting a block from L2 forces it out of L1 too.
  • Exclusive cache: a block is in L1 or L2, never both. Total usable space = L1 + L2, but blocks must be swapped between the levels on a miss.

Problem 4: many cores, many copies (cache coherence)

A multicore processor has several cores (complete CPUs) on one chip, each running its own program or thread at the same time, each with its own private L1 (and often L2) cache. A shared cache is one that all cores use, typically the L3.

Two friends print the trip plan: train at 6:00. Riya changes her copy to 7:00. Aman, with his old copy, reaches the station at 6:00. His copy is stale: an old value that is no longer true.

The failing attempt: private write-back caches, no protocol

# two cores, each with its own write-back cache
ram = {"x": 0}
cache = [{}, {}]        # core 0 cache, core 1 cache

def read(core, var):
    if var not in cache[core]:
        cache[core][var] = ram[var]   # miss: copy RAM
    return cache[core][var]

def write(core, var, value):
    cache[core][var] = value      # RAM later

print("core 1 reads x =", read(1, "x"))
write(0, "x", 1)
print("core 0 wrote x = 1")
print("core 1 reads x =", read(1, "x"))

Output:

core 1 reads x = 0
core 0 wrote x = 1
core 1 reads x = 0

This is the cache coherence problem: two cores looking at the same address see different values. A system is coherent when every read of an address returns the most recent write to it, whichever core made it.

The fix: snooping

All caches sit on a shared bus (a set of wires every cache can see). Before a core writes, it announces "invalidate x" on the bus, and every other cache listens (snoops) and deletes its copy. On a read miss, a cache also checks whether another cache holds a newer copy.

# same two cores, but every write is announced on the bus
ram = {"x": 0}
cache = [{}, {}]

def read(core, var):
    if var not in cache[core]:
        other = cache[1 - core]
        if var in other:       # snooped: newest copy
            ram[var] = other[var]
        cache[core][var] = ram[var]
    return cache[core][var]

def write(core, var, value):
    other = cache[1 - core]
    if var in other:
        del other[var]         # invalidate their copy
        print(f"  bus: invalidate {var} in core {1 - core}")
    cache[core][var] = value

print("core 1 reads x =", read(1, "x"))
write(0, "x", 1)
print("core 0 wrote x = 1")
print("core 1 reads x =", read(1, "x"))

Output:

core 1 reads x = 0
  bus: invalidate x in core 1
core 0 wrote x = 1
core 1 reads x = 1

This is a write-invalidate snooping protocol (the common kind). The alternative, write-update, sends the new value to the other caches instead of deleting their copies.

Snooping vs directory

Snooping Directory
Idea Broadcast every change; every cache listens A table records which caches hold each block; send messages only to those
Real-life A WhatsApp group: everyone gets every message The society office register that knows which flats have a copy of the notice
Good for A few cores on one bus Many cores
Cost The bus gets crowded as cores grow Memory for the table, an extra lookup per miss

The MESI protocol

Real snooping caches give every line one of four states (named by their initials):

State Meaning Who else has it? Same as RAM?
Modified Only my copy, and I changed it (dirty) Nobody No
Exclusive Only my copy, unchanged Nobody Yes
Shared A read-only copy; others may have it too Maybe Yes
Invalid No usable copy — —

Key transitions:

  • Read miss, nobody else has the line → E.
  • Read miss, another cache has it → both become S (if the other was M, it first writes its data back).
  • Write to an S line → send "invalidate" on the bus, others go to I, I go to M.
  • Write to an E line → straight to M, no bus message (nobody else has it). This is the whole reason the E state exists.
  • Another core writes my line → I.
# MESI states of ONE cache line in two cores
state = ["I", "I"]     # M, E, S or I per core

def read(c):
    o = 1 - c
    if state[c] == "I":
        if state[o] == "I":
            state[c] = "E"              # nobody else has it
        else:
            state[o] = state[c] = "S"   # M writes back
    show(f"core {c} reads")

def write(c):
    o = 1 - c
    if state[o] != "I":
        state[o] = "I"          # invalidate the other
    state[c] = "M"
    show(f"core {c} writes")

def show(op):
    print(f"{op + ':':<14} core0={state[0]}  "
          f"core1={state[1]}")

read(0); write(0); read(1); write(1); read(0)

Output:

core 0 reads:  core0=E  core1=I
core 0 writes: core0=M  core1=I
core 1 reads:  core0=S  core1=S
core 1 writes: core0=I  core1=M
core 0 reads:  core0=S  core1=S

(Extensions you may hear about: MOESI adds an Owned state, MESIF adds a Forward state. Both reduce RAM traffic for shared dirty data.)

Problem 5: two counters, one line (false sharing)

Two flatmates keep accounts in one notebook: rent on page 1, groceries on page 2. Different pages, but only one person can hold the notebook, so every write means fetching it from the other's room.

Coherence works on whole lines, not single variables. If core 0 keeps updating counter a and core 1 keeps updating counter b, and both sit in the same 64-byte line, every write must steal the line from the other core:

# two cores bump two DIFFERENT counters, 1000 times each
def run(same_line):
    holder, invalidations = {}, 0   # line -> core
    for i in range(1000):
        for core in (0, 1):     # 0 bumps a, 1 bumps b
            line = "L" if same_line else f"L{core}"
            if holder.get(line, core) != core:
                invalidations += 1   # steal the line
            holder[line] = core
    where = "the same line" if same_line \
        else "their own lines"
    print(f"a, b in {where}: {invalidations} invalidations")

run(True)
run(False)

Output:

a, b in the same line: 1999 invalidations
a, b in their own lines: 0 invalidations

This is false sharing: the cores share no data, but they share a line, so they cause coherence traffic anyway. The fix is padding (or alignment): place each core's busy variable in its own cache line, for example by adding unused bytes between them or using a language feature that aligns a variable to the line size.

Common mistakes (and the real output)

Mistake Real output Fix
LFU in a program that changes phase LFU: 0/10 hits in the new phase LRU, or age the LFU counters
Private write-back caches with no coherence protocol core 1 reads x = 0 (after core 0 wrote 1) Invalidate other copies on a write (snooping or directory)
The global L2 miss rate in the AMAT formula wrong AMAT = 2.2 ns right AMAT = 4 ns Use the local rate: local = global ÷ L1 miss rate
Write-back without a dirty bit RAM writes without dirty bit: 100 with dirty bit: 10 Write back only dirty lines
"More ways always means more hits" with FIFO FIFO 3 ways: 3 hits FIFO 4 ways: 2 hits Belady's anomaly: FIFO isn't a stack algorithm; LRU and OPT are
Two threads' counters side by side a, b in the same line: 1999 invalidations Pad each counter to its own line

The program behind rows 3 to 5:

# common mistakes, measured
# 1. the global L2 miss rate put into the AMAT formula
l1_hit, m1, l2_hit, m2_local, ram = 1, 0.10, 10, 0.20, 100
m2_global = m1 * m2_local                       # 0.02
wrong = l1_hit + m1 * (l2_hit + m2_global * ram)
right = l1_hit + m1 * (l2_hit + m2_local * ram)
print(f"wrong AMAT = {wrong:.1f} ns   right AMAT = {right:.0f} ns")

# 2. forgetting the dirty bit: write back EVERY evicted line
evicted, changed = 100, 10                      # 100 lines leave, 10 were written
print("RAM writes without dirty bit:", evicted, "  with dirty bit:", changed)

# 3. assuming more ways always means more hits with FIFO (Belady's anomaly)
def fifo(trace, ways):
    cache, hits = [], 0
    for b in trace:
        if b in cache:
            hits += 1
        else:
            if len(cache) == ways:
                cache.pop(0)
            cache.append(b)
    return hits
trace = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("FIFO 3 ways:", fifo(trace, 3), "hits   FIFO 4 ways:", fifo(trace, 4), "hits")

Output:

wrong AMAT = 2.2 ns   right AMAT = 4 ns
RAM writes without dirty bit: 100   with dirty bit: 10
FIFO 3 ways: 3 hits   FIFO 4 ways: 2 hits

Mini project: a write-back cache simulator with three replacement policies

A set-associative, write-back, write-allocate cache. Each line stores its tag and a dirty bit; a dirty victim costs one RAM write, and at the end every dirty line is flushed. The workload reads a[i] and writes b[i] for 64 ints, twice. The cache is 4 sets × 2 ways × 16 bytes = 128 bytes, smaller than the 512 bytes the loop touches, so this workload has many capacity misses.

# mini project: a set-associative, write-back, write-allocate cache simulator
# with a choice of replacement policy. Counts hits, misses and RAM writes.
import random

def simulate(trace, sets=4, ways=2, block=16, policy="LRU", seed=1):
    rng = random.Random(seed)
    cache = [[] for _ in range(sets)]   # each set: list of [tag, dirty], front = victim
    hits = misses = ram_writes = 0
    for op, addr in trace:
        blk = addr // block
        s, tag = blk % sets, blk // sets
        line = next((l for l in cache[s] if l[0] == tag), None)
        if line:
            hits += 1
            if policy == "LRU":                      # most recent goes to the back
                cache[s].remove(line); cache[s].append(line)
        else:
            misses += 1
            if len(cache[s]) == ways:                # set full: pick a victim
                victim = rng.choice(cache[s]) if policy == "RANDOM" else cache[s][0]
                cache[s].remove(victim)
                if victim[1]:                        # dirty -> write it back
                    ram_writes += 1
            line = [tag, False]
            cache[s].append(line)                    # write-allocate: bring it in
        if op == "W":
            line[1] = True                           # write-back: just mark dirty
    ram_writes += sum(l[1] for st in cache for l in st)   # flush at the end
    return hits, misses, ram_writes

# a loop that reads a[i] and writes b[i] for 64 ints, twice
trace = []
for rep in range(2):
    for i in range(64):
        trace += [("R", 4 * i), ("W", 1024 + 4 * i)]

for p in ["LRU", "FIFO", "RANDOM"]:
    h, m, w = simulate(trace, policy=p)
    print(f"{p:6}: hits {h:3}  misses {m:3}  RAM writes {w}")

Output:

LRU   : hits 192  misses  64  RAM writes 32
FIFO  : hits 192  misses  64  RAM writes 32
RANDOM: hits 164  misses  92  RAM writes 39
  • Each 16-byte block holds 4 ints, so 1 miss is followed by 3 hits (spatial locality): 64 misses for 256 accesses.
  • The 16 blocks of b are written back once per pass: 32 RAM writes. A write-through cache would make 128 RAM writes (one per write).
  • Random throws out a block that is still in use now and then, so it misses more here.
  • Try it: make sets=16 (a 512-byte cache) and watch the second pass become all hits; change the policy of a write-through cache by counting ram_writes += 1 on every "W".

Practice

  1. FIFO and LRU, 3 ways, trace A B C D A B E A B C D E. Hits for each?
  2. L1 1 ns, miss rate 4%; L2 12 ns, local miss rate 25%; RAM 150 ns. AMAT?
  3. Two cores, MESI: core 1 reads, core 0 reads, core 0 writes. States after each step?
  4. Extend the false-sharing demo to 3 cores. How many invalidations in the same line, and in separate lines?
  5. Three levels: L1 1 ns, 5%; L2 8 ns, 30% local; L3 30 ns, 50% local; RAM 200 ns. AMAT?
  6. The L1 miss rate is 6% and the global L2 miss rate is 1.5%. What is the local L2 miss rate?
  7. A program makes 1 million memory instructions, 30% of them writes. How many RAM writes with write-through (no write buffer merging)?
  8. L1 2 ns, 5% miss; RAM 200 ns. AMAT without an L2, and with an L2 of 20 ns and 40% local miss rate?
  9. How many bits per set does true LRU need for an 8-way cache?
  10. Why does a direct-mapped cache need no replacement policy?
  11. Why does the E state in MESI save a bus message?
  12. Which pairing is more common, and why: write-back + write-allocate, or write-back + no-write-allocate?
  13. Give one advantage of an inclusive L3 and one of an exclusive L2.
  14. Why is a split L1 instruction/data cache useful in a pipelined CPU?
Solutions

Numbers computed with a Python 3.13 script; its output:

Q1 FIFO 3 /12   LRU 2 /12
Q2 AMAT = 2.98 ns
Q4 3 cores same line: 2999   own lines: 0
Q5 three-level AMAT = 3.35 ns
Q6 local L2 miss rate from global 1.5% and L1 miss 6% = 0.25
Q7 write-through, 30% writes, 1M instructions -> RAM writes = 300,000
Q8 AMAT L1 2 ns 5%, no L2, RAM 200 = 12 ns; with L2 20 ns local 40% = 7 ns
  1. FIFO 3/12, LRU 2/12. This is the classic Belady string; here LRU is even worse than FIFO, which shows no policy wins on every trace. (OPT would get 5.)
  2. 1 + 0.04 × (12 + 0.25 × 150) = 1 + 0.04 × 49.5 = 2.98 ns.
  3. core 1 reads → core0=I, core1=E. core 0 reads → core0=S, core1=S. core 0 writes → core0=M, core1=I (an invalidate goes on the bus).
  4. 2,999 in the same line (every write after the first steals the line), 0 in separate lines.
  5. 3.35 ns (worked in the notes above).
  6. local = 0.015 ÷ 0.06 = 0.25 (25%).
  7. 300,000: every write goes to RAM.
  8. 12 ns without L2; 7 ns with it.
  9. 8! = 40,320 orders → ⌈log₂ 40,320⌉ = 16 bits per set.
  10. Each block has exactly one possible line, so the block already there is always the victim: there is no choice to make.
  11. In E, the core knows nobody else has a copy, so a write can go straight to M without telling anyone. From S it would have to broadcast an invalidate.
  12. Write-back + write-allocate. After the block is brought in, the following writes to it hit and stay in the cache; with no-write-allocate every write miss would go to RAM anyway, wasting write-back's advantage.
  13. Inclusive: to know whether any core holds a block, check only L3 (simple snoop filtering). Exclusive: no duplicates, so the total capacity is L1 + L2.
  14. IF and MEM both access memory in the same cycle; with separate caches they don't fight over one cache port (no structural hazard).

Quick quiz

L1 hits in 2 ns with a 5% miss rate. L2 hits in 20 ns with a local miss rate of 40%. RAM takes 200 ns. What is the AMAT?

  • A. 5 ns
  • B. 7 ns
  • C. 12 ns
  • D. 14 ns
Answer

B, 7 ns. 2 + 0.05 × (20 + 0.4 × 200) = 2 + 0.05 × 100 = 7 ns.

Interview questions

  • Why does a set-associative cache need a replacement policy? A new block can go into any of k ways; when they are all full, some rule must choose the victim.
  • LRU vs FIFO? FIFO evicts the oldest arrival; LRU evicts the oldest use. LRU follows temporal locality, so it usually wins, but it costs more bits and updates on every hit.
  • What is pseudo-LRU and why is it used? A cheap approximation of LRU (a few bits per set) because exact LRU needs ⌈log₂(k!)⌉ bits and constant updates.
  • What is Belady's OPT and why can't hardware use it? Evict the block used furthest in the future; it needs knowledge of the future. It's a yardstick.
  • What is Belady's anomaly? With FIFO, more frames/ways can produce more misses. LRU and OPT are stack algorithms and don't suffer from it.
  • Write-through vs write-back? Write-through updates RAM on every write (simple, RAM always current, more traffic). Write-back updates RAM only when a dirty line is evicted (less traffic, needs a dirty bit, more complex).
  • What is a dirty bit? A per-line bit set when the line is written; only dirty lines are written back on eviction.
  • What is a write buffer? A queue of pending writes so the CPU doesn't wait for RAM on each write-through.
  • Write-allocate vs no-write-allocate? On a write miss, either bring the block into the cache first, or write straight to RAM.
  • Local vs global miss rate? Local = misses ÷ accesses reaching that level; global = misses ÷ all CPU accesses = product of the local miss rates above.
  • Why multilevel caches? One cache can't be both large and fast; a small fast L1 plus a large slower L2/L3 gives low hit time and low miss rate.
  • Inclusive vs exclusive caches? Inclusive: outer level holds everything in the inner level (simple coherence checks, wasted space). Exclusive: no duplicates (more capacity, more data movement).
  • What is cache coherence? Every core reading an address sees the latest write to it, even though each core has a private cache.
  • Snooping vs directory? Snooping broadcasts on a shared bus and every cache listens; directory tracks the holders of each block and sends targeted messages, scaling to many cores.
  • Explain MESI. Four states per line: Modified (only copy, dirty), Exclusive (only copy, clean), Shared (read-only, maybe other copies), Invalid. A write needs M; getting there from S needs an invalidate broadcast.
  • What is false sharing and how do you fix it? Different variables used by different cores sit in one cache line, so coherence bounces the line between cores. Pad or align them to separate lines.

Glossary

Term Plain meaning Example
Cache Small, fast memory near the CPU holding copies of recently used blocks the kitchen counter
Block / line A fixed-size chunk of memory / the cache slot holding one 16 or 64 bytes
Set, way In a k-way cache, a group of k lines; one line in that group a 3-way set has 3 ways
Trace The list of blocks or addresses a program accesses, in order A B A C A D ...
Replacement policy The rule that chooses which block to throw out of a full set LRU
Victim The block chosen to be evicted jar put back on the shelf
Evict Throw a block out of the cache to make room cache.pop(0)
FIFO First in, first out: evict the earliest-arrived block put back the first jar taken out
LRU Least recently used: evict the block whose last use is oldest keep the salt you just used
Pseudo-LRU A cheaper approximation of LRU using a few bits per set tree of bits in an 8-way set
Random replacement Evict a randomly chosen block any jar
LFU Least frequently used: evict the block with the smallest use count LFU: 0/10 hits after a phase change
MFU Most frequently used: evict the block with the largest count rarely used
OPT / Belady's algorithm Evict the block needed furthest in the future; ideal, not buildable used to grade other policies
Belady's anomaly With FIFO, more ways/frames can give fewer hits 3 ways: 3 hits, 4 ways: 2 hits
Temporal locality Recently used data is likely to be used again soon a loop counter
Write-through Every write updates both the cache and RAM 1000 RAM writes
Write-back Writes update only the cache; RAM is updated when the line is evicted 1 RAM writes
Dirty bit Per-line bit: 1 = changed since it came from RAM the teacher's star on a page
Write buffer Small queue of pending RAM writes so the CPU needn't wait a post box
Write miss A write to a block not in the cache first write to x
Write-allocate On a write miss, bring the block in, then write it then reads hit
No-write-allocate On a write miss, write straight to RAM, skip the cache write-around
Multilevel cache Several cache levels, small/fast to big/slow L1 → L2 → L3 → RAM
L1, L2, L3 Level 1 (smallest, fastest, per core), level 2, level 3 (biggest, often shared) wallet, almirah, bank
Local miss rate Misses ÷ accesses that reach that level L2: 20%
Global miss rate Misses ÷ all CPU accesses; product of local rates 10% × 20% = 2%
AMAT Average memory access time = hit time + miss rate × miss penalty 4 ns with L2
Split I/D cache Separate L1 caches for instructions and for data L1i and L1d
Unified cache One cache for both instructions and data L2, L3
Harvard architecture Separate paths/memories for instructions and data the split L1
Inclusive cache Outer level holds a copy of everything in the inner level L3 contains all L1 blocks
Exclusive cache A block lives in only one level at a time L1 or L2, never both
Multicore processor Several complete CPUs (cores) on one chip a 2-core demo
Core One complete CPU inside a multicore chip core 0, core 1
Shared cache A cache used by all cores a shared L3
Stale data An old copy that no longer matches the latest write Aman's 6:00 plan
Cache coherence Every core sees the latest write to each address core 1 reads x = 1
Bus Shared wires connecting the caches and memory where "invalidate x" is announced
Snooping protocol Every cache watches the bus and reacts to other caches' actions the WhatsApp group
Invalidate Mark another cache's copy unusable bus: invalidate x in core 1
Write-invalidate / write-update On a write, delete others' copies / send them the new value MESI is write-invalidate
Directory protocol A table records which caches hold each block; messages go only to them society office register
MESI Coherence protocol with states Modified, Exclusive, Shared, Invalid core0=M core1=I
False sharing Different variables in one line cause coherence traffic between cores 1999 invalidations
Padding Unused space added so busy variables land in separate lines a second notebook

Summary

  • Replacement: FIFO evicts the oldest arrival, LRU the oldest use (usually best, built as pseudo-LRU), random is cheap and robust, LFU clings to old favourites (0/10 vs 8/10), OPT is the unbuildable ideal. FIFO can show Belady's anomaly.
  • Writes: write-through writes RAM every time (1000 writes; helped by a write buffer); write-back writes only evicted dirty lines (1 write). On a write miss: write-allocate (pairs with write-back) or no-write-allocate (pairs with write-through).
  • Multilevel: AMAT = h₁ + m₁ × (h₂ + m₂ × RAM) with local miss rates; global = m₁ × m₂. L2 took AMAT from 11 ns to 4 ns. L1 is usually split (I and D), L2/L3 unified; caches are inclusive or exclusive.
  • Coherence: private caches give stale data; snooping (broadcast) or directory (targeted) protocols fix it; MESI gives each line Modified, Exclusive, Shared or Invalid.
  • False sharing: two cores' variables in one line cost 1,999 invalidations; pad them apart.

Next episode: Pipelining and parallel processors. How a CPU works on five instructions at once, the hazards that break it, forwarding, branch prediction, superscalar and out-of-order CPUs, and Flynn's taxonomy.