Value Profiling Driven Optimisations for Embedded Processor Architectures and Applications

Many researchers have investigated the exploitation of the fact that the individual instructions executed by a program often produce repetitive results. The prevalence of such repetitive behaviour is demonstrated in the prior art where for 15 Spec95 benchmarks studied, it was found that on average, 48% of a program's memory locations were occupied by 8 benchmark specific frequently occurring values. The three main ways of exploiting such repetitive behaviour are:--

Value locality based techniques that use a reduced number of bits to represent frequently occuring values. Such techniques may require data encoding and compression. Such techniques can increase the effective memory hierarchy bandwidth and/or, reduce power consumption via reductions in the switching activity associated with external bus loads/stores and arithmetic operations on frequent values.

Value reuse optimisations that seek to bypass redundant computation by dynamically storing or precomputing the previously produced results of computations using associative memory implemented with software and, or, custom hardware support.

Value sensitive code specialisation or partial evaluation that generates additional specific code for frequently occuring values requiring fewer instructions/processor cycles to execute than the unspecialised code. Such optimisations enable computations to be simplified in a manner similar to strength reduction.

Value locality based optimisations generally require custom hardware support to implement the encoding/decoding of frequent values whereas reuse and code specialisation can be beneficial with a purely software approach if the computational granularity is sufficiently large. However, efficient value sensitive specialisation and value reuse at instruction level requires hardware support to dynamically recognise that an instruction can be bypassed or simplified. For example, run-time algebraic simplification enables the bypass of instructions for; multiplication A * B and division A/B, when registers A or B are equal to 1,-1, 0 and when A=B, A=-B, A=0, B=1,-1 respectively.

In this cluster we seek to:
i) Develop an academic and industrial collaboration between ARM and Manchester with a focus on value profiling driven optimisations for both processor architecture and code transformation. We will organise 2 meetings of approximately 1 week duration at ARM in order for meaningful discussions to take place with appropriate engineers at ARM Cambridge. During the initial meeting we will discuss in detail the form of preliminary investigations into opportunities for value profiling driven optimisations, using simulation platforms and/or soft-core on FPGA platforms by running embedded and multimedia applications of interest to ARM and Manchester.

ii) Develop and encourage HiPEAC interest in our research cluster and related clusters such as "Value-driven Embedded Processors". We will organise a meeting at the HiPEAC conference which ARM and Manchester will attend to steer discussions on the research directions of the cluster and to present preliminary results.

iii) Develop related proposals to further develop the research of the cluster. This will be a main goal of the cluster. The research directions and content of future proposals will be finalised before and during the second 1 week visit to ARM.

Participants:
Andy Nisbet Manchester Metropolitan University. UK
Emre Ozer ARM Ltd, Cambridge, UK

Budget outline
Andy Nisbet Manchester Metropolitan University. UK
Collaboration:
2x5 day visit to ARM Cambridge: 5 days (750 Euros per trip=> 1500 Euro)
1x4 day attendance at HiPEAC Conference (800 Euros)

Travel:
2 round trips Manchester- Cambridge (150 Euros per trip => 300 Euros)
1 round trip Manchester - Goteborg for HiPEAC Conference (300 Euro)

Emre Ozer ARM Ltd, Cambridge, UK.
Collaboration:
1x4 day attendance at HiPEAC Conference (800 Euros)

Travel:
1 round trip Cambridge to Goteborg for HiPEAC Conference (300 Euro)