Program parallelization through safe dependence hints and all-context dependence analysis.

Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 2012.Speculative parallelization divides a sequential program into possibly parallel tasks and permits these tasks to run in parallel if and only if they show no dependences with each other. The parallelization is safe in that a speculative execution always produces the same output as the sequential execution. Most previous systems allow speculation to succeed only if program tasks are completely independent, i.e. embarrassingly parallel. The goal of this dissertation is to extend safe parallelization in the presence of dependences and in particular to identify and support tasks with partial or conditional parallelism. The dissertation makes mainly two contributions. The first is safe dependence hints, an interface for a user to express partial parallelism so speculative tasks can communicate and synchronize with each other. The interface extends Cytron's post-wait and recent OpenMP ordering primitives and makes them safe and safely composable. Dependence hints are based on channel communication. A unique feature is channel chaining to express conditional dependences. The second is parallelization support. The thesis describes STAPLE, a system for finding safe task parallelism by first analyzing a program using a compiler and then analyzing its executions using a profiler. The STAPLE compiler collects profiles for all program constructs including loops and functions in a single run. After profiling, STAPLE ranks program constructs by their potential for improving the whole-program performance. STAPLE analysis proceeds in two levels. The first analyzes potential parallelism assuming complete data privatization to remove false dependences. It considers both loop and function tasks but assumes no reordering of statements within a loop or function. Often the parallelism can be enhanced by reordering dependent operations. The second-level analysis identifies opportunities for such reordering and computes the increase in parallelism. It combines the (context) tree based dependence profile and the code-based dependence graph to analyze and emulate the effect of parallelism enhancing code transformations. Dependence analysis is costly. It must track all accesses to all data so not to miss a single dependence. Previously, loop profilers analyze one loop at a time and ignore dependences outside the loop. In task profiling, STAPLE has to consider all dependences in a complete execution, including the effect of abnormal control flow such as exceptions, which complicates context tracking. The compiler support is built using GCC. A set of optimizations is devised to reduce the cost. The resulting tool is robust and efficient enough to evaluate all SPEC CPU2006 integer benchmarks (on training inputs). The source code may have thousands of nested loops and recursive functions (as in GCC itself), and the unmodified run time can be over 4 minutes