David M. Peixotto
Research
Haskell is a lazy functional language with a strong static type system and excellent support for parallel programming. The language features of Haskell make it easier to write correct and maintainable programs, but execution speed often suffers from the high levels of abstraction. While much past research focuses on high-level optimizations that take advantage of the functional properties of Haskell, relatively little attention has been paid to the optimization opportunities in the low-level imperative code generated during translation to machine code. One problem with current low-level optimizations is that their effectiveness is limited by the obscured control flow caused by Haskell's high-level abstractions. My thesis is that trace-based optimization techniques can be used to improve the effectiveness of low-level optimizations for Haskell programs. I claim three unique contributions in this work.
The first contribution is to expose some properties of low-level Haskell codes by looking at the mix of operations performed by the selected benchmark codes and comparing them to the low-level codes coming from traditional programming languages. The low-level measurements reveal that the control flow is obscured by indirect jumps caused by the implementation of lazy evaluation, higher-order functions, and the separately managed stacks used by Haskell programs.
My second contribution is a study on the effectiveness of a dynamic binary trace-based optimizer running on Haskell programs. My results show that while viable program traces frequently occur in Haskell programs the overhead associated with maintaing the traces in a dynamic optimization system outweigh the benefits we get from running the traces. To reduce the runtime overheads, I explore a way to find traces in a separate profiling step.
My final contribution is to build and evaluate a static trace-based optimizer for Haskell programs. The static optimizer uses profiling data to find traces in a Haskell program and then restructures the code around the traces to increase the scope available to the low-level optimizer. My results show that we can successfully build traces in Haskell programs, and the optimized code yields a speedup over existing low-level optimizers of up to 86%. with an average speedup of 5% across 32 benchmarks.
We are exploring the use of functional coordination languages for parallel computing. The idea is to have a two level language in which a domain expert can express the algorithm in high level terms of the sequential steps, data read and written by the steps, and the control dependencies between the steps. The steps themselves are written in a traditional sequential language, and it is the job of the compiler and runtime to produce an efficient (parallel) execution. I have explored some of these ideas in a .NET implementation based on the Concurrent Collections programming model from Intel.
The habanero project was started by Vivek Sarkar at Rice University. The project aims to develop new technologies to deal with the multi-core challenge: improve performance on modern hardware while making it easy for the programmer to write concurrent software. Habanero attacks the problem along the entire software stack by developing new programming languages, compilers, transformations, and libraries. My work with habanero has been in two areas: developing an extension to the work stealing algorithm for efficient scheduling of lightweight tasks, and developing a new synchronization mechanism called phasers. Our work on phasers is published in ICS 2008 and IPDPS 2009.
My master's thesis research focused on using adaptive compilation to fairly compare two register allocation algorithms. We found that the Chaitin-Briggs graph coloring register allocation algorithm was superior to the Chow-Hennessy priority-based algorithm even after extensive tuning through adaptive compilation. The full details are available in my masters thesis, linked from the publications page.
You need the willingness to fail all the time. You have to generate many ideas and then you have to work very hard only to discover that they don't work. And you keep doing that over and over until you find one that does work.
-- John Backus