Memory dependence prediction

Memory dependence prediction is a technique, employed by high-performance out-of-order execution microprocessors that execute memory access operations (loads and stores) out of program order, to predict true dependences between loads and stores at instruction execution time. With the predicted dependence information, the processor can then decide to speculatively execute certain loads and stores out of order, while preventing other loads and stores from executing out-of-order (keeping them in-order). Later in the pipeline, memory disambiguation techniques are used to determine if the loads and stores were correctly executed and, if not, to recover.

By using the memory dependence predictor to keep dependent loads and stores in order, the processor avoids memory dependence violations and the pipeline flush that is required to recover from them. In this way, the processor gains the benefits of aggressive out-of-order load/store execution, but avoids much of the penalty that can arise when loads and stores were incorrectly executed. See the memory disambiguation article for more information on memory dependences, memory dependence violations, and recovery.

Analogy to branch prediction

Memory dependence prediction for loads and stores is analogous to branch prediction for conditional branch instructions. In branch prediction, the branch predictor predicts which way the branch will resolve before it is known. The processor can then speculatively fetch and execute instructions down one of the paths of the branch. Later, when the branch instruction executes, it can be determined if the branch instruction was correctly predicted. If not, this is a branch misprediction, and a pipeline flush is necessary to throw away instructions that were speculatively fetch and executed.

Mechanisms

• Store Set predictor (Chrysos & Emer 1998)

See also

• Memory disambiguation