These questions are the senior end of the bank: each asks for a design choice, so a strong answer gives the deciding conditions and a number, not a ranking. Keep the correctness rule first (every possible holder is covered, dirty data always has a home) and the cost second. When a real protocol is named, give its rule with the document and revision.
Field | Answer |
|---|---|
Interviewer is testing | Field-level arithmetic and the full-map versus sparse distinction. |
Weak answer | One bit per core, which becomes too big for many cores. |
Strong answer (a 4) | Assumption: per 64-byte line (512 data bits), tags and ECC excluded, MESI coverage. Mechanism: a full bit vector is 2 + N bits: 66 bits (12.9%) at 64 caches, 1,026 bits (200.4%) at 1,024. Four pointers cost 2 + 4 x (id + 1) + 1: 31 bits at 64 caches, and beat the full vector from 26 caches. A groups-of-eight coarse vector plus an exact exclusive-holder id grows as N/8 and exceeds four pointers from 233 caches. A full-map directory has one entry per memory line and no tag; a sparse directory tracks cached capacity, needs a tag per entry and is sized by coverage ratio (as a general guideline about 1, up to about 2 for set conflicts). Trade-off: smaller entries buy imprecision (overflow broadcasts, group invalidations) and sparse entries add directory-induced invalidations. Boundary case: at small N limited pointers lose: with two caches one pointer costs 5 bits against 4 for the full vector. Evidence: measure sharers per line and directory-induced invalidations on the target workload. |
Follow-ups | Do limited pointers always save storage? (No: with two caches, one pointer is 5 bits against 4.) Why does a coarse vector need an exact holder id? (A GetS must be forwarded to exactly one exclusive holder.) |
Common trap | Comparing N presence bits with a pointer format that omits valid, overflow or holder bits. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The three classic schemes and the clearing rule. |
Weak answer | Drop the oldest pointer. |
Strong answer (a 4) | Assumption: K pointers per entry; extend the course model to four caches with one pointer (Dir_1 B). Mechanism: Dir_i B sets an overflow bit and grants the read; a later GetM sends Inv to all N - 1 other caches and waits for N - 1 Inv-Acks; overflow clears only when the entry becomes exclusive(requester) after that full invalidation, never on PutS. Dir_i NB invalidates one existing sharer to free its pointer. Dir_i CV_r reinterprets the pointer bits as group bits and invalidates every member of each set group. Worked case: C0 and C1 read, C3 writes; Dir_1 B sends three Invs and C2 acks from I. Trade-off: B suits rare overflow; NB is pathological for widely read lines (locks, flags, code); CV_r wastes Invs only inside set groups. Names from Agarwal, Simoni, Hennessy and Horowitz (ISCA 1988) and Gupta, Weber and Mowry (ICPP 1990). Evidence: assert after every event that real holders are a subset of the entry's candidates. |
Follow-ups | C1 sends PutS after overflow: why can H not clear the bit? (It cannot know the pointer list is now complete.) Must each Inv-Ack match its GetM? (Yes: a leftover ack must not complete a new round.) |
Common trap | Truncating to K ids without setting overflow. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Back-invalidation with a data path, and the race with an eviction in progress. |
Weak answer | Evict the least recently used entry. |
Strong answer (a 4) | Assumption: an inclusive filter or sparse directory, new request for Y waiting for X's entry. Mechanism: H freezes conflicting requests for X and retires the entry: Inv to clean sharers and collect every Inv-Ack; for an exclusive entry send Fwd-GetM on its own behalf, write the returned Data to memory, then free the entry. In MESI an exclusive(C0) victim takes the dirty path even if C0 was given E, because of the silent store. If C0 is already evicting (MI^A), it answers from its WB entry and goes to II^A; its later PutM is from a non-holder and gets Put-Ack with no change. Trade-off: each retirement costs the holders a miss (a directory-induced invalidation); victim choice (fewer or clean holders) reduces it. Evidence: count directory-induced invalidations per set; a hot set can cause misses even when private working sets fit. |
Follow-ups | Why can H not free after the first of two acks? (Its evidence is incomplete.) Would more pointer slots help a full set? (No: the shortage is entries, not sharers.) |
Common trap | Treating Inv-Acks as recovery of dirty data. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The four-event comparison and the snoop-filtering consequence. |
Weak answer | Inclusive is simpler, exclusive has more capacity. |
Strong answer (a 4) | Assumption: the LLC sits at H; PutM writes the LLC line; memory is written only when the LLC evicts a dirty line. Mechanism: inclusive fills both levels, and its presence bits make the LLC a directory: a tag miss proves no private copy, but an LLC eviction back-invalidates every private copy (inclusion victims arise because private hits do not refresh LLC replacement state). Exclusive fills only the private cache, moves victims, clean ones too, into the LLC (so clean evictions must carry data), and needs a separate snoop filter. NINE fills both and drops LLC lines freely, but also needs a snoop filter, whose own evictions still back-invalidate. Trade-off: with 2 x 256 KiB private and a 1 MiB LLC (illustrative), unique capacity is about 1 MiB inclusive against 1.5 MiB exclusive. Boundary case: when an inclusive LLC evicts a line C0 holds in M, the back-invalidation must recover the dirty data (Fwd-GetM on H's behalf), not just send an Inv. Evidence: the ratio of total private capacity to LLC size, filter storage and fill bandwidth on the workload. |
Follow-ups | May the LLC answer a GetS while C0 holds E or M? (No: its copy may be stale.) Does NINE remove back-invalidation? (No: it moves it to the filter.) |
Common trap | Adding private and LLC capacities for an inclusive design. |
Taught in | Inclusive, Exclusive and Non-Inclusive and Back-Invalidation |
Field | Answer |
|---|---|
Interviewer is testing | Separating requester, home node and dirty-responsible holder, and costing legs. |
Weak answer | Put the memory near the core that uses it most. |
Strong answer (a 4) | Assumption: two nodes A and B, home beside the memory node holding X's page, MSI, four-hop dirty reads; illustrative costs: 3 cycles per leg inside a node, 12 across, 2 for H's lookup, 10 for a memory read, 1 to handle a forward. Mechanism: for C0 on node A: local clean read 18 cycles, remote clean 36, remote home with C1 (also on A) holding M / 1: 51, the same dirty read after the page moves to A: 15. Trade-off: first-touch placement fixes the page where the first faulting thread runs, so a single initialisation thread on the wrong node makes every home remote; page migration copies the lines coherently and gives the data a new physical address, and so a new home, at the cost of 64 line copies and a TLB shootdown per 4 KiB page. Boundary case: a line written from both nodes cannot be local for every writer under any placement; only the sharing pattern can change that. Evidence: change one policy at a time and count memory traffic separately from cache-to-cache traffic. |
Follow-ups | Does first touch keep later dirty data local? (No: coherent writes move the current copy.) Can any placement make a line written from both nodes local for every writer? (No.) |
Common trap | Calling every remote access a remote DRAM access. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Counting coherence messages per lock algorithm and knowing what placement cannot fix. |
Weak answer | Spread the lock across homes or add backoff. |
Strong answer (a 4) | Assumption: course model, MSI, acks at H, four-hop for lines in another cache's M, N contending cores. Mechanism: test-and-set makes every spin a GetM that steals the line: four messages per failed attempt for as long as the lock is held. Test-and-test-and-set spins on S copies (no messages while held) but each release costs 12(N - 1) messages for N of 4 or more: 36 at N = 4, 84 at N = 8. A ticket lock removes the failed atomics and serves waiters in order but is still O(N) per handoff. A queue lock (MCS, CLH) has each waiter spin on its own line: 8 messages per handoff whatever N is. Race: at a test-and-test-and-set release all N - 1 waiters see the Inv, reload and race with GetM; H serializes them, one wins and the rest fail their atomic and return to spinning. Trade-off: backoff thins the storm but adds handoff latency and is no fairness proof. Evidence: run the counts on the model and on per-line Fwd-GetM and Inv counters. No home mapping can split one line, and none of these fixes shortens the serial critical section. |
Follow-ups | First check before any lock change? (Unrelated written fields in the same line: false sharing.) Does moving X to another home parallelise updates? (No.) |
Common trap | Treating M permission as an atomicity or acquire contract. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Spec-accurate correspondences with document and revision, and where they differ. |
Weak answer | They are all MOESI with different names. |
Strong answer (a 4) | Assumption: AMBA ACE (Arm IHI 0022 Issue H.c), AMBA 5 CHI (Arm IHI 0050 Issue E.a), SiFive TileLink 1.8.1. Mechanism: states: course M = UD, O = SD, E = UC, S = SC, I = I; CHI adds UCE (unique, no valid bytes) and UDP (unique dirty partial). ACE and CHI SC mean 'not responsible for memory', not 'memory current'. TileLink uses positions None, Branch, Trunk, Tip, with dirt outside the permission. Serialization: the CHI HN-F, the ACE interconnect, the TileLink slave. Completion: CHI CompAck (Read and Dataless transactions; not ReadOnce* or ReadNoSnp; for CopyBack the write data acts as an implicit CompAck), ACE RACK and WACK, TileLink GrantAck (mandatory for every Grant), all the real form of the course's grant-delivery rule. Direct data: only CHI (DCT); ACE and TileLink route snoop data through the home. Retry: CHI RetryAck with PCrdGrant; ACE and TileLink have none. Trade-off: direct transfer saves a leg but makes the home track a transfer it did not perform. Evidence: the course's dirty write costs four critical-path legs; TileLink is AcquireBlock, ProbeBlock, ProbeAckData, GrantData, with GrantAck off the critical path. |
Follow-ups | C0 holds UCE and C1 issues ReadShared: where does the data come from? (Memory via the home: UCE has no valid bytes and no cache is dirty.) Why is TileLink's E channel highest priority? (GrantAck must always sink.) |
Common trap | Reading SC as clean memory, or Tip as M. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Coherent versus non-coherent paths, one-way coherence and CXL's division of roles. |
Weak answer | Use a coherent interconnect and the device sees the right data. |
Strong answer (a 4) | Assumption: device D added to the course model, C0 M / 1, H exclusive(C0), memory = 0. Mechanism: a coherent (I/O-coherent) read snoops C0 through H (Fwd-GetS on D's behalf), writes memory and returns 1; H keeps no entry for D because D retains nothing; a partial-line device write needs Fwd-GetM to recover the other bytes. Only transactions with the snoop attribute (from D or the IOMMU / SMMU page) take that path. A non-coherent path needs software maintenance: clean before the device reads; clean or invalidate before it writes; invalidate after it completes and before the CPU reads. CXL (Revision 2.0, Version 1.0): Type 1 is CXL.io plus CXL.cache, Type 2 adds CXL.mem, Type 3 is CXL.io plus CXL.mem with no device cache. Coherence is host-managed: the device's MESI cache issues D2H requests and answers H2D snoops; Host and Device Bias apply only to a Type 2 device's own memory. Trade-off: coherent paths cost snoop traffic; non-coherent ones cost software and its bugs. Evidence: coherence never replaces the doorbell ordering and completion handshake. |
Follow-ups | Why can a device read 0 while C0 correctly holds 1? (A missing clean: a stale device input, not a lost CPU value.) Should D be recorded as an S holder after a coherent read? (No.) |
Common trap | Treating equal physical addresses as proof of a coherent observation path. |
Taught in | Coherent Versus Non-Coherent DMA and Device Caches and CXL.cache |
Field | Answer |
|---|---|
Interviewer is testing | A precise done predicate and the order of leaving the coherence domain. |
Weak answer | After it writes back its dirty lines. |
Strong answer (a 4) | Assumption: course model with C0's cache power-gated; course-defined Leave, Leave-Ack, Join, Join-Ack messages. Mechanism: gate the core, drain the MSHRs, flush (every M or O line with PutM, every clean line with PutS or PutE, each with Put-Ack), send Leave, keep the snoop port answering until Leave-Ack, then power off. Done = core stopped, every line I, MSHRs and WB entries free, Puts minus Put-Acks zero. Rejoin in reverse: power on with every line I, enable snoops, Join, wait for Join-Ack, then accept core requests. Trade-off: a bulk Leave saves per-line PutS but makes H walk its directory. Evidence: each shortcut has a concrete failure: powering off in M loses data and hangs the next Fwd; an S line with no PutS hangs the next Inv; flushing after Leave is a stale read, a safety failure. AMBA CHI (Arm IHI 0050 Issue E.a, Chapter 15) does the same job with the SYSCOREQ and SYSCOACK handshake. |
Follow-ups | Can you power off on the first Put-Ack? (No: wait for the last.) Why must the snoop port be on before Join? (A broadcast may target C0 as soon as H adds it.) |
Common trap | Gating the snoop logic with the core's power domain. |
Taught in | Flushing Before Power-Down and Leaving and Rejoining the Domain |
Field | Answer |
|---|---|
Interviewer is testing | Poison for data, conservative recovery for metadata, and their limits. |
Weak answer | Raise a machine check and stop. |
Strong answer (a 4) | Assumption: MSI, poison granule = the 64-byte line. Mechanism: for data, poison travels with the Data (a bit beside the payload, kept in H's buffers and stored in memory); coherence runs normally; only a load that consumes the line gets a synchronous error; a partial store keeps the poison, a full overwrite clears it. SWMR holds; the data-value invariant has failed but visibly. For a directory entry there is no payload to mark: unknown means broadcast. H freezes X and recalls every cache except the requester with Fwd-GetM on its own behalf; an M holder returns Data, others answer Inv-Ack; once all have answered H writes memory, rebuilds the entry as U and resumes the request. Trade-off: recovery costs n - 1 recalls and answers and empties every copy, which is acceptable on a rare slow path. Evidence: if the dirty holder cannot answer (powered off unflushed), H needs a time-out, then poisons the line if it still knows the address, or escalates if not. |
Follow-ups | Why not treat an unknown entry as U? (One M holder is enough for a stale read.) Can poison fix a bad tag? (No: it needs a correct address and state around it.) |
Common trap | Raising a fatal error at detection, when the forwarding cache or memory controller is rarely the consumer. |
Taught in |
LLC data evictions would no longer invalidate private copies, and inclusion victims from LLC replacement go away. But an LLC tag miss no longer proves a private copy is absent, so H needs a separate snoop filter, and that filter's own evictions still back-invalidate (Inv to clean holders, Fwd-GetM to an exclusive holder). The question becomes filter sizing and its directory-induced invalidations, measured on the workload, not their elimination.