The earlier lessons argued about E and O one transaction at a time. Here a small simulator runs a whole trace and counts. It uses the course model's messages and routes, with data through H and acks collected at H, extended to three cores. Each operation completes before the next starts, so there are no races. Messages are counted per delivered message, not per byte.
Event at H | Messages counted | Memory access |
|---|---|---|
GetS, no exclusive or dirty holder | GetS, Data = 2 | 1 read |
GetS, holder in E or M (MSI, MESI) | GetS, Fwd-GetS, Data to H, Data = 4 | 1 write |
GetS, holder in M or O (MOESI) | 4, holder ends in O | none |
GetM | GetM, Data, plus Inv and Inv-Ack per S copy, plus Fwd-GetM and Data to H if a holder exists | 1 read only from I with no holder |
Evict | PutS, PutE or PutM, then Put-Ack = 2 | 1 write for PutM |
The trace: C0 stores X, then C1 and C2 each read X twice (the second read hits), for three rounds; finally C0 evicts X. Every load is checked against the last value stored. Two broken variants are run. The first lets memory answer a read while an O holder exists, which is exactly the shortcut O forbids. The second lets O leave without writing memory, as if it were a clean PutS.
def run(proto, trace, broken=None):
st, val, mem, last = {}, {}, 0, 0
n = {"msgs": 0, "mem_wr": 0, "mem_rd": 0}
for op, c in trace:
s = st.get(c, "I")
others = {k: x for k, x in st.items() if k != c and x != "I"}
holder = next((k for k, x in others.items() if x in "EMO"), None)
if op == "load" and s == "I":
if holder is None or (broken == "read" and others[holder] == "O"):
n["msgs"] += 2; n["mem_rd"] += 1 # GetS, Data from memory
val[c] = mem
st[c] = "E" if proto != "MSI" and not others else "S"
else:
n["msgs"] += 4 # GetS, Fwd-GetS, Data, Data
val[c] = val[holder]
if proto == "MOESI" and others[holder] in "MO":
st[holder] = "O" # keep dirty responsibility
else:
st[holder] = "S"; mem = val[holder]; n["mem_wr"] += 1
st[c] = "S"
assert val[c] == last, (proto, c, val[c], last)
elif op == "load":
assert val[c] == last # hit
elif op == "store":
if s not in "EM": # E -> M is silent
sharers = [k for k, x in others.items() if x == "S"]
n["msgs"] += 2 + 2 * len(sharers) # GetM, Data, Inv/Inv-Ack
if holder is not None:
n["msgs"] += 2 # Fwd-GetM, Data to H
elif s == "I":
n["mem_rd"] += 1
for k in others:
st[k] = "I"
last += 1
st[c], val[c] = "M", last
elif op == "evict":
n["msgs"] += 2 # Put*, Put-Ack
if s == "M" or (s == "O" and broken != "evict"):
mem = val[c]; n["mem_wr"] += 1 # PutM writes memory
st[c] = "I"
if not any(x in "MO" for x in st.values()):
assert mem == last, ("memory", mem, last) # memory current when clean
return n
def producer(rounds, readers):
t = []
for _ in range(rounds):
t += [("store", 0)] + [("load", r) for r in readers] * 2
return t + [("evict", 0)]
pc = producer(3, [1, 2])
msi, mesi, moesi = (run(p, pc) for p in ("MSI", "MESI", "MOESI"))
assert msi == mesi == {"msgs": 34, "mem_wr": 3, "mem_rd": 4}
assert moesi == {"msgs": 40, "mem_wr": 1, "mem_rd": 1}
one = producer(3, [1])
a, b = run("MESI", one), run("MOESI", one)
assert a["msgs"] == b["msgs"] == 24 and (a["mem_wr"], b["mem_wr"]) == (3, 1)
assert a["mem_rd"] == b["mem_rd"] == 1
soon = [("store", 0), ("load", 1), ("evict", 0)]
assert run("MESI", soon) == run("MOESI", soon) == {"msgs": 8, "mem_wr": 1, "mem_rd": 1}
private = [("load", 0), ("store", 0)]
assert run("MSI", private)["msgs"] == 4
assert run("MESI", private)["msgs"] == run("MOESI", private)["msgs"] == 2
def caught(broken):
try:
run("MOESI", pc, broken=broken)
except AssertionError as e:
return e.args[0]
raise AssertionError(broken + " variant was not caught")
assert caught("read") == ("MOESI", 2, 0, 1) # C2 got memory's 0 while C0 held O / 1
assert caught("evict") == ("memory", 0, 3) # O left like PutS, memory never written
print("PASS: O saves memory writes, E saves the private upgrade, both broken O variants caught")Trace (illustrative) | Protocol | Messages | Memory writes | Memory reads |
|---|---|---|---|---|
3 rounds, readers C1 and C2 | MSI, MESI | 34 | 3 | 4 |
3 rounds, readers C1 and C2 | MOESI | 40 | 1 | 1 |
3 rounds, reader C1 only | MESI | 24 | 3 | 1 |
3 rounds, reader C1 only | MOESI | 24 | 1 | 1 |
Store, one read, evict | MESI, MOESI | 8 | 1 | 1 |
Private load then store | MSI | 4 | 0 | 1 |
Private load then store | MESI, MOESI | 2 | 0 | 1 |
MSI and MESI tie on the producer trace because the first access is a store, so E is never granted. MOESI saves two memory writes and three memory reads over three rounds, but C2's reads now go to C0 instead of memory, two extra messages per round in this H-routed model. With one consumer, O is free. When the line is evicted straight after one read, O changes nothing. On a private line, E saves the GetM and its Data that MSI needs for the upgrade.
The first broken run fails at round 1: C2 is served memory's 0 while C0 holds O / 1. The checker compares each returned value with the last store, not with memory, so it catches the stale response although every permission was legal. The second broken run returns correct values on every load, because C1 and C2 still hold 3, but the final check finds memory = 0 after the last dirty copy left: the newest value was lost, and the next miss would read 0.
MESI writes memory at the dirty read and C0 later leaves S with PutS. MOESI skips that write but C0 leaves O with PutM, which writes memory. Both send GetM and Data, then four messages for the read, then two for the eviction, and both write memory once.