superoptimization


Making your program faster and greener

Jeremy Bennett, Embecosm

Abstract

Compilers take computer programs and translate them to the binary machine code processors actually run. Two of the most widely used compilers are completely free and open source: GCC and LLVM. In this article we look at two recent industrial research projects supported by Innovate UK, the government’s innovation agency, which advance the state of the art with these compilers.

The MAGEEC project, a joint project between Embecosm and Bristol University, is an open source machine learning framework for any compiler, which allows the compiler to be trained to generate more energy efficient code. A side-benefit is that energy efficient code turns out to be much faster code.

Superoptimization as a technique to achieve the ultimate in compiled performance has been around in academic circles for nearly 30 years.

During the summer of 2014, Innovate UK funded a feasibility study to see whether any of these techniques were commercially viable. The good news is that some techniques could now, or with a modest amount of further industrial R&D, offer exceptional benefit for real-world software. And once again the software is open source.

MAchine Guided Energy Efficient Compilation (MAGEEC)

A study carried out by James Pallister at Bristol University and funded by the UK compiler development company Embecosm in summer 2012 found that choice of compiler optimization  flags had a major effect on the energy consumed by the compiled program. The bad news was that the options to be used varied from architecture to architecture and program to program [1].

The MAGEEC project was funded by the Technology Strategy Board (now Innovate UK) under its Energy Efficient Computing initiative, to develop a machine learning based compiler infrastructure capable of optimizing for energy. Running from June 2013 to November 2014, it was a joint feasibility study between Embecosm and Bristol University, to develop a machine learning compiler infrastructure that could optimize for energy. Key criteria were that the infrastructure should be generic, it should optimize for energy, that it should be based on real energy measurements, not models and that it should create a fully working system. The entire project was free and open source. (more…)


Superoptimization and Supercomputing

The BCS OSSG is hosting two talks which look at “super” themes.

Venue: The Prince Philip room, Royal Society of Arts, 8 John Adam Street, London WC2N 6EZ (N.B. Note the change of venue to the RSA)
Date: Wednesday 26 November
Time: 6:00pm for 6:30pm start

This event is free to attend for both BCS Members and non-members but booking is required.

Superoptimization: How fast can your code go

Speaker: James Pallister, University of Bristol

Super TuxModern compiler optimization can take almost any code and produce a reasonably efficient binary at the end. However compiler “optimization” doesn’t make your code “optimal”, just better.

In contrast, superoptimization can produce perfect code – the fastest, the smallest or the most energy efficient code. The technique, first introduced in the late 80s found in some cases it could do 25% better than the best assembly programmer, and 40% better than the best compiler at the time.

Free software has always played a central role in superoptimization research, with the GNU Superoptimizer being one of the very first tools constructed.

(more…)