Using Algebraic Transformations to Optimize Expression Evaluation in Scientific Codes

Julien ZORY and Fabien COELHO
Research report EMP CRI A-307
April 1998
18 references - 15 pages

Abstract

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 suggest the use of algebraic transformations to improve the performances of computationally intensive applications on modern architecture computers. We claim that 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 introduce two performance enhancing algorithms providing factorization and multiply-add extraction heuristic and choice criteria. This paper describes our approach and a first implementation. Experiments on real codes, including a SPEC FP95 excerpt, are very promising as we automatically obtain the same results than hand made transformations, with up to 70% performance improvements.

Keywords

Algebraic transformations, Expression evaluation, Instruction Level Parallelism, Multiply-add instructions.



Download the gzipped postscript version here


Résumé

Les propriétés algébriques telles que l'associativité ou la distributivité autorisent la manipulation d'un ensemble d'expressions équivalentes au sens mathématique. Cependant, le coût d'évaluation par un ordinateur de ces expressions varie considérablement. Nous proposons l'utilisation de transformations algébriques dans le but d'améliorer les performances des applications ayant un grand volume de calcul, sur les architectures modernes. Nous affirmons que la prise en compte du parallélisme d'instruction et des nouvelles possibilités des processeurs, pour l'application de ces transformations, permet d'obtenir de fortes améliorations des performances. Les techniques de pattern-matching associatif-commutatif ne peuvent être systématiquement utilisées dans ce contexte, à cause d'une explosion combinatoire. C'est pourquoi, nous proposons deux heuristiques permettant d'une part la factorisation d'expressions et d'autre part la reconnaissance de constructions du type "multiplication-addition". Toutes deux sont basées sur des critères de choix visant à améliorer les performances. Cet article présente notre approche, et en décrit la première implémentation. Les expériences sur des applications réelles, dont une extraite des benchmarks SPEC FP95, sont très prometteuses, dans la mesure où nous obtenons de manière automatique des résultats identiques (voire meilleurs dans certains cas) à ceux obtenus suite à des transformations manuelles, avec jusqu'à 70% d'amélioration des performances.

Mots clés

Transformations algébriques, évaluation d'expressions, parallélisme d'instruction, instructions multiply-add.