Interim report

From Superoptimization
Jump to: navigation, search

This is the interim report covering the work up to 31 July 2014. It follows the format prescribed by the Technology Strategy Board, and has been submitted in PDF form.

Company Name: Embecosm Limited
Project Title: Superoptimizing compilers: Evaluation of feasibility of commercial deployment
Project Number: 131637

Description of company business

Development of open source compilers and silicon chip models, with an emphasis on embedded and low-power sectors.

Overall problem statement and why it is significant

Superoptimization offers the potential of a major improvement in performance of compiled code performance, size and energy efficiency. For compiler users (Embecosm's customers), these are major technical drivers of commercial success.

Brief description of feasibility study

Superoptimization allows compilers to generate the best possible code. The technical complexity and computational requirements have meant it remains an academic idea applied only to a SUBSET of processor features, despite the huge potential gains in code performance, size and energy efficiency.

We believe that advances in algorithms, particularly modern machine learning techniques, formal methods (particularly SMT solvers) and increases in computer power mean that it may be feasible to offer compiler superoptimization as a commercial product to processor manufacturers.

This study will develop a proof of concept superoptimizer that addresses ALL features of a modern processor. This will provide the basis for a developing a future commerical offering. The innovation is in investigating whether superoptimization can be used in a sufficiently predictable and generic way. It builds on Embecosm's collaborative work with the University of Bristol.

Eventual impact

If successful Embecosm would expect to attract new contracts specifically to carry out superoptimization work, which would require hiring new staff and increase the commercial success of the business.

How is it proceeding?

The project plan identified 5 work packages.

  1. Work Package 1. Complete. Has identified constructive techniques based on SMT solvers within a DAG code framework may be commercially tractable for two use cases: 1) low-level library optimization (e.g. libgcc, CompilerRT) and 2) inner loop optimization of performance critical code.
  1. Work Package 2. Complete. We have established that peephole optimization is not appropriate, but found that the approach could either be integrated as an optimization pass elsewhere in the compiler, or provided as a standalone tool. This work package now overlaps WP4, and is regarded as an interim step on completion of that WP.
  1. Work Package 3. In progress. We have built a prototype system capable of selecting superoptimized sequences of code for a subset of the Atmel AVR instruction set. Over the next two weeks, we expect to complete measurements on the success of this approach.
  1. Work Package 4. In progress. This is now combined with work pacakge 2, which forms the interim report described for this work package. The initial design is captured on the project website (see [www.superoptimization.org]). This will be written up as a full application note by the completion of the project.
  1. WP5. Started. The key headlines for the business plan are captured on the project website.

The risk register is also updated on the project website.

What kind of partner would you like/need to take the project forward after the study is completed?

Any of Embecosm's customers for compiler technology would be an approprate partner.

Would you like a Technology Strategy Board Lead Technologist to contact you

To discuss your journey from concept to commercialisation - how our suite of programmes, tools and connections with others in the wider innovation landscape, may be able to accelerate it?

We believe we have a commercialization strategy, but would welcome the opportunity to discuss our ideas with a Lead Technologist.

Publicity

The Technology Strategy Board frequently publicises results/details of competitions and this includes engagement with the media. If you do not wish for this document to be used for marketing purposes and networking opportunities leading to and after the associated event please tick the box (not ticked).