Extends:
Adaptive Optimisation

Description:

Current hand-crafted approaches to compiler development are no longer
sustainable. With each generation of architecture, the compiler
development time increases and the performance improvement achieved
decreases. As high performance embedded systems move from ASICs to
programmable heterogeneous processors, this problem is becoming
critical. This proposal explores an emerging alternative approach
where, rather than developing and hard-coding a compiler optimisation
strategy for each configuration, we aim to develop a novel portable
compiler approach that can automatically tune itself to any embedded
hardware configuration (for performance as well as resource
utilization improvements). This is achieved by employing machine
learning approaches to optimisation, where the compiler searches and
learns an optimisation space adapting its behaviour depending on the
hardware configuration and application domain.

HiPEAC contains a unique group of academic and industrial partners,
who collectively have experise in the diverse range of areas needed
for such a project. This proposal aims at bringing this group together
in order to orchestrate a long term agenda in machine learning based
optimisation. It aims to bring industrial and academic partners
together, accompanying the developments within the HiPEAC compiler
platform. Furthermore, it aims at supporting and disseminatiog related
aspects within the SCALA project and the (pending, but well ranked)
MilePost STREP proposal.

This will have a profound significance in compiler optimisation in the
coming decade and this proposed cluster will ensure that HiPEAC is
best able to capitilise on our expertise.

The goals of the cluster are:

1. Continuous iterative optimization is a promising approach to
optimize and generate self-tuning programs that can adapt to a variety
of complex architectures and input contexts. This approach has yet to
be made practical, especially in embedded systems contexts with
resource constraints. Fursin's HiPEAC'05 paper (a result of the
existing Adaptive Optimization cluster) use multiversioning to embed
multiple optimization options in one single object code. To avoid code
size explosion, other works rely on binary translation but are limited
to narrow-scoped, low level transformations. At the other extreme,
run-time recompilation is very flexible but can incur high overhead.
We propose to investigate a just-in-time code generation approach,
where an intermediate representation of the code (e.g., bytecode) is
annotated with search space and transformation information. This
representation should allow to express any given transformation in a
very compact form (compared to multiversioning) yet incur the minimal
compilation-time or run-time overhead. We will leverage on related
work by the INRIA members (published at ICS'05 and LCPC'05, and
special issues of Science of Computer Programming and Intl. J. of
Parallel Processing in 2006).

2. While the previous goal addresses the compact representation of
multiple program versions (with low run-time overhead), it is critical
to narrow-down the huge search space to a set of most promising
candidate optimizations to be evaluated. Typically, only dozens
different optimization variants can be represented together with the
intermediate code file, and only a few of these can effectively be
evaluated at run-time (to minimize just-in-time code generation overhead).
Therefore we plan to evaluate predictive modelling techniques to learn
the best mapping from program features and run-time behavior to
optimizations. The key issues are:
- to identify the most significant features in every program hotspot
  (function or loop), including syntactic, semantic and run-time
  behavior features;
- to store the resulting map from local program features to
  optimization variants in a compact form;
- and to evaluate the impact of each variant on the application's
  overall performance.
This goal will benefit from recent results of its Edinburgh members
(published at SC'05 and CGO'06) and INRIA members (SC'04).

3. Our proposed approach is aimed towards multi-phase optimization,
including link-time and just-in-time compilation frameworks, as well
as compiler training approaches (with narrowing of the search space
and tuning interleaved with production uses), and automatic compiler
construction (building an optimizer from raw transformation
primitives). We wish to conduct practical experiments in real-world
tools. We are currently considering the GCC link-time optimizer
(currently in development), STMicroelectronics's virtual machine for
.NET, and IBM's Jikes virtual machine for Java. 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. One also need to measure the
impact on each tool's optimization chain, and quantify the expected
performance benefits.

 

Nature:
Research cluster

Total funding:
Requested: € 20500
Granted: € 0

Including fellowship funding:
Requested: € 6000
Granted: € 0

Description of how the funding will be used:

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

  Cost : 6 people traveling * 3 meetings * 500 euros = 9000 euros (500 and 6 are averaged over the effective costs and savings from colocated meetings, taking into account flights from Israel).

In addition, we are planning a few exchanges of personnel, motivated
by bidirectional transfer of knowledge activities between academic and
industrial groups. This would also allow for meetings with local
machine learning experts (at IBM Haifa, and Prof. Williams at the U.
of Edinburgh) who do not belong to the HiPEAC network. Two researchers
of IBM and STMicroelectronics could spend a total of 1 month at INRIA
and Edinburgh.

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

We will eventually ask for one 4-month (maximum 6-month) 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.

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

  Total Funding Requested : 14500 euros + intenship

Duration of the funding:
Requested: 12 month(s)
Granted: 0 month(s), starting on: Tue, January 1, 1980

Participating members:
TEMAM Olivier (INRIA) (--member--)
BERNSTEIN David (IBM) (--member--)
CORNERO Marco (STMicroelectronics) (--member--)
O'BOYLE Michael (Edinburgh University) (--member--)
ZAKS Ayal (IBM) (--member--)
MENDELSON Bilha (IBM) (--member--)
BODIN François (INRIA) (--colleague--)
COHEN Albert (INRIA) (--member--)

Other people collaborating:

John Cavazos        U. of Edinburgh
Erven Rohou        STMicroelectronics
Grigori Fursin        INRIA Futurs