Data-dependence profiling to enable safe thread level speculation
Arnamoy Bhattacharyya, José Nelson Amaral, Hal Finkel · Computer Science and Software Engineering · 2015
Data-dependence profiling is a technique that enables a compiler to judiciously decide when the execution of a loop --- which the compiler could not prove to be dependence free --- should be speculated through the use of Thread Level Speculation (TLS). The data collected by a data-dependence profiler can be used to predict if may dependencies reported by a compiler static analysis are likely to materialize at runtime. A cost analysis can then be used to decide that some loops with a lower probability of dependence should be speculatively parallelized. This paper addresses the question as to whether a loops' dependence behaviour changes when the input to the program changes --- a study of 57 different benchmarks indicates that it usually does not change. Then the paper describes SpecEval, an automatic speculative parallelization framework that uses single-input data-dependence profiles to find speculation candidates in the SPEC2006 and PolyBench/C benchmarks. This paper also presents a performance evaluation of TLS implementation in IBM's Blue-Gene/Q supercomputer and shows that the performance of TLS is affected by several factors, including the number of speculated loops, the execution-time coverage of speculated loops, the miss-speculation overhead, the L1 cache miss rate and the effect on dynamic instruction path length.