« Optimisation des compilateurs » : différence entre les versions

Contenu supprimé Contenu ajouté
Ligne 58 :
ADD e, R0
MOV R0, d
 
=== Optimisation des boucles ===
 
Cette technique agit sur les instructions qui constituent la boucle. Cette procédure est très intéressante car une bonne partie du temps d’exécution d’un programme est dédié à l’exécution des boucles.
Il existe plusieurs opérations possibles dans ce type d’optimisation.
 
;Changement de l’ordre des boucles
Cette optimisation consiste à changer l’ordre des boucles entrelacées. En effet, on pourrait échanger une boucle externe avec une interne.
Cette transformation nous permet de vérifier le principe de localité. D’ailleurs, ça permet d’éviter à la mémoire cache de chercher des lignes de données d’une itération à une autre.
Considérons l’exemple d’un tableau à deux dimensions et qu’on dispose du code suivant pour le remplir :
 
For i from 0 to 10
For j from 0 to 20
A [i,j]= i + j
 
Ce code peut être optimisé de la sorte avec ce type d’optimisation :
 
For j from 0 to 20
For i from 0 to 10
A [i,j]= i + j
 
Mais cette transformation dépend de la technique du cache utilisée et de la disposition du tableau dans la mémoire utilisée par le compilateur.
 
 
;« Loop splitting » ou « loop peeling »
C’est la division d’une boucle en plusieurs autres boucles ou bien la suppression de dépendance.
 
Un cas simple et spécial de cette technique consiste à supprimer une première itération complexe de la boucle et de la mettre à l’extérieur de cette dernière.
 
Voici un exemple de « loop peeling ». On suppose que le code original est :
 
For j from 1 to 20
A [j] = A [1] + B [j]
 
Comme cette affectation du tableau A dépend du tableau A lui même, le compilateur ne peut pas utiliser le parallélisme en toute sécurité. Pour cela, il supprime l’affectation problématique de A[1] de l’intérieur de la boucle et la met à l’extérieur.
 
On obtient donc après ce type d’optimisation :
 
A [1] = A [1] + B [1]
For j from 2 to 20
A [j] = A [1] + B [j]
La valeur de A[1] issu du premier calcul peut ensuite être stockée en registre pour l'utiliser à chaque itération de la boucle.
 
Cette technique d’optimisation est introduite dans le compilateur gcc dans la version 3.4.
 
;Fusion de boucles
Elle fusionne plusieurs boucles en une seule.
Exemple en C :
 
int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
a[i] = 1;
}
for (i = 0; i < 100; i++)
{
b[i] = 2;
}
 
L’exécution de ces deux boucles séparées est équivalent au code suivant :
 
int i, a[100], b[100];
for (i = 0; i < 100; i++)
{
a[i] = 1;
b[i] = 2;
}
 
Cette technique optimise le temps d’exécution du programme. En outre, il y a une technique similaire appelée fission de boucle qui consiste à exécuter une seule boucle en deux boucles et qui optimise l’utilisation de mémoire et donc qui applique mieux le principe de localité.
 
;« Loop Unwiding »
La transformation est la mise en place de prochaines affectations dans la même itération et cela pour augmenter le taux de « cache hit ».
 
Par exemple une procédure dans un programme a besoin d’effacer 100 éléments. Pour l’accomplir, il faut appeler 100 fois la fonction delete comme suit :
 
for (int x = 0; x < 100; x++)
{
delete(x);
}
 
Avec cette technique, on va diminuer le temps d’exécution et on obtient le code optimisé suivant :
 
for (int x = 0; x < 100; x += 5)
{
delete(x);
delete(x+1);
delete(x+2);
delete(x+3);
delete(x+4);
}
 
Avec cette modification, on exécute seulement 20 boucles au lieu de 100. Donc on diminue le nombre d’instructions composées par un test et un « jump » par un facteur de 1/5.
Cependant 4 nouvelles opérations d'additions sont ajoutées, mais cela peut rester négligeable face aux 4 instructions de bouclage économisées (incrément de x et test de la condition), et dépend du coût des instructions sur le processeur utilisé.
 
;« Loop unswitching »
C’est le fait d’enlever une structure conditionnelle de l’intérieur de la boucle et de la mettre à l’extérieur.
Ensuite, on duplique la boucle, et on met chaque version dans une branche.
 
Pour illustrer ce cas de figure, on additionne deux tableaux X et Y, et on fait une affectation dépendant de W, une variable booléenne.
 
On a au début ce pseudo code :
 
for i to 1000 do
x[i] = x[i] + y[i];
if (w) then y[i] = 0;
end_for;
La condition à l’intérieur de la boucle rend très difficile un parallélisme en toute sécurité.
Et après l’utilisation de cette technique on obtient :
if (w) then
for i to 1000 do
x[i] = x[i] + y[i];
y[i] = 0;
end_for;
else
for i to 1000 do
x[i] = x[i] + y[i];
end_for
end_if;
 
Chacune de ces boucles peut être optimisée séparément. On note aussi que le code généré est presque le double en terme de quantité que le code initial. Cette technique est introduit dans le gcc version 3.4
 
;Inversion de boucle
: C’est le remplacement d’une boucle While par un block contenant une boucle do…while.
 
Ce code en C :
int i, a[100];
i = 0;
while (i < 100) {
a[i] = 0;
i++;
}
 
Est équivalent à :
int i, a[100];
i = 0;
if (i < 100) {
do {
a[i] = 0;
i++;
} while (i < 100);
}
Apparemment, cette technique n’est pas efficace ; la même boucle et un code plus long. Mais la plus part des CPU utilisent les « pipelines » pour exécuter leurs instructions. Donc par nature un « jump » causera un « pipeline stall », c’est à dire une initialisation de la pipeline.
 
Considérant ce code assembleur suivant :
i := 0
L1: if i >= 100 goto L2
a[i] := 0
i := i + 1
goto L1
L2:
Si i est initialisé à 100, l’ordre de l’exécution des instructions serait :
1: if i >= 100
2: goto L2
Et de l’autre coté, si on voit l’ordre de l’exécution des instructions si on initialise i à 99 :
1: goto L1
2: if i >= 100
3: a[i] := 0
4: i := i + 1
5: goto L1
6: if i >= 100
7: goto L2
8: <<at L2>>
Et maintenant regardant le code optimisé :
i := 0
if i >= 100 goto L2
L1: a[i] := 0
i := i + 1
if i < 100 goto L1
L2:
Et si on répète les mêmes exécutions faites dans l’ancien code on obtient successivement :
Pour i=100
1: if i >= 100
2: goto L2
Pour i=99
1: if i < 100
2: goto L1
3: a[i] := 0
4: i := i + 1
5: if i < 100
6: <<at L2>>
Et comme on peut le constater, on élimine deux « goto » et donc deux initialisations du pipeline.