Compiler driver memory system optimization using speculative execution

Abstract

Wide-issue microprocessors are capable of remarkable execution rates, but they generally achieve only a fraction of their peak instruction throughput on real programs. This discrepancy is due to performance degrading events, largely branch mispredictions and cache misses. In this work we have addressed the performance degradation due to the latter through the use of Program Embedded Precomputation using Speculative Execution (PEPSE). Towards this, we introduce the Load Dependence Graph (LDG), which is a sub-graph of the traditional Program Dependence Graph(PDG) that computes the address of a load instruction.In the context of data prefetching, we illustrate how PEPSE can accurately predict and effectively prefetch future memory references with negligible overhead for both regular array-based applications as well as irregular pointer-based applications. We use profiling to identify delinquent loads. LDGs are created only for those loads. Subsequently, speculative versions of the LDG operations are statically scheduled along with a prefetch instruction for the computed address, such that these instructions execute and prefetch the value before the actual load is encountered resulting in either an elimination or reduction of the processor stall cycles due to the load instruction. Our prototype implementation of the optimizations within the Open Research Compiler (ORC) delivered encouraging results. For a 900 MHz Itanium 2 server, we could achieve speedups ranging from 1.05 to 2.14 for several benchmarks from SPEC and OLDEN suites.