Domain-Specific Optimisation Components

Introduction - Optimisation as a poorly separated concern

Object-oriented programming is a well-known technique for achieving the design goals of abstraction and separation of concerns in software engineering. There are, however, many other concerns which cannot be represented adequately in the object-oriented paradigm. One example, which can be nicely addressed with Aspect-Oriented Programming is tracing and logging. This project is aimed at looking at another concern which is typically poorly separated: optimisation.

Tiling, unrolling, software pipelining etc. are all examples of code optimisations which interfere in a significant way with the structure of a code base, and hence become difficult to maintain and verify. The idea behind this project is that optimisation should be a separate piece of code, which is "applied to" (i.e. restructures or re-writes) a code-base to yield the optimised code. The hope is that in this way, both the original code base and the optimisation become independently re-usable and maintainable.

Where to start

I suggest that you build this project on top of an existing metaprogramming infrastructure (metaprogramming means writing programs that write programs, or re-write programs). One possible tool is the TaskGraph Library, which has back-ends for both SUIF and ROSE. The TaskGraph library allows us to construct the abstract syntax tree (AST) for a piece of code at runtime, then print, compile and link this code and execute it. Beforehand, we have a chance to apply restructuring transformations using SUIF or ROSE.

Things to do

• Install, use and learn about the TaskGraph library. Implement some examples.
• Identify a collection of optimisations which are likely to be profitable across a range of different codes (i.e. re-usable).
• Identify a suitable collection of benchmarks which are likely to different from different optimisations.
• Study the both the impact and the cost (note that some optimisations can take a significant amount of time) of applying different optimisations to different benchmarks.
• How can we predict which optimisations are going to be profitable for a given piece of code? Try to formulate metadata that characterise optimisations and allow making this prediction without having to apply the optimisation.

Is this project for you?

To do this project, you should not be scared by large, existing pieces of software, and have the ability to get complex pieces of code to work.

Olav Beckmann
Last modified: Thu Oct 6 01:58:38 BST 2005