Using Program Slicing to Drive Pre-Execution on Simultaneous Multithreading Processors

Pre-execution uses helper threads running in spare hardware contexts to trigger cache misses in front of the main thread, hence hiding their latency. At the heart of pre-execution is the code that runs in the pre-execution threads themselves. The most common approach is for preexecution threads to run a subset of the instructions executed by the original program, called backward slices [18], which are extracted from the main thread at the instruction level. This paper proposes a new pre-execution technique that uses program slicing [2] to extract the code for pre-execution threads. Program slicing performs static analysis on the program source to create slices consisting of source code rather than binary code. Compared to previous techniques, our approach requires less hardware, and is more natural to automate in a compiler. To study the feasibility of our approach, we built a slicing system based on a publicly available program slicer, called Unravel, that constructs program slices for pre-execution. We also developed several program slice parallelization techniques that partition our program slices onto multiple pre-execution threads. Our techniques enable pre-execution threads to effectively get ahead of the main thread by exploiting thread-level parallelism. Finally, our work provides an evaluation of program slice driven pre-execution using a detailed simulator of a simultaneous multithreading (SMT) processor. Our techniques achieve a 27.4 % speedup across 7 integer applications on an 8-way SMT with 4 contexts, and a 56.7 % speedup on an SMT with 9 contexts.