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

Contenu supprimé Contenu ajouté
Tavernier (discussion | contributions)
m 7 version(s) depuis w:Optimisation des compilateurs
Tavernier (discussion | contributions)
mep ortho nettoyage et cat
Ligne 2 :
 
 
# 1 == Définition :==
 
C’est la procédure qui minimise certains facteurs (ou maximiser l’efficacité) d’un programme exécutable. Les facteurs les plus mis en considération sont le temps d’exécution. Néanmoins on pourrait éventuellement s’intéresser à minimiser la quantité de mémoire utilisé ou bien à la consommation en énergie du programme.
----
 
# 2 == Techniques :==
 
Les techniques d’optimisation peuvent être départagées en deux catégories. La première s’applique localement, sur une instruction ou bien sur tout le programme. La deuxième s’applique globalement et nous permet d’obtenir plus de gain mais avec une implémentation plus complexe.
 
*=== A Optimisation sur des fenêtres « peephole » :===
 
Cette technique, appliquée après génération du code machine, consiste à examiner quelques instructions adjacentes et voire si c’est possible de les remplacer par une instruction ou une séquence d’instructions plus courte. Par exemple, une multiplication par deux peut être efficacement exécutée par un décalage à gauche ou par une simple addition de la valeur à elle-même.
 
Considérant ce code en assembleur Java :
 
aload 1
aload 1
mul
aload 1
mul
 
Il peut être remplacé par :
aload 1
dup
mul
 
Ce type d’optimisation a besoin d’avoir des hypothèses sur l’efficacité des instructions. Dans ce cas précis, on a assumer que l’opération « dup », qui duplique et écrit dans la pile, est plus efficace que l’opération « aload X », qui lit une variable locale et l’écrit dans la pile.
Un autre exemple d’optimisation est d’éliminer les opérations de lecture redondante.
 
Ce code
 
A = B + C ;
D = A + E ;
 
devient
 
MOV b, R0
ADD c, R0
MOV R0, a
MOV a, R0 # lecture redondante, elle peut être supprimée
ADD e, R0
MOV R0, d
 
 
*=== B 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 pourrais é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.
 
 
;Loup splitting :
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]
 
Cette technique d’optimisation est introduite dans le compilateur gcc dans la version 3.4.
 
;Fusion de boucles
 
• Fusion de boucles : Elle fusionne plusieurs boucles en une seule.
 
 
 
• 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 :
 
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 optimiser 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.
 
;« Loop unswitching »
• « Loop unswitching » : C’est le fait d’enlever une structure conditionnelle de l’intérieur de la boucle et de la mettre a 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.
 
 
 
• « Loop unswitching » : C’est le fait d’enlever une structure conditionnelle de l’intérieur de la boucle et de la mettre a 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];
Ligne 155 ⟶ 157 :
end_if;
 
Chacune de ces boucles peut être optimiseroptimisée séparément. On note aussi que le code générer est presque le double en terme de quantité que le code initial. Cette technique est introduit dans le gcc version 3.4
 
Cette technique est introduit dans le gcc version 3.4
;Inversion de boucle
• Inversion de boucle : C’est le remplacement d’une boucle While par un block contenant une boucle do…while.
 
• 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) {
Ligne 166 ⟶ 169 :
i++;
}
 
Est équivalent à :
int i, a[100];
i = 0;
if (i < 100) {
Ligne 176 ⟶ 180 :
}
Apparemment, cette technique n’est pas efficace ; la même boucle et un code plus long. Mais la plus part des CPU utilisent les « pipeline » 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
Ligne 186 ⟶ 189 :
L2:
Si i est initialisé à 100, l’ordre de l’exécution des instructions serais :
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
Ligne 198 ⟶ 201 :
8: <<at L2>>
Et maintenant regardant le code optimiser :
i := 0
if i >= 100 goto L2
L1: a[i] := 0
Ligne 206 ⟶ 209 :
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
Ligne 216 ⟶ 219 :
6: <<at L2>>
Et comme on peut le constater, on élimine deux « goto » et donc deux initialisations du pipeline.
----
 
# 3 == Facteurs : ==
 
*=== A La machine elle- même : ===
 
Plusieurs choix de techniques d’optimisation sont basés sur les caractéristiques de la machine cible. C’est possible parfois de paramétrer ces différents facteurs qui dépendent de la machine, et de ce fait un compilateur peut optimiser plusieurs machines juste en changeant les paramètres. Le GCC est un parfait exemple de cette technique d’adaptation.
 
 
*=== B L’architecture du processeur cible : ===
 
;Le nombre de registres
• Le nombre de registres : Généralement, plus on a de registres, plus facile sera l’opération d’optimisation. En effet, les variables locales peuvent être enregistré dans les registres et n’ont pas dans la pile. En outre les résultats intermédiaires peuvent être sauvegardé dans les registres au lieu d’effectuer une opération d’écriture en suite une autre opération de lecture pour récupérer le résultat.
• RISC vs. CISC : Les instructions de CISC sont de longueurs variables. Et il y a une panoplie d’instructions possibles qui différent en temps d’exécution. En revanche les instructions RISC ont généralement la même longueur avec quelques exceptions. En plus, le nombre d’instructions par cycle est presque constant dans le cas où on ne considère pas la durée d’accès mémoire. Ceci dit les instructions CISC nous offrent une marge par rapport celle du RISC, pour optimiser certaines opérations. Ce qui reste à faire pour le compilateur est de savoir le coût des différentes instructions et de choisir la meilleure séquence (Voire optimisation sur des fenêtres).
;RISC vs. CISC
• Pipeline : Essentiellement, une pipeline utilise l’unité arithmétique et logique (ALU) pour exécuter plusieurs instructions en même temps et en différentes étapes : Décodage d’instruction, décodage d’adresse, lecture mémoire, lecture registre, calcul, écriture mémoire,… D’ailleurs, une instruction peut être dans l’écriture de mémoire pendant une autre effectue une lecture registre. Les conflits dans la pipeline se produisent quand une instruction dans une étape de la pipeline dépend du résultat d’une autre instruction qui est devant elle dans la pipeline et qui n’est pas encore totalement exécuté. Ces conflits causent un blocage du pipeline « Pipeline Stall » et une perte de temps dans lequel le processeur attend la résolution du conflit.
• RISC vs. CISC : Les instructions de CISC sont de longueurs variables. Et il y a une panoplie d’instructions possibles qui différent en temps d’exécution. En revanche les instructions RISC ont généralement la même longueur avec quelques exceptions. En plus, le nombre d’instructions par cycle est presque constant dans le cas où on ne considère pas la durée d’accès mémoire. Ceci dit les instructions CISC nous offrent une marge par rapport celle du RISC, pour optimiser certaines opérations. Ce qui reste à faire pour le compilateur est de savoir le coût des différentes instructions et de choisir la meilleure séquence (Voire optimisation sur des fenêtres).
Les optimisateurs peuvent ordonnancer et réorganiser les instructions pour éviter au mieux les blocages du pipeline.
;Pipeline
• Pipeline : Essentiellement, une pipeline utilise l’unité arithmétique et logique (ALU) pour exécuter plusieurs instructions en même temps et en différentes étapes : Décodage d’instruction, décodage d’adresse, lecture mémoire, lecture registre, calcul, écriture mémoire,… D’ailleurs, une instruction peut être dans l’écriture de mémoire pendant une autre effectue une lecture registre. Les conflits dans la pipeline se produisent quand une instruction dans une étape de la pipeline dépend du résultat d’une autre instruction qui est devant elle dans la pipeline et qui n’est pas encore totalement exécuté. Ces conflits causent un blocage du pipeline « Pipeline Stall » et une perte de temps dans lequel le processeur attend la résolution du conflit.
:Les optimisateurs peuvent ordonnancer et réorganiser les instructions pour éviter au mieux les blocages du pipeline.
 
;Le nombre d’unités fonctionnelles
• Le nombre d’unités fonctionnelles : Un processeur peut posséder plusieurs ALU et FPU (unité de calcul en virgule flottante). Cela permettra d’exécuter des instructions en parallèle. Ou en d’autres termes, cela nous permettra de mettre les instructions en pairs. Ici aussi un ordonnancement minutieux doit être effectué par le compilateur pour utiliser au mieux les ressources du plateforme utilisé. Cela requiert bien sur une connaissance approfondie d’une part des instructions et d’autre part du processeur utilisé.
 
*=== C L’architecture de la machine : ===
• Le nombre d’unités fonctionnelles : Un processeur peut posséder plusieurs ALU et FPU (unité de calcul en virgule flottante). Cela permettra d’exécuter des instructions en parallèle. Ou en d’autres termes, cela nous permettra de mettre les instructions en pairs. Ici aussi un ordonnancement minutieux doit être effectué par le compilateur pour utiliser au mieux les ressources du plateforme utilisé. Cela requiert bien sur une connaissance approfondie d’une part des instructions et d’autre part du processeur utilisé.
 
;La taille et le type du cache
* C L’architecture de la machine :
• La taille et le type du cache : Quelques techniques d’optimisations, comme « loop unwiding », permettent d’augmenter la taille du code générer et en même temps vérifier de plus en plus le principe de localité.
;Le temps moyen d’accès mémoire/cache
• Le temps moyen d’accès mémoire/cache : En ayant connaissance de ce facteur, un compilateur a une connaissance des pénalités causées par les différents types d’opérations mémoire/cache. Ceci est pris compte dans des applications très spécialisées.
 
# 4 == Problèmes avec l’optimisation : ==
• La taille et le type du cache : Quelques techniques d’optimisations, comme « loop unwiding », permettent d’augmenter la taille du code générer et en même temps vérifier de plus en plus le principe de localité.
• Le temps moyen d’accès mémoire/cache : En ayant connaissance de ce facteur, un compilateur a une connaissance des pénalités causées par les différents types d’opérations mémoire/cache. Ceci est pris compte dans des applications très spécialisées.
----
 
# 4 Problèmes avec l’optimisation :
Au début des histoires des compilateurs, leurs optimisations n’ont pas été plus efficaces que l’optimisation manuelle faite par les programmeurs. Et avec l’avancement de la technologie des compilateurs, le résultat est devenu plus efficace qu’une optimisation effectuer par le programmeur. Et ceci est plus évident avec les architectures RISC et les processeurs VLIW (Very Long Instruction Word).
En revanche, un compilateur qui peut garantir à sa sortie le plus rapide (ou petit) programme compilé est fondamentalement impossible à implémenter. Ceci est du au problème d’arrêt. En effet, selon cette dernière théorie, le compilateur ne peut pas décider automatiquement et dans tout les cas si le programme compilé va se terminer. Cette théorie démonte donc qu’il n’existera jamais de compilateur capable de vous dire que le programme que vous avez écrit est mal conçu et qu’il bouclera indéfiniment.
 
En revanche, un compilateur qui peut garantir à sa sortie le plus rapide (ou petit) programme compilé est fondamentalement impossible à implémenter. Ceci est du au problème d’arrêt. En effet, selon cette dernière théorie, le compilateur ne peut pas décider automatiquement et dans tout les cas si le programme compilé va se terminer. Cette théorie démonte donc qu’il n’existera jamais de compilateur capable de vous dire que le programme que vous avez écrit est mal conçu et qu’il bouclera indéfiniment.
 
[[Catégorie:Informatique]]
--[[Utilisateur:Dajdouj|Dajdouj]] 9 février 2007 à 10:54 (CET)