Optimisation de boucle

Dans la théorie des compilateurs , l'optimisation des boucles est le processus d'augmentation de la vitesse d'exécution et de réduction des frais généraux associés aux boucles . Elle joue un rôle important dans l'amélioration des performances du cache et l'utilisation efficace des capacités de traitement parallèle . La majeure partie du temps d'exécution d'un programme scientifique est consacrée aux boucles ; de ce fait, de nombreuses techniques d'optimisation des compilateurs ont été développées pour les rendre plus rapides.

Étant donné que les instructions à l'intérieur des boucles peuvent être exécutées de manière répétée, il n'est souvent pas possible de donner une limite au nombre d'exécutions d'instructions qui seront affectées par une optimisation de boucle. Cela pose des défis lors du raisonnement sur l'exactitude et les avantages d'une optimisation de boucle, en particulier les représentations du calcul optimisé et de la ou des optimisations effectuées.

L'optimisation de boucle peut être considérée comme l'application d'une séquence de transformations de boucle spécifiques (énumérées ci-dessous ou dans Transformations du compilateur pour le calcul haute performance ) au code source ou à la représentation intermédiaire , chaque transformation étant associée à un test de légalité. Une transformation (ou séquence de transformations) doit généralement préserver la séquence temporelle de toutes les dépendances si elle doit préserver le résultat du programme (c'est-à-dire être une transformation légale). L'évaluation de l'avantage d'une transformation ou d'une séquence de transformations peut être assez difficile dans cette approche, car l'application d'une transformation bénéfique peut nécessiter l'utilisation préalable d'une ou plusieurs autres transformations qui, à elles seules, entraîneraient une réduction des performances.

Les transformations de boucle courantes incluent :

• Fission ou distribution – la fission de boucle tente de diviser une boucle en plusieurs boucles sur la même plage d'index, mais chaque nouvelle boucle ne prend qu'une partie du corps de la boucle d'origine. Cela peut améliorer la localité de référence , à la fois les données consultées dans la boucle et le code dans le corps de la boucle.
• Fusion ou combinaison : cela combine les corps de deux boucles adjacentes qui itéreraient le même nombre de fois (que ce nombre soit connu ou non au moment de la compilation), à condition qu'elles ne fassent aucune référence aux données de l'autre.
• Échange ou permutation : ces optimisations échangent des boucles internes avec des boucles externes. Lorsque les variables de boucle sont indexées dans un tableau, une telle transformation peut améliorer la localité de référence, en fonction de la disposition du tableau.
• Inversion – cette technique transforme une boucle while standard en une boucle do/while (alias repeat/until  ) enveloppée dans une condition if , réduisant le nombre de sauts de deux pour les cas où la boucle est exécutée. Cela duplique la vérification de condition (augmentant la taille du code) mais est plus efficace car les sauts provoquent généralement un blocage du pipeline . De plus, si la condition initiale est connue au moment de la compilation et est connue pour être sans effet secondaire , la protection if initiale peut être ignorée.
• Mouvement de code invariant en boucle – cela peut améliorer considérablement l'efficacité en déplaçant un calcul de l'intérieur de la boucle vers l'extérieur de celle-ci, en calculant une valeur une seule fois avant le début de la boucle, si la quantité résultante du calcul sera la même pour chaque itération de boucle (c'est-à-dire une quantité invariante en boucle). Ceci est particulièrement important avec les expressions de calcul d'adresse générées par des boucles sur des tableaux. Pour une implémentation correcte, cette technique doit être utilisée avec l'inversion, car tout le code ne peut pas être déplacé en toute sécurité en dehors de la boucle.
• Parallélisation – il s'agit d'un cas particulier de parallélisation automatique qui se concentre sur les boucles, en les restructurant pour qu'elles fonctionnent efficacement sur des systèmes multiprocesseurs. Elle peut être effectuée automatiquement par des compilateurs ( parallélisation automatique ) ou manuellement (insertion de directives parallèles comme OpenMP ).
• Inversion – une optimisation subtile qui inverse l'ordre dans lequel les valeurs sont attribuées à la variable d'index. Cela peut aider à éliminer les dépendances et ainsi permettre d'autres optimisations. Certaines architectures utilisent des constructions de boucle au niveau de l'assemblage qui comptent dans une seule direction (par exemple, decrement-jump-if-not-zero [DJNZ] ).
• Planification : cela divise une boucle en plusieurs parties qui peuvent être exécutées simultanément sur plusieurs processeurs.
• Skewing – cette technique est appliquée à une boucle imbriquée itérant sur un tableau multidimensionnel, où chaque itération de la boucle interne dépend des itérations précédentes et réorganise ses accès au tableau de sorte que les seules dépendances se situent entre les itérations de la boucle externe.
• Pipelining logiciel – un type d’ exécution désordonnée d’itérations de boucle pour masquer les latences des unités de fonction du processeur.
• Fractionnement ou épluchage : cette méthode tente de simplifier une boucle ou d'éliminer les dépendances en la divisant en plusieurs boucles qui ont les mêmes corps mais qui itèrent sur différentes parties de la plage d'index. Un cas particulier est le peeling de boucle , qui peut simplifier une boucle avec une première itération problématique en effectuant cette itération séparément avant d'entrer dans la boucle.
• Tuilage ou blocage : réorganise une boucle pour parcourir des blocs de données dimensionnés pour tenir dans le cache.
• Vectorisation – tente d’exécuter autant d’itérations de boucle que possible en même temps sur un système SIMD .
• Déroulement – ​​duplique le corps de la boucle plusieurs fois, afin de diminuer le nombre de fois où la condition de boucle est testée et le nombre de sauts, ce qui peut dégrader les performances en altérant le pipeline d'instructions. Le déroulement complet d'une boucle élimine toute surcharge (à l'exception des récupérations d'instructions multiples et de l'augmentation du temps de chargement du programme), mais nécessite que le nombre d'itérations soit connu au moment de la compilation (sauf dans le cas d' une compilation juste à temps ). Il faut également veiller à ce que le recalcul multiple des variables indexées ne représente pas une surcharge plus importante que l'avancement des pointeurs dans la boucle d'origine.
• Unswitching – déplace une condition de l'intérieur d'une boucle vers l'extérieur de celle-ci en dupliquant le corps de la boucle et en plaçant une version de celle-ci à l'intérieur de chacune des clauses if et else de la condition.
• Sectionnement ou strip-mining – introduit pour les processeurs vectoriels , le sectionnement de boucle est une technique de transformation de boucle permettant d'activer les codages SIMD (instruction unique, données multiples) des boucles et d'améliorer les performances de la mémoire. Cela implique que chaque opération vectorielle soit effectuée pour une taille inférieure ou égale à la longueur vectorielle maximale sur une machine vectorielle donnée.

L'approche de transformation unimodulaire utilise une seule matrice unimodulaire pour décrire le résultat combiné d'une séquence de plusieurs des transformations ci-dessus. Au cœur de cette approche se trouve la vision de l'ensemble de toutes les exécutions d'une instruction dans n boucles comme un ensemble de points entiers dans un espace n -dimensionnel, les points étant exécutés dans l'ordre lexicographique . Par exemple, les exécutions d'une instruction imbriquée dans une boucle externe d'indice i et une boucle interne d'indice j peuvent être associées aux paires d'entiers ⁠ ⁠ . L'application d'une transformation unimodulaire correspond à la multiplication des points dans cet espace par la matrice. Par exemple, l'échange de deux boucles correspond à la matrice .

Une transformation unimodulaire est légale si elle préserve la séquence temporelle de toutes les dépendances ; mesurer l'impact sur les performances d'une transformation unimodulaire est plus difficile. Les boucles imparfaitement imbriquées et certaines transformations (comme le pavage) ne s'intègrent pas facilement dans ce cadre.

Le modèle polyédrique gère une classe plus large de programmes et de transformations que le cadre unimodulaire. L'ensemble des exécutions d'un ensemble d'instructions dans un ensemble de boucles éventuellement imparfaitement imbriquées est considéré comme l'union d'un ensemble de polytopes représentant les exécutions des instructions. Des transformations affines sont appliquées à ces polytopes, produisant une description d'un nouvel ordre d'exécution. Les limites des polytopes, les dépendances de données et les transformations sont souvent décrites à l'aide de systèmes de contraintes, et cette approche est souvent appelée approche basée sur les contraintes pour l'optimisation des boucles. Par exemple, une seule instruction dans une boucle externe ' for i := 0 to n ' et une boucle interne ' for j := 0 to i+2 ' est exécutée une fois pour chaque paire (i, j) telle que 0 <= i <= n et 0 <= j <= i+2 .

Encore une fois, une transformation est légale si elle préserve la séquence temporelle de toutes les dépendances . L'estimation des avantages d'une transformation, ou la recherche de la meilleure transformation pour un code donné sur un ordinateur donné, restent l'objet de recherches en cours au moment de la rédaction de cet article (2010).