Work Package 5

From Superoptimization
Jump to: navigation, search

Work package 5 is to construct an early stage business plan.

Work package summary

Start date: 2 June 2014
End date: 19 September 2014

Description

Construct an early stage business plan for future commercial deployment. This will explore likely markets, potential customers and appropriate business models.

Deliverables

An early stage business Plan

Dependencies

Will need to know likely techniques as identified by work package 1.

Status

Complete, with more detailed business plan delivered to Embecosm.

Early stage business plan

This is a summary of a fuller business plan prepared for Embecosm.

Context

Compilers translate software written in programming languages to the binary code a computer actually executes. All compilers try to “optimize” the translation, but this is a misnomer, since the result is not “optimal” in the sense of being the best possible translation of the software. Superoptimization, in which the compiler searches for the truly optimal translation dates from 1987, and involves exhaustively searching through all sequences of binary codes to find the very best. The potential gains are huge – one early example reduced a common sequence from 9 to 4 instructions, resulting in reduced execution time, smaller programs and more energy efficient code.

Due to the computational demands, exhaustive search can only tackle tiny code fragments. Over the past 27 years, the algorithms have been improved, and peephole optimization used for more general deployment. In the summer of 2013, research by one of Embecosm's team, James Pallister, suggested the technique could potentially be applied to optimizing for energy efficiency.

Market opportunity

Compiler technology underpins the huge processor design market, in which the UK is arguably the world leader (with multi-billion pound companies like ARM and Imagination Technology). The UK already has a strong position in compiler technology, particularly for energy efficiency. This feasibility work, will reinforce UK leadership, pulling more of this global business into the UK. It is notable that both major industry compiler conferences are being held in the UK in 2014.

The key commercial differentiator for any compiler is the performance of the code it generates. That performance may be measured as the speed at which the code executes, the size of the code generated (particularly for the deeply embedded market) or more recently for energy efficiency of the generated code. This last is being explored by the Embecosm with Bristol University through the Technoogy Strategy Board funded MAGEEC project.

After 40+ years of development, compiler technology is now quite mature. Companies such as Embecosm typically differentiate on compiler performance improvements of the order of 5-10%. The scale of the benefits possible through superoptimization would represent a disruptive advantage for any company that could deliver. However as 27 years of research indicates, there is huge risk in attempting to achieve this. The assistance of the UK Technology Strategy Board has allowed Embecosm to undertake the initial evaluation of that risk. In the unlikely event of this feasibility study yielding success, Embecosm would be in a position to take a world-leading position in compiler delivery.

Market size

We have previously estimated that the global compiler market is worth £150M-170M/year. A significant minority proportion of that market is due to proprietary compiler development by two major companies, Microsoft and Intel. A further minority proportion is down to open source compiler development in-house by major chip vendors, such as ARM. However the remainder is supported by competing compiler development companies of which Embecosm is one. Establishing dominance in superoptimization technology would allow Embecosm over time to grow to take a major part of this market. It is even possible that the benefits possible would open up the potential for a change of strategy by Microsoft and Intel, and encourage in-house development to move out-of-house

Use Cases

We can identify 5 use cases for superoptimization.

  1. Compiler writers. The users of the superoptimizer in this case are likely to be experts in the architecture, and want to do a “one-off” superoptimization of target specific libraries used in the compilation process. A superoptimizer is also beneficial during the initial porting of a compiler to a new architecture. This involves creating a range of very efficient target-specific implementations, for functionality such as soft floating point and division emulation. A superoptimizer can also enable peephole optimizations to be found quickly and automatically, enhancing the compiler's ability to produce competitive code early in the design cycle.
  2. Library writers. In a similar vein to compiler writers, library writers are likely to perform a one-time superoptimization of key hot spots in the code. The library is likely to be used many times compared to the one time cost of superoptimization, producing speed/code size/energy efficiency benefits to the library user. Some libraries, such as libc would have a large impact if they were superoptimized.
  3. Application developer (embedded/mobile). An embedded developer is likely to recompile more frequently than a compiler or library writer, as such extremely long times to optimize the application are not possible. However, superoptimization is still desirable, since code size and energy consumption are frequently very important to the final application.
  4. Application developer (desktop). Desktop developers often expect a short compilation time, allowing rapid, iterative development of the application. As such, a slow superoptimization stage of compilation is not appropriate for general use, but may be very beneficial when releasing a final version of the software or for a key region of the software.
  5. Application developer (HPC). Superoptimization would be very beneficial to HPC users, since there are frequently small, hot loops which dominate the execution time of the application. A superoptimizer targeted towards HPC applications could decrease the time it takes to get a scientific application's results, leading to a greater number of simulations and faster results. These applications typically run for a long time, so a moderate time spent optimizing is acceptable.

The later use cases will not be feasible until some of the future technology (machine learning, constructive superoptimizers) has been developed.

Service offering

Most compiler development companies are now service companies developing one of the two major open source compilers, GCC and LLVM. The market for a proprietary compiler for any particular processor is tool small to justify the investment, and a per-user licensing model is not liked by end-customers, because it inhibits their ability to promote their product. As a consequence we are seeing the disappearance of product-centric proprietary compiler companies, most recently with the acquisition of Target Compiler Technologies by Synopsys Inc.

We can identify three flavors of service offering:

  1. Provide a superoptimizer. Embecosm can provide a customer with a superoptimizer for their own use. We can start with the GNU Superoptimizer, but move on from that as technology evolves.
  2. Provide superoptimization training. This requires that a superoptimizer already exists for the customer's target architecture.
  3. Provide a superoptimization service. Customers which distribute libraries along with their products, or require specific regions of code to be highly efficient would benefit from a superoptimization service. This requires that a superoptimizer for the target architecture has already been constructed. Embecosm would utilize this superoptimizer, and in-house expertise to optimize the library, resulting in a library which is smaller, and faster. The service would most serve use case 2 described above, with further interest from the application developers use case.

Execution strategy

In the short term, Embecosm is developing reference case studies and sales collateral for the brute force approach based on GNU Superoptimizer.

In the medium term, Embecosm will seek support to move more applicable research to the market (for example machine learning techniques, support for floating point).

For the long term, Embcosm's relationships with Universities are key. We will discuss with our academic colleagues how we can encourage relevant research.

Forecast business value

An early stage business plan cannot give meaningful concrete figures. However Embecosm has doubled in size every year since 2008. Delivery of compelling new service offerings is central to continuing that growth.