Cache Coherence and Memory System Interview Questions

You added a second thread to a loop and it got slower. Each thread only touches its own counter, so nothing is shared. Why would the hardware disagree? If you can answer that without guessing, you understand much of what a memory system interview probes.

This guide draws on public university course notes: UT Austin's cache lecture and MESI slides, Stanford CS149's coherence and consistency lecture, Wisconsin's ECE/CS 757 coherence slides, and Berkeley's CS 61C notes on the TLB. The practice prompts are ours, not questions reported from any employer.

How do cache organization and AMAT work?

The UT Austin cache lecture frames organization as four questions: where does a block get placed, how do you find it, which block do you replace, and what happens on a write. Direct mapped means each block lands in exactly one location (block address mod the number of blocks). Fully associative means anywhere. Set associative sits between, and the extremes are one way per set (direct mapped) and one set total (fully associative).

For replacement it lists random and least recently used. On writes it contrasts write-through (also update memory, usually with a write buffer) with write-back (set a dirty bit, update memory when the block is evicted).

AMAT is hit time plus miss rate times miss penalty. The lecture extends it across levels: the L1 miss penalty is the L2 hit time plus the L2 miss rate times the L2 miss penalty. It also gives a rule of thumb that a direct mapped cache of size N performs about like a 2-way cache of size N/2, while higher associativity usually costs hit time. Say that tradeoff out loud rather than reciting that more ways means fewer misses.

What is a coherence protocol actually doing?

The Stanford notes define coherence per location: each address has a serial order of operations, and a read returns the last write in that order. Their invariants are single writer or multiple readers, plus a data-value invariant.

Snooping is the simple implementation. The UT Austin slides describe each cache watching the bus for writes to lines it holds. They compare write-invalidate with write-update and say invalidate protocols use significantly less bus bandwidth, since repeated writes to a block need one invalidate instead of one update each.

MESI has four states: Modified (only copy, differs from memory), Exclusive (only copy, matches memory), Shared (matches memory, others may hold it), and Invalid. Stanford's point about E: plain MSI needs two bus transactions to read then write, even with no sharing, and E lets the write upgrade silently.

Wisconsin's slides add an Owned state for MOESI, which lets a dirty line be shared and sourced cache to cache without writing back to memory first. They list AMD Opteron as a user. Sources differ on write permission in O, so check which convention your course uses.

On scale, both UT Austin and Stanford say snooping relies on broadcast and does not scale. Directories keep per-line records of which caches hold a copy and use point to point messages. The UT slides show a presence-bit design and note its storage cost grows with processor count.

Consistency, false sharing, and the TLB

Stanford separates coherence from consistency cleanly. Coherence covers one address. Consistency covers the apparent order of operations to different addresses. Their example: A and B start at 0, P0 writes A then reads B, and P1 writes B then reads A. Sequential consistency forbids both reads returning 0, but with write buffers, which they say every modern processor uses, it can happen. They note x86 uses an incompletely specified form of TSO.

Stanford defines false sharing as two processors writing different addresses in the same cache line, so the line ping-pongs between caches. In their demo, threads update per-thread counters: 14.2 seconds packed versus 4.7 seconds padded (8 threads, 4-core system). Treat that as one lecture's demo, not a benchmark.

Berkeley's CS 61C notes treat the TLB as a small cache of virtual to physical translations. By their approximations a hit takes about one cycle, a miss with a valid entry roughly 100, and a page fault roughly 1000. TLB reach is entries times page size. Those notes do not cover keeping TLBs consistent across cores, so read about TLB shootdowns separately.

Topic	What the source says	Practice prompt
Associativity	One way per set is direct mapped, one set is fully associative	When would you pick 2-way over direct mapped for an L1?
AMAT	Hit time plus miss rate times miss penalty, level by level	Compute AMAT for two levels. Which term do you attack first?
MESI	E allows a silent upgrade to M	Why is E useful when the program has no sharing?
Directory vs snooping	Broadcast limits snooping scalability	What does a directory cost you?
Consistency	Write buffers allow both reads to return 0	Can both reads return 0 on x86? Why?
TLB	Reach is entries times page size	What happens to reach if you move to larger pages?

An illustrative scenario: the slower second thread

This is our own scenario, not a reported question. A service keeps an array of per-thread counters, and adding threads makes throughput flat, then worse. One way to talk through it:

1. Ask what is shared. Each thread writes only its own counter, so the logic has no true sharing.
2. Check the layout. Adjacent counters can land in one cache line.
3. Trace the line. Each write needs the line in M, which invalidates the other cores' copies, so the line bounces on every update.
4. Use the cost model. Stanford's slides list an L3 hit on a line modified in another core at about 75 cycles, against about 4 for an L1 hit, on older Intel parts. The writers' AMAT rises.
5. Propose a test: pad each counter to its own line, rerun, compare. Stanford also names Intel VTune and Xcode Instruments for finding this.
6. State the tradeoff. Padding spends memory, and it would not fix a truly shared counter or lock.

Where this fits in your preparation

These topics tend to sit next to pipelines and hazards, which our CPU microarchitecture questions cover. For the fabric underneath the protocol, see network-on-chip interview questions, and for the far end of the hierarchy, DDR memory controller questions and memory design interviews. Coherence also reaches off chip in PCIe and CXL.

If a question goes past what you know, say what you can derive, as in our guide to handling an unfamiliar question. You can also book a mock interview on MockVise and practice walking through a state transition out loud.

Sources: UT Austin CS 352 cache lecture, UT Austin CS 377P MESI slides, Stanford CS149 coherence and consistency, Wisconsin ECE/CS 757 coherence, UC Berkeley CS 61C TLB notes. This article offers general technical preparation guidance, not an official interview process or reported company questions. Lecture figures come from specific course notes and hardware, and may not match current processors. Confirm the interview format with your recruiter. MockVise is not affiliated with or endorsed by UT Austin, Stanford University, the University of Wisconsin, UC Berkeley, or AMD.

FAQ

Q: What is AMAT? AMAT is hit time plus miss rate times miss penalty. It extends across levels, so the L1 miss penalty is the L2 hit time plus the L2 miss rate times the L2 miss penalty.

Q: What are the four MESI states? Modified (only copy, differs from memory), Exclusive (only copy, matches memory), Shared (matches memory, others may hold it), and Invalid.

Q: What is false sharing? Two processors write different addresses in the same cache line, so the line ping-pongs between caches. In one Stanford demo, per-thread counters took 14.2 seconds packed versus 4.7 seconds padded.

Q: What is the difference between coherence and consistency? Coherence covers a single address, with a serial order of operations. Consistency covers the apparent order of operations to different addresses.