Valentin Gheorghita

www.ics.ele.tue.nl/~vali

 

 

 

 

 

FAME project description

Acronym:
FAME = Flexible Application Mapping Environment

Name:
FAME: Flexible Application Mapping Environment

Duration:
2000-2007

Goal:
The goal of FAME is to achieve low power solutions when mapping applications on processor platforms; in particular by properly exploiting the data memory hierarchy.
We like to achieve this goal by creating a compiler infrastructure capable of performing source-code transformations. We propose a dynamic approach in combination with analytic pruning of transformation search space in order to find the best low-power optimizations.

Description

Designing embedded systems requires the mapping of an application to the available resources. In order to do this, compilers try to aggressively analyze and optimize programs. Since at compile time only a part of the application code is exposed and no major changes may be done to the data structures, efficient code generation requires source-to-source restructuring, when the entire code is exposed and both, data structures and algorithm’s code may be modified. Most of source-to-source transformations require loop restructuring.

Although a lot of transformations have been recognized as being potentially beneficient, it is not easy to determine which transformations are to be used for a given application, in which order to apply them and to which code sections. This longstanding open problem is called phase order problem. Instruction Level Parallel makes this problem even worse. In traditional compilers, the phase order problem is approached by hard coding a number of transformations, based on observed behavior of a small number of benchmarks. The transformations parameters are fixed or determined using a simplified machine model. In some circumstances, profiling information is employed.

However, modern processors and their associated back-end compilers have a very complex organization; therefore this approach has much difficulty in delivering optimal code. Moreover, transformations are highly interdependent and the effect of several compound transformations is extremely difficult to predict. Previous research has concluded that the optimal transformations depend on both application and platform in such a complex way that purely analytical methods are unlikely to produce optimal results. However, static models may be employed to restrict the optimization space to the areas that are likely to produce good results.

This problem is compound by the fact that new processors with sophisticated hardware (e.g. like branch predictors, out-of-order execution, trace caches or multiscalar organization) are coming out on the market rapidly. Moreover, digital signal processors (DSPs) are increasingly important in embedded systems and need to be programmed in a high level language. These architectures tend to have complex instruction sets, and complex data path and memory organizations.

To cope with the need to highly optimize for all these different and quickly changing platforms, there is a need to tackle the phase order problem from a new perspective, named iterative compilation. In this approach, the transformation space is searched and the profiling is used to measure the impact of chosen transformations. In theory, the optimal version of the program may be found considering all possibilities. However, in practice the search space is extremely large and the need to execute transformed versions of the source program is extremely time consuming. Since this project is targeted toward the embedded systems, we can afford time-consuming optimization phase, since compilation time may be amortized across the number of products shipped. Moreover, for embedded systems, the quality of the code (which may means power consuming for hand held appliances) is much more important than the compilation time. Nevertheless, the complexity of the search need to be controlled and this is one of the most important goals of the project.

Partners involved:

People involved (from TU/e-EE-ES):