How do you write a coherence decision so a team can act on it?

A design memo records one decision: the problem, what limits the choice, the options, numbers that compare them, the recommendation and what would change it. It is short because readers decide from the first page. The structure below works for any coherence decision: a protocol state set, an LLC policy, a routing choice.

The sentence that separates a senior memo from a junior one is the flip condition: 'we recommend MOESI; if fewer than about 25% of hand-offs reuse a line still in the producer's cache, MESI is better'. It tells the reader which measurement would change the decision.

Worked memo (illustrative): MESI or MOESI for an accelerator hand-off

Problem

A CPU core writes command descriptors into a ring, and an accelerator's coherent cache reads each one. On the course model C0 is the CPU producer, C1 the accelerator's cache and X one descriptor line. Decide whether the coherence protocol on this interface should be MESI or MOESI.

Constraints

• Memory write bandwidth on this interface is the limiting resource (illustrative).

• MOESI's extra transitions (M to O, O upgrade, PutM from O with sharers) cost verification time, so they are worth taking only if they remove at least a quarter of the memory writes, 0.25 per hand-off (illustrative threshold set by the team).

• Routing as in the course: data through H, Inv-Acks at H, notified evictions, one consumer.

Options

• MESI: every dirty read by C1 makes H write memory.

• MOESI: C0 goes from M to O on C1's read, memory stays stale, and C0 writes back once with PutM.

Analysis

Each hand-off is a round: C0 stores X, C1 loads X. In a keep round C0 still holds X when it writes the next descriptor; in an evict round C0's cache evicts X after the hand-off. The per-round message counts follow the routing table of Comparing Protocol Traffic, and the keep round is the one traced in When the Owned State Pays:

A store after an evict round also costs a memory read under both protocols, because C0 starts from I. Messages and memory reads are therefore equal round by round; only memory writes differ, by one per keep round. The script runs two 20-round mixes on a single trace each (seed 1), including the cold start and a final flush, so the write MOESI owes at the end is counted, then finds the flip point over ten seeds. Mix A is a small ring where 16 of 20 hand-offs reuse a line still in C0's cache; mix B is a large ring where only 2 do.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import random

def run(proto, trace, writes_at_puts=True):
    st, n = {0: "I", 1: "I"}, {"msgs": 0, "wr": 0, "rd": 0}
    for op, c in trace:
        o = 1 - c
        if op == "store" and st[c] not in "EM":
            n["msgs"] += 2 + (2 if st[o] == "S" else 0)   # GetM, Data, Inv, Inv-Ack
            if st[o] in "MO":
                n["msgs"] += 2                            # Fwd-GetM, Data to H
            elif st[c] == "I":
                n["rd"] += 1                              # H reads memory
            st[o], st[c] = "I", "M"
        elif op == "load" and st[c] == "I":
            if st[o] in "EMO":
                n["msgs"] += 4                            # GetS, Fwd-GetS, Data, Data
                if proto == "MOESI" and st[o] in "MO":
                    st[o] = "O"                           # memory stays stale
                else:
                    st[o] = "S"; n["wr"] += 1             # H writes memory
            else:
                n["msgs"] += 2; n["rd"] += 1              # GetS, Data from memory
            st[c] = "S"
        elif op == "evict" and st[c] != "I":
            n["msgs"] += 2                                # PutS or PutM, Put-Ack
            if st[c] in "MO" and writes_at_puts:
                n["wr"] += 1                              # PutM: H writes memory
            st[c] = "I"
    return n

def trace(keep, rounds=20, seed=1):
    kinds = ["keep"] * keep + ["evict"] * (rounds - keep)
    random.Random(seed).shuffle(kinds)
    t = []
    for k in kinds:
        t += [("store", 0), ("load", 1)] + ([("evict", 0)] if k == "evict" else [])
    return t + [("evict", 0)]                            # final flush: owed writes count

def recommend(keep, rounds=20, seed=1, **kw):
    a, b = (run(p, trace(keep, rounds, seed), **kw) for p in ("MESI", "MOESI"))
    saved = (a["wr"] - b["wr"]) / rounds
    return ("MOESI" if saved >= 0.25 and b["msgs"] <= a["msgs"] else "MESI"), a, b

for keep in range(21):                                   # general claim, every mix
    _, a, b = recommend(keep)
    assert a["msgs"] == b["msgs"] and a["rd"] == b["rd"] and a["wr"] == 20
    assert keep - 1 <= a["wr"] - b["wr"] <= keep         # about one write saved per keep round
rec, a, b = recommend(16)                                # mix A: small ring
assert rec == "MOESI" and a == {"msgs": 168, "wr": 20, "rd": 5} and b["wr"] == 5
rec, a, b = recommend(2)                                 # mix B: large ring, the failing case
assert rec == "MESI" and a == {"msgs": 194, "wr": 20, "rd": 18} and b["wr"] == 18
rec, a, b = recommend(0)
assert rec == "MESI" and a == b                          # no keep rounds: O changes nothing
flips = {min(k for k in range(21) if recommend(k, seed=s)[0] == "MOESI") for s in range(1, 11)}
assert flips == {5, 6}                                   # flip point depends on the seed
rec, _, b = recommend(0, writes_at_puts=False)           # analysis that forgets PutM's write
assert rec == "MOESI" and b["wr"] == 0                   # the deferred-write trap
print("PASS: MOESI pays for mix A, not for mix B, flip at 5 to 6 of 20 over 10 seeds, deferred-write trap caught")

The broken analysis in the last check counts MOESI's writes only at reads and forgets the PutM: it reports zero writes and recommends MOESI even when no line is ever reused. That is the trap from When the Owned State Pays: O defers the write, and only removes it when the producer writes the line again first.

Recommendation

For mix A, MOESI: it removes 0.75 memory writes per hand-off for the same messages and reads. The recommendation flips to MESI below 5 to 6 keep rounds in 20 (25 to 30%), depending on the shuffle seed: MOESI saves one write per keep round, minus the owed final write when the run ends on a keep round, so over long runs the flip tends to 25%. Mix B is well below it: MOESI saves 0.1 writes per round and does not pay for its extra transitions.

Risks

• The keep fraction is a property of ring size against C0's cache capacity; a larger ring in a later software release moves the design toward mix B.

• A second reader (for example a core polling the descriptor) adds two messages per round under MOESI through H, as the three-core run in Comparing Protocol Traffic shows. If the interconnect, not memory, becomes the limit, the recommendation must be re-run.

• The model has no races and counts messages, not bytes or latency.

Verification plan

• Coverage for every new MOESI cell: M to O on Fwd-GetS, O upgrade with a sharer, Fwd-GetM to O with sharers, PutM from O while sharers remain, and each racing with an eviction.

• The reference model must catch both broken O variants of Comparing Protocol Traffic: memory answering while O exists, and O leaving like a clean PutS.

Related topics

• Shared course model

• Part 8: Comparing Protocol Traffic

• Part 8: Choosing a Protocol