CPU Load-Store Queue Interview: Forwarding, Disambiguation, and Replay

A load-store queue must preserve the correct relationship between a load and older stores even when execution happens out of order. For each loaded byte, identify the youngest eligible older store that writes it. If relevant address or data information is missing, the design must wait or speculate with enough bookkeeping to detect and recover from a wrong assumption.

This original exercise traces byte forwarding and a replay caused by a late store address. PracHub's out-of-order and memory-system question supplies broader discussion context. The models below explain mechanisms; they do not predict an employer's questions or claim performance on a real processor.

BOOM's documentation provides one concrete implementation reference. The addresses, bytes and replay values here are synthetic. We executed a local byte-level oracle, not BOOM RTL, a complete ISA model or a multicore memory-consistency test.

Establish program order before execution order

Give every operation an unambiguous age or sequence in the active instruction window. “Older” means earlier in program order, not earlier to finish address generation. A younger store must not supply a value to an older load merely because it reached the queue first.

For this exercise, consider one thread using ordinary cacheable memory. Exclude atomics, memory-mapped I/O, fences, exceptions and page translation. Those exclusions do not make the mechanism universally sufficient; they make a small forwarding calculation independently checkable.

BOOM documents separate load and store queues, store address/data state and dependency tracking for loads. Its implementation can make progress when a store's address and data become ready at different times. The exact queue allocation and search behavior belongs to that documented design. BOOM load/store unit

Ask whether addresses are virtual or physical at each comparison and how aliasing is handled. Our integer addresses represent already comparable byte addresses. They do not model a translation delay or establish that equal virtual offsets imply the same physical location.

Forward from the youngest older writer for each byte

Use three stores and one load in the original ledger. Store 10 writes four bytes A, B, C and D at addresses 100 through 103. Store 20 writes X and Y at addresses 102 and 103. Load 30 reads four bytes starting at 100. Store 40 writes Z at 100 but is younger than the load.

The correct result is A, B, X, Y. Store 10 supplies the first two bytes, store 20 supplies the last two, and store 40 supplies nothing. Choosing the first matching store would incorrectly return C and D for the overlapping tail.

This byte-level reference defines the required values. It does not claim that every implementation merges arbitrary partial stores in one cycle. A design may stall, split the access or use a more restricted forwarding path. It must still produce the required value when the operation completes architecturally.

An interview follow-up can change store 20's address to 104. Predict the result before editing the model: it no longer overlaps the load, so store 10 supplies A, B, C and D. The rule remains the same even though the output changes.

Separate unknown address from unavailable data

An older store with a known overlapping address and missing data creates a concrete dependency. If it is the youngest older writer of a requested byte, the load cannot use an older value for that byte and call the result correct. In our reference behavior, it waits.

An older store with an unknown address creates uncertainty about whether a dependency exists. A conservative design can hold the load until the address is known. An aggressive design can allow early execution, but must retain enough information to determine whether that speculation was wrong.

Do not collapse the two situations into “the store is not ready.” Address readiness can help rule out overlap even while data is unavailable. Conversely, available data does not establish whether a store affects this load until its address and byte range are known.

Partial overlap makes the distinction sharper. If a newer eligible store fully overwrites a byte, an older known store's missing data may be irrelevant to that byte. A real forwarding policy must reason about its supported byte masks and ordering relationships rather than applying a whole-word shortcut blindly.

Trace a late-address violation through dependent work

For a second original scenario, memory at the loaded location initially contains zero. Store 10 is older but its address is unknown. Load 20 speculatively reads zero from memory. Dependent operation 21 adds one, producing a speculative result of one.

Store 10 then resolves to the same address with value seven. Under the stated program semantics, load 20 should observe seven, and its dependent should produce eight. The earlier load and dependent result are no longer valid merely because their arithmetic completed successfully.

Before address resolution: load 20 = 0; dependent 21 = 1
Older store resolves:      store 10 writes this location with 7
After correct replay:      load 20 = 7; dependent 21 = 8

Updating only the load's saved value is insufficient if a consumer already used the old value. Recovery must invalidate or replay affected work according to the design's dependency and pipeline policy. A broad flush is one option; a selective mechanism requires stronger bookkeeping.

The trace does not claim the precise stage at which every CPU detects the violation. Detection timing, replay granularity and retained state vary. Our purpose is to show why speculative completion cannot be treated as architectural correctness.

Keep the consumer’s result at one after patching the load to seven as a negative test. The final result exposes incomplete recovery immediately. This tests a different bug from selecting the wrong forwarding store in the first ledger.

Keep store retirement distinct from memory visibility

An uncommitted speculative store must not become an irreversible architectural memory update merely because its address and data are ready. The retirement mechanism first establishes that older instructions permit it to commit. The memory system can then drain a committed store under its own rules.

BOOM's reorder-buffer documentation describes commit coordination with the load/store unit. Its load/store documentation describes stores becoming eligible to fire after commitment. Those are distinct events; neither means every other core has already observed the write. BOOM reorder buffer

For a single-thread forwarding answer, a load may obtain a value from an older store before that store has reached the cache. Explain the local source of the value without equating it to global visibility. Inter-core ordering requires the ISA memory model, coherence and fence rules in addition to the queue mechanism.

This is why a C++ atomics explanation cannot be replaced with “the store queue forwards correctly.” Language-level ordering, compiler transformations and architectural guarantees operate at different layers. The practice table includes an atomics record for that boundary, not as proof that this toy queue implements it.

Check the forwarding rule against a separate oracle

Our local checker evaluates each requested byte by searching eligible older stores and selecting the highest sequence number. It falls back to the supplied memory byte only when no eligible store writes that location. A relevant newest store with unavailable data returns a wait result.

The independent oracle uses a different method: copy memory, apply all eligible stores in program order, then read the load range. Across 250 seeded random cases with partial overlaps and varied lengths, the two methods agreed. The A/B/X/Y example also checked provider identities explicitly.

That comparison is stronger than testing only one word-aligned example. It can detect an oldest-store selection bug, a younger-store leak or a missed overlapping byte. It does not cover unknown-address prediction, translation, exception priority or timing-sensitive queue reuse.

For a proposed RTL testbench, preserve an independent program-order reference and log accepted operations. Do not compute expected bytes by duplicating the same CAM winner logic used in the implementation. A shared priority bug can make two matching calculations equally wrong.

A second oracle check should record provider identity as well as byte value. If two older stores happen to write the same number, selecting the wrong store can produce the expected bits accidentally. The original A/B/X/Y fixture uses different values and explicitly checks provider sequences ten, ten, twenty and twenty.

For a proposed negative test, give the youngest overlapping store unavailable data while an older store has identical-looking ready data. The load must not declare success merely because the older bytes would be numerically plausible. It must follow the dependency contract.

Finally, distinguish a conservative wait from a wrong result. A restricted implementation may delay a partially overlapping load that the byte oracle can already resolve. That can be a performance cost without a semantic error. The verification plan should classify unnecessary stalls separately from incorrect forwarding or unrecoverable speculation, then evaluate progress under the actual resource assumptions.

Examine capacity, wraparound and stale responses

Queue indices are finite and reused. A late response must identify the intended operation, not merely an index that now belongs to a different load. A generation tag or another valid identity mechanism can prevent a squashed response from waking unrelated work after slot reuse.

Capacity accounting also deserves explicit checks. An entry waiting for data or replay still owns resources unless the recovery protocol releases them. Marking it completed for one purpose must not accidentally make its slot available for another live operation.

BOOM's memory-system overview places the load/store unit beside translation and cache interfaces. Use that separation to ask where backpressure and request acceptance occur. Our byte oracle has no outstanding cache requests and therefore cannot validate those interfaces. BOOM memory system

If the interviewer introduces an unaligned access crossing a page or cache line, extend the contract before answering. Splitting one architectural access can introduce multiple responses and faults. The simple byte semantics remain useful, but the implementation and recovery requirements become more demanding.

Practice a forwarding answer and a replay answer

These PracHub records cover out-of-order execution, CPU modeling, a software interpreter and memory ordering. The interpreter is an architectural semantics exercise; the atomics question adds a different concurrency layer. Neither is a ready-made implementation of this load-store queue or a prediction of an employer's interview.

Use the out-of-order memory-system question and explain the four-byte ledger first. Then introduce the late store address and follow the stale value into its dependent. A complete answer identifies which result is wrong, how the design notices and which work must be invalidated before retirement.

Sources and Further Reading

• BOOM: load/store queues and memory-ordering failures
• BOOM: reorder buffer and commit coordination
• BOOM: memory-system boundaries

Sources checked November 3, 2026. Original byte-level and replay exercises do not establish full-ISA or multicore correctness.