Part IIIOut-of-Order Execution
Load, Store, and Memory Ordering
July 31, 2026·52 min read·advanced
text The SUB reads r3, which the ADD writes, so the machine must enforce that order. The question that matters is when it finds out. It finds out at decode, from a 5-bit comparison of rd = 3 against rs1 = 3…
01.Part 1, why memory is harder than registers
1.1 The case that works
ADD r3, r1, r2 ; r3 = r1 + r2
SUB r5, r3, r4 ; r5 = r3 - r4
```text
The SUB reads `r3`, which the ADD writes, so the machine must enforce that order. The question that matters is **when it finds out**. It finds out at decode, from a 5-bit comparison of `rd = 3` against `rs1 = 3`, before either instruction executes anything. Renaming in [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) turns that into a physical tag and the scheduler enforces it automatically.
Name the property that made it possible, because everything below is about not having it. **A register operand carries its identity in the instruction encoding.** The name is a constant printed in the binary, independent of any value the program computes.
### 1.2 The same two instructions in memory
```text
STR r1, [r2] ; store r1 to the address held in r2
LDR r3, [r4] ; load into r3 from the address held in r4
```text
Do these conflict? There is no answer at decode. Not a hard answer, no answer, because it depends on the runtime contents of `r2` and `r4`, and those are values rather than names. Two runs of the identical binary.
| Run | `r2` holds | `r4` holds | Conflict? | What the load must do |
|---|---|---|---|---|
| A | `0x2000` | `0x2000` | **yes**, same byte | must receive the store's data |
| B | `0x2000` | `0x2008` | **no**, 8 bytes apart | may execute freely, before the store |
| C | `0x2000` | `0x2003` | **yes, partially**, if both are 4 bytes | needs part of the store's data |
Same bits, same register numbers, three correct behaviors. The decoder needs the register **contents**, which arrive several cycles later when the address generation unit adds base and offset. Put a clock on the gap.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig01.svg" alt="Both instructions are decoded by cycle three, but the load has already read memory at cycle eight while the store's address does not exist until cycle ten, so the question of whether they conflict cannot be asked until long after the load has committed to a value." caption="Both instructions are decoded by cycle three, but the load has already read memory at cycle eight while the store's address does not exist until cycle ten, so the question of whether they conflict cannot be asked until long after the load has committed to a value." id="fig:15-Load-Store-and-Memory-Ordering-1" />
The load finished before the question could be asked. That is the whole problem.
### 1.3 The two asymmetries
**First.** A register dependence is known at decode from the encoding. A memory dependence is known only at execute, from a computed value. Register hazards need a structure that runs once per instruction at a fixed stage. Memory hazards need one that survives past decode and re-resolves whenever any address arrives, in any order.
The obvious follow-up is why the machine cannot rename memory. Renaming gives every write a fresh name and rewrites subsequent readers to use it, which requires knowing at rename time which address each access touches. That is exactly the missing information, and renaming cannot solve a problem whose input it does not have.
**Second, and people forget this one.** A register write is trivially undoable, since the old physical register still exists and the map table holds the old mapping. A memory write is not. Once a store writes the L1, the previous value is gone, because there is no shadow copy of DRAM. So a speculative store, if allowed to write the cache, destroys state a squash needs to restore. **A store must not touch the cache until the machine is certain the store will happen.**
### 1.4 What certain means
An instruction is speculative for as long as anything older could cancel it, meaning an older mispredicted branch, an older exception, an interrupt, or an older memory ordering violation. All of those resolve by the time it reaches the head of the reorder buffer, so a store becomes non-speculative exactly at retirement, which is in strict program order.
A store dispatched at cycle 20 might not retire until cycle 300 if a long-latency load ahead of it is stuck on DRAM. For those 280 cycles it has a fully computed address and fully computed data and may write nothing. It has to live somewhere.
---
## Part 2, the two queues
### 2.1 The store queue
The **store queue** is where a store lives between dispatch and retirement. Entries are allocated at dispatch, in program order, from a circular buffer, and freed when the store drains to the cache after retiring. An entry holds everything needed to answer "does this store cover the bytes some load wants" and "is this store older than that load."
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig02.svg" alt="A store queue entry carries separate validity bits for its address and its data, because the two arrive from independently scheduled micro-ops, and a byte mask, because memory is byte addressed and accesses have widths." caption="A store queue entry carries separate validity bits for its address and its data, because the two arrive from independently scheduled micro-ops, and a byte mask, because memory is byte addressed and accesses have widths." id="fig:15-Load-Store-and-Memory-Ordering-2" />
Two features of that layout produce half the interview questions here.
**Address and data arrive separately, in either order.** Most machines crack a store into a **store-address** micro-op and a **store-data** micro-op, scheduled independently, because the base register and the source register become ready at unrelated times. So a store can sit with a valid address and no data, which breaks forwarding in 3.3, or with data and no address, which is what makes Part 4 necessary.
**The byte mask exists because memory is byte addressed and accesses have widths.** A 4-byte store and an 8-byte load at the same address are not the same access, and 3.4 is entirely about that.
### 2.2 The load queue
The store queue exists so a speculative store has somewhere to wait. The load queue exists for a different reason, and conflating the two reasons is a common stumble.
A load **is** allowed to execute speculatively and read the cache, because reading destroys nothing. It takes a value, writes its destination physical register, and wakes its dependents. That is fine until something proves the value wrong, and two things can. An older store may compute its address later and turn out to overlap. Or another core may invalidate the line, meaning the load read a value the memory model says it could not see. Neither is checkable when the load executes, because the information arrives afterwards, so the machine keeps a **record** of every executed load and checks it when the information shows up.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig03.svg" alt="A load queue entry adds two fields the store queue has no use for, an executed bit that marks the load as a liability whose value may have to be retracted, and a store queue cutoff that fixes which stores count as older than it." caption="A load queue entry adds two fields the store queue has no use for, an executed bit that marks the load as a liability whose value may have to be retracted, and a store queue cutoff that fixes which stores count as older than it." id="fig:15-Load-Store-and-Memory-Ordering-3" />
The `EXE` bit is the point of the structure. A load that has not executed cannot have read a wrong value. A load that has executed and published is a liability until it retires, because that value may have to be retracted.
### 2.3 Both are CAMs, and that is why they are small
Both searches ask the same shape of question. Given an address, find every matching entry. A RAM takes an index and returns contents. These take **contents** and return matches, which from Part 7 of [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams) is a **content addressable memory**, implemented by putting a comparator on every entry and running all of them in parallel. A 64-entry store queue with 48-bit physical addresses and two load ports needs
$$64 \text{ entries} \times 48 \text{ bits} \times 2 \text{ ports} = 6144 \text{ bit comparators}$$
evaluating every cycle at core frequency, plus match lines and the age resolution logic that picks a winner. Growth is linear in entries and linear in ports, with no cache-like trick available, because a CAM has no locality to exploit. Every entry genuinely might match. That is why these queues hold tens of entries rather than thousands, and why they are among the first limits on how many memory operations a core keeps in flight.
| Core | Store queue | Load queue | Ratio |
|---|---|---|---|
| Intel Sunny Cove, 2019 | 72 | 128 | 1.8 |
| Intel Golden Cove, 2021 | 80 | 192 | 2.4 |
| AMD Zen 4, 2022 | 64 | 144 | 2.3 |
| ARM Neoverse N2, 2021 | 72 | 100 | 1.4 |
| ARM Neoverse V2, 2023 | 80 | 120 | 1.5 |
Load queues are consistently larger because loads outnumber stores roughly two to one. Some designs unify the two, which gets age ordering free by construction but makes every search scan entries of the wrong kind and forces the capacities to be sized together. Split queues pay for the explicit age mechanism of 2.5 and buy independent sizing and smaller searches.
### 2.4 The whole unit, drawn
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig04.svg" alt="Three paths carry all the difficulty in this unit, a load's address searching the store queue for older stores, a store's address searching the load queue for younger executed loads, and a snoop address searching the load queue on behalf of the memory model." caption="Three paths carry all the difficulty in this unit, a load's address searching the store queue for older stores, a store's address searching the load queue for younger executed loads, and a snoop address searching the load queue on behalf of the memory model." id="fig:15-Load-Store-and-Memory-Ordering-4" />
Three paths carry all the difficulty. Load address into the store queue is forwarding, Part 3. Store address into the load queue is violation detection, Part 4. Snoop into the load queue is memory model enforcement, Part 5.
### 2.5 Age, and the wraparound trap
Every mechanism here says older or younger, so the machine needs a cheap program-order comparison. Comparing raw queue indices is wrong for the same reason FIFO full and empty are subtle in 4.3 of [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams). The queues are circular, so index order stops being program order once the pointers wrap.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig05.svg" alt="Once the head pointer has wrapped past the end of the circular buffer, raw index order and program order disagree completely, so age has to be computed as a rotation rather than read off the index." caption="Once the head pointer has wrapped past the end of the circular buffer, raw index order and program order disagree completely, so age has to be computed as a rotation rather than read off the index." id="fig:15-Load-Store-and-Memory-Ordering-5" />
The fix is a rotation, $\text{age}(i) = (i - \text{head}) \bmod N$, which is a subtractor and a mask.
| Entry index | Store | $(i - 6) \bmod 8$ | Order |
|---|---|---|---|
| 6 | S1 | 0 | oldest |
| 7 | S2 | 1 | |
| 0 | S3 | 2 | |
| 1 | S4 | 3 | youngest |
A load is not in this queue, so it has no index here. At dispatch it copies the store queue's current tail pointer into its own entry, and that snapshot is its **cutoff**. Every store already allocated is older, every store allocated afterwards is younger. A load that dispatched when tail was 2 has cutoff $(2 - 6) \bmod 8 = 4$, so stores with relative age below 4 are older, which is entries 6, 7, 0, and 1. A store later allocated into entry 2 gets age 4, correctly younger. Be able to draw this, because "how do you know which stores are older" is the standard follow-up to the forwarding question and "compare the indices" earns a follow-up you cannot survive.
---
## Part 3, store-to-load forwarding
### 3.1 The problem
The compiler runs out of registers and spills.
```text
STR x5, [sp, #16] ; spill x5 to the stack
... other work reusing x5's register ...
LDR x9, [sp, #16] ; reload the spilled value
```text
The store is speculative and sitting in the store queue, possibly for hundreds of cycles. If the load simply reads the L1 it gets whatever was at `[sp, #16]` before the spill, which is garbage from a previous stack frame. That is a correctness failure on the most common pattern a compiler emits.
So the load first asks whether any older in-flight store covers the bytes it wants. That is **store-to-load forwarding**, and it is not an optimization. It is what makes the 1.3 decision to hold stores out of the cache legal at all. The performance side is a bonus, since forwarding delivers data with no cache access. Published figures put a clean forward at 4 to 7 cycles against an L1 hit of 4 to 5, so a spill-reload pair costs about what a hit costs and sometimes less.
### 3.2 Which store wins
The search can produce several matches and picking wrong is silently wrong.
```text
program order store queue state when the load executes
------------- ----------------------------------------
S1: STR w0,[x1] addr 0x2000, data 0xAA, older than the load
S2: STR w2,[x3] addr 0x2000, data 0xBB, older than the load
S3: STR w4,[x5] addr 0x2000, data 0xCC, older than the load
L1: LDR w6,[x7] addr 0x2000 <-- executing now
S4: STR w8,[x9] addr 0x2000, data 0xDD, YOUNGER than the load
```text
Four entries match. Reason from the program rather than the hardware. S1 wrote `0xAA` and S2 overwrote it, so `0xAA` is dead. S2 wrote `0xBB` and S3 overwrote it, dead. S3 wrote `0xCC` and nothing before the load overwrote it. S4 writes `0xDD` but has not happened yet, and taking it would be reading the future.
The rule is **the youngest store that is older than the load**. Both halves matter, since youngest kills the stale overwrites and older-than-the-load kills the future stores. Implementation is a two-step reduction, masking the match vector by the cutoff from 2.5 and then priority encoding the survivors for maximum relative age.
```text
match vector from the CAM : S1=1 S2=1 S3=1 S4=1
mask by "older than load" : S1=1 S2=1 S3=1 S4=0
priority encode by age, max : S3 <-- forward from here
```text
That encode must run in **relative** age order. In the wrapped example of 2.5 a naive highest-index-wins encoder picks entry 7, which is S2, when the correct answer is entry 1, which is S4. Designs either rotate the match vector by the head pointer first, costing a barrel shifter in the load path, or carry a non-wrapping sequence number and do a real magnitude compare, costing comparator width. Either way a priority encode across 64 entries sits in the middle of the load pipeline, which is one reason the store queue cannot grow without hurting load latency.
### 3.3 The store whose data has not arrived
Now the case 2.1 set up. The address matches, the store is the correct one to forward from, and `D_vld` is zero.
| Cycle | Store S | Load L | Store queue entry for S |
|---|---|---|---|
| 10 | dispatches | | allocated, `A_vld=0`, `D_vld=0` |
| 12 | | dispatches | unchanged |
| 13 | store-address executes, addr `0x1000` | | `A_vld=1`, `D_vld=0` |
| 14 | | AGU gives addr `0x1000` | unchanged |
| 15 | | searches store queue | **address match, no data** |
| 16 | store-data executes, data `0x42` | | `D_vld=1` |
| 17 | | could now forward | fully valid |
At cycle 15 the load knows exactly where its data will come from and cannot have it. Three options. **Stall in place** is simple but occupies a load pipeline slot, blocks younger loads, and waits an unbounded time because the store's data register may itself be waiting on a miss. **Reject and replay** frees the pipeline at the cost of a full re-issue, typically 5 to 10 cycles, and risks a replay storm. **Wake on data arrival** parks the load with a pointer to the offending entry and re-issues when `D_vld` sets, which is most efficient and needs a wakeup network from store entries to parked loads. Most designs replay, with a heuristic to damp storms. The observable cost is 10 to 20 cycles rather than 5, and it shows up in performance counters as an event distinct from a cache miss.
### 3.4 The partial overlap problem
This is the deepest question in the topic and it gets asked directly. A 4-byte store writes `0xDEADBEEF` at `0x100`. An 8-byte load then reads at `0x100`. Draw the bytes, because the drawing makes the answer obvious and prose does not.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig06.svg" alt="The eight-byte load draws its low four bytes from a store still sitting in the store queue and its high four bytes from the cache, so neither source alone can satisfy it." caption="The eight-byte load draws its low four bytes from a store still sitting in the store queue and its high four bytes from the cache, so neither source alone can satisfy it." id="fig:15-Load-Store-and-Memory-Ordering-6" />
The load needs half its data from the queue and half from the cache, and neither source alone is correct.
Formalize with byte masks, which is how the hardware decides. Within an aligned 8-byte block, let mask bit $i$ mean "byte at offset $i$ is covered." A 4-byte access at offset 0 is `0x0F`, an 8-byte access at offset 0 is `0xFF`, a 4-byte access at offset 2 is `0x3C`, a 4-byte access at offset 4 is `0xF0`. One AND decides everything.
| Case | Store mask | Load mask | AND | Verdict | Action |
|---|---|---|---|---|---|
| disjoint | `0x0F` | `0xF0` | `0x00` | no bytes shared | ignore this store, read the cache |
| fully contained | `0xFF` | `0x3C` | `0x3C` = load mask | store covers all the load wants | **forward**, shift right 2 bytes |
| exact | `0x0F` | `0x0F` | `0x0F` = load mask | trivially contained | **forward**, no shift |
| **partial** | `0x0F` | `0xFF` | `0x0F`, neither `0x00` nor `0xFF` | some but not all | **the hard case** |
Zero AND means no relationship. An AND equal to the load's mask means the store covers the load entirely and a byte shift suffices. Anything else is partial.
Why not merge the two sources? **Two different timing paths.** The store queue and the L1 data array are physically far apart and arrive in different cycles, so a merge needs an extra alignment stage, and that stage lands on load-use latency, the most timing-critical number in the core because it feeds the speculative wakeup loop of Part 5 of [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution). **And the general case is not two sources.**
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig07.svg" alt="In the general case each byte of the load needs the youngest older store covering that byte, so the eight bytes can come from as many as eight different store queue entries plus the cache, and a full merge would be eight parallel per-byte priority encodes on the most timing-critical path in the core." caption="In the general case each byte of the load needs the youngest older store covering that byte, so the eight bytes can come from as many as eight different store queue entries plus the cache, and a full merge would be eight parallel per-byte priority encodes on the most timing-critical path in the core." id="fig:15-Load-Store-and-Memory-Ordering-7" />
In the limit the load's 8 bytes come from 8 different store entries plus the cache, each byte independently needing the youngest older store covering **that byte**. A fully general merge is eight parallel per-byte priority encodes across the whole store queue feeding an 8-way byte mux, on the most timing-critical path, to serve a rare case.
So most designs refuse. They detect the partial condition, cancel the load, and **stall it until the offending store retires and drains to the cache**, after which the load re-executes against one clean source, at 10 to 20 cycles typically and much more if the store is stuck behind a long-latency instruction at the reorder buffer head. The design point is not binary, since real machines support a cheap subset, typically forwarding whenever the store fully contains the load at any alignment, and the published optimization guides tabulate which size and offset combinations forward per generation. In profiles, a loop that stores 8 bytes and reloads 4 at a non-zero offset can pay 15 to 20 cycles per iteration, and the fixes are to match producer and consumer widths, align the data, or keep the value in a register.
### 3.5 Physical or virtual, and the trick that gets you both
Which address does the CAM compare? The tempting answer is the virtual address, available straight out of the AGU with no TLB in the way. It is **wrong**, and wrong in the dangerous direction.
Virtual memory allows **synonyms**, where two virtual addresses map to one physical address. Shared library text, shared memory segments, and a page mapped twice inside one process all produce them. If a store writes through $V_1$ and a load reads through $V_2$, both translating to $P$, they genuinely alias and the load must get the store's data. A virtual comparison sees $V_1 \ne V_2$, reports no match, and lets the load read stale data. Silent wrong answer.
So the comparison must be on **physical** addresses, which appears to put the search behind the TLB. The escape is a fact from [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering) worth re-deriving because it is used constantly.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig08.svg" alt="Only the page number is translated, so the low twelve bits of the physical address are known the instant the AGU produces the virtual address and can be compared a full TLB lookup early." caption="Only the page number is translated, so the low twelve bits of the physical address are known the instant the AGU produces the virtual address and can be compared a full TLB lookup early." id="fig:15-Load-Store-and-Memory-Ordering-8" />
Bits `[11:0]` of the physical address are known at AGU time, before the TLB does anything. Twelve exact bits for free. Check both error directions, because that check is the whole justification. **False negatives are impossible**, which is what correctness demands, since the same physical address implies the same $PA[11:0]$, and $PA[11:0] = VA[11:0]$, so a true alias always sets the filter. **False positives are possible** and merely annoying, since two accesses at the same offset in different pages match without aliasing.
| | Virtual address | Physical address | $VA[11:0]$ |
|---|---|---|---|
| store | `0x0000_7FFF_A230_1040` | `0x0000_0001_2340_1040` | `0x040` |
| load | `0x0000_5555_1111_1040` | `0x0000_0001_2340_1040` | `0x040` |
A full virtual comparison calls these unrelated. They are the same byte of memory. The offset filter fires, and the later comparison of $PA[47:12]$, `0x0000000012340` on both sides, confirms.
The structure is therefore **early filter, confirm later**. A fast CAM compares the untranslated offset bits, often extended to 16 or 20 bits by speculatively including a few translated bits for a sharper filter, producing candidates in the same cycle as the AGU result. The full physical tag comparison runs a cycle or two later on that small candidate set using ordinary comparators rather than a CAM. The cost is that a false positive must be recoverable, so designs either place the confirm before the value is consumed or accept a replay. And once translated bits enter the filter, false **negatives** become possible, which forces an independent full physical check on every store at the confirm stage and puts the cost back.
### 3.6 The load pipeline, cycle by cycle
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig09.svg" alt="Cycle two is the point of the pipeline, because the TLB, the store queue CAM, and the L1 tag and data arrays all start from the virtual address at the same instant rather than waiting on each other." caption="Cycle two is the point of the pipeline, because the TLB, the store queue CAM, and the L1 tag and data arrays all start from the virtual address at the same instant rather than waiting on each other." id="fig:15-Load-Store-and-Memory-Ordering-9" />
Cycle 2 is the point. The TLB, the store queue CAM, and the L1 tag and data arrays all start from the virtual address at the same instant, because none can afford to wait for the others. That parallelism is what makes a 4-cycle load possible, and it is bought with the VIPT constraint from [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering) on the cache side and the offset-filter trick on the store queue side. Both are the same idea, which is to start work on the untranslated bits and confirm with the translated ones.
---
## Part 4, memory disambiguation
### 4.1 The reverse case
```text
STR x3, [x4] ; x4 comes from a long dependence chain, address unknown
LDR x1, [x2] ; x2 is ready now, address known immediately
```text
The load is ready at cycle 5. The store's address will not exist until cycle 20. The load queue entry knows an older store entry has `A_vld = 0` and does not know whether that store will land on its address. The machine must commit to a policy without the information the policy needs.
### 4.2 Conservative stalling, costed
Policy one is to wait until every older store has a valid address, after which the comparison is exact and no violation is possible. Trivially correct. Cost it before dismissing it.
Take a loop of 10 instructions with 3 loads and 2 stores on a machine issuing 4 per cycle, so ideal steady state is $10/4 = 2.5$ cycles per iteration. Suppose the average load waits 8 cycles for the oldest unresolved store address, which is not extreme when store addresses depend on pointer arithmetic that itself depends on a load.
$$\frac{2.5 + 8}{2.5} = 4.2\times \text{ slower}$$
That gives back the entire benefit of out-of-order execution and more, and the damage lands where it hurts most, since loads sit at the head of most dependence chains. A milder version stalls only against stores whose address is unknown, letting the load pass resolved non-matching stores. That helps and is the real fallback, but it does not fix the case that matters, which is one slow store address blocking a stream of unrelated loads.
### 4.3 Speculating, and what a squash costs
Policy two assumes no conflict, executes, and repairs if wrong. The repair is the branch-misprediction machinery, so the load and everything younger is flushed, rename and free list roll back, and the front end refetches. On a 256-entry reorder buffer with a 10-stage front end that is roughly 20 to 30 cycles and discards up to 250 in-flight instructions.
The policy is a bet and the bet can be evaluated. With $p$ the probability a load conflicts with an older unresolved store, $C_{sq}$ the squash cost, and $C_{st}$ the conservative stall,
$$\text{expected speculative cost} = p \cdot C_{sq}, \qquad \text{conservative cost} = C_{st}$$
With $C_{sq} = 25$ and $C_{st} = 8$, speculation wins whenever
$$p < \frac{C_{st}}{C_{sq}} = \frac{8}{25} = 0.32$$
Measured aliasing rates are typically well under 5 percent of loads and often under 1 percent, because most stores go to a different object than most loads. At $p = 0.01$ the expected cost is $0.25$ cycles per load against 8, a factor of 32, with a break-even at 32 percent that leaves enormous headroom. That is why every high-performance machine speculates, and why the answer to "conservative or speculative" is not a matter of taste.
### 4.4 The predictor, because the average hides the tail
Aliasing is not uniform. A handful of static loads alias almost every execution, typically because they read through a pointer a nearby store just wrote, and the rest never alias. Speculating on the first group pays the 25-cycle squash repeatedly at the same program counter, so predict per static instruction. The canonical design is the **store set predictor** of Chrysos and Emer, in which each load learns the set of stores it has conflicted with and waits only for those. Two tables implement it.
- **SSIT**, the store set identifier table, indexed by program counter, mapping both loads and stores to a store set identifier. A load and a store share an identifier if they have aliased.
- **LFST**, the last fetched store table, indexed by identifier, holding the store queue entry of the most recently dispatched store in that set.
| Event | SSIT`[0x3800]` store | SSIT`[0x4000]` load | LFST`[7]` | What the load does |
|---|---|---|---|---|
| first execution, untrained | invalid | invalid | empty | issues freely, **violation**, 25-cycle squash |
| handler allocates set 7 | 7 | 7 | empty | |
| store dispatches into SQ entry 12 | 7 | 7 | 12 | |
| load dispatches | 7 | 7 | 12 | reads SSIT, gets 7, reads LFST, gets SQ 12, **waits for entry 12's address** |
| store's address resolves, no overlap | 7 | 7 | 12 | load issues, small stall, no squash |
The load paid a few cycles instead of 25, and only because this specific load had been caught before.
**Merging.** When a violation fires and both instructions already have identifiers, the sets must become one, and the standard rule is that the smaller identifier wins. Arbitrary, but deterministic, and determinism is what stops two stores from ping-ponging a load between sets forever.
**Clearing.** Without a periodic reset, one alias observed once poisons a load permanently, because programs change phase and aliasing that was real in one phase is fiction in the next. The tables are cleared wholesale every $N$ retired instructions. Too small an $N$ and nothing is learned, so every trained pair pays its squash again. Too large and stale sets stall loads that no longer alias.
**Confidence.** A two-state prediction flips on a single event, so a two-bit or three-bit saturating counter per entry gives hysteresis, the same idea as branch prediction in [Front End and Branch Prediction](/learn/hardware-interview-prep/front-end-and-branch-prediction) applied to a different question.
### 4.5 Detection, and the symmetry
Prediction is a guess, so something checks it. When a store's address becomes valid, the store searches the **load queue** for **younger** loads that have already executed and whose byte masks overlap. A hit means that load read memory before this store wrote it, which is a **memory ordering violation**. State the symmetry explicitly, because being able to state it is what separates understanding the structure from memorizing two mechanisms.
| | store-to-load forwarding | ordering violation detection |
|---|---|---|
| Triggered by | a **load** getting its address | a **store** getting its address |
| Structure searched | the **store** queue | the **load** queue |
| Age direction | entries **older** than the searcher | entries **younger** than the searcher |
| Extra qualification | the store must have valid data | the load must have already executed |
| Match selected | the **youngest** match | the **oldest** match |
| Purpose | supply correct data | discover that incorrect data was already supplied |
| Outcome | forward bytes, no penalty | flush from that load, roughly 25 cycles |
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig10.svg" alt="The two searches are mirror images, a load looking backwards through the store queue for the youngest older match and a store looking forwards through the load queue for the oldest younger match." caption="The two searches are mirror images, a load looking backwards through the store queue for the youngest older match and a store looking forwards through the load queue for the oldest younger match." id="fig:15-Load-Store-and-Memory-Ordering-10" />
The asymmetry in which match wins has a clean reason. Forwarding wants **one value**, and the correct one is the most recent write before the load, so youngest wins. Detection wants a **recovery point**, and flushing from the oldest offender automatically covers every younger one, so oldest wins. Selecting the youngest violator would leave older violations unrepaired.
### 4.6 Recovery
The straightforward recovery is a full flush from the offending load, identical to a branch squash. Correct and blunt, because it discards every instruction younger than the load including the vast majority that never touched the address.
**Selective replay** re-executes only the offending load and the transitive closure of its consumers, which is far less work when the chain is short. The cost is tracking that closure, meaning dependence information retained after issue, which is neither small nor easy to verify. Designs that already have a replay mechanism for cache-miss speculation can reuse it. Designs that do not, flush. A third option is elegant and rarely built, which is to **rewrite** the load's destination register with the correct value at detection and let dependents recompute, legal because nothing younger has retired. It is rare because the write port and wakeup broadcast needed to re-publish collide with normal operation. Raise it if asked what else could be done.
---
## Part 5, enforcing the memory model
### 5.1 What the unit is responsible for
Parts 3 and 4 dealt with one core, where correctness means its own program order semantics. Part 5 is about what other cores may observe, which is the **memory consistency model** from [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering). Coherence, in [Cache Coherence Protocols](/learn/hardware-interview-prep/cache-coherence-protocols), makes accesses to a single address appear in one global order. Consistency constrains order between **different** addresses. The load-store unit is where that constraint becomes gates.
The critical realization is that a memory model does not forbid **reordering**, it forbids reordering that is **observable**. A machine may execute two loads in any order as long as no other core can construct evidence that it did. That distinction is the entire basis of 5.2, and getting it backwards produces designs that stall enormously for nothing.
### 5.2 Detecting that reordering became visible
With `x` and `y` both starting at 0 in different cache lines,
```text
Core 0 Core 1
------ ------
ST x = 1 A: LDR r1, [y]
ST y = 1 B: LDR r2, [x]
```text
Under a strong model such as x86's total store order, core 1's loads must appear to execute in program order, so the outcome $r1 = 1$ and $r2 = 0$ is **forbidden**. If core 1 saw the store to `y`, which came after the store to `x`, it must also see `x = 1`.
Now let the hardware do what it wants. `x` is in core 1's L1 and `y` is not, so B executes first at cycle 5 and reads `x = 0`. A misses and returns at cycle 60. In between, core 0 executes both stores. A then returns `y = 1`, and the forbidden outcome has occurred.
Here is the counterintuitive part. **Executing B first was not the error.** Had core 0 not run in that window, the reordering would have been undetectable and perfectly legal. The error is that it became **visible**, and it can only become visible if another core writes one of these locations during the window. Writing requires taking the line exclusive, which sends an **invalidation**. So the invalidation is exactly the observability signal, arriving unbidden precisely when the reordering could be detected.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig11.svg" alt="An invalidation arriving from the coherence fabric is exactly the signal that another core is in a position to observe the reordering, so a snoop that hits an executed load while an older load is still outstanding forces a squash." caption="An invalidation arriving from the coherence fabric is exactly the signal that another core is in a position to observe the reordering, so a snoop that hits an executed load while an older load is still outstanding forces a squash." id="fig:15-Load-Store-and-Memory-Ordering-11" />
Three costs come with it and naming all three makes the answer credible. **A second CAM port on the load queue**, because snoops arrive asynchronously and cannot wait for a free port without backpressuring coherence, which risks the protocol deadlocks in Part 7 of [Cache Coherence Protocols](/learn/hardware-interview-prep/cache-coherence-protocols). **Line granularity, therefore false squashes**, because a snoop to any byte of a 64-byte line matches an entry for any other byte of it, so two cores working on adjacent independent variables in one line squash each other repeatedly. That is false sharing reappearing as pipeline flushes rather than coherence traffic. **A conservative condition**, since the check fires whenever an older load is incomplete without proving this interleaving is actually forbidden, so the machine squashes on a superset of real violations.
### 5.3 What a weak model deletes
Under a weakly ordered model such as AArch64, loads to **different** addresses may be reordered freely with no requirement that other cores fail to observe it, and software that cares inserts barriers. The 5.2 check therefore does not run on ordinary loads at all, which removes a CAM port from the load queue, removes a large source of flushes including all the false-sharing ones, and removes a set of hard multiprocessor corner cases from the verification plan.
That is a real simplification, worth saying plainly given Apple ships an ARM architecture, and worth **not overstating**, because the honest version is more impressive. The machinery does not disappear, it becomes conditional.
- **Same-address ordering still holds**, because coherence requires that two loads from one core to the same address return values consistent with one order for that location.
- **Acquire and release accesses still need it**, since `LDAR` must order everything after it and `STLR` everything before it, over the window each defines.
- **Barriers still need it**, per 5.4, and **atomics still need it**, per 5.5.
So a strong model makes ordering the default and pays for it everywhere, while a weak model makes ordering opt-in and pays only where software asked. Similar total machinery, very different exercise frequency.
### 5.4 Barriers, and what they cost
| Instruction | What it orders | Typical implementation | Rough cost |
|---|---|---|---|
| `DMB` | accesses before it against accesses after it | block issue of younger memory ops until older ones are ordered | tens of cycles |
| `DSB` | as `DMB`, plus waits for **completion**, including cache and TLB maintenance | full drain | tens to hundreds |
| `ISB` | flushes the instruction pipeline so later fetches see updated system state | pipeline flush and refetch | branch-mispredict cost |
| `LDAR` | this load against everything **after** it | one-sided, no drain of older work | a few cycles |
| `STLR` | this store against everything **before** it | older accesses ordered before this store becomes visible | moderate |
Cost the conservative `DMB`. Suppose 40 live stores when the barrier issues and the naive implementation drains before allowing anything younger. The L1 takes one store per cycle, so the drain alone is 40 cycles, and if any store misses it cannot drain until its line arrives, roughly 15 cycles from L2 and well over 100 from DRAM.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig12.svg" alt="A naive full drain makes the barrier cost the whole time the slowest store takes to reach memory, so one missing store holds every younger memory operation at issue for a hundred and thirty-one cycles." caption="A naive full drain makes the barrier cost the whole time the slowest store takes to reach memory, so one missing store holds every younger memory operation at issue for a hundred and thirty-one cycles." id="fig:15-Load-Store-and-Memory-Ordering-12" />
Making barriers **precise** is where the microarchitecture work lives. **Order only what the scope requires**, since AArch64 barriers carry a shareability domain and an access direction, so `DMB ISHST` orders only stores within the inner shareable domain, and treating every `DMB` as a full system barrier leaves large performance unclaimed. **Order at visibility rather than at issue**, letting younger operations execute but tagging them so they cannot become architecturally visible until the condition is met, which lets younger misses start during the drain, at the cost of applying the 5.2 squash check to anything that executed across the barrier. **Track the condition with a counter** of outstanding older accesses rather than forcing a drain rate.
### 5.5 Atomics and the exclusive monitor
```text
retry:
LDXR w1, [x0] ; load exclusive, arms the monitor
ADD w1, w1, #1
STXR w2, w1, [x0] ; store exclusive, w2 = 0 on success, 1 on failure
CBNZ w2, retry ; retry if the store failed
```text
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig13.svg" alt="The whole monitor is one valid bit and one reserved line address, and the long list of things that clear it is what makes a store exclusive able to fail spuriously while never succeeding spuriously." caption="The whole monitor is one valid bit and one reserved line address, and the long list of things that clear it is what makes a store exclusive able to fail spuriously while never succeeding spuriously." id="fig:15-Load-Store-and-Memory-Ordering-13" />
**The monitor may fail spuriously and may not succeed spuriously.** A `STXR` failing when nothing conflicted is legal and costs a retry. A `STXR` succeeding after another core wrote the line breaks atomicity. That asymmetry is why implementations may clear the monitor on almost anything, and why the architecture requires the loop to be short and free of unrelated accesses. Software that puts a function call or a missing load inside the loop can livelock, not because the hardware is broken but because the monitor keeps getting cleared.
**Two cores can livelock each other.** Core 0 does `LDXR`, core 1 does `LDXR` then `STXR`, which invalidates core 0's line and clears its monitor, so core 0's `STXR` fails and retries, invalidating core 1's line, and so on. Implementations add forward progress, typically holding the line exclusive for a small window after a `LDXR` so the local `STXR` can land, and software adds backoff.
**Far atomics** answer real contention. ARMv8.1 added single-instruction atomics such as `LDADD`, `SWP`, and `CAS`, whose important freedom is that the operation may execute **at the point of coherence** rather than in the core. Cost eight cores incrementing one shared counter. With the exclusive pair, each increment needs the line exclusive locally, so it migrates once per increment at, say, 80 cycles per transfer, giving $8 \times 80 = 640$ cycles fully serialized. With a far atomic the line never moves, each core sends an add request to the shared cache, and the cache performs them back to back at perhaps 4 cycles each, so $8 \times 4 = 32$ cycles of occupancy plus one overlapped round trip per core. An order of magnitude, widening with core count because the migrating version scales in transfers while the far version scales in cache occupancy. The unit's job is to recognize the condition and route outward rather than acquiring the line, and some designs make that adaptive.
---
## Part 6, the rest of the unit
### 6.1 Address generation, and what actually limits memory throughput
The **address generation unit** computes the effective address, generally
$$VA = X_n + (X_m \ll s) + \text{imm}$$
The shift $s$ is a constant from the encoding, so it is free wiring rather than a barrel shifter, which is why the ISA restricts the scale to the access size. The addition is a 3-input sum, usually a carry-save adder feeding one carry-propagate adder rather than two chained adders per [Arithmetic Hardware](/learn/hardware-interview-prep/arithmetic-hardware), because it sits directly on load-use latency.
AGU count limits memory operations per cycle the way port count limits arithmetic in Part 3 of [Execution Units](/learn/hardware-interview-prep/execution-units), but it is rarely the binding constraint by itself, and knowing what actually binds is a better answer than reciting the AGU number. Work a vector copy loop of 8 instructions per iteration with 2 loads and 2 stores, on a machine with 6-wide issue, 3 load AGUs, 2 store AGUs, 2 L1 load ports, and 1 L1 store port.
| Resource | Demand per iteration | Supply per cycle | Cycles per iteration allowed |
|---|---|---|---|
| issue width | 8 instructions | 6 | 1.33 |
| load AGU | 2 loads | 3 | 0.67 |
| store AGU | 2 store-address ops | 2 | 1.00 |
| L1 load port | 2 loads | 2 | 1.00 |
| **L1 store port** | **2 stores to write** | **1** | **2.00** |
The binding constraint is the store port at 2 cycles per iteration. The machine is 50 percent idle on issue width and it does not matter. Each AGU also implies a dTLB read port and an L1 tag read port, which are the expensive parts, so a fourth load AGU without a fourth TLB port buys nothing and extra cache ports without AGUs buy nothing either. "How many loads per cycle" really means "how many of AGU, TLB port, tag port, data port, and store queue CAM port do you have," and the smallest is the answer.
### 6.2 Write combining
A store missing the L1 normally triggers a **read for ownership**, fetching the whole 64-byte line so the store's few bytes can merge into it. That read is necessary when only part of the line will be written and pure waste when the whole line is about to be. Cost it for a kernel producing 1 GB of output.
| Policy | Memory traffic | |
|---|---|---|
| write allocate with read for ownership | 1 GB read + 1 GB written | **2 GB** |
| full-line write, no read | 1 GB written | **1 GB** |
Half the traffic on a workload where bandwidth is the entire story. A **write combining buffer** captures this with a few line-sized entries, each holding a line address, accumulated data, and a per-byte written mask. Stores to the same line merge. A complete mask issues a full-line write with no preceding read, and an entry evicted with a partial mask issues a partial write, which is the expensive case the mechanism exists to avoid.
The second saving is transaction count on uncached regions. Writing 64 bytes to a framebuffer with eight 8-byte stores costs eight bus transactions uncombined and one combined, an 8x reduction on an interconnect where per-transaction cost dominates small payloads, per [Interconnect and AMBA](/learn/hardware-interview-prep/interconnect-and-amba). The consequence software lives with is ordering, since the buffer reorders and merges by construction, so writes through it are weakly ordered even on architectures that otherwise are not. That is why x86 has `SFENCE` despite total store order, and it illustrates that a memory model is defined per memory type rather than per architecture.
### 6.3 Non-temporal stores
A **non-temporal** store, `STNP` on AArch64 or the `MOVNT` family on x86-64, says the data will not be read again soon. The problem it addresses is pollution. Stream 1 MB of output through a core whose L2 is 1 MB and the output evicts the entire L2, so a 512 KB hot working set is gone and the next phase refetches all of it, in exchange for zero reuse value from the streamed data. Non-temporal stores bypass the cache through the write combining buffer of 6.2, or allocate into a restricted subset of ways so the damage is bounded.
Two honest caveats. It is a **hint**, which an implementation may ignore, so software depending on it for performance depends on a specific microarchitecture. And it is wrong when the programmer is wrong, converting a cache hit into a full memory access on exactly the access being optimized. Non-temporal accesses are also weakly ordered where ordinary ones are not, so they need an explicit fence before any consumer relies on them.
### 6.4 Misaligned accesses
An access is **misaligned** when its address is not a multiple of its size. What matters is not the misalignment but whether it crosses a cache line.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig14.svg" alt="The bottom six bits of the physical address are the byte offset within a sixty-four byte line, so whether an access splits depends only on that offset and the access size, not on whether the address is aligned." caption="The bottom six bits of the physical address are the byte offset within a sixty-four byte line, so whether an access splits depends only on that offset and the access size, not on whether the address is aligned." id="fig:15-Load-Store-and-Memory-Ordering-14" />
| Access | Offset `addr[5:0]` | Offset + size | Splits? | Bytes in line A / B |
|---|---|---|---|---|
| 8-byte load at `0x1038` | `0x38` = 56 | 64 | **no**, fits exactly | 8 / 0 |
| 8-byte load at `0x1039` | `0x39` = 57 | 65 | **yes** | 7 / 1 |
| 8-byte load at `0x103F` | `0x3F` = 63 | 71 | **yes** | 1 / 7 |
| 4-byte load at `0x103C` | `0x3C` = 60 | 64 | **no**, fits exactly | 4 / 0 |
Misalignment alone does not force a split. A 4-byte load at `0x1002` is misaligned and lives entirely in one line, costing a byte rotate and nothing more. Only a split costs real time.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig15.svg" alt="A load that straddles a line boundary takes one byte from the end of the first line and seven from the start of the second, so it needs two tag lookups, two data reads, and a rotate and merge network before it can hand back eight contiguous bytes." caption="A load that straddles a line boundary takes one byte from the end of the first line and seven from the start of the second, so it needs two tag lookups, two data reads, and a rotate and merge network before it can hand back eight contiguous bytes." id="fig:15-Load-Store-and-Memory-Ordering-15" />
Costs are concrete. Two tag lookups, two data reads, two TLB accesses if it also crosses a page, a rotate-and-merge network in the load path, and either two cache port occupancies in one cycle or two passes through the pipeline, so it consumes twice the cache bandwidth either way. Both halves can miss independently, so a split can occupy two MSHRs from Part 7 of [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching). It also interacts badly with Parts 3 and 4, since two physical addresses means two store queue searches and two load queue entries, which is one reason splits are handled by cracking into micro-ops per 6.7.
Some architectures avoid the problem by faulting. AArch64 permits misaligned access to Normal memory but **requires** alignment for Device memory and for exclusive accesses such as `LDXR`, a concrete case where an architectural rule exists specifically to keep a hardware structure, here the exclusive monitor, from having to handle a split.
### 6.5 Page crossing, two translations, and precise exceptions
A split across a **page** boundary is qualitatively worse, because the halves need two independent translations.
<Figure src="/figures/hardware-interview-prep/iv-15-Load-Store-and-Memory-Ordering-fig16.svg" alt="The split rule for a page has the same shape as the split rule for a line, but the two halves now fall in different pages and so need two independent translations, either of which can miss, fault, or carry different permissions and a different memory type." caption="The split rule for a page has the same shape as the split rule for a line, but the two halves now fall in different pages and so need two independent translations, either of which can miss, fault, or carry different permissions and a different memory type." id="fig:15-Load-Store-and-Memory-Ordering-16" />
Everything that can go wrong with one translation now goes wrong twice, independently. Either can miss the TLB and require a page table walk, so one access can generate two walks. Either can **fault**, because the page is absent, unmapped, or fails a permission check. The two pages can carry different permissions, so a store can be legal in one half and illegal in the other, and different **memory types**, so half an access can be Normal cacheable and half Device, which per 6.6 have incompatible rules.
The hard consequence is precise exceptions. From [CPU Foundations Pipeline and Hazards](/learn/hardware-interview-prep/cpu-foundations-pipeline-and-hazards), precise means architectural state must look exactly as though every instruction before the faulting one completed and the faulting one and everything after did nothing.
Suppose a page-crossing **store** writes its first half and the second half faults. Architectural memory is now half modified by an instruction that did not complete. The handler sees inconsistent state, and the standard recovery of fixing the mapping and re-executing writes the first half a second time. That happens to be harmless for a plain store because the write is idempotent, but the state visible to the handler is wrong regardless.
The fix is ordering. **Both translations must be resolved and known non-faulting before either half modifies architectural state.** In practice a page-crossing store occupies two store queue entries, each carrying its own fault status, and the drain logic refuses to write either until both are clean. If either faults, neither writes and the exception is taken with memory untouched. A load is easier but not free, since it writes only a register but must still publish nothing before both translations validate.
A second hazard is easy to miss. If the halves are separate micro-ops with separate reorder buffer entries, an **interrupt** can be taken between them, and architectural state at that instant shows a half-executed instruction. The remedy is to mark the micro-ops as an atomic group that retires all or none, which is the same constraint microcoded sequences need and the bridge to 6.7.
### 6.6 Memory types, and why a load cannot always speculate
A quiet assumption runs through Parts 3 and 4, which is that executing a load early is harmless because reading has no side effect. That is false for a large class of addresses.
Architectures classify memory by **type**, carried in the page tables and returned by the TLB alongside the translation. AArch64 distinguishes Normal memory, which may be cached, reordered, merged, and speculatively accessed, from Device memory, which may not. Device memory covers memory-mapped IO, and reading one of those registers can pop a FIFO, clear an interrupt, or advance a state machine. A speculative read of a UART receive register **destroys a byte** whether or not the load is later squashed, and no pipeline recovery gets it back. So the unit may not speculate on Device memory, may not prefetch it, may not merge accesses to it, and may not reorder them.
The awkward part is timing. The memory type arrives from the TLB in the same cycle as the physical address, which is **after** the load issued and after the L1 lookup started speculatively from the virtual index. The resolution is that the L1 lookup itself is harmless, since Device pages are non-cacheable and will miss, so the machine need only guarantee that the request is not **sent outward** to the fabric until the type is known and the access is non-speculative. A Device access is therefore held at the core boundary until it is the oldest instruction, which is why polling a hardware register in a tight loop is catastrophically slow compared to reading a variable.
### 6.7 Splitting into micro-ops, and the microcode connection
Several mechanisms above reduce to the same technique, in which one architectural instruction becomes several internal operations.
| Architectural instruction | Micro-ops | Why |
|---|---|---|
| any store | store-address, store-data | the operands become ready at unrelated times, per 2.1 |
| load pair `LDP` | two loads | two destinations, possibly two lines |
| store multiple, `STM` | N stores | one instruction, N architectural writes |
| line-crossing access | two accesses plus a merge | per 6.4 |
| page-crossing access | two accesses with two translations | per 6.5 |
| unaligned atomic | a locked sequence | the monitor cannot span lines |
| x86-64 `REP MOVSB` | a microcoded loop | arbitrary length known only at runtime |
There is a real choice about **when** the split is decided. **Statically at decode**, always emitting two micro-ops for anything that might split, is simple and uniform and costs decode bandwidth and issue slots on the overwhelmingly common non-splitting case, so it is right for instructions that are architecturally always multi-access such as `LDP` or `STM`. **Dynamically at execute**, emitting one micro-op, evaluating the 6.4 condition at the AGU, and replaying as two accesses if it fires, costs a replay of perhaps 10 cycles but only in the rare case and nothing at all when aligned. Most modern designs use the second for alignment splits and the first for architecturally multi-access instructions.
The microcode connection is direct rather than analogous. Once an instruction expands into a sequence of memory micro-ops, someone specifies what happens when an exception or interrupt lands mid-sequence. Which micro-ops form an atomic retirement group. Which one reports the fault. What state the handler must see. Whether re-execution after the handler repeats completed micro-ops and whether that repetition is architecturally visible. Whether a partially completed `REP MOVSB` resumes from a counter register or restarts. That is microcode work sitting directly on top of the load-store unit's structures.
---
## Part 8, check yourself
Answer out loud, in full sentences, as if an interviewer asked. If you cannot, reread the section named.
1. Why can a register dependence be resolved at decode while a memory dependence cannot? Give the property of register operands that makes it work, and say why the machine cannot simply rename memory instead. (1.1, 1.3)
2. Give the second asymmetry, the one about undo, and explain why it forces a store to wait rather than write the cache when it executes. When exactly does a store become non-speculative? (1.3, 1.4)
3. A store queue has 8 entries, head is 6, tail is 2. Which entry holds the oldest live store, and how does a load that dispatched when tail was 2 determine which stores are older than it? (2.5)
4. Count the comparators in a 64-entry store queue with 48-bit addresses and two load ports, and explain why that cost cannot be made sublinear in entries. (2.3)
5. Three older stores and one younger store all match a load's address. Which forwards, and give the reasoning from program semantics rather than from hardware. (3.2)
6. A store's address matches a load but its data has not arrived. Name the three things the machine can do and what each costs. (3.3)
7. A 4-byte store at `0x100` is followed by an 8-byte load at `0x100`. Draw the bytes, give the mask arithmetic, say what most designs do and what it costs, then explain why a general merge is not two sources but up to nine. (3.4)
8. Why must the store queue comparison use physical addresses, and what specific bug appears if you compare full virtual addresses? Describe the early-filter trick and prove it cannot produce false negatives. (3.5)
9. Conservative stalling versus speculation. Work the break-even probability with a 25-cycle squash and an 8-cycle stall, and say what the measured aliasing rate actually is. (4.2, 4.3)
10. Walk the store set predictor's two tables through a first violation, the merge, and a later correct stall. What does the periodic clear protect against, and what breaks if the interval is too short? (4.4)
11. State the symmetry between the two searches in six dimensions, and explain why forwarding takes the youngest match while detection takes the oldest. (4.5)
12. Under a strong memory model, how does the machine detect that speculative load reordering became visible? Say why an invalidation is exactly the right signal, and name the three costs including the false-sharing one. (5.2)
13. What does a weak memory model remove, and what does it specifically **not** remove? Name at least three cases where the ordering machinery still runs. (5.3)
14. Cost a conservative `DMB` with 40 live stores where one misses to DRAM, then give two ways to make barriers more precise. Separately, what clears an exclusive monitor, and why may it fail spuriously but not succeed spuriously? (5.4, 5.5)
15. Give the split rule for a 64-byte line, apply it at offsets `0x38`, `0x39`, and `0x3F`, then explain why a page-crossing store whose second half faults is a precise-exception violation and what ordering rule prevents it. (6.4, 6.5)
---
## Part 9, related notes
- [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) for renaming, the reorder buffer that defines when a store becomes non-speculative, the wakeup loop that load-use latency feeds, and the squash machinery a violation reuses
- [Virtual Memory and Memory Ordering](/learn/hardware-interview-prep/virtual-memory-and-memory-ordering) for the architectural memory models this unit enforces, the page offset fact behind the early filter in 3.5, and the VIPT constraint that lets the L1 start in parallel with the TLB
- [Cache Coherence Protocols](/learn/hardware-interview-prep/cache-coherence-protocols) for the invalidations that drive the snoop check in 5.2, and for false sharing, which reappears here as spurious pipeline flushes
- [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching) for the L1 underneath, the MSHRs a split access occupies two of, and write allocate against the full-line write in 6.2
- [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams) for what a CAM is, why it is always small, and the circular-buffer reasoning behind the age wrap in 2.5
- [Execution Units](/learn/hardware-interview-prep/execution-units) for the ports and bypass network the AGU competes with and feeds
- [CPU Foundations Pipeline and Hazards](/learn/hardware-interview-prep/cpu-foundations-pipeline-and-hazards) for precise exceptions, which 6.5 puts under real pressure
- [Front End and Branch Prediction](/learn/hardware-interview-prep/front-end-and-branch-prediction) for the saturating-counter confidence machinery the dependence predictor borrows
- [Interconnect and AMBA](/learn/hardware-interview-prep/interconnect-and-amba) for what a write combining buffer's transactions look like once they leave the core
- [Load-Store Queue Design](/learn/computer-architecture/load-store-queue) for the vault's treatment of Parts 1 through 4, with production queue sizes and more on the store-set predictor
- [Virtual Memory](/learn/computer-architecture/virtual-memory) and [TLBs and Address Translation](/learn/computer-architecture/tlbs) for the translation machinery behind Parts 3 and 6Book mode
Was this helpful?