Optimisation des compilateurs/Les optimisations liées à la hiérarchie mémoire

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Optimisation des boucles[modifier | modifier le wikicode]

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