Excelsior - PoLite: polyhedral optimizations for Scala
Apr. 26th, 2011
02:31 am - PoLite: polyhedral optimizations for Scala
A couple of hours ago I was accepted as a participant of this year's Google Summer of Code! My project involves implementing a polyhedral optimizer for parallel programming in Scala. If you fancy, you can take a look at the full text of the proposal. Below I'll cover the most essential ideas.
One of the important initiatives in Scala ecosystem is the creation of a commodity parallel programming platform. This initiative relies on language virtualization, a new principle that enables the construction of parallel domain-specific languages that are embedded in a common host language. The best introduction to language virtualization is Tiark Rompf's paper that describes the original idea. You can also take a look at slides for one of the lectures at Stanford for a practical point of view towards language virtualization. To keep it short, a special build of Scala compiler lets the programmer overload all constructs of the language: operators, method bindings and even syntactic constructs such as conditionals and loops. By leveraging this machinery, one can develop an embedded DSL and an accompanying optimizing compiler completely at library level.
Delite is a joint effort of researchers from EPFL and Stanford towards practical implementation of ideas described above. Most of the infrastructure is already in place (it's actually possible to clone the repo and play with some tests - see instructions on the main page of the project), and now it's about time to implement optimizations.
Polyhedral model is a theory of optimizing for parallelism and locality. Unlike its predecessors, it is capable of analyzing arbitrary superpositions of loop transformations (tiling, unrolling, fusion). This allows for deeper insight into optimization possibilities and provides noticeable performance improvements. I have always been fascinated by this framework, and even blogged about it back then (warning: linked post is in Russian). The best introduction to the polyhedral model is the second section of Pouchet's thesis (if you've got a spare hour, take a look - you won't regret it). To put it in a nutshell, polyhedral framework operates on algebraic representation of programs and their transformations. Its calculus features simple composition laws and enables reasoning about data dependences, code transformations and their validity.
The aim of the project is to implement polyhedral optimizations for Delite. By following the ideas of the researchers from Ohio University and adapting them for (quite extravagant) intermediate representation of Delite, I'm going to implement optimizers for CPU and GPU hardware targets. Subsequent posts will feature mentioned stuff in more detail - stay tuned for updates.