Load-Store Queue Design

Register renaming in Chapter 51 solved one ordering problem cleanly. Every architectural register write got a fresh physical register, so out-of-order execution of register-only instructions never produced wrong values. Loads and stores do not get that treatment. Memory has one architectural address space shared across the whole program, and the addresses are not known at dispatch. Two stores can write the same byte. A load can read a byte that an older store wrote earlier in program order. The hardware cannot rename memory the way it renames registers, because the rename would have to be keyed on values it does not yet have.

The load-store queue is the structure that handles this. It holds every in-flight memory operation from dispatch to retirement, and it enforces program-order memory semantics through a pair of content-addressable searches. When a load executes, it searches the store queue for an older store to the same address and takes that store’s data directly if it finds one. When a store retires, it searches the load queue for a younger load to the same address that already executed, and flushes the pipeline if it finds one. The combination lets memory operations issue out of order while the architectural state still looks like in-order execution.

This chapter develops the load-store queue from first principles. It opens with the basic problem of why memory ordering is harder than register ordering, walks through store queue organization and store-to-load forwarding, develops the load queue and the memory-ordering-violation check, covers the partial-forwarding stall and its cost, treats memory dependence prediction with the store-set predictor as the canonical example, and closes with the microarchitectural cost of the LSQ in modern x86-64 and AArch64 implementations.

01.Why Memory Ordering Is Harder Than Register Ordering

The register renamer in Chapter 51 works because every architectural register is named statically by a small encoded field in the instruction. The renamer reads the field, allocates a fresh physical register, updates the map table, and is done. Two writes to the same architectural register from two in-flight instructions land in distinct physical registers, and any subsequent reader of that architectural register reads the correct physical one by consulting the map table at the moment of its own dispatch.

Memory does not work that way. A store writes to a byte address that has to be computed from a register plus an immediate offset, and the register value is not known until execute. Consider the sequence:

Two memory accesses with hidden dependence

At dispatch, the renamer sees that the store reads architectural registers x10 and x5, and the load reads x6 and writes x11. From a register standpoint the two instructions are independent. They share no architectural register, and renaming gives them disjoint physical destinations. A naive out-of-order engine would dispatch them to separate execution lanes and let them race.

The catch is that nothing tells the renamer whether x5 and x6 hold the same value. If x5 and x6 both compute to address 0x1000 at execute time, the load must read the value that the store wrote. If they compute to different addresses, the load may execute before the store with no ordering penalty. The renamer cannot tell which case applies. It does not have the address arithmetic.

This is the fundamental asymmetry. Registers carry their identity in the instruction encoding, so the renamer can resolve every dependence at dispatch. Memory carries its identity in a value that does not exist until execute. The hardware must therefore reserve a structure that lives past dispatch and lets a memory operation resolve its dependences when its address arrives. The load-store queue is that structure.

A second asymmetry compounds the first. A store, once committed to architectural memory, is hard to undo. A register write is easy to undo because the old physical register is still in the free list and the map table still has the old mapping. A memory write is hard to undo because the old value sat in DRAM (or in a shared cache line in another core), and once it is overwritten the old value is gone. The LSQ resolves this by holding every store back from the cache until its retirement is certain. The store sits in the store queue with its address, its data, and its program-order position. Only when the retirement pointer reaches that position does the store drain to the L1 data cache.

The load queue solves a related problem in reverse. A load reads memory, and the read happens once. If a later store turns out to have been older in program order than the load, the load already saw the wrong data. The load queue records every in-flight load so that a retiring store can search backward and check whether any younger load executed early and read the pre-store value. If one did, the load (and everything younger than it) must be flushed and re-executed.

02.The Store Queue

The store queue holds every in-flight store from dispatch until retirement. Each entry carries the store’s effective address (when known), the store’s data (when known), the store’s age tag (a sequence number that orders it against other in-flight stores), and a pair of valid bits for the address and data. A store dispatches into an unoccupied entry, and that entry stays bound to the store until the store retires.

A concrete numerical example sets the scale. Intel’s Sunny Cove core, used in Ice Lake, carries a 72-entry store queue. AMD’s Zen 4 core has a 64-entry store queue. ARM’s Neoverse V2 carries about 80 entries. The store queue is one of the larger structures in the core because every store that has been dispatched but not retired occupies a slot, and on a wide out-of-order machine with a deep reorder buffer that population can be substantial.

Allocation happens at dispatch. The dispatch unit reserves an entry in the store queue alongside the entry it reserves in the reorder buffer. The entry is tagged with the store’s ROB index, which is the store’s program-order position. If no entry is free, dispatch stalls. This back-pressure is one of the structural limits a wide core has to balance against the reorder-buffer size and the issue-queue size that Chapter 53 developed.

Address generation happens when the store’s base-register operand becomes available. The store address agen unit reads the register, adds the immediate, and writes the resulting effective address into the store queue entry along with the address-valid bit. Data generation can happen later (or earlier) because the store data is a separate register read. Many ISAs encode store address and store data as a single instruction, but the microarchitecture splits them into two micro-ops with separate scheduling: a store-address micro-op and a store-data micro-op. The two micro-ops can issue out of order with respect to each other, and the store queue entry accumulates whichever arrives first.

Retirement happens when the store reaches the head of the reorder buffer with no preceding exceptions. At that point the store is architecturally certain to happen, and the store queue forwards the address and data to the L1 data cache write port. The store queue entry is released, the L1 cache writes the data into the appropriate line (allocating on a miss for a write-allocate policy or going through a write-combining buffer for some weakly-ordered configurations), and the program-visible architectural state moves forward by one store.

03.Store-to-Load Forwarding

When a load executes, it has to read either the cache or an in-flight older store. If an older store sits in the store queue with the same address and is older in program order, the load must take that store’s data. If no such store exists, the load goes to the L1 cache. The choice happens by searching the store queue.

The search is a content-addressable lookup keyed on the load’s effective address. Every store queue entry compares its address field against the load’s address in parallel. The entries that match raise their match line. The age comparator then picks the youngest matching store that is still older than the load, because that is the store whose value the load should see. The load takes the data from that entry and writes it into its destination physical register.

A worked example clarifies the timing. Assume a store dispatches at cycle 10 and gets its address (0x1000) at cycle 13, but its data (0x42) does not arrive until cycle 16. A load dispatches at cycle 12, gets its address (0x1000) at cycle 14, and is ready to execute at cycle 15. The load searches the store queue at cycle 15. It finds the older store with address 0x1000, but the store’s data is not yet valid (the data-valid bit is 0). The load cannot forward. The load options are to stall in the load buffer waiting for the store data to arrive, or to replay the load when the store data is later written. Most designs stall.

If instead the load arrived at cycle 17, after the store data was written at cycle 16, the search would find the matching store with both valid bits set. The data forwards directly from the store queue entry to the load’s destination register, and the load completes in one cycle without going to the cache at all.

The CAM (content-addressable memory) cost is the main constraint on store queue size. Each store queue entry’s address field must be compared against every executing load’s address every cycle. A 64-entry store queue with a 48-bit address comparator and two load ports is 64 entries times 48 bits times 2 ports, which is a substantial number of comparators clocked at the core frequency. Power and area scale roughly linearly with the entry count and with the number of issue ports.

Designers split the search to manage the cost. The full 48-bit comparison is expensive. A common shortcut is to compare only the low-order bits of the address (perhaps the low 12 or 16 bits) in the fast CAM, and then verify the high-order bits with a slower arithmetic comparator after the candidate match is identified. A false positive at the low-order CAM (two addresses with the same low bits but different high bits) is handled by the slow check. A false negative is forbidden, which is why the low-order CAM must be precise within its bit range.

04.Partial Forwarding and the Forwarding Stall

A complication arises when the load and the older store overlap in address but not exactly. The load wants 8 bytes starting at address 0x1004. The store wrote 4 bytes starting at address 0x1000. The store covers bytes 0x1000 through 0x1003, and the load wants bytes 0x1004 through 0x100B. The two ranges do not overlap. The store does not forward, and the load goes to the cache cleanly.

The harder case is a partial overlap. The load wants 8 bytes starting at 0x1000. The store wrote 4 bytes starting at 0x1000. The store covers bytes 0x1000 through 0x1003, and the load wants bytes 0x1000 through 0x1007. The first 4 bytes the load wants are in the store queue. The last 4 bytes are in the cache, possibly stale relative to even older stores.

A microarchitecture could in principle synthesize the load’s data by combining the store’s 4 bytes with the cache’s 4 bytes. Most do not. The combination is fast in theory but messy in implementation, because the cache read and the store-queue read are on different timing paths and the merge requires byte-level steering that the load pipeline does not provide. Instead, designs detect the partial overlap and stall the load until the older store retires. Once the store retires it drains to the cache, and the load can re-execute with a clean cache read.

This is the partial-forwarding stall, and its cost is one of the larger pitfalls in performance analysis. A single partial-forwarding stall can cost 10 to 20 cycles because the load has to wait for the store’s retirement plus the cache fill. Repeated partial-forwarding stalls compound. They appear in code patterns where a narrow store (4 bytes) is followed by a wider load (8 bytes) that spans past the store’s bytes, or where two adjacent stores of different sizes are followed by a load that spans them. The compiler can mitigate by aligning data, by using the same width for producer and consumer, or by introducing a register pass-through where the store’s source register is reused directly.

A second complication is the size mismatch in the other direction. The store wrote 8 bytes at 0x1000. The load wants 4 bytes at 0x1002. The load’s range is fully contained in the store’s range, and the data is in the store queue. This case can forward, because the store queue entry holds all 8 bytes and the load can shift and mask to extract its 4. Most designs handle this case in the forwarding path with a shifter on the store data, but some restrict forwarding to exact-address-and-size matches and stall the load otherwise. The Intel optimization guides document which patterns forward and which stall on each microarchitecture generation, and the AMD software optimization guide does the same.

05.The Load Queue and Memory Ordering Violations

The store queue handles the case where a load needs data from an older in-flight store. The reverse case is also possible. A load executes early, gets its data from the cache, and writes its destination register. Some cycles later, an older store (older in program order, but slower to compute its address) finally materializes and turns out to write the same address. The load read the wrong value.

The load queue catches this. Every load that executes records its effective address, its ROB index, and the data it read into a load queue entry. The entry stays bound to the load until the load retires. When a store reaches the head of the store queue and retires (or when it has its address ready, depending on the design point), the store searches the load queue for any younger load to the same address.

If the search finds a match, the load got its data before the store landed. The cache value the load read was the pre-store value, but program order says the load should have read the post-store value. The pipeline has a memory ordering violation. The recovery is the same as a branch misprediction. The hardware flushes the load and every younger instruction in the ROB, restores the renamer and free list, and refetches from the load’s address. The flush is expensive (10 to 30 cycles depending on the depth of the pipeline) and frequent enough that designers spend significant effort predicting and preventing it.

The load queue search is symmetric to the store queue search. It is also a content-addressable lookup, keyed on the store’s address on the store side and on the load’s address on the load side. The load queue’s CAM is sized to match the load population (typically larger than the store population, because loads outnumber stores in most code).

Sizing is again a balance. A larger load queue lets more loads be in flight at once, which is good for memory-level parallelism, but the CAM cost grows. Modern x86-64 cores carry 128 to 192 load queue entries (Sunny Cove has 128, Golden Cove has 192, Zen 4 has 144), which dominate the store queue in size. ARM Neoverse V2 carries about 100 to 120 load queue entries depending on the configuration.

06.Memory Dependence Prediction

The naive form of speculative memory disambiguation, letting every load issue as soon as its address is ready and relying on the load queue check to catch the mistakes, exposes the core to frequent memory ordering violations. The naive opposite policy of waiting until every older store’s address is known before issuing a load is correct but slow. A load that follows a chain of 20 stores would wait until all 20 store addresses had computed before issuing, even if the load aliases with none of them. Most loads do not alias with any in-flight store, and forcing them to wait sacrifices substantial memory-level parallelism.

Memory dependence prediction threads the needle. At dispatch, the predictor guesses whether a load is likely to alias with an older in-flight store. If the prediction is "independent," the load issues as soon as its own address is available, ignoring the older stores. If the prediction is "dependent," the load waits for the older store (specifically, the store the predictor identifies as the likely conflict) before issuing.

Predictions are checked at retirement. If a predicted-independent load gets caught by a memory ordering violation, the predictor records the offending store-load pair and learns to wait next time. If a predicted-dependent load reaches retirement with no actual conflict, the predictor can relax (after some hysteresis) and allow the load to issue earlier next time.

The Store-Set Predictor

The canonical memory dependence predictor is the store-set predictor introduced by Chrysos and Emer at ISCA 1998 [3]. It tracks, for each load, the set of stores that have aliased with that load in past executions. When the load dispatches, it checks whether any older in-flight store is in its store set. If yes, the load waits for that store. If no, the load issues independent.

The structure of the store-set predictor is two tables. The first table is the load PC table, indexed by the load’s program counter, which maps each load to a store-set identifier (SSID). The second is the store PC table, indexed by the store’s program counter, which also maps each store to an SSID. Two instructions share an SSID if and only if they belong to the same store set, meaning they have aliased with each other in the past.

Updates happen on memory ordering violations and on a periodic clearing. When a violation fires, the predictor merges the load’s current SSID with the offending store’s current SSID. If both already have SSIDs, the smaller-numbered SSID wins (a simple deterministic tie-break). If only one has an SSID, the other inherits it. If neither has an SSID, a fresh SSID is allocated. The merge causes both instructions to share their store set going forward.

The clearing is a periodic flush that resets all entries to "no SSID" every $N$ cycles or every $N$ retired instructions. This prevents stale aliases from accumulating after a phase change in the program. Without clearing, a load that aliased once 100,000 cycles ago would forever wait for stores that no longer matter.

Confidence and Hysteresis

A simple two-state predictor (alias yes / alias no) is brittle. A single misprediction in either direction toggles the prediction. Real designs add hysteresis with confidence counters. A two-bit saturating counter per load PC, incremented on alias and decremented on no-alias, gives the predictor a few cycles of inertia before it changes its mind. The Intel and AMD predictors in current cores carry confidence counters of two to three bits, according to the disclosed information in optimization guides.

Modern Designs

Production processors mostly implement variants of the store-set predictor. The Intel Sunny Cove and later cores use a more refined predictor that combines store-set tracking with a separate alias predictor for specific store-load patterns. AMD Zen and later use a similar approach. The ARM Neoverse series carries a memory dependence predictor whose details are not fully disclosed but which appears to follow the same overall structure based on performance counter behavior.

07.Memory Models and the LSQ

The LSQ is the place where the architecture’s memory consistency model meets the microarchitecture. A strong memory model like x86’s Total Store Order (TSO) requires that loads from one core see stores from other cores in the program order in which the other cores issued them, with one exception (a load can pass an older store on the same core if the addresses differ). A weak model like ARM AArch64’s allows more aggressive reordering, with explicit barriers (DMB, DSB, ISB) to enforce ordering where needed.

The LSQ implementation differs between the two. An x86-64 LSQ has to ensure that store-to-load forwarding never lets a load from core 0 see a store from core 1 out of order. The load queue is checked against incoming snoops and invalidations from other cores, and a snoop that hits a load queue entry whose load has already executed fires a memory ordering violation on the core receiving the snoop, because that load read a value another core has since overwritten. An AArch64 LSQ has more flexibility because the architecture permits more reordering, but barrier instructions must drain the LSQ to make the ordering visible.

The chapter has covered the LSQ’s core mechanics within a single core. The full memory model treatment, including cross-core snooping, write-back caches with the MOESI protocol, and the ordering rules for atomic operations, is the subject of Part VI’s multicore and coherence chapters. The LSQ’s behavior at those interfaces is the same content-addressable lookup with extra inputs from the coherence protocol and from barrier instructions.

08.Worked Examples

09.Exercises

References

1. [1](2024). “Intel.”
2. [2](2024). “AMD64.”
3. [3]Chrysos, George Z. and Emer, Joel S. (1998). “Memory Dependence Prediction Using Store Sets.” In Proceedings of the 25th Annual International Symposium on Computer Architecture (ISCA), pp. 142--153. doi:10.1145/279358.279378