These questions ask you to draw a transaction correctly and then break it: what each message does, which serial legs are on the requester's critical path, where the newest value is at every step, and what happens when two requests or a request and an eviction meet. The course conventions apply throughout: Inv-Acks are collected at H, evictions wait for Put-Ack, and no FIFO order is assumed.
Field | Answer |
|---|---|
Interviewer is testing | A correct message order, the ack boundary and the serial-leg count. |
Weak answer | C1 sends GetM, H sends the data and invalidates C0. |
Strong answer (a 4) | Assumption: MSI, C0 S / 0, C1 I / -, H S{C0}, memory = 0, acks collected at H, no FIFO order. Mechanism: 1. GetM to H (C1 in IM^D, no loads or stores). 2. Inv to C0, which goes to I. 3. Inv-Ack to H, entry U, pend GetM C1, acks 1/1. H reads memory (it may start the read while waiting for the ack). 4. Data(X=0, M) to C1, entry exclusive(C1), then C1 stores 1. Trade-off: from U the miss is two legs; from S{C0} four, the extra two being the Inv round trip. Overlapping the memory read hides memory latency but not that round trip. Evidence: H must not send Data before the Inv-Ack: with no FIFO order C1 could store while C0 still reads 0. |
Follow-ups | And if C0 held the line in M? (Fwd-GetM instead of Inv: C0 supplies the value.) How many legs with the Primer's acks to the requester? (Three.) |
Common trap | Counting the Inv as done when H sends it. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | That only the refill is absent, not the permission work. |
Weak answer | C0 already has the data, so it just tells H it is writing. |
Strong answer (a 4) | Assumption: MSI, C0 S / 0, C1 S / 0, H S{C0,C1}, acks at H. Mechanism: C0 sends GetM and waits in SM^D, where loads hit and stores stall. H sends Inv to C1, collects the Inv-Ack, then sends Data with M permission and no refill. Still four serial legs. The Primer sends Inv-Acks to the requester with an ack count in Data (three legs, state SM^AD). Both are legal; granting usable M before every ack is the bug. Trade-off: the retained copy saves bytes, not messages. Evidence: the permission-only path is valid only while C0's S copy stays valid; if an Inv from a competing GetM arrives in SM^D, C0 acks, becomes IM^D and must be sent the data. |
Follow-ups | Can permission-only Data recreate a copy C0 lost? (No: a grant carries permission, not bytes.) What does C0 do with a load in SM^D? (Hits.) |
Common trap | Calling an upgrade a data miss, or assuming the requester still has data because it asked for an upgrade. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Critical-path reasoning and the completion problem a direct transfer creates. |
Weak answer | Three-hop is faster because it has fewer messages. |
Strong answer (a 4) | Assumption: MSI, C0 M / 1, C1 I / -, H exclusive(C0), memory = 0, C1 wants to write; a hop is one message leg. Mechanism: four-hop is GetM, Fwd-GetM, Data to H, Data(M) to C1. Three-hop is GetM, Fwd-GetM, then C0 sends Data(X=1, M) straight to C1. Trade-off: the direct route saves one leg on C1's critical path, and loses only if the C0-to-C1 leg is slower than the two legs through H. Its cost is elsewhere: H did not see the transfer, so it needs a completion message from C1 (off C1's critical path) or C1 must hold an Inv or Fwd that arrives before its Data. Evidence: count critical-path legs, say how H learns the transfer finished. In real protocols CHI has direct cache transfer (DCT), while ACE and TileLink route snoop data through the home. |
Follow-ups | Is memory written in either route? (No: C1 becomes the dirty holder; memory stays stale legally.) Who decided the transfer? (H, by forwarding: C0 cannot grant on its own.) |
Common trap | Counting router hops or total messages without saying which. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The writeback order, the WB entry's lifetime and what it must still answer. |
Weak answer | As soon as it sends the writeback. |
Strong answer (a 4) | Assumption: MSI, C0 M / 3, course default order. Mechanism: C0 moves the value into a WB entry, frees the array entry, enters MI^A and sends PutM. H writes memory (a Note at H) and only then sends Put-Ack; C0 frees the WB entry on Put-Ack. Meanwhile loads and stores to X stall, and any Inv or Fwd for X is answered from the WB entry. If no WB entry is free, the eviction stalls and the line stays M in the array. Trade-off: an early Put-Ack variant frees C0's WB entry sooner, but then H's buffer holds the only copy until memory is written and H must answer from it, never from memory. Evidence: read the newest-data column: the value is always somewhere. |
Follow-ups | At PutM arrival, may H record U? (No: only after memory holds 3.) Does Put-Ack mean the data is persistent? (No: only that memory accepted it.) |
Common trap | Treating 'PutM sent' as 'PutM accepted'. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The eviction-versus-intervention race and the late-writeback rule. |
Weak answer | H waits for the writeback, then serves the read. |
Strong answer (a 4) | Assumption: MSI, C0 evicted X = 1 into its WB entry (MI^A) and sent PutM W; H still records exclusive(C0); C1 sends GetS R. Mechanism: order A, W first: H writes memory, sends Put-Ack, then grants C1 S / 1 and records S{C1}. Order B, R first: H sends Fwd-GetS; C0 answers from the WB entry with Data marked 'PutM outstanding' and goes to SI^A; H writes memory, grants C1 and records S{C1}, not C0. When W arrives, C0 is no longer a recorded holder, so H sends Put-Ack with no directory or memory change. A Fwd-GetM in MI^A sends Data and goes to II^A. Trade-off: the rule costs nothing extra; a generation tag per entry is optional. Evidence: H never makes R wait for W, which would form a cycle; treating the late PutM as a normal writeback could overwrite newer data or erase C1's record. |
Follow-ups | Why not recreate S at C0 in order B? (Its line is evicted; SI^A serves no loads.) When is the WB entry freed? (Only on Put-Ack.) |
Common trap | Answering 'absent' from the cache tag while the WB entry holds the only current value. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Whether you know what real protocols do when the grant-delivery rule is dropped. |
Weak answer | It cannot happen. |
Strong answer (a 4) | Assumption: the course model's grant-delivery rule makes it impossible in Parts 1 to 3; real protocols do not assume H can see delivery. Mechanism: with no FIFO order, H sends C0's Data for GetS A and at once starts C1's GetM B, so B's Inv can overtake A's Data. C0 sends Inv-Ack immediately (it has no readable copy) and moves to IS^D_I. When the late Data arrives it serves the one pending load and the copy is dropped, so C0 ends in I. Similarly a Fwd-GetM that reaches a cache in IM^D is held until Data arrives and the stalled store is done. Trade-off: the alternative is a completion message (Unblock or CompAck style) after the requester installs Data; it costs one message and keeps the line busy at H one leg longer, off the requester's critical path. Evidence: the pending load returns the value B replaces, so it is ordered before B's store. |
Follow-ups | What goes wrong in a naive IS^D that acks and then installs the late S? (A stale readable copy beside a writer.) Which messages do ACE and TileLink use for completion? (RACK or WACK, GrantAck.) |
Common trap | Delaying the Inv-Ack until the Data arrives, or installing the late Data as a normal S copy. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Serialization at H, the loser's transient change and the livelock policy. |
Weak answer | Both get M, then one gets invalidated. |
Strong answer (a 4) | Assumption: MSI, C0 S / 0, C1 S / 0, H S{C0,C1}, H queues rather than NACKs. Mechanism: both enter SM^D. H accepts C0's GetM A first and queues B. C1 must still process A's Inv: it loses its copy, acks and becomes IM^D, keeping its store intent. H grants C0 permission-only Data; C0 stores 1. H then starts B with Fwd-GetM to C0, which sends Data(1) to H, and H grants C1 Data(X=1, M), with the value, because C1's copy was revoked. Trade-off: the store-before-Fwd policy (a cache that receives M performs at least its stalled store before handling a Fwd or Inv for X) prevents the line passing back and forth with no store completing. Evidence: if C1 refused the Inv until B completed, A would wait for C1 while B waited behind A: a dependency cycle. |
Follow-ups | Why can B not get permission-only Data? (C1 no longer holds the bytes.) How does H know C1's copy is gone? (The matching Inv-Ack, not B's arrival.) |
Common trap | Letting C1 keep its S copy because its own GetM is already queued. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Concrete fields and the event that needs each. |
Weak answer | The MSHR stores the miss until the data comes back. |
Strong answer (a 4) | Assumption: a private cache controller and H on the course model. Mechanism: the MSHR holds the line address, request type, transient state (IS^D, IM^D, SM^D, IS^D_I), the waiting loads and stores with store data, a transaction id or generation and merged secondary misses. H's pending entry holds the requester, the request and its identity, acks needed and received, whether authoritative data has arrived and where it is protected, and the next queued request for the line. Trade-off: each record has its own release condition; one global done bit frees something too early. Evidence: name for each field the future event that needs it, and match responses by identity, not by address alone, so a delayed response cannot complete a reused entry. |
Follow-ups | Can C1 hold an MSHR for B while H works on A? (Yes: it tracks C1's operation, not a grant.) What happens when H has no slot? (Backpressure or a stated refusal, never overwrite.) |
Common trap | Freeing the MSHR on a squash or on an ack count while Data is still coming. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Independent completion conditions and identity-based counting. |
Weak answer | When the ack count reaches zero. |
Strong answer (a 4) | Assumption: MSI, C0 S / 1, H S{C0}, memory = 1, C1 sends GetM, acks at H. Mechanism: H starts the memory read and sends Inv; the Inv-Ack arrives first. The entry is U, pend GetM C1, acks 1/1, data pending, and H still waits. It grants Data(X=1, M) only when both the required ack set is empty and authoritative data is in its buffer, plus a matching identity, the right grant state and output capacity. Trade-off: counting identities (an expected-responder set) rejects duplicate or stale acks; a bare counter must count each response exactly once. The Primer's alternative keeps a signed counter at the requester, since an Inv-Ack can arrive before the Data that carries the ack count. Evidence: check both arrival orders and a duplicate ack. |
Follow-ups | Does receiving data prove the sharers are gone? (No.) Why not grant from 'memory = 1' at the ack? (H has not read the line yet.) |
Common trap | Using the data's truth value as its presence flag, which rejects a valid zero. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Who keeps the obligation in each scheme and what each does for progress. |
Weak answer | NACK when full and let the requester retry later. |
Strong answer (a 4) | Assumption: H has finite slots and a request it cannot serve now. Mechanism: backpressure keeps the request at the sender; a queue means H accepted and keeps it; a NACK means H saw it, kept nothing, and the sender retries with the same identity. Credits give the sender one credit per free receiver slot, so the buffer never overflows and never needs a NACK. Trade-off: NACKs risk starvation (one requester refused forever) and livelock (retriers displacing each other); remedies are a reserved slot or retry token at NACK time, or oldest-first service. A credit is capacity, not permission: a returned credit is not an Inv-Ack or a grant. Responses and accepted dirty data must never be refused: responses must always sink. Evidence: CHI's RetryAck with PCrdGrant (Arm IHI 0050 Issue E.a) is the reserved-retry remedy: the resent request is guaranteed to be accepted. |
Follow-ups | Does random backoff guarantee progress? (No: a fairness rule is still needed.) May a slow, already accepted GetM be resent? (No: duplicate grants or invalidations.) |
Common trap | Applying a refusal rule to responses or to dirty data H has already accepted. |
Taught in |
C0 answers from its WB entry with Data (marked PutM outstanding) and moves to II^A; loads and stores to X still stall and the WB entry is freed only on Put-Ack. H grants C1 M and records exclusive(C1). When the PutM arrives, C0 is no longer a recorded holder, so H sends Put-Ack with no directory or memory change. Treating it as a writeback could overwrite C1's newer data in memory or erase exclusive(C1).