Optimisation des boucles imbriquées

informatique , et plus particulièrement en conception de compilateurs , l'optimisation des boucles imbriquées (LNO) est une technique d'optimisation qui applique un ensemble de transformations aux boucles afin d' optimiser leur localité , de paralléliser leur exécution ou de réduire la surcharge liée à l'imbrication des boucles. ( On parle de boucles imbriquées lorsqu'une boucle est incluse dans une autre.) Une application classique consiste à réduire la latence d'accès à la mémoire ou la bande passante du cache nécessaire à la réutilisation de ce dernier pour certains algorithmes d'algèbre linéaire courants .

La technique utilisée pour produire cette optimisation est appelée pavage de boucle , également connue sous le nom de blocage de boucle ou exploitation à ciel ouvert et échange .

cache jusqu'à leur réutilisation. Ce partitionnement permet de diviser un grand tableau en blocs plus petits, ce qui adapte les éléments du tableau accédés à la taille du cache, améliorant ainsi sa réutilisation et réduisant les contraintes liées à sa taille.

Une boucle ordinaire

interchangeabilité des boucles ) joue également un rôle important dans l'amélioration des performances du cache. Le blocage explicite nécessite de choisir une taille de tuile en fonction de ces facteurs. À l'inverse, les algorithmes insensibles au cache sont conçus pour utiliser efficacement ce dernier sans blocage explicite.

Exemple : multiplication matricielle

De nombreuses opérations mathématiques complexes sur ordinateur consacrent une grande partie de leur temps à la multiplication matricielle . L'opération consiste à :

C = A×B

où A, B et C sont des tableaux N×N. Les indices, pour la description suivante, sont de la forme C[row][column].

La boucle de base est :

additionneur actif malgré sa latence de plusieurs cycles, le code doit mettre à jour plusieurs accumulateurs en parallèle.

Les machines ne peuvent généralement effectuer qu'une seule opération de mémoire par multiplication-addition , les valeurs chargées doivent donc être réutilisées au moins deux fois.

Les systèmes de mémoire PC classiques ne peuvent supporter qu'un double mot de 8 octets pour 10 à 30 multiplications-additions en double précision, les valeurs chargées dans le cache doivent donc être réutilisées plusieurs fois.

La boucle initiale calcule le résultat pour chaque élément de la matrice de résultats un par un. En calculant simultanément un petit bloc d'éléments, la boucle suivante réutilise deux fois chaque valeur chargée, de sorte que la boucle interne effectue quatre chargements et quatre multiplications-additions, résolvant ainsi le problème n° 2. En utilisant simultanément quatre accumulateurs, ce code permet de maintenir un additionneur à virgule flottante unique, d'une latence de 4, occupé presque en permanence (problème n° 1). Cependant, le code ne résout pas le troisième problème. (Il ne traite pas non plus le nettoyage nécessaire lorsque N est impair. Ces détails seront omis dans la suite de la discussion.)

ISA . Si le processeur ne possède pas suffisamment de registres, le compilateur planifiera des chargements et des stockages supplémentaires pour répartir les données des registres dans la pile, ce qui ralentira l'exécution de la boucle par rapport à une boucle par blocs plus courte.

La multiplication matricielle, comme de nombreux autres programmes, peut être limitée par la bande passante mémoire. L'utilisation d'un plus grand nombre de registres permet au compilateur et au programmeur de réduire les besoins en bande passante mémoire. C'est pourquoi les fabricants de processeurs RISC , qui souhaitaient concevoir des machines plus parallèles que les processeurs x86 et 68000 à usage général, ont adopté des fichiers de registres à virgule flottante de 32 entrées .

Le code ci-dessus n'exploite pas efficacement le cache. Lors du calcul d'une bande horizontale de résultats C, une bande horizontale de A est chargée, ainsi que la matrice B entière. Pour l'ensemble du calcul, C est stocké une seule fois (ce qui est optimal), A est chargé une seule fois dans le cache (en supposant qu'une bande de A puisse y être placée avec une bande de B), mais B est chargé N/ib fois, où ib est la taille de la bande dans la matrice C, soit un total de N³ ^/ ib chargements de mots doubles depuis la mémoire principale. Dans le code ci-dessus, ib vaut 2.

L'étape suivante pour réduire le trafic mémoire consiste à maximiser la valeur de `ib`. Celle-ci doit être supérieure à la valeur de « balance » renvoyée par les flux. Dans le cas d'un système Pentium 4 à 2,8 GHz utilisé pour cet exemple, cette valeur est de 16,5. Le deuxième exemple de code ci-dessus ne peut être étendu directement, car cela nécessiterait un nombre beaucoup plus important de registres accumulateurs. C'est pourquoi la boucle est bloquée sur `i`. (Techniquement, il s'agit en fait du deuxième blocage de `i`, le premier étant un blocage par un facteur 2.)

transferts mémoire. B est toujours transféré N/ib fois, pour transferts. Tant que

2*N/kb + N/ib < N/balance

Le système de mémoire de la machine suivra la cadence de l'unité de calcul en virgule flottante et le code s'exécutera à pleine performance. Le cache de 16 Ko du Pentium 4 est légèrement insuffisant : si l'on choisissait ib=24 et kb=64, 12 Ko du cache seraient utilisés, évitant ainsi sa saturation. Ceci est souhaitable pour permettre le passage des données des tableaux C et B. Ces valeurs correspondent à moins de 20 % de la vitesse de calcul en virgule flottante maximale du processeur.

Voici le code avec la boucle kbloquée.

isolent probablement l'itération `kk == 0` des autres kkitérations afin de supprimer l'instruction `if` de la iboucle. C'est là l'un des avantages de ces compilateurs : s'il est simple de coder les cas simples de cette optimisation, maintenir l'exactitude de tous les détails lors de la duplication et de la transformation du code est un processus complexe et sujet aux erreurs.

La boucle ci-dessus n'atteindra que 80 % des opérations en virgule flottante maximales sur le système d'exemple lorsqu'elle est bloquée par la taille du cache L1 de 16 Ko. Ses performances seront moindres sur des systèmes dont la mémoire est encore plus déséquilibrée. Heureusement, le Pentium 4 dispose d'un cache de niveau 2 à large bande passante de 256 Ko (ou plus, selon le modèle), en plus du cache de niveau 1. Le choix est donc possible :

Ajustez la taille des blocs du cache de niveau 2. Cela sollicitera fortement la capacité du processeur à traiter simultanément un grand nombre d'instructions, et il est fort probable qu'il ne puisse pas exploiter pleinement la bande passante du cache de niveau 2.
Bloquez à nouveau les boucles, une fois encore, pour les tailles de cache de niveau 2. Avec un total de trois niveaux de blocage (pour le fichier de registres, pour le cache L1 et pour le cache L2), le code minimisera la bande passante requise à chaque niveau de la hiérarchie mémoire . Malheureusement, ces niveaux de blocage supplémentaires engendreront une surcharge de boucle accrue, qui, pour certaines tailles de problèmes et sur certains matériels, peut s'avérer plus coûteuse en temps que les limitations matérielles liées à la capacité du matériel à transférer les données depuis le cache L2.

Au lieu d'optimiser spécifiquement un algorithme pour une taille de cache particulière, comme dans le premier exemple, un algorithme insensible au cache est conçu pour exploiter tout cache disponible, quelle que soit sa taille. Il tire ainsi automatiquement parti de deux niveaux de hiérarchie mémoire, voire plus, si possible. Des algorithmes de multiplication matricielle insensibles au cache sont connus.