What is Memory Dependence Prediction?

Modern CPUs are incredibly complex devices. They use many very clever tricks to eke out as much performance as possible. One of those tricks is memory dependence prediction. This is simply the process of predicting if a specific memory access is dependent on any other memory access. This is only necessary because of another performance trick called Out Of Order execution.

What is OOO?

An OOO CPU can look at a buffer of decoded instructions and choose to reorder them to improve efficiency. The main purpose of this is to delay instructions that need data that isn’t available yet. If that data is stored in RAM, then it might be a few hundred clock cycles before that data is available. An out of order processor can keep itself busy in the meantime, performing instructions that are ready to go.

OOO can provide a significant speed-up, simply by being able to delay instructions that aren’t ready. Other performance benefits can also be felt such as prioritising branching instructions. A branch instruction can result in the branch being taken or not taken. The result determines what code needs to be run next. In code, an “IF” statement is one implementation of a branch. Branch prediction is another trick that assumes that the branch is or isn’t taken and speculatively executes the predicted result too. If the prediction is later shown to be wrong, some work needs to be scrapped, but if it’s right a bunch of work may already be complete. By executing the actual branch instruction as early as possible you find out as soon as possible which path should be taken, minimising the effect of an incorrect prediction.

If you just implement these features as is, one of the first things you will run into is a bunch of memory errors. The problem is that while many things can be reordered, some instructions are dependent on other instructions. For example, if you read data from a variable before an instruction that was supposed to write data to that variable, you end up reading the wrong value. This is the sort of problem that memory dependence prediction aims to fix.

Predicting dependencies

If some memory operations getting reordered cause issues then there are a few things you could do to fix it. The most extreme example is to not reorder any memory operations, at least in relation to other memory operations. This can lead to potentially lost performance optimisation. In some cases, the lost optimisation can actually be so significant that more performance could be gained by reordering all memory accesses and then handling any memory issues that result.

The other solution is to try to predict which memory operations are dependent on other memory operations to avoid reordering those while reordering the memory accesses that are safe to do so. This involves tracking and analysing memory accesses and determining which ones interact with memory that still has pending operations.

Conclusion

Memory dependency prediction is a function whereby a CPU predicts which memory operations are dependent on any other, as yet unexecuted memory operation. Specifically, it allows memory operations without dependencies to be reordered to increase performance. It does this while tying the execution of memory operations with dependencies to the execution of their dependencies. This enables the performance gain from out of order execution. At the same time, it negates the risk of memory issues or performance loss resulting from ignoring memory dependencies. The techniques needed to perform this accurately have been known since the late 1990s.