Companies involved: ST Microelectronics

Application domain: Mobile multimedia applications. Downloaded Java/.NET applications on
mobile devices

Time frame. Medium 3-6 years

Description:

Dynamic compilation has several advantages over static compilation
when targetting embedded processors.
Programs are stored using a compact respresentation and
have smaller footprints than statically compiled
binaries. Furthermore, representation such as bytecode, allows
dynamically compiled languages (e.g., Java and .NET) to be portable
across a variety of embedded processors. Finally, dynamically compiled
programs have the potential to be both faster and more energy efficient
if they can effectively exploit runtime information.

Today however, on-line dynamic compilation cannot afford agressive
optimisations. Expensive analysis
(e.g., whole-program analysis) and optimizations (e.g., graph coloring and
superblock scheduling) are not implemented in dynamic compilers because their
cost typically outweighs any benefit they might bring. Also, these costly
operations do not benefit many programs and it is difficult to discern at
runtime whether they will be beneficial to a specific program.

This proposal will explore an alternative approach to traditional dynamic
compilation, where rather than performing all analysis and optimizations
at runtime, we perform as much work as possible ahead of time before the
program is executed. Runtime optimization will then focus on those optimization
that are compile-time undecidable. We will then have the best of both worlds
applying expensive analysis and optimization off-line and using lightweigth
runtime compilation for just those optimisations that need it.

We will experiment with passing the results of ahead
of time analysis and optimizations through annotations to the dynamic compiler.
This novel approach will have a profound impact on dynamic compiler optimization
targetted to embedded processors in the coming decade changing the optimization landscape.

The goals of the cluster are:

1. Performing optimizations in a dynamic compilation environment, that take
advantage of the phase behavior of large applications and the multi-context
behavior of library/codec code, to adaptively generate different code
versions and go through different optimizations. We propose to investigate a
just-in-time code generation approach, where bytecodes are annotated with
search space and transformation information targetted at phase detection and
optimizing for multi-context behavior. The annotation representation should allow
expressing any given transformation in a very compact form yet incur minimal
compilation-time or run-time overhead.

2. To construct a machine learning JIT compiler with features provided as
annotations to the bytecode, letting the learned model in the JIT take a swift
decision based not only on runtime features but also using offline ones that would be
too expensive to gather at runtime. This goal will benefit from recent papers
published by Edinburgh members (at Supercomputing'05, CGO'06, OOPSLA '06) and
INRIA members (Supercomputing'04).

3. Enabling more expensive optimizations in the JIT through the identification of
a specific encoding of static properties as annotations. We wish to conduct
practical experiments in real-world tools. Therefore, we will do work
with STMicroelectronics's virtual machine for .NET, and IBM's Jikes RVM for Java.
An in-depth study of each environment is needed before being able to define a
generic annotation scheme to represent multiple program versions, to identify the most
promising optimizations (including program transformations as well as
system-level optimizations, e.g., garbage collection, thread scheduling and lock
management), and to capture the associated predictive model in a compact form. We
will also measure the impact on each tool's optimization chain to quantify the expected
performance benefits.

This project brings together a strong grouping of individual from industry
and academia. The focus of the funding is on substantial research visits

Two researchers at STMicroelectronics will spend a
total of 1 month at INRIA and Edinburgh.

Cost : 30 days * 150 euros + 2 trips * 500 euros = 5500 euros.

We also request ask one 3-month (6 months maximum) industrial
fellowship, in the AST department of STMicroelectronics. This
fellowship is necessary to guarantee the effectiveness of our research
proposals in practical embedded systems, and to experiment with the
.NET virtual machine.

Finally, we wish to fund 3 cluster meetings for the participants (one every 4
months), preferably in conjunction with other HiPEAC events.

Cost : 4 people traveling * 3 meetings * 500 euros = 7000 euros (500
euros is averaged on the effective costs and savings from collocated
meetings).

Cost : standard internship cost for STMicroelectronics and/or HiPEAC.

Total Funding Requested : 12500 euros + internship of 3000 euros.

John Cavazos U. of Edinburgh
Mike O'Boyle U. of Edinburgh
Marco Cornero STMicroelectronics
Erven Rohou STMicroelectronics
Grigori Fursin INRIA Futurs
Albert Cohen INRIA Futurs
Olivier Temam INRIA Futurs
Piotr Lesnicki INRIA Futurs
Stefano Crespi Reghizzi Politecnico di Milano
Giampado Agosta Politecnico di Milano

This cluster welcomes other members interested in long-term compiler
construction issues related with dynamic compilation for embedded systems.