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.
|Commitee:||Huang, Michael, Kautz, Henry, Scott, Michael L.|
|School:||University of Rochester|
|Department:||Hajim School of Engineering and Applied Sciences|
|School Location:||United States -- New York|
|Source:||DAI-B 73/07(E), Dissertation Abstracts International|
|Keywords:||All-context, Profiling, Program parallelization, Safe dependence hints, Speculation|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be