A Study of Source-Level Compiler Algorithms for Pre-Execution · 51

Pre-execution is a promising latency tolerance technique that uses one or more helper threads running in spare hardware contexts ahead of the main computation to trigger long-latency mem-ory operations early, hence absorbing their latency on behalf of the main computation. This article investigates several source-to-source C compilers for extracting pre-execution thread code automatically, thus relieving the programmer or hardware from this onerous task. We present an aggressive profile-driven compiler that employs three powerful algorithms for code extraction. First, program slicing removes non-critical code for computing cache-missing memory references. Second, prefetch conversion replaces blocking memory references with non-blocking prefetch in-structions to minimize pre-execution thread stalls. Finally, speculative loop parallelization gener-ates thread-level parallelism to tolerate the latency of blocking loads. In addition, we present four “reduced ” compilers that employ less aggressive algorithms to simplify compiler implementation. Our reduced compilers rely on back-end code optimizations rather than program slicing to remove non-critical code, and use compile-time heuristics rather than profiling to approximate runtime information (e.g., cache-miss and loop-trip counts). We prototype our algorithms on the Stanford University Intermediate Format (SUIF) frame