Use this page as the contract behind every example in the course. It is an educational directory system, not a claim that a commercial protocol uses exactly these messages or directory encodings. The vocabulary follows the style of the Sorin, Hill, Wood and Nagarajan primer on memory consistency and cache coherence, second edition. Lessons follow every convention on this page without repeating it; a lesson that departs from one says so.
X is one location inside a 64-byte line; permissions cover the whole line, so neighbouring bytes share them. Tables show the value of X only. X starts at 0 in memory, with no cached copies.
Each trace resets to that state unless it gives an explicit warm-up prefix.
Local loads and stores act only with the required permission. Pending requests do not create permission. An exclusive holder may keep changing data locally until it processes a conflicting Inv, Fwd-GetS or Fwd-GetM.
A lesson names MSI, MESI or MOESI. E (MESI, MOESI) and O (MOESI) are explicit model extensions, not a silent change of protocol.
Delivery is reliable, but no FIFO order is assumed, either across message classes or between the same two nodes; no trace in the course depends on one. An ordered snooping bus is a separately stated model (Snooping on a Shared Bus). Reliability alone gives no bounded latency or fairness guarantee. H serializes conflicting transactions for X and keeps a pending entry while data or acknowledgements are outstanding.
Grant delivery: in Parts 1 to 3, H starts no conflicting transaction for X until the previous grant has been delivered, and the model assumes H can tell when that has happened. Real protocols either add a completion message from the requester or let the requester handle an Inv or Fwd that arrives before its Data; Part 4 covers both in Racing Requests at the Home. Later lessons that keep the assumption instead of a completion message show the step as its own row labelled (assumed); Part 8 shows the real completion messages (CHI CompAck, ACE RACK and WACK, TileLink GrantAck).
Term | Cache states | What it means | H forwards to it when |
|---|---|---|---|
Exclusive holder | E or M | The only cache that may read and write the line. | Another cache requests the line (Fwd-GetS or Fwd-GetM). |
Dirty-responsible holder | M or O | Memory may be stale; this cache must supply or write back the newest data. O may not write. | Another cache needs the data (MOESI O: Fwd-GetS, or Fwd-GetM alongside Inv to sharers). |
An M holder is both. H forwards to whichever role applies. 'Owner' means different things in different protocols, so the course does not use it alone.
H entry | Meaning | Data consequence |
|---|---|---|
U | No recorded cached holder | Memory is authoritative. |
S{C0,C1} | Read-only sharers in an MSI or MESI snapshot | Memory is current at this stable boundary. |
exclusive(C0) | C0 is the exclusive holder, in E or M | H cannot infer clean data: a silent local store may have changed E to M. |
O: C0, sharers {C1} | MOESI: C0 is dirty-responsible and may read; C1 holds S | Memory may be stale; neither cache may write until exclusive permission is acquired. |
F: C1, sharers {C0} | MESIF: C1 is the designated clean responder for reads; C0 holds S | Memory is current; F only chooses which cache answers. |
S{C0}, pend GetM C1, acks 0/1 | A transaction is in progress: the stable part, the pending request and requester, and acknowledgements received out of those required | Do not treat the requester as already holding the permission it asked for. |
Pending entries for other requests follow the same pattern, for example U, pend GetS C0 or exclusive(C0), pend GetS C1.
Name | Meaning | Local accesses while waiting |
|---|---|---|
IS^D | Was I, sent GetS, waits for Data | None: no usable value yet |
IM^D | Was I, sent GetM, waits for Data | None |
SM^D | Was S, sent GetM, waits for Data (often permission-only) | Loads hit the S copy; stores stall |
IS^D_I | Was IS^D, received Inv and sent Inv-Ack; waits for Data (Part 4, Racing Requests at the Home) | The pending load uses the value once, then the line goes to I |
OM^D | Was O, sent GetM, waits for Data (permission-only); MOESI (Part 8, When the Owned State Pays) | Loads hit; stores stall |
MI^A, EI^A, SI^A | Was M, E or S, sent PutM, PutE or PutS, waits for Put-Ack; a dirty value stays in the writeback buffer | Loads and stores to X stall; Inv or Fwd for X is still answered (from the writeback buffer) |
II^A | Lost the line to an Inv or Fwd-GetM while waiting for Put-Ack | Loads and stores to X stall until Put-Ack |
Inv-Acks are collected at H, so the requester waits only for Data, and an upgrade with sharers takes four serial legs: GetM, Inv, Inv-Ack, Data. The Primer instead sends Inv-Acks to the requester and puts the ack count in Data, which takes three legs; its states are therefore named IS^D, IM^AD and SM^AD. Both are legal. Within one lesson the diagram, table and prose agree on who collects the acknowledgements, and nobody grants or uses M until all have arrived.
Message | Direction in the educational model | Meaning |
|---|---|---|
GetS | Requester to H | Request readable data. MESI and MOESI may grant E when no other cache holds the line. |
GetM | Requester to H | Request exclusive write permission; an S or O holder can upgrade without a fresh data refill. |
Inv | H to a possible sharer | Revoke the line's read permission. |
Inv-Ack | Invalidated cache to H | The addressed permission has been revoked. H waits for all required acknowledgements before granting another writer. |
Fwd-GetS | H to the exclusive or dirty-responsible holder | Supply data for a reader and perform the named protocol's downgrade. |
Fwd-GetM | H to the exclusive or dirty-responsible holder | Supply the newest data and give up permission so that another cache can write. |
Data | H or a holder to the specified recipient | Carry a value and/or grant the explicitly named permission. A forwarding response does not grant unrelated permission. |
PutS | S holder to H | Notify H of a clean shared eviction; waits for Put-Ack. |
PutE | E holder to H | Notify H of a clean exclusive eviction; waits for Put-Ack. |
PutM | M or O holder to H | Write back dirty data and responsibility; waits for Put-Ack. |
Put-Ack | H to the evicting cache | H has accepted the release and, for PutM, written memory. A Put from a cache H no longer records as a holder also gets Put-Ack, with no change to the directory or memory. It is not a universal guarantee of DRAM persistence. |
Evictions are notified: PutS, PutE and PutM each wait for Put-Ack before the cache forgets the line. Silent clean eviction, where an S or E copy is dropped without a message, is a variant taught in Part 3 (Clean Eviction: Silent or Notified). In MSI and MESI a dirty read settles as S/S only after memory has been updated. In MOESI an M holder can downgrade to O on a read, keeping dirty responsibility while memory stays stale.
Item | Convention |
|---|---|
Participants | Sequence diagrams list C0, C1, H, then memory. Messages are numbered; a numbered arrow is observed at delivery, not when it is sent. |
Local events | A core's own load or store is a note labelled L (L1, L2 when there are several), not an interconnect message. |
Memory at H | H reading or writing memory is a note such as |
Names | 'Memory' or 'memory = 0' means the memory node. M on its own always means the Modified state. |
Cells | Cache cells are state / value: |
Rows | Each row is the snapshot after that delivery or local event, not a clock cycle. |
Newest data | The last column lists every place that holds the newest value, including data in flight, written as 'Data(1) in flight to H'. Revoking permission must not make that value disappear. |
Mermaid text | Labels avoid semicolons and the hash sign, which the diagram renderer treats as syntax. |
Grant delivery rows | When H sends a grant, the row where the requester receives it still shows H's pending entry; the next row, labelled (assumed) grant delivered, shows H's settled entry. The same applies when the Data comes from another cache. |
Fwd-GetS Data at H | MSI and MESI: the entry stays |
Put during a pending transaction | A Put that arrives while X has a pending transaction waits in X's pending entry until that transaction's forward or Inv is answered. A Put from a cache H no longer records as a holder gets Put-Ack with no directory or memory change. |
Python models | A model in a later part may simplify the course protocol, for example an upgrade grant that carries memory's value, or when H updates its record. Each model says where it simplifies. |
The base model omits virtual addresses, multiple cache levels, speculation, finite queues, transport errors, instruction-cache maintenance and power transitions. A lesson that needs one states it as an extension (see the table below). The model does not supply a complete ISA memory model, language-level synchronization contract or cycle-accurate implementation. Transient-state names and pending directory entries are educational labels, not the encodings of any product. I means no usable copy: old bits left in the data array are not a readable value. Numbers and traces are illustrative, not captured silicon measurements. Where a lesson cites gem5 or another real system, it uses the cited definition, not that system's messages or hierarchy.
Each extension below is introduced by the lesson linked, applies only where a lesson says it does, and changes nothing else in this page. The ordering, data and notation rules above stay in force.
Extension | What it adds | Introduced in |
|---|---|---|
A second line Y | Y in a different 64-byte line, Y = 0 initially, for resource cycles and cross-location ordering | |
Two words in one line | X at offset 0 and Y at offset 8 of the same line, for false sharing | |
Three or four cores | C2 (and C3) where sharing or races need more than two caches | MESIF and the Forward State, Limited Pointers and Coarse Vectors, the three-core capstone |
Completion message | Complete from the requester after it installs Data, instead of the grant-delivery assumption | |
Finite buffers and credits | Bounded pending entries, ingress and egress slots, NACKs and credits, so backpressure and resource cycles become possible | |
Finite inclusive filter F | H's holder record has a limited number of entries and must back-invalidate to free one | |
Clusters and dies | Clusters of cores behind local proxies H0 and H1, a global record G at H, then clusters on different dies | |
Store buffers and load queues | Per-core store buffers (TSO) and load-queue snooping for ordering | |
An LLC at H | PutM writes the LLC line; memory is written only when the LLC evicts a dirty line | |
A device D | A DMA agent on a coherent or non-coherent path | |
Power states | A cache that can power down or enter retention, with Leave, Leave-Ack, Join and Join-Ack | |
Clock domains | A clock domain on each side of H, one asynchronous FIFO per message class and direction | |
ECC and poison | Check bits on tags, data and directory, and a poison bit on Data | |
Real protocol names | ACE, CHI and TileLink messages and states, always with the specification and revision |
Not under the grant-delivery assumption of Parts 1 to 3: H starts no conflicting transaction for X until the previous grant has been delivered. With no FIFO order, the Inv could reach C1 before its Data. Real protocols add a completion message or let C1 handle the early Inv, as Part 4 shows.