Evaluation Optimization for Loops and Expressions
The EOLE project is developped by the Computer Science Center
(Centre de Recherche en
Informatique) at Ecole des Mines de
Paris. The main part of this project is done by Julien Zory as a PhD thesis work.
Fabien Coelho also
contributes to this work.
The overall goal is to define and implement new compilation techniques
that improve the performance of scientific applications. Expressions and
Loops constitute the two major targets of this optimizing process.
- Optimizing Expression Evaluation
Algebraic properties such as associativity or
distributivity allow the manipulation of a set of mathematically
equivalent expressions. However, the cost of evaluating such
expressions on a computer is not constant within this domain.
We use algebraic transformations to improve the performances of
computationally intensive applications on modern architecture
computers. Taking into account instruction-level parallelism and new
capabilities of processors when applying these transformations leads
to large run-time improvements.
Due to a combinatorial explosion, associative-commutative
pattern-matching techniques cannot systematically be used in that
context. Thus, we have introduced two performance enhancing greedy heuristics
providing factorization and multiply-add extraction.
Efficient choice criteria based on a simple cost model are also used.
Experiments on real codes, including an excerpt from SPEC FP95
benchmarks, are very promising since we automatically obtain the same
results as manual transformations, with a performance
improvement by a factor of up to 3.
- Optimizing Loop nests
Invariant instruction motion
Associative-Commutative operand reassociation
Common sub-expression elimination
All these transformations have been extended in order to take into
account algebraic properties such as associativity and
- A first prototype has been implemented
- It automatically performs (source-to-source transformations)
- expression normalization - pattern-matching techniques
- factorization - greedy heuristics
- multiply-add extraction - greedy heuristics
- invariant instruction motion - algorithm
- Associative-Commutative operand reassociation - algorithm
- Associative-Commutative common subexpression elimination - heuristics
- Build over STORM (Orléans University and Stony Brook)
- Written in C++ (40 000 code lines)
- An interface with the Pips workbench (analyzes and transformations of scientific and signal processing
applications) is also available. It allows automatic source-source transformations of real scientific codes written in Fortran.
- Using Algebraic Transformations to Optimize Expression Evaluation
in Scientific Code - PACT'98 - October 14-17 in
Paris - (get the postscript).
Slides in english - PACT'98 conference.
Slides in french are
also available : Optimisation d'expressions dans les applications
- Seminaire commun A3 (INRIA, Rocquencourt/PRISM, Université de
Versailles-Saint-Quentin) et CRI (Ecole des Mines, Fontainebleau). June
- Seminaire du groupe calcul parallèle et scientifique - Université
de Genève. July 1998
- Réunion C3 (iHPerf). November 1998
You can also find a lot of explanations in my PhD thesis in french .
Please feel free to ask any question about this project to Julien Zory
last update : November 20, 1999.
URL : http://cri.ensmp.fr/~zory/EOLE |
email : email@example.com