Lecture 15c: Load-Store Handling in Out-of-Order Execution

What this lecture covers

This lecture explains why handling memory instructions is the hardest part of building an out-of-order execution engine, harder than the register renaming covered in earlier lectures. It answers a specific question: since a load or store's address isn't known until the instruction partially executes, how can hardware still schedule loads early and give them the correct value when an earlier store might write to the same address?

The lecture builds on the reorder buffer and register renaming material from prior lectures in this course. After watching, you should understand why memory dependences can't be resolved at decode time the way register dependences can, the three broad strategies for scheduling loads relative to unknown stores, and how the store queue's content-addressable search works to forward data from a store directly to a dependent load.

Key ideas

• Memory disambiguation problem: determining whether a load depends on an earlier store (with an unknown address) requires comparing addresses that aren't available until execution.
• Conservative approach: stall every load until all older stores have computed their addresses (or retired); correct but slow.
• Aggressive approach: schedule loads immediately, assuming independence from prior stores, then check and recover (flush) if wrong.
• Intelligent approach: predict load-store dependence based on past behavior, since the same dependence tends to repeat across loop iterations.
• Store queue (store buffer): an in-order, hardware list of in-flight stores holding address, data, and validity bits, searched by later loads.
• Store-to-load forwarding: when a load's address matches a valid store address, the load gets its value directly from that store instead of from memory.
• Content-addressable search: the store queue search must match on address range and size, not just an exact address, because loads and stores can partially overlap.

Walkthrough

Why memory is harder than registers (0:03)

The lecture opens by contrasting registers and memory as sources of complexity in out-of-order machines. Register dependences are known statically, right after decode, so renaming can happen early and in order. Memory addresses are only known after an instruction partially executes, addresses are far larger than register identifiers, and in multiprocessors memory is shared across threads in a way registers are not.

The unknown-address problem (3:03)

Using a store followed by a load example, the lecture shows that if the store is stalled waiting on its source registers, its address is unknown when a younger, ready load wants to execute. The hardware cannot tell whether the load depends on that store, yet still wants high performance, which is the core tension the rest of the lecture addresses.

Conservative, aggressive, and predicted scheduling (7:07)

Three strategies are compared: stalling a load until all older stores resolve (conservative, low performance), scheduling loads immediately and recovering on misprediction (aggressive), and predicting dependence based on history (intelligent, used in real machines). A chart of instructions-per-cycle across benchmarks shows the conservative approach performing far worse than the aggressive one, with a large remaining gap to a perfect predictor, which is why simple prediction schemes capture most of the available performance.

Store-to-load forwarding and the load/store queues (14:11)

Even assuming all store addresses were known, the machine still needs a mechanism to check whether a load depends on a store and to forward that store's data to the load. This is handled by dedicated structures, typically a store queue and a load queue (combined into a single "memory ordering buffer" in the Pentium Pro), each entry tracking address, data, and separate validity bits for address and data.

The store-to-load forwarding search logic (17:15)

A load searches the store queue with a wide comparator against every in-flight store's address. Because a load can read bytes written by several different stores, the search must match by address range and size, not equality alone, and must select the youngest matching store for each byte. If no store covers a byte, the load must still access memory for it.

Before you watch

• Be comfortable with the reorder buffer and register renaming, covered in the preceding out-of-order execution lectures.
• Recall what content-addressable memory structures do, introduced in the previous lecture on scheduling logic.

Check your understanding

1. Why can't memory addresses be renamed at decode time the way register operands can?
2. What is the tradeoff between the conservative and aggressive approaches to scheduling loads relative to unknown stores?
3. Why does a store-to-load forwarding search need to compare address ranges and sizes rather than just checking for an exact address match?
4. Why do real processors keep the store buffer much smaller than the instruction window?