The decision, the evidence behind it, the condition that would change it and what is still unproven. The memo structure is taught in Writing a Design Memo: problem, constraints, options, analysis, recommendation with its flip condition, risks, verification plan. This lesson fills it in for the capstone, so you can compare your own memo with a worked one. Everything below comes from the earlier steps: the model of Build the Model, the traces of Find the Races and the numbers of Fix and Compare.
Choose the protocol for the first implementation of the X-line directory (MESI or MOESI), and approve the three home-controller rules the capstone's race hunt found to be required. The decision is needed now because the rules fix the structure of H's Put path, its sharer bookkeeping and its input buffers.
Limiting resource (illustrative): messages through H's interconnect port. Memory write bandwidth has headroom on this design.
Verification budget (illustrative): one protocol can be taken through the race model, the planted-bug audit and RTL regression before freeze. Every state and transition beyond MESI must be paid for from that budget.
Fixed: three private write-back caches, one home with directory and memory controller, the course message set, Inv-Acks collected at H, data from a holder routed through H, notified evictions with Put-Ack, an unordered network, two request slots at H's input.
MESI: every read of dirty data by another cache makes H write memory.
MOESI: the dirty holder moves to O on such a read and memory stays stale until the last O holder writes back with PutM. Adds O and its transitions (M to O on Fwd-GetS, Fwd-GetM to O with sharers, O upgrade, PutM from O).
The executable model (about 150 lines of Python, MESI) checks after every event that every usable copy equals the golden value, that H's entry and memory agree with the holders, and that SWMR holds; it also checks message legality, progress and an exact directory at quiescence. It passes 20 seeds of 4,000 events and one run of 100,000 events, and those runs contain every race below. Three planted defects were each found by the intended check:
Bug | Class | Found by | Why it matters | Rule adopted |
|---|---|---|---|---|
Queued upgrader removed from the sharer set | Lost invalidation (safety) | Value checker with SWMR at the same event, all 20 seeds, 8 of 30 short runs | Silent stale reads after a permission-only upgrade; nothing else touches the stale copy | Clear a sharer bit only on its Inv-Ack or Put; grant M only with all acks |
Late PutM accepted from a non-holder | Stale writeback (safety) | Value checker, authority half, all 20 seeds, 15 of 30 short runs | Memory overwritten with old data and the real holder forgotten; without the authority check the symptom appears much later | Put from a non-holder: Put-Ack, no change; WB entry held until Put-Ack |
Requests and responses share H's input | Resource cycle (progress) | Progress check, all 20 seeds, 23 of 30 short runs | Permanent hang under ordinary contention; invisible to value checks | Responses in their own class with reserved slots (n - 1, so none ever waits) |
Counter trace, two rounds (illustrative) | Messages | Memory writes |
|---|---|---|
MESI | 70 | 6 |
MOESI | 82 | 1 |
Difference | MOESI +12 | MOESI -5 |
Per steady turn | MESI 12, MOESI 14 | MESI 1, MOESI 0 |
MOESI removes the memory write at each read of dirty data, up to 5 of the 6 writes here, and pays 2 extra messages per turn (12 in all) because the second reader is served by the O holder through H instead of by memory. On a private line the two are identical. The MESI numbers come from the verified model and match an independent counter; the MOESI numbers come from counting only.
MESI for the first implementation, with the three rules above. Flip condition: MOESI pays when the memory writes it saves, up to 5 per 6 turns here, are worth more than 2 extra messages per turn on the limiting resource, that is when one memory write costs more than about 2.4 messages over the whole trace (12 messages for 5 writes), measured on the target workload, and the verification budget can absorb O.
The model assumes H learns when its grant is delivered. A real design needs a completion message or transient states that accept an early Inv or Fwd (the Part 4 race); this is the largest gap between model and design.
The traffic trace is illustrative. If the workload shares dirty lines more often, or memory write bandwidth becomes the limit, the flip condition may be met and the decision must be re-run on a measured trace.
One line and one outstanding request per cache: cross-line resource cycles, like the two-line deadlock of Part 5, are not exercised.
Caches always accept H's messages. The cache side needs its own reserved resources for forwards and invalidations.
No timing: starvation and fairness on a contended line are not checked, only deadlock.
Item | Method | Exit criterion |
|---|---|---|
Three rules above | The five directed race scripts (each arrival order of each race) as regression tests, on the RTL through the same scoreboard | All pass in each scripted order and in every drain order the testbench can force |
Planted-bug audit | Re-plant each defect in the RTL behind a test-only switch | Each fails the intended check |
Random traffic | Seeded runs with race coverage counters (Inv at SM^D and SI^A, forwards at MI^A and EI^A, late Puts, full request buffer, loads hitting in SM^D) | Every coverage point hit; failing seeds kept as regressions through their logs |
Progress | Formal or bounded check that responses always sink; drain check at the end of every test | No reachable state with pending work and no enabled move |
Grant delivery | Add the completion message or early-Inv handling to the model before RTL freeze | Model passes the same suite without the delivery assumption |
If MOESI is chosen later | Run O and its transitions through the same race model and planted-bug audit | The broken-O variants are caught, and the counted MOESI numbers are reproduced by the model |
Check | Yes if... |
|---|---|
Problem first | The first paragraph says what must be decided and why now |
Constraints | The limiting resource and the verification budget are named, with what may not change |
Options | Two or three real alternatives, each in one line |
Analysis with evidence | Model and assumptions stated; each bug has its check, its seeds and a pointer to a reduced trace; each number is asserted by a runnable block |
Traffic honest | Trace, routing and what is counted are named; numbers labelled illustrative; the saving and its cost both shown |
Recommendation with a flip condition | It gives the choice and the number at which it would change |
Risks | The model's simplifications appear as risks, with the largest one first |
Verification plan | Each item has a method and an exit criterion someone else can check |
Length | Fits on two pages; detail lives in linked traces and code |
That the seeds show the fixed model passes the traffic it generated, including the counted races, and nothing more. The memo's risk list names what the model cannot see (grant delivery, multiple lines, cache-side resources, fairness), and the verification plan says how each will be closed. A pass is evidence within stated assumptions, not a proof.
Over the two rounds MOESI sends 82 messages against 70 and writes memory once against 6 times: 12 extra messages buy 5 saved writes, 2.4 messages per write. In a steady turn MOESI sends 14 against 12 and writes 0 against 1, so 2 messages per write; each of the six turns costs MOESI 2 extra messages and saves 1 write (12 and 6 in all), but MOESI still owes one write at the end, when C2 leaves O with PutM, so the net saving is 5 and the whole-trace figure is 12 / 5 = 2.4.