Load/Store Queues and Memory Disambiguation

Registers are easy to reorder because their names are known at decode. Memory is not: a load cannot know whether it depends on an earlier store until both addresses have been computed, and a store cannot be undone once it reaches memory. Load and store queues are the structures that let an out-of-order processor run memory instructions early and still behave as if they ran in order. This article explains store queues, store-to-load forwarding, memory disambiguation, memory-order violations and how processors predict dependences.

11 min read | Intermediate

What You'll Learn

• Explain why stores must wait for commit
• Describe store-to-load forwarding and when it can fail
• Explain memory disambiguation and how a violation is detected
• Describe how memory dependence prediction works

Why Memory Is Hard

Out-of-Order Execution and Register Renaming showed how register dependences are found early, since the register numbers are in the instruction. A load's address comes from a register, and is known only when the address is computed. Look at this:

sw  a0,0(a1)      # store to the address in a1
lw  a2,0(a3)      # load from the address in a3

If a1 and a3 are equal, the load must return the stored value. If they are different, the two have nothing to do with each other, and the load can run at once. Until both addresses are known, nobody can tell.

Waiting would be safe but slow. Loads are often the start of a chain of dependent work, and an early load unblocks everything behind it. So the processor would very much like to run loads early, as soon as it can.

Stores have a further problem. A register write goes to a physical register, and it can be dropped if the instruction turns out to be on a wrong path. A write to memory cannot be taken back: other cores or devices might see it. So a store must not change the cache until it is certain to commit.

The Store Queue

When a store executes, it computes its address and reads its data, then writes both to an entry in the store queue (SQ), also called the store buffer. Nothing touches memory yet. Entries are kept in program order. When the store reaches the head of the reorder buffer and commits, it is marked as safe, and afterwards it writes to the cache, in order, when the cache is free. If the store was on a wrong path, its entry is simply thrown away.

Because a store only has to wait in a queue, a store miss in the cache doesn't stall the pipeline: the store sits in the queue until its line arrives. Only a full queue stops the core.

Store-to-Load Forwarding

A problem appears at once. A load may need data from a store that is still in the queue. Memory holds an old value, so reading the cache would be wrong. So each load searches the store queue for the youngest older store to the same address, and if it finds one, takes the data straight from there:

This is store-to-load forwarding. It is common, because compilers often store a value to the stack and soon load it back. The search must find the youngest older match, and it compares addresses in every entry, in one cycle, so the store queue is one of the more timing-critical parts of the core, and that limits its size.

Forwarding can get complicated. The store and the load may not match exactly. A byte store followed by a word load that includes that byte needs data from two places. Most designs handle only the simple cases by forwarding, and in the hard cases the load simply waits until the store has reached the cache, at a cost of many cycles. This is why performance guides warn against writing a value in small pieces and reading it back as one large value.

Memory Disambiguation

Forwarding assumes the load knows the addresses of all earlier stores. In an out-of-order core, some of those stores may not have computed their address yet. The store marked "unknown" in the picture is one. May a load go ahead of a store with an unknown address?

Finding out whether two memory instructions touch the same address is called memory disambiguation. There are two approaches:

• Conservative: a load waits until all earlier store addresses are known. This is always safe, but it loses much of the gain.
• Speculative: a load goes ahead on the bet that it doesn't depend on any unknown store. Studies of real programs show this bet is nearly always right, because only a small share of loads depend on a store that is in flight.

All large cores speculate. That means they must detect the rare case in which the bet was wrong.

Catching a Violation

The load queue (LQ) keeps a record of each load in flight, with its address, in program order. When a store computes its address, it searches the load queue for any younger load to the same address that has already run. If one exists, that load read old data, which is a memory-order violation. The processor flushes the load and everything after it, and restarts from there, just as for a branch misprediction.

The bet is safe because no wrong value can become visible before commit. It is only expensive when it fails.

Predicting Dependences

Since a violation costs many cycles, it is worth not repeating it. A load at one particular address in the code tends to depend on the same store each time, for example when a function saves a register and later reloads it. So the processor keeps a small table indexed by the load's PC. If a load caused a violation, the table remembers, and next time it waits for the earlier store instead. This memory dependence predictor gives most of the gain of speculation and few of the violations. Designs vary from a single "wait" bit per load to tables that link particular loads to particular stores. Good ones remove most violations, and cost little storage.

A Full Walk

Putting it together, here is the life of a load in a large core:

1. At rename, it gets an entry in the load queue and the ROB.
2. When its base register is ready, it computes the address, and translates it in the TLB.
3. It searches the store queue. A match forwards the data. A partial match waits.
4. With no match, it reads the L1 cache at the same time. On a miss, an entry is made to fetch the line, and the load waits.
5. It delivers the value to waiting instructions, usually assuming a hit.
6. It stays in the load queue until it commits, watching for later-found stores that conflict with it.

Step 5 hides a further speculation. Instructions that depend on a load are woken up on the assumption that it will hit the cache, so that they can run right away. If the load misses after all, those instructions must be replayed.

Consistency: What Other Cores See

A store queue changes what other processors can observe. A core's own loads see its stores through forwarding, but other cores see them only when they reach the cache. So a core's store may become visible to others later than its next load. On a single core this can't be noticed, because it sees its own data. With many cores it can, and rules are needed about which orders are allowed. Those rules are the memory consistency model, the subject of Memory Consistency, Atomics and Fences.

Loads have a matching concern. If a core runs two loads out of order, and another core stores between them, the result may break the model's rules. So strongly ordered processors such as x86 also snoop their load queues for writes by other cores, and replay any load that ran too early. RISC-V's default model, RVWMO, is more relaxed, which gives hardware more freedom.

Small Cores Have These Too

Even an in-order core benefits from a store buffer. A write to the cache may take longer than a read, or the line may be missing, and the pipeline doesn't want to wait, so stores go into a short queue and the core moves on. As soon as this exists, loads must check it, as in Replacement and Write Policies. The principle is the same at a small scale.

Getting all of this right takes a great deal of verification, because the bugs appear only with unusual orders of stores and loads. Random tests with heavy memory traffic are the standard way to find them, as Verifying a CPU explains.

Common Mistakes