Automatic mining of tasks in structured programs

Abstract

This dissertation describes the design and implementation of a suit of static analyses and code generation techniques to annotate programs with OpenMP pragmas for task parallelism. These techniques approximate the ranges covered by memory regions, bound recursive tasks and estimate the profitability of tasks. These ideas have been implemented in a tool called TaskMiner, a source-to-source compiler that inserts OpenMP pragmas into C/C++ programs without any human intervention. By building onto the static program analysis literature, and relying on OpenMP's runtime ability to disambiguate pointers, TaskMiner is able to annotate large and convoluted programs, often replicating the performance gains of handmade annotation. Furthermore, the techniques employed in TaskMiner give us the means to discover opportunities of parallelism that remained buried in the syntax of well-known benchmarks for many years -- sometimes leading to up to four-fold speedups on a 12-core machine at zero programming cost.