Bypassing the Memory Wall: Breaking Memory Dependencies in a Superscalar CPU

Since the early 90s, almost every high-end microprocessor has been making use of out-of-order execution to exploit the instruction-level parallelism (ILP) a program exposes and execute the maximum number of operations at the same time. A big obstacle that hinders the performance of out-of-order machines is given by dependencies that intrinsically serialize the execution flow and nullify the advantages that come from parallelization. Many techniques have been developed in order to overcome these limitations: branch prediction is able to bypass control-flow dependencies and instruction scheduling does the same for data dependencies. However, memory dependencies are still an undergoing issue because they are associated with the “memory wall”: the memory subsystem, which is constantly becoming more and more a strong bottleneck in high-end microprocessors. The goal of this research is to investigate different techniques to bypass the aforementioned memory wall with the usage of two technique based on speculation: memory dependence prediction and memory renaming, implementing them as well in a timed CPU model to estimate the impact on CPU performance. We will demonstrate the difference between various memory dependence techniques, declaring the Store Set the most effective. However, we will see how a simpler predictor can achieve similar results with a substantially smaller size. Other than that, we will propose a memory renaming strategy based on an extension of the Store Set and we will shows how this technique has a low performance impact compared to the hardware implementation cost.