Compiler techniques for thread-level speculation

Dual-core, quad-core and many-core processors are replacing the traditional single-core processors. To take advantage of these multicore processors, traditional sequential applications need to be parallelised. However, the compiler often fails to find enough thread-level parallelism from sequential applications, especially from general-purpose applications with the extensive use of pointers, indirectly-indexed structures, or complex control flows. The major challenge lies in identifying dependences in sequentialapplications so that independent threads can be extracted from the applications.Thread-level speculation (TLS) is a promising solution to address this problem. It allows the compiler to extract parallel threads from a sequential application without having to prove that they are independent.This dissertation investigates the compiler techniques for TLS. We propose three compiler techniques on parallelising loops and recursive procedures: Loop Recreation Transformation (LRT), Thread-sensitive Modulo Scheduling (TMS), and Speculative Parallelisation of Recursive Procedures (SPRP). LRT restructures a loop into a prologue, a kernel loop and an epilogue so that the new kernel loop can achieve higher thread-level parallelism than the original loop on TLS systems. TMS generalises traditional modulo scheduling to exploit both thread-level parallelism and instruction-level parallelism in a loop. SPRP exploits thread-level parallelism in recursive procedures, especially the recursive procedures whose invocation orders might change at runtime. SPRP uses a helper thread running on one core topredict the invocation order of recursive procedures dynamically. Thus, SPRP is capable of effectively parallelising recursive procedures that are otherwise difficult to beparallelised by existing TLS techniques. We also propose a Statically Greedy and Dynamically Adaptive (SEED) approach to parallelise multi-level loops. It is necessary to use out-of-order thread spawning when parallelising multi-level loops. Therefore, a new thread scheduling policy is proposed in SEED to couple with the out-of-order thread spawning strategy. SEED allows the compiler to greedily select the set of loops to beparallelised and relies on a runtime scheduler to maximise the performance adaptively.All the compiler techniques and approaches proposed in this dissertation have been implemented on top of either the MachSUIF or the GCC compilation framework. We also provide a comprehensive evaluation of these techniques and their implementations using a realistic simulation platform. A wide range of benchmarks, such as benchmarks from Spec2000 and Olden, are used for evaluation. The results show the effectiveness and efficiency of our techniques and approaches in parallelising general-purpose applications on TLS systems