15.5 Load-Store Handling in Out-of-Order Execution

Lecture from: 26.04.2023 | Video: YT

This lecture served as a continuation of the discussion on Out-of-Order (OoO) Execution from Lecture 15, specifically addressing the significant complexities introduced by memory operations (loads and stores) in such processors.

The lecture focused on understanding why handling memory operations out of their original program order is substantially more challenging than handling register operations, and explored the hardware mechanisms employed to manage these complexities while maintaining correctness and performance.

Registers Versus Memory: Fundamental Differences in OoO Context

To understand the challenges of memory handling in OoO execution, it is essential to recognize the fundamental differences between registers and memory from the perspective of a processor’s microarchitecture:

1. Dependency Information: For register operations, dependencies (which instruction produces a value needed by another instruction) are typically known statically at the decode stage by examining the register IDs specified in the instruction. This allows for straightforward register renaming and dependency tracking. For memory operations (loads and stores), however, the actual memory address being accessed is often not known until the instruction executes and computes the address (e.g., using base register + offset).
2. State Size: The register state is relatively small and managed by a dedicated, fast structure (the register file or physical register file). The memory state, accessed via addresses, is vast and managed hierarchically (caches, main memory). This sheer scale and the multi-level access latency of memory introduce complexities not present with registers.
3. Sharing: While architectural registers are typically private to a thread or context, memory in shared-memory multiprocessors is shared between multiple threads and processors. This raises cache coherence issues and further complications that must be managed, although these specific issues were noted as beyond the scope of this particular discussion.

The first two differences, the dynamic nature of address determination and the vast size of the memory state, are the primary sources of complexity for handling loads and stores in an Out-of-Order execution engine.

Memory Dependence Handling: The Unknown Address Problem

In an Out-of-Order processor, instructions execute and complete based on operand readiness, not program order. This means a load or store instruction that appears later in the program sequence might attempt to execute before an earlier load or store. To maintain program correctness, the processor must still ensure that memory dependencies are obeyed – specifically, a load must receive the correct data, which might be the value written by the most recent preceding store to the same location.

The critical problem is that the memory address for a load or store is typically not known until the instruction progresses through the execution stage.

Problem: A later load instruction might be ready to execute and compute its address, but an earlier store instruction (older in program order) whose address is not yet known is still in flight in the pipeline. If this older store’s address, when finally computed, matches the load’s address, the load should have received its data from that store, not from memory.

This challenge is known as the memory disambiguation problem or the unknown address problem. Determining whether a load and a store access the same memory location cannot always be done early in the pipeline because the addresses are not ready.

This leads to several corollaries:

• Renaming memory addresses, unlike registers, is difficult because addresses are dynamic properties, not static identifiers known at decode.
• Checking for dependencies or independence between memory operations must often be done after the instructions have partially executed (i.e., after address generation).
• When a load or store generates its address, there might be older or younger memory operations in the pipeline with addresses that are still unknown, making definitive dependency checks impossible at that moment.

Approaches to Memory Disambiguation

Given the unknown address problem, processors employ different strategies when a load instruction reaches the point where it could be scheduled to access memory:

1. Conservative Approach: Stall the load until all previous stores in program order have completed execution and their addresses are known. In an extreme form, the load might even wait until all previous stores have retired and updated memory. This approach is simple in terms of logic but severely limits performance by sacrificing parallelism, as independent loads are unnecessarily delayed by older, unrelated stores.
2. Aggressive Approach: Assume the load is independent of all previous stores whose addresses are unknown. Schedule the load immediately to access memory. This strategy favors performance in the common case (most loads are independent of prior unknown-address stores) but requires complex hardware to detect mispredictions later. If an older store’s address later becomes known and conflicts with the load’s address, the processor must recover (e.g., flush the load and all subsequent instructions that depended on its incorrect result) and re-execute the load.
3. Intelligent Approach: Predict whether the load is likely to be dependent on an older store with an unknown address using sophisticated prediction mechanisms. Schedule the load based on this prediction. This aims to achieve better accuracy than simply assuming independence but still requires recovery on mispredictions. Memory dependence predictors can learn from past load/store access patterns.

Empirical studies have shown that predicting store-load dependencies can significantly improve performance compared to strictly conservative or aggressive approaches, although it adds hardware complexity.

Hardware for Out-of-Order Memory Handling: Load and Store Queues

To manage memory operations and their dependencies in an OoO processor, specialized hardware structures are used, most notably the Load Queue (LQ) and the Store Queue (SQ). These structures buffer load and store instructions after they are decoded and renamed, and play a crucial role in scheduling and ensuring correct data transfer.

When a load instruction is ready to proceed past address generation, it enters the LQ. When a store instruction generates its address and data, it enters the SQ. These queues (or sometimes a combined structure like a Memory Ordering Buffer) maintain memory instructions in program order.

A critical function is store-to-load forwarding. When a load computes its address, it must check if any older store in the SQ (or Reorder Buffer, if integrated) is targeting the same or an overlapping memory location. If such a store exists and its data is available, the load must bypass memory and receive the data directly from the store’s entry in the SQ. This is a complex search logic within the SQ.

The load’s address must be compared against the addresses of all older stores in the SQ. This comparison involves not just the base address but also the size of the memory access, requiring range comparisons. Furthermore, if multiple older stores access the same location, the load must receive the data from the youngest (closest in program order) preceding store. This requires an age-based search or prioritization logic.

The hardware for this search is complex, essentially implementing a Content Addressable Memory search based on address, but also needing to consider the size and age of the memory operations.

Load data can therefore come from several places: a direct read from the cache/memory (if no older store in the SQ is pending to the same location), or forwarded from one or more entries in the SQ (if older stores are pending to the location, considering ranges and age).

Store instructions themselves update memory only when they retire in program order from the Reorder Buffer (and SQ). This ensures that memory is updated sequentially, preserving precise state.

Continue here: 16 Superscalar Execution & Branch Prediction