Definitions use the course model. Real protocols can encode the same responsibilities differently; matching names do not guarantee matching semantics. Terms are grouped by the part that introduces them and listed alphabetically within each group; the last column links the lesson that teaches the term.
Term | Meaning | Taught in |
|---|---|---|
Cache line | The allocation and coherence unit; 64 bytes in our model. X is one location inside a line; permissions cover the whole line. | |
Coherence | The permission and value rules for accesses to one location, implemented here using line-granularity transactions. | |
Consistency | The architectural rules constraining observable memory executions, including ordering across locations. | |
Data-value invariant | The value at the start of an epoch is the value at the end of the last write epoch; if there has been no write, the initial value. | |
Directory | Metadata identifying possible sharers, the exclusive or dirty-responsible holder and pending actions. It is not itself a data copy unless explicitly buffering data. | |
Dirty responsibility | The obligation to preserve and eventually forward or write back data that memory may not hold. It need not imply current write permission. | |
Dirty-responsible holder | The cache in M or O: memory may be stale, and this cache must supply or write back the newest data. An O holder may not write. | |
Epoch | An interval of one line's history. In a write epoch one cache holds exclusive write permission; in a read epoch there is no writer and zero or more caches hold read-only copies. | |
Exclusive holder | The cache in E or M: the only cache that may read and write the line. H records it as exclusive(C0). | |
Home H | The serialization and directory agent for a line, including the memory-controller role in this model. | |
Invalidation | Revocation of a cached copy's permission. It need not erase the physical data bits. | |
Owner | Not used alone in this course, because protocols disagree on its meaning. Say exclusive holder or dirty-responsible holder. | |
Permission | Authority to read or write, independent of whether a register or SRAM still physically contains bits. | |
Serialization point | Where conflicting transactions are ordered. Request ordering, permission grant, data arrival and software retirement need not be the same event. | |
Sharer | An agent recorded as possibly holding a readable copy. A conservative directory may retain false positives, but must not omit a real holder when revoking permission. | |
Snoop filter | A finite structure that predicts which caches may hold a line, so that probes go only to them instead of being broadcast. A positive result means possibly present, not newest data; a negative result may skip a target only when the filter's maintained invariant proves absence. | |
Stable state | A state summarising permissions between transactions. Stable does not mean the value can never change locally. | |
SWMR | Single writer or multiple readers: exclusive write permission cannot coexist with another agent's read or write permission for the same line. | |
Transient state | State recording a transaction in progress and its outstanding data, permissions or acknowledgements, such as IS^D, IM^D, SM^D and the eviction states MI^A, EI^A, SI^A and II^A. | |
Write-back (cache policy) | A cache may keep a modified value without immediately updating memory; it must preserve responsibility for that value until it is written back or transferred. |
Term | Meaning | Taught in |
|---|---|---|
Acknowledgement | Evidence that a specified action completed; exactly what it establishes depends on the message and protocol. | |
Backpressure | The receiver has no space, so the sender keeps the message and does not send it yet. A finite stall that ends when capacity returns; not by itself a progress failure. Different from a NACK (the receiver saw the request and rejected it) and from queueing (the receiver kept it). | |
Completion message | A message from the requester telling H that its grant has arrived (called Complete in the course; real protocols use names such as CompAck, GrantAck or RACK). H holds the next conflicting transaction for X until it arrives. | |
Forwarding | H directs a request to the exclusive holder or the dirty-responsible holder, which supplies the data and gives up or downgrades its permission. | |
IS^D_I | The Primer's name for a cache that was in IS^D and received an Inv before its Data. It sends Inv-Ack at once, uses the late Data once for the pending load, then drops the copy and becomes I. | |
MSHR | Miss-status holding register: a core-side record of an outstanding miss and the local operation waiting for it. Different from H's pending entry, which records the system work for the line. | |
OM^D | Was O (MOESI), sent GetM, waits for permission-only Data. The O analogue of SM^D: loads hit, stores stall. | |
Pending entry | H's record of a transaction in progress for a line: requester, current holders, required revocations, data source and grant progress, written as | |
Writeback (PutM transaction) | A cache sends PutM with its dirty data to H and waits for Put-Ack, which means H has accepted the data and the responsibility. It is not a universal guarantee of DRAM durability. | |
Writeback buffer (WB entry) | Storage that holds an evicted line's address and data from PutM until Put-Ack. Forwards and invalidations for X must search it, because it may hold the only current value. |
Term | Meaning | Taught in |
|---|---|---|
Back-invalidation | Home-initiated revocation of private copies so that a tracking entry (a filter entry or an inclusive LLC way) can be freed: Inv for clean holders, Fwd-GetM on H's own behalf for a dirty one. The entry is freed only after clean holders ack or dirty data reaches memory. | |
Deadlock | A set of operations cannot progress because each waits on resources or actions held by another in the set, and no permitted event can free any of them. | |
Fairness assumption | A stated service guarantee used in a progress argument, not an automatic property of a reliable channel. | |
Inclusive filter | A snoop filter that keeps the invariant: every cache holding X in any non-I state, or with an admitted fill for X in flight, is in F(X). A false positive costs work; a false negative is a correctness bug. | |
Livelock | Messages keep moving but no useful operation completes, for example M passing back and forth between two caches before either store performs. | |
Message class | A group of messages defined by what consuming them may wait on: requests (GetS, GetM, PutS, PutE, PutM), forwards (Inv, Fwd-GetS, Fwd-GetM) and responses (Inv-Ack, Data, Put-Ack). | |
Protocol deadlock | A cycle through endpoint resources, such as pending entries and ingress queues, created by dependencies between message classes. Broken by the request < forward < response rule, reserved response capacity and a virtual network per class. | |
Request < forward < response rule | Consuming a message may wait only on resources of a later class. Responses wait on nothing, because each pending entry reserves its response slot and data destination when it is allocated, so a response can always be sunk. | |
Routing deadlock | A cycle of packets each holding router buffers or channels while waiting for the next, around a loop in the topology, independent of what the messages mean. Broken inside each virtual network by deadlock-free routing or an escape channel. | |
Starvation | One eligible request is bypassed without bound while other requests complete, for example a GetM NACKed on every retry. | |
Virtual channel | A separate buffer and credit set multiplexed on one physical link. | |
Virtual network | One message class's own virtual channels on every link plus its own endpoint queues, end to end. Independent only if the resources its progress needs cannot be held by blocked work of another class. |
Term | Meaning | Taught in |
|---|---|---|
Acquire | A load (or the load part of an atomic) that orders the core's later accesses after it. Paired with a release: operations before the release are ordered before operations after an acquire that reads the value that release stored. | |
Atomic RMW | A read-modify-write operation that is indivisible under its specified architectural semantics; coherence alone is not the complete specification. | |
Fence | An ordering operation with architecture-defined scope and semantics. It orders a core's own accesses (a TSO fence stalls younger loads until older stores have drained); it does not clean or flush caches. | |
Litmus test | A tiny multi-core program with stated initial values whose possible final register values distinguish memory models, such as SB (store buffering), MP (message passing) and IRIW. | |
Load replay | Re-execution of a load that has performed but not committed when an Inv (or loss of the line) matches its load-queue entry and the core's ordering rules would otherwise be violated. The Inv-Ack is sent at once, never delayed until the replay. | |
LR/SC | Load-reserved reads a location and records a reservation; store-conditional writes only if the reservation is still valid, and reports success or failure. A write by another core clears the reservation even if the value returns to its old bits (ABA): it tracks interference, not values. | |
Other-multi-copy-atomic | A store that has been seen by one other core has been seen by all other cores; only the issuing core may see its own store early, through its store buffer. Armv8-A has this property; an invalidation protocol that collects every Inv-Ack before granting M provides it. | |
Release | A store (or the store part of an atomic) that orders the core's earlier accesses before it, so an acquire that reads its value also sees them. | |
Reservation set | The bytes an LR reserves (RISC-V). It may be arbitrarily large but must include all bytes of the addressed word or doubleword; a store from another hart to it must make the SC fail. | |
Store buffer | A per-core queue of stores that have executed but not yet joined the shared memory order. Under TSO it is FIFO and the core's own loads forward from the newest matching entry; it is why SB can return r1 = r2 = 0 under TSO. |
Term | Meaning | Taught in |
|---|---|---|
Coarse vector | Dir_i CV_r: when the sharers no longer fit, the pointer bits are reinterpreted as group bits, one per group of r caches. A later GetM sends Inv to every member of every set group, including members that never held the line. | |
False sharing | Different cores write distinct data in the same line, so line-granularity permission makes the line move between them although no logical variable is shared. | |
Full bit vector | One presence bit per cache plus state bits in every directory entry: 2 + N bits in the course format, 66 bits for 64 caches, tags and ECC excluded. | |
Hit-modified | A snoop-response type meaning a local miss was served from a line another cache held in M. It shows a line moving between writers, not which word moved it. | |
Limited-pointer directory | An entry naming up to K sharers exactly (Dir_i with i = K). When reader K + 1 arrives it must broadcast later (Dir_i B), invalidate one sharer (Dir_i NB) or switch to a coarse vector; it may never drop the new reader. | |
Sparse directory | A directory with tagged entries only for lines some private cache holds, sized against the private caches (coverage ratio) rather than memory. Freeing an entry needs back-invalidation. |
Term | Meaning | Taught in |
|---|---|---|
Exclusive LLC | An LLC that holds a line only while no private cache does. "Exclusive" is a relation between storage levels, not the MESI E state; clean evictions must carry data down. | |
F state (MESIF) | Forward: exactly one clean sharer is the designated responder for reads, so one cache answers instead of memory or every sharer. F is read-only and clean, memory is current, and F migrates to the newest requester (Goodman and Hum, 2004). | |
Inclusive LLC | An LLC that holds every line any private cache holds. Evicting an LLC line forces back-invalidation of every private copy. | |
NINE LLC | Non-inclusive, non-exclusive: an LLC that follows neither the inclusive nor the exclusive rule. | |
Point of coherence (PoC) | Arm's term (DDI 0487): the point at which all agents that can access memory, cores and DMA devices, see the same copy of a location. A target for cache maintenance; not the same as H, the per-line point of serialization. | |
Point of unification (PoU) | The level at which one core's instruction fetch, data accesses and translation table walks see the same copy. | |
UCE, UDP (CHI) | AMBA 5 CHI states with no course equivalent: Unique Clean Empty (unique permission, no valid bytes) and Unique Dirty Partial (some bytes stored, merge needed). |
Term | Meaning | Taught in |
|---|---|---|
Chicken bit | A configuration field that switches off one optimisation and selects a simpler path that already exists in the RTL and was verified. It never creates a new path. | |
Coverage cross (race cross) | A coverage item naming the transient state, the conflicting message that arrives in it and the request that caused that message; where the result depends on arrival order, both orders are bins. | |
Golden value checker | The checker half of a reference model: it keeps the golden value of each location (the latest write in that location's order) and compares every load and every usable copy with it after every event. Where it observes matters: at the core, the memory model allows some older values. | |
Ghost variable | Verification-only state, invisible to the design, updated with the value of every store performed on X (X = 0 at reset). The data-value invariant then reads: every readable copy equals the ghost. SWMR makes the last store well defined. | |
Leave / Join | Course-defined messages (with Leave-Ack and Join-Ack) for taking a cache out of the coherence domain and back. H sends Leave-Ack only when no entry names the cache and no Inv or Fwd to it is unanswered; the cache keeps answering until then. CHI's SYSCOREQ/SYSCOACK handshake does the same job. | |
Liveness | Something good eventually happens: every accepted GetS or GetM is eventually granted. No finite trace violates it, so it needs a stated fairness assumption. | |
Poison | A bit carried with Data that marks it known-bad. It travels through buffers and memory like any data, and an error is raised only when a core or device consumes it. | |
Quiesce | Bring a link or cluster to a state with nothing in flight before resetting it: stop new requests, keep forwards and responses running, wait until no transaction is half done (MSHRs, eviction states and H's pending entries empty), then check every class FIFO is empty and every credit returned. | |
Reference model | An executable specification: a simple, obviously correct protocol half plus a checker half with the golden memory, asserting the invariants after every event. | |
Retention | A low-power state that keeps the array's bits but switches off the logic that looks up tags and answers snoops. A retained cache must either leave the domain first or wake on every snoop. | |
Safety | Nothing bad ever happens: SWMR, no stale read, no lost writeback. A violation has a finite counterexample. A controller that never grants anything is safe but not live. | |
SECDED | Single-error correction, double-error detection: a Hamming code plus one overall parity bit, for example 8 check bits over 64 data bits. On tags, state or directory bits an uncorrected error is a coherence bug, not only a data error. | |
Trace buffer | An on-chip circular buffer that records filtered coherence messages at taps on H and the cache ports, with timestamps. It is armed on a line, frozen when the failure occurs and dumped before any reset. | |
Vacuity | An assertion passes trivially because its antecedent is never true, for example when an over-constraining assumption removes every trace in which an Inv is sent. Cover properties and witness traces expose it. |
Yes. An S copy is readable but cannot be written until exclusive permission is acquired. Conversely, a retained bit pattern in I is not valid merely because its bits happen to match memory.
No. That is a false positive: H sends one unnecessary Inv and the cache answers Inv-Ack from I. The bug is the opposite case, a holder missing from the filter, because H could then grant another cache from stale memory.