Next: Découpage en instructions
Up: 2.2.3 Les différentes étapes
Previous: Normalisation
Une fois normalisée, l'expression arithmétique doit être mise
en forme (que ce soit pour rechercher une opération de type
"multiply-add" ou pour extraire une ou plusieurs sous-parties
invariantes par rapport aux indices de boucles). Il est donc
nécessaire de "factoriser" les expressions selon certains critères
(par exemple essayer d'obtenir des sous-expressions indépendantes des
indices les plus internes - figure 7). Le critère que
nous avons choisi dans un premier temps est la minimisation du nombre
d'opérations d'un point de vue global ( peut être
considéré comme une opération "multiply-add"). Cependant, nous
pourrions (devrions ?) envisager de tenir compte simultanément
d'autres critères tels que le nombre de registres utiles, ou encore la
profondeur du chemin critique.
Figure 7: Critères de factorisation.
Plusieurs problèmes apparaissent à ce niveau :
- En se limitant aux critères proposés figure 7,
une factorisation décidée à l'étape i peut empêcher une
factorisation "meilleure" disponible seulement à une étape i+k
ultérieure (sur la figure 8, la factorisation
effectuée sur j à l'étape 1 interdit une factorisation sur k
par la suite). Il pourrait donc être utile de conserver en mémoire
un historique des transformations, et si une factorisation de niveau
plus profond devient possible alors on "défait" (redistribution) les
précédentes (mais pas toutes !?)...
- Il peut s'avérer par ailleurs nécessaire d'effectuer une
renormalisation locale (pour conserver l'associativité et la
distributivité par exemple). C'est le cas sur l'exemple de la
figure 8 à l'étape 3.
Figure 8: Exemple de factorisations.
Factoriser une expression permet de diminuer le nombre d'opérations
nécessaires pour son évaluation à deux niveaux :
- La factorisation d'une opération permet de passer de n à n-k
opérations.
- En permettant d'extraire une sous-expression indépendante des
indices de boucles les plus internes, la factorisation permet de
remonter certains calculs (par exemple sur la figure 9
passage de l'étape 5 à l'étape 6).
Remarques: Les valeurs données sur l'exemple 9 tiennent
compte des déplacements de sous-expressions invariantes, mais les
déréférencements et calculs d'adresses ne sont pas pris en compte
pour simplifier.
Figure 9: Nombre d'opérations.
Next: Découpage en instructions
Up: 2.2.3 Les différentes étapes
Previous: Normalisation
Julien Zory
Thu Mar 12 17:35:23 MET 1998