Gluon: Interface for Trusted Programming
Participants: Wen-mei Hwu, Christopher Rodrigues, I-Jui Sung, John Stratton, Matthieu Delahaye
Executive Summary
The Gluon project leverages correctness specifications to enable safe parallelization and optimization of code.
Goals - Extended Description
The goal of this project is to provide a compiler framework that generates fast parallel kernels from a high-level parallel programming language that guarantees race freedom. In particular, we are working to to relieve developers of the responsibility to manually conform the parallelism and locality of an algorithm to the processor parallelism, vector parallelism, and memory system of a target architecture.
Besides correctness and automatic optimization, such a framework helps to eliminate the abstraction overhead of using high-level library code. Current programming trends toward libraries of generic algorithms and data collections, as illustrated by the C++ STL and the LINQ extensions to .NET, are creating heavily-executed code that spans library and user codebases. These libraries hide data organization and loops, thereby foiling optimization. Such a compiler framework could be leveraged to optimize parallel execution of code using these constructions.
Achieving this goal requires detailed visibility into memory access patterns and other side effects within a compiler, and here we take a novel approach. In the past, compiler-driven analysis has had some success in enabling automatic optimization for narrow problem domains. However, it has proven very difficult to reliably and automatically generate fast code, and this "hands-off" approach gives developers very little visibility into and control over the compilation process.
We address the limitation of analysis-driven optimization with two connected projects. Gluon is an intermediate program representation that hosts optimizations on parallel code. Its type system is able to track side effects more precisely than traditional analysis methods. Pyon is a high-level language that serves as a programmer interface to Gluon. Pyon includes design-by-contract features that provide programmers an adjustable level of static checking, while also communicating side effect information to Gluon.
Gluon is an intermediate representation supporting optimization of parallel code. It uses a static type system to represent information that is valuable to optimizations, such as integer bounds and side effects. The type system adds value in three ways. First, it statically detects some classes of errors including potential races. Second, it can preserve information that can be generated from high-level knowledge of source code, but would be difficult or impossible to infer solely by analyzing unadorned low-level code. Third, the type system offers a degree of extensibility, as new information can be defined within the type system as new data types. This eliminates some of the obstacles to optimization in a conventional compiler environment. Our goals are to use Gluon to vectorize code, improve data structure layout, and improve memory locality in parallel kernels.
We are beginning work on Pyon, a compiled, Python-like language with parallel operators and contracts. Pyon will allow programmers to mix sequential, dynamic code with parallel, statically checked code. Pyon borrows the "map and reduce" style of programming, in which data-parallel operators are used to build explicitly parallel code. Parallel code must be verifiably race-free. Contract-style specifications, augmented with local analysis, will be used to verify that parallel code is safe; in doing so, they generate information that is fed to Gluon's optimizations.
Results
As high-level operators and contracts offered by Pyon must allow developers to easily write parallel algorithms, we will test their usefulness toward applications currently developed from the Application Group. Writing core algorithms from these applications in Pyon will demonstrate that our parallel operators and contracts provide a reasonably simple but complete toolset from a developer perspective. It will, moreover, validate the quality of our analysis and optimizations.
We believe the applications developed by the Application group cover a wide variety of domains and gives a good representation of the kind of parallel algorithms that are currently in need for agressive optimizations. However, we will ensure our high-level operators and contracts are sufficient for a broader usage.
Our work is decomposed currently into three major milestones marking the increased maturity of our developments.
Milestone 1
Our first milestone will be to generate optimized GPU code from Pyon for some common signal and image processing algorithms, including some heavily used kernels from the ViVid library. We will implement memory layout optimization and parallel loop transformations as a first demonstration of Gluon's analysis capabilities.
This work will be in collaboration with Sanjay Patel, Minh Do and Tom Huang from the Image and Video processing group which is authoring the Vivid library.
Milestone 2
Our second milestone will be to extend Pyon and Gluon capabilities to encompass more general sequential constructs, allowing larger parts of an application to be written in Pyon. The scope of our optimizations will include inter-kernel optimizations. This includes kernel fusion and fission, as well as enabling more judicious intermediate data layout choices.
We will continue to collaborate with the Image and Video processing group to optimize larger image and video processing applications.
Milestone 3
We will support parallel manipulation of more sophisticated data structures such as k-D Trees. Pyon will have to support operators and contracts that enable the creation and safe manipulation of non-trivial data structures in parallel.
Gluon will support vectorization, so that we can generate efficient code for non-massively parallel architectures such as multi-core processors.
We will start to work in collaboration with the Dynamic Virtual Environments group as their work focus on the creation and exploitation of k-D trees data structure.
In addition, we will start studying the possibility to exploit Gluon in the context of pre-existing languages. While we will reuse the high-level operators and contracts defined for Pyon, the challenge of this work will resides on being as little as intrusive in the "host" language philosophy.
Once we have reached the third milestone, we will focus on implementing all the set of operators and and contracts needed to reimplement most of the applications developed at UPCRC. We will have working examples on using the same operators and contracts on other languages than Pyon, showing how Gluon can be integrated into existing compilers.
| Autotuning | Gluon: Interface for Trusted Programming |
Interactive Porting | Libraries | Optimizations for Power |
| Refactoring | Safe Parallel Prog. Languages | Scheduling | Verification & Validation |