MUTLS: Mixed Model Universal Software Thread-Level Speculation

Thread-level speculation (TLS) is a safety-guaranteed approach to automatic or implicit parallelization. Speculative threads are optimistically launched at fork points, executing a code sequence from join points well ahead of their parent thread. Safety is preserved in this speculative model by buffering reads and writes of the speculative thread. The speculative thread commits or rollbacks once the parent thread reaches the join point.

MUTLS is a software-TLS system that is purely based on the popular LLVM intermediate representation (IR). Our design enables generic application of TLS to any LLVM input language and executes on any architecture supported by LLVM, significantly extending previous TLS systems which only support a single language context and/or architecture. MUTLS maximizes parallel coverage by applying a mixed forking model that allows all threads to speculate, forming a tree of threads.

We evaluate MUTLS using several C/C++ and Fortran benchmarks on a 64-core machine. On 3 computation intensive applications we achieve speedups of 30 to 50 and 20 to 50 for the C and Fortran versions, respectively. We also observe speedups of 2 to 7 for memory intensive applications. Our experiments indicate that a mixed model is preferable for parallelization of tree-form recursion applications over the simple forking models used by previous software-TLS approaches. Our work also demonstrates that actual speedup is achievable on existing, commodity multi-core processors while maintaining the flexibility of a highly generic implementation context.