Optimisation qui recopie plusieurs fois le corps d'une boucle pour réduire le nombre d'itérations. Elle diminue le coût des branchements et des tests de compteur et facilite le réordonnancement des instructions, mais augmente la taille du code.
Nom japonais: ループ展開
« Déroulage de boucle (loop unrolling) » apparaît dans 5 questions d'entraînement réparties sur 2 thèmes, dont Compilateurs, Hiérarchie mémoire.
Domaine: Compilateurs
Une boucle qui additionne deux tableaux élément par élément effectue normalement, pour chaque élément, une incrémentation de compteur, une comparaison et un branchement conditionnel en plus du travail utile. Dérouler d'un facteur quatre écrit le corps quatre fois, traitant les éléments i à i+3 en un passage et incrémentant i de 4 : la boucle exécute quatre fois moins d'itérations et le surcoût n'est payé qu'une fois pour quatre éléments. Lorsque le nombre d'itérations n'est pas un multiple du facteur de déroulage, une courte boucle de reste traite les éléments restants. Les petites boucles dont le nombre d'itérations est une constante connue peuvent être entièrement déroulées.
Outre la réduction du surcoût des branchements et du compteur, le déroulage place plusieurs copies indépendantes du travail dans un même bloc de base, ce qui donne à l'ordonnanceur d'instructions du compilateur la liberté de les entrelacer. Un chargement d'une copie peut être lancé pendant que l'arithmétique d'une autre progresse, masquant les latences. Pour les réductions comme les sommes, dérouler avec plusieurs accumulateurs séparés brise une longue chaîne de dépendances unique ; en virgule flottante, cela modifie l'ordre des arrondis, si bien que les compilateurs ne le font que si c'est autorisé. Le déroulage fait aussi apparaître des groupes d'opérations pouvant être combinés en instructions vectorielles SIMD.
Chaque copie supplémentaire agrandit le code, ce qui peut faire sortir des boucles critiques du cache d'instructions, et un plus grand nombre de valeurs simultanées accroît la pression sur les registres, pouvant forcer des débordements en mémoire (spills) qui annulent le gain. Les processeurs modernes à exécution dans le désordre, dotés d'une prédiction de branchement précise, masquent déjà une grande partie du surcoût de boucle ; un déroulage poussé apporte donc souvent peu. Les compilateurs choisissent par conséquent les facteurs de déroulage de façon heuristique, et les programmeurs peuvent demander un comportement précis par des options de compilation ou des pragmas lorsque les mesures le justifient.
Le déroulage de boucle cible le surcoût de contrôle et la liberté d'ordonnancement. La réduction de force (strength reduction) est différente : elle remplace une opération coûteuse par une opération moins chère, par exemple en calculant i * 4 en ajoutant 4 à une variable distincte à chaque itération ou par un décalage. Le pavage de boucle (loop blocking ou tiling) restructure des boucles comme le produit matriciel pour travailler sur des blocs de la taille du cache et augmenter la réutilisation des données, s'attaquant aux défauts de cache plutôt qu'aux branchements. Les compilateurs appliquent souvent plusieurs de ces techniques ensemble à une même boucle.
Réponse : A. Le coût des tests de comptage et des branchements diminue, et les instructions sont plus faciles à réordonner
Le déroulage de boucle recopie par exemple quatre fois le corps de la boucle et divise par quatre le nombre d'itérations. Les instructions de test et de branchement diminuent, et les instructions des corps recopiés peuvent être combinées et réordonnées, ce qui permet de mieux masquer les latences des opérations. En contrepartie, le code grossit et peut saturer le cache d'instructions. Un corps réduit à une copie avec un code plus petit décrit l'inverse, et l'extraction de la boucle en fonction est une autre transformation.
Le déroulage de boucle est une optimisation, réalisée par le compilateur ou à la main, qui recopie plusieurs fois le corps de la boucle et réduit d'autant le nombre d'itérations, diminuant les mises à jour du compteur et les branchements et exposant davantage d'instructions à l'ordonnancement.
Non. Il augmente la taille du code et l'utilisation des registres, ce qui peut provoquer des défauts du cache d'instructions ou des débordements de registres ; et sur les CPU modernes, le surcoût de boucle restant est souvent faible : le bénéfice doit donc être mesuré.
Le déroulage recopie le corps de la boucle pour réduire le surcoût des branchements et augmenter le parallélisme d'instructions. Le pavage découpe l'espace d'itération en blocs de la taille du cache pour améliorer la réutilisation des données et réduire les défauts de cache.
Le déroulage de boucle recopie par exemple quatre fois le corps de la boucle et divise par quatre le nombre d'itérations.
Quel est le principal effet du déroulage de boucle (loop un…Une fonction comprend généralement plusieurs blocs de base, et la recopie du corps de boucle est le déroulage de boucle.
Quelle définition du bloc de base est correcte ?La recopie du corps de boucle est le déroulage de boucle, et le regroupement d'appels de fonction une autre optimisation.
Quel exemple de repliement de constantes (constant folding)…La recopie du corps en quatre exemplaires est le déroulage de boucle.
Dans la boucle ci-dessus, quelle transformation correspond …La réduction des branchements est l’objectif du déroulage de boucle, et la mémoire totale utilisée reste inchangée.
Quel est le but principal du blocage de boucles (tiling), u…Bloc de base Graphe de flot de contrôle Repli de constantes (constant folding) Réduction de force (strength reduction) Découpe (dicing) Allocation de registres Analyse lexicale Analyse syntaxique Arbre syntaxique abstrait (AST) Compilation JIT