Home

Superoptimization

Superoptimization is the brute-force version of programming. Given a target instruction sequence, a superoptimizer will try every possible combination of instructions until it finds one which does something functionally equivalent. If this found sequence is faster, smaller or lower energy then it may be chosen to replace the target sequence, resulting in a performance boost (in your chosen metric). Over Summer 2013, I will be looking at whether we can superoptimize our code for energy consumption.

History

Superoptimization was first proposed by Henry Massalin in his paper 'Superoptimizer - A look at the smallest program'. Several other studies have been conducted since.

Project Plan

This is a preliminary project plan.

Week	Item
1-2	Literature review. Evaluate existing implementation of superoptimizers. This should better define the scope of the project. The search space and type of instruction sequences to be considered should be defined by this point. The benchmarks and method of evaluation will also be selected (likely benchmarks used previously?). The method of verifying that the selected instruction sequence is functionally equivalent to the input sequence is selected. This will heavily influence what type of instruction sequences are considered.
3-4	Instruction enumerator and testing. Implementation of a framework to generate instruction sequences and run/simulate them.
5	GCC Cauldron Away presenting previous work at GCC Cauldron.
6-7	Cost function development. This considers how the energy of a short sequence of instructions should be collected. Options: energy model, running of target sequence on hardware (many times to allow for data collection), running target sequence within an existing benchmark, to measure improvement.
8-10	Evaluation. Run the superoptimizer on benchmarks, and analyse its output.
11-13	Write up. Academic paper write up.

Research Questions

There are many interesting questions which could be answered by using a superoptimizer targetted for energy. Many of these will likely be out of the scope of the project due to time constraints, however they are listed below.

Does superoptimization for energy consumption produce different optimal sequences than if targeting code size or performance?
If different code sequences are found, how different are they? Is it algorithmically different to the optimal code for performance?
Can we create a database of energy efficient peephole optimizations, which can quickly be applied to existing programs (similar to Bansal2006)?
Are there any unexpected sequences of code? If so, why do they appear?
Is the optimal sequence dependent on the input data? Do different algorithms arise from different data?