Compiler techniques for thread-level speculation

Thread-Level Speculation (TLS) allows potentially dependent threads to execute in parallel, by postponing the detection and verification of inter-thread data dependences until runtime. Although TLS greatly simplifies automatic parallelization, only moderate performance improvements have been achieved for general-purpose applications. Thus adequate compiler techniques must be developed to fully utilize the underlying TLS support. In this thesis, we address the key compiler issues involved in the speculative parallelization and propose several optimization techniques to improve the performance of general-purpose applications under TLS.; One important task of a TLS compiler is to identify speculative threads with good performance potentials. We propose a loop selection algorithm that determines which loops to parallelize to maximize the program performance. For applications with limited loop-level parallelism, a partitioning algorithm is proposed to extract threads from sequential codes.; To further enhance the performance of parallel threads, we propose three compiler optimizations: instruction scheduling, reduction transformation and iteration merging. Instruction scheduling improves the efficiency of synchronizing frequently occurring memory dependences; reduction transformation reduces the impact of a class of reduction variables whose intermediate results are used by non-reduction operations; iteration merging improves the load balancing by dynamically combining loop iterations to achieve more balanced workloads.; All the proposed techniques are implemented in a TLS compiler framework built on the Intel's Open Research Compiler (ORC). We achieve an average program speedup of 1.38 for the SPEC2000 benchmarks. Our experimental results show that, in the context of TLS, adequate compiler support is crucial in delivering the desirable performance for general-purpose applications, and our proposed techniques are effective in exploiting speculative parallelism.