| Research |
| [ CSI ] [ ETH ] |
[ Lab Manager ]
| [ Publications ] [ Research Opportunities ] [ Partners & Supporters ] [ Earlier Work ] |
|
Exploiting Task-Order Information in Compilers for Shared-Memory Parallel Programs |
| Christoph Angerer, Exploiting Task-Order Information in Compilers for Shared-Memory Parallel Programs, ETH Zurich. (Diss. ETH No. 20022), November 2011. [DISS_ETH_20022.pdf] |
| With the arrival of multicore systems, parallel programming is becoming increasingly mainstream. Writing correct parallel programs, however, has turned out to be difficult and prone to errors without proper support from the employed programming languages, compilers, and runtime systems. Over the last years, researchers and engineers have developed numerous abstractions and programming models that make developing parallel programs easier, safer, and more efficient. Despite the advances made in parallel programming models, libraries, and runtime systems, the corresponding compilers still remain largely ignorant of the parallelism exhibited by the program execution. In particular, current compilers do not have any knowledge about what tasks are scheduled when in the program and how they are ordered---even though many higher-level parallel programming models and libraries contain a wealth of task-order information that can be exploited by the compiler. Without task-scheduling knowledge, however, compilers are missing important optimization and verification opportunities. This dissertation explores how compilers for parallel programs with shared memory can gather and exploit knowledge about the scheduling of tasks at runtime. By analyzing potential orderings between tasks, the compiler can decide whether accesses to shared memory by different tasks may conflict and thus result in data races. We present a concrete schedule analysis that can extract task-ordering information from real-world programs. The schedule analysis can be combined with standard program analyses such as points-to and escape analyses to improve the precision of known optimizations as well as enable new optimizations. We present two case studies to evaluate the effectiveness of the schedule analysis. The first case study is an optimizing compiler for a version of Java that uses sequential consistency as its memory model. Sequential consistency solves many inconsistencies of the Java Memory Model. However, it comes at the cost of large runtime overhead, because it prevents many of the standard optimization techniques. Our compiler exploits task-order information to decide whether or not a program operation may conflict with a parallel task. If not, the compiler is allowed to aggressively apply all standard optimizations to this program part. The second case study is an optimizing compiler for a system with dynamic fractional permissions. In this system, every object is associated with a list of tasks that have read and/or write permission for the object. Tasks can grant read permission to subtasks by splitting their own permission into fractions and later collect those fractions back to re-gain the original permission. The overhead of checking permissions is reduced by an optimizing compiler that uses task-ordering information to minimize the places where permission checks must be inserted. In addition to the two case studies, we describe multiple smaller optimization and verification techniques that benefit from task-order information. While we do not present a thorough evaluation of those techniques, we do report anecdotal evidence where we have data available. |
| [ Publications ] [ Research Opportunities ] [ Partners & Supporters ] [ Earlier Work ] |