These questions check that you can define coherence precisely and reason with the course model before any race appears: the two invariants, what each stable state permits, what E and O cost as well as save, when stale memory is legal, and how discovery is organised. Answer each one by naming the protocol first: the same question has different correct answers in MSI, MESI and MOESI.
Field | Answer |
|---|---|
Interviewer is testing | Whether you define the invariant over permissions at a logical instant, not over stores in progress. |
Weak answer | Only one cache can write at a time. |
Strong answer (a 4) | Assumption: an invalidation protocol on the course model, X one location in a 64-byte line, permissions per line. Mechanism: at every logical instant the line is either in a write epoch, where exactly one cache may read and write and no other cache has a usable copy, or in a read epoch, where any number of caches, including zero, may only read. A writable holder (E or M) need not be storing, and a pending GetM is not permission. Trade-off: invalidation lets the writer store locally once granted, at the cost of a revocation round trip for every new writer. Evidence: classify snapshots. M / 0 beside S / 0 is illegal although the bits agree; O / 1 beside S / 1 in MOESI is a legal read epoch. A checker asserts it per address over all caches, after every event. Boundary case: a sharer in SM^D still serves loads, so granting M to another cache while it waits is already a violation. |
Follow-ups | Is E / 0 beside I / - a write epoch? (Yes: E is writable.) Must a writer exist at every moment? (No: an idle read epoch with zero readers is legal.) Is O writable? (No.) |
Common trap | Writing it as 'at most one M'. That misses E and misses a writer beside an S or SM^D reader. (Two O copies break the separate one-dirty-holder rule, not SWMR.) |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Whether you know the second invariant and that it needs a reference outside the design. |
Weak answer | No: if permissions are right, the data is right. |
Strong answer (a 4) | Assumption: per-location write history from X = 0. Mechanism: the data-value invariant says each epoch starts with the value at the end of the last write epoch. Counterexample: the last write epoch ended at 2, both caches hold S / 1 and memory = 1. SWMR passes, every copy agrees, and the value is still wrong. Trade-off: checking it needs store history (a golden value or ghost variable), not a vote among copies and not memory. Evidence: a checker that compares loads with memory fails both ways: it flags a legal C0 M / 2 with memory = 0 and approves the stale 1 because memory also holds 1. |
Follow-ups | Why must stores in a testbench write unique values? (A stale read of a repeated value looks correct.) Where would you take the reference from? (Performed stores, never a storage element of the design.) |
Common trap | Treating agreement among caches and memory as proof. Agreement cannot repair a lost update. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Clean separation of permission, cleanliness and dirty responsibility, and naming the protocol before the answer. |
Weak answer | M is modified, E is exclusive, S is shared, O is owned, I is invalid. The owner writes the data back. |
Strong answer (a 4) | Assumption: name the protocol first; E exists in MESI and MOESI, O only in MOESI. Mechanism: I has no usable copy. S is read-only. M is the exclusive holder and the dirty-responsible holder: read, write, memory may be stale. E (MESI, MOESI) is exclusive and clean: writable, and a store moves it silently to M. O (MOESI) is read-only but dirty-responsible: other caches may hold S while memory is stale. Every eviction is notified in the course: PutS, PutE or PutM, then wait for Put-Ack. Trade-off: E saves a transaction for read-then-write private data; O saves memory writes on repeated dirty reads; each adds states to verify. Boundary case: a lone S copy with no other sharers still may not store silently; it must send GetM. Evidence: in MSI and MESI a remote read of an M line settles S/S only after H writes memory; in MOESI it settles O/S with memory stale. |
Follow-ups | Which pair is legal: M/S or O/S? (O/S, in MOESI.) Which states evict with PutM? (M and O.) Can a lone S copy store silently? (No.) |
Common trap | Saying 'owner' without qualifying it. Say exclusive holder (E or M, may write) or dirty-responsible holder (M or O, memory may be stale); O may not write. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Whether you see the cost on the directory side, not just the saved request. |
Weak answer | E saves the upgrade when nobody else has the line. It is a pure optimisation. |
Strong answer (a 4) | Assumption: MESI, C0 the lone reader of X = 0. Mechanism: H sees no other holder, grants Data with E and records exclusive(C0). C0's first store hits and moves E to M with no message, so H's entry is unchanged. Trade-off: it saves a GetM and Data per read-then-write of private data, but H can no longer tell E / 0 from M / 1. Every later GetS must be forwarded with Fwd-GetS to C0, even if the line is clean, and C0 must downgrade. Silent E eviction would need a 'no copy' reply, which is why the course sends PutE. Reclaiming a directory entry for an exclusive(C0) line must take the dirty path (Fwd-GetM), not a bare Inv. Evidence: the MESI cold-read trace, where H's column does not change at the local store. |
Follow-ups | May H answer C1 from memory when C0 is really E / 0? (No: C0 could still store silently while C1 reads, an SWMR violation.) Does every lone reader get E? (No: the protocol may grant S.) |
Common trap | Assuming H knows the line is clean because it granted E. |
Taught in | MESI and the Exclusive State and Filter Eviction and Back-Invalidation |
Field | Answer |
|---|---|
Interviewer is testing | Quantitative reasoning about a protocol choice instead of 'MOESI is faster'. |
Weak answer | O avoids writing back to memory, so MOESI always saves traffic. |
Strong answer (a 4) | Assumption: MOESI, two cores, C0 produces and C1 consumes. Mechanism: Fwd-GetS reaches C0 in M; C0 goes to O and keeps dirty responsibility, C1 gets S, H records O: C0, sharers {C1}, memory stays stale. Every later reader is forwarded to C0. To store again C0 must upgrade (OM^D, H invalidates C1, permission-only Data). Trade-off: R rounds of write-then-read cost the same messages under MESI and MOESI (24 for R = 3), but R memory writes against 1: R - 1 writes are removed and the last is deferred to C0's final PutM. Store, read, evict costs one memory write under either protocol. With several readers each later read is a four-leg forward instead of a two-leg memory read, and the directory needs a field for the O holder. Boundary case: when C0 evicts from O while C1 still holds S, its PutM writes memory and H records S{C1}, so memory is current again. Evidence: count messages and memory writes on the target pattern. |
Follow-ups | C0 stores 1, C1 reads, C0 evicts: how many memory writes in each? (One each.) Who supplies a third reader in O/S? (C0, the dirty-responsible holder.) |
Common trap | Counting the deferred write as saved, or letting C0 store while in O. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The difference between legally stale memory and a stale response. |
Weak answer | Yes, memory and the cache disagree. |
Strong answer (a 4) | Assumption: write-back caches, course model. Mechanism: no. C0 is the dirty-responsible holder and H records exclusive(C0), so any request for X is forwarded to C0. Memory is a source only when H's record makes it authoritative (U, or S in settled MSI or MESI). The bug is a grant that carries memory's 0 to a requester, or losing 1 altogether. Trade-off: write-back saves memory bandwidth but makes the directory record and the forward path responsible for the value. Evidence: follow the newest value through every step, including H's buffer and Data in flight. A pending transfer with the value only in H's buffer is not U, even though both caches show I. |
Follow-ups | Give an illegal case with the same memory value. (C1 granted M / 0 after 5 was written and lost.) Why is a pending entry with data in H's buffer not U? (Memory is stale and the transfer is not finished.) |
Common trap | Building a checker that compares cache values with memory. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Whether you look for the first illegal step, not the symptom. |
Weak answer | In the reader's cache: it returned old data, so the load path is wrong. |
Strong answer (a 4) | Assumption: MSI, both caches S / 0, H S{C0,C1}, memory = 0, a deliberately broken H. Mechanism: C0 sends GetM and H grants permission-only Data without invalidating C1. At that grant C0 is M / 0 beside C1 S / 0: SWMR already fails although every bit agrees. Only later does C0 store 1 and C1 read 0. Trade-off: a permission check catches the grant at once; a value-only check waits until a store makes the values differ and then blames the load. Evidence: give the earliest failing row, the obligation it breaks (revoke C1 and collect its Inv-Ack before writable Data) and the fix (the acknowledgement boundary). Waiting a fixed number of cycles is not equivalent evidence. |
Follow-ups | If C0 never stores, is it still a bug? (Yes: incompatible permissions are the violation.) Which checker fires first? (The SWMR check, at the grant.) |
Common trap | Patching the reader. In this case the reader behaved correctly given what it was told. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Conditional design judgement with the costs on each side, not a core-count rule. |
Weak answer | Snooping for small systems, directories for big ones. |
Strong answer (a 4) | Assumption: discovery and ordering are separate from MSI, MESI or MOESI; a directory does not require MOESI. Mechanism: pure snooping broadcasts every request; an ordered bus is the point of serialization and every cache's own state is the record, with no sharer list. A directory keeps holders at H, which serializes each line, targets only recorded holders and collects their acks. Trade-off: snooping costs about N - 1 tag checks per miss on one shared ordering point but gives a two-leg cache-to-cache path. A directory adds a lookup on every miss and a third leg for cache-to-cache transfers, and its full-map entry costs 2 + N bits per line: 4 bits (0.78% of a 64-byte line) for two caches, 66 bits (12.9%) for 64. Race: a fabric that broadcasts without ordering can deliver two racing GetMs in different orders at different caches, so it still needs a home or another ordering point. Evidence: the request rate, sharing degree and available ordering of the target workload, with traffic and latency numbers. |
Follow-ups | Does snooping broadcast the data? (No: only requests need to reach every cache.) What makes a directory's home a bottleneck? (Lookup and contention for hot lines.) |
Common trap | 'Directories are always faster', or inferring an ordered bus from a fabric that merely broadcasts packets. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | That you state the correctness invariant before the energy saving. |
Weak answer | It remembers which caches have the line so we can skip the others. |
Strong answer (a 4) | Assumption: H keeps a finite inclusive filter F instead of a full directory. Mechanism: every cache that holds X in any non-I state, or has an admitted fill for X in flight, must be in F(X) at every instant. A false positive costs work, for example a stale bit after a silent clean eviction gives a wasted Inv and an Inv-Ack from I. A false negative is a correctness bug: with C0 M / 1 and memory = 0, omitting C0 makes H grant 0. Unknown is not absent. To evict an entry H back-invalidates first, Inv to clean holders and Fwd-GetM to an exclusive holder, and frees the entry only after every ack or the data has arrived. Trade-off: fewer snoops against filter storage and back-invalidation misses. Evidence: an assertion that the real holders are a subset of F(X) after every event. |
Follow-ups | When is the reader allocated in F? (When H admits its GetS, before Data leaves, or later only while a pending entry blocks conflicting requests.) Why does an exclusive(C0) victim need Fwd-GetM? (C0 may be M after a silent store.) |
Common trap | Treating a filter miss after replacement as proof that no cache holds X. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Whether you can compare policies by workload and by what each must prove. |
Weak answer | Invalidation is simpler and uses fewer messages. |
Strong answer (a 4) | Assumption: the course uses invalidation. Mechanism: before a writable grant, H removes every independent reader and collects their Inv-Acks; then the writer's stores stay local. Sending new bits to a sharer does not revoke its read permission, so an update design needs its own rules for ordering writes and for when a retained copy may serve a read. Trade-off: repeated writes with no remote reuse favour invalidation, since updates would push every value; prompt reuse by readers can favour update. An update protocol that pushes values to sharers one at a time can also break multi-copy atomicity, which an invalidation protocol provides as long as every Inv-Ack is collected before M is usable (at H or at the requester). Race: when two cores write X at once, invalidation serializes them at H, while an update design must deliver both pushes in the same order at every sharer. Evidence: the write-to-remote-read ratio of the workload. |
Follow-ups | Which litmus test detects the multi-copy atomicity difference? (IRIW.) Does an upgrade with a valid S copy still need the Inv round trip? (Yes.) |
Common trap | Declaring a winner without a workload. |
Taught in |
The mechanism is wrong because the assumption about H's knowledge is wrong. H records only exclusive(C0); a silent E-to-M store would leave that entry unchanged, so H cannot know C0 is still clean. Worse, if C0 stays in E it may store silently while C1 reads, which breaks SWMR. H must send Fwd-GetS, C0 downgrades to S and replies with Data, and H writes that Data to memory before settling S{C0,C1}.