Critical-Path-Guided Interactive Parallelisation

With the prevalence of multi-core processors, it is essential that legacy programs are parallelised effectively and efficiently. However, compilers have not been able to automatically extract sufficient parallelism in general programs. One of the major reasons, we argue, is that algorithms are often implemented sequentially in a way that unintentionally precludes efficient parallelisation. As manual parallelisation is usually tedious and error-prone, we propose a profiling-based interactive approach to program parallelisation, by presenting a tool-chain with two main components: Embla 2, a dependence-profiler that estimates the amount of task-level parallelism in programs, and Woolifier, a source-to-source transformer that uses Embla 2´s output to parallelise programs using Wool, a Cilk-like API, to express parallelism. Based on profiled dependences, our tool-chain (i) performs an automatic best-effort parallelisation and (ii) presents remaining critical paths in a concise graphical form to the programmer, who can then quickly locate and refactor parallelism bottlenecks. Using case studies from the SPEC CPU 2000 benchmarks, we demonstrate how this tool-chain enables us to efficiently parallelise legacy sequential programs, achieving significant speed-ups on commodity multi-core processors.