Prélecture du cache

La prélecture du cache est une technique utilisée par les processeurs informatiques pour améliorer les performances d'exécution en récupérant des instructions ou des données de leur stockage d'origine dans une mémoire plus lente vers une mémoire locale plus rapide avant qu'elles ne soient réellement nécessaires (d'où le terme « prélecture »). d'une mémoire cache rapide et locale dans laquelle les données pré-extraites sont conservées jusqu'à ce qu'elles soient nécessaires. La source de l'opération de pré-extraction est généralement la mémoire principale . En raison de leur conception, l'accès aux mémoires cache est généralement beaucoup plus rapide que l'accès à la mémoire principale , de sorte que la pré-extraction des données puis leur accès à partir des caches sont généralement beaucoup plus rapides que l'accès direct à partir de la mémoire principale. La pré-extraction peut être effectuée avec des instructions de contrôle de cache non bloquantes .

La prélecture du cache peut soit récupérer des données, soit des instructions dans le cache.

• La prélecture des données récupère les données avant qu'elles ne soient nécessaires. Étant donné que les modèles d'accès aux données présentent moins de régularité que les modèles d'instructions, la prélecture précise des données est généralement plus difficile que la prélecture des instructions.
• La prélecture des instructions récupère les instructions avant qu'elles ne doivent être exécutées. Les premiers microprocesseurs grand public à utiliser une certaine forme de prélecture des instructions étaient l' Intel 8086 (six octets) et le Motorola 68000 (quatre octets). Ces dernières années, tous les processeurs hautes performances utilisent des techniques de prélecture.

La prélecture du cache peut être réalisée soit par du matériel, soit par du logiciel.

• La prélecture basée sur le matériel est généralement réalisée en ayant un mécanisme matériel dédié dans le processeur qui surveille le flux d'instructions ou de données demandées par le programme en cours d'exécution, reconnaît les prochains éléments dont le programme pourrait avoir besoin en fonction de ce flux et les pré-récupère dans le cache du processeur.
• La prélecture basée sur un logiciel est généralement réalisée en demandant au compilateur d'analyser le code et d'insérer des instructions de « prélecture » supplémentaires dans le programme pendant la compilation elle-même.

• Les tampons de flux ont été développés sur la base du concept de « schéma OBL (one block lookahead) » proposé par Alan Jay Smith .
• Les tampons de flux sont l'une des techniques de prélecture matérielle les plus courantes. Cette technique a été initialement proposée par Norman Jouppi en 1990 et de nombreuses variantes de cette méthode ont été développées depuis. L'idée de base est que l' adresse d'échec de cache (et les adresses suivantes) sont récupérées dans un tampon séparé de profondeur . Ce tampon est appelé tampon de flux et est séparé du cache. Le processeur consomme ensuite les données/instructions du tampon de flux si l'adresse associée aux blocs pré-récupérés correspond à l'adresse demandée générée par le programme exécuté sur le processeur. La figure ci-dessous illustre cette configuration :

• Chaque fois que le mécanisme de prélecture détecte un échec sur un bloc de mémoire, par exemple A, il alloue un flux pour commencer à précharger les blocs successifs à partir du bloc manqué. Si le tampon de flux peut contenir 4 blocs, alors le processeur préchargera A+1, A+2, A+3, A+4 et les conservera dans le tampon de flux alloué. Si le processeur consomme ensuite A+1, il sera alors déplacé « vers le haut » du tampon de flux vers le cache du processeur. La première entrée du tampon de flux sera désormais A+2 et ainsi de suite. Ce modèle de prélecture de blocs successifs est appelé prélecture séquentielle . Il est principalement utilisé lorsque des emplacements contigus doivent être préchargés. Par exemple, il est utilisé lors de la prélecture d'instructions.
• Ce mécanisme peut être étendu en ajoutant plusieurs « tampons de flux » de ce type, chacun d'entre eux conservant un flux de prélecture distinct. Pour chaque nouvel échec, un nouveau tampon de flux serait alloué et fonctionnerait de manière similaire à celle décrite ci-dessus.
• La profondeur idéale du tampon de flux est quelque chose qui fait l'objet d'expérimentations par rapport à divers repères et dépend du reste de la microarchitecture impliquée.

Ce type de prélecture surveille le delta entre les adresses des accès mémoire et recherche des modèles en son sein.

Dans ce modèle, des accès mémoire consécutifs sont effectués sur des blocs séparés par des adresses. Dans ce cas, le pré-récupérateur calcule le et l'utilise pour calculer l'adresse mémoire pour la pré-extraction. Par exemple : si le est 4, l'adresse à pré-extraire serait A+4.

Dans ce cas, le delta entre les adresses des accès mémoire consécutifs est variable mais suit toujours un modèle. Certaines conceptions de préchargeurs exploitent cette propriété pour prédire et précharger les accès futurs.

Cette classe de préchargeurs recherche des flux d'accès à la mémoire qui se répètent dans le temps. Par exemple, dans ce flux d'accès à la mémoire : N, A, B, C, E, G, H, A, B, C, I, J, K, A, B, C, L, M, N, O, A, B, C, ... ; le flux A, B, C se répète dans le temps. D'autres variantes de conception ont tenté de fournir des implémentations plus efficaces et plus performantes.

Les applications informatiques génèrent une variété de modèles d'accès. Les architectures de processeur et de sous-système de mémoire utilisées pour exécuter ces applications clarifient encore davantage les modèles d'accès à la mémoire qu'elles génèrent. Par conséquent, l'efficacité et l'efficience des schémas de prélecture dépendent souvent de l'application et des architectures utilisées pour les exécuter. Des recherches récentes se sont concentrées sur la création de mécanismes collaboratifs pour utiliser de manière synergique plusieurs schémas de prélecture pour une meilleure couverture et une meilleure précision de prélecture.

La prélecture dirigée par le compilateur est largement utilisée dans les boucles comportant un grand nombre d'itérations. Dans cette technique, le compilateur prédit les futurs échecs de cache et insère une instruction de prélecture en fonction de la pénalité d'échec et du temps d'exécution des instructions.

Ces pré-extractions sont des opérations mémoire non bloquantes, c'est-à-dire que ces accès mémoire n'interfèrent pas avec les accès mémoire réels. Ils ne modifient pas l'état du processeur et ne provoquent pas de défauts de page.

L’un des principaux avantages de la prélecture logicielle est qu’elle réduit le nombre d’échecs de cache obligatoires.

L'exemple suivant montre comment une instruction de prélecture serait ajoutée au code pour améliorer les performances du cache .

Considérez une boucle for comme illustré ci-dessous :

pour ( int i = 0 ; i < 1024 ; i ++ ) { tableau1 [ i ] = 2 * tableau1 [ i ]; }

À chaque itération, le i ^-ème élément du tableau « array1 » est consulté. Par conséquent, le système peut pré-extraire les éléments qui seront consultés dans les itérations futures en insérant une instruction « prefetch » comme indiqué ci-dessous :

pour ( int i = 0 ; i < 1024 ; i ++ ) { prélecture ( tableau1 [ i + k ]); tableau1 [ i ] = 2 * tableau1 [ i ]; }

Ici, la vitesse de pré-extraction dépend de deux facteurs, la pénalité de cache miss et le temps nécessaire pour exécuter une seule itération de la boucle for . Par exemple, si une itération de la boucle prend 7 cycles pour s'exécuter et que la pénalité de cache miss est de 49 cycles, alors il devrait y en avoir - ce qui signifie que le système doit pré-extraire 7 éléments plus loin. Avec la première itération, i sera 0, donc le système pré-récupère le 7ème élément. Maintenant, avec cet arrangement, les 7 premiers accès (i=0->6) seront toujours des échecs (sous l'hypothèse simplificatrice que chaque élément de array1 se trouve dans une ligne de cache distincte).

• Alors que la prélecture logicielle nécessite l'intervention d'un programmeur ou d'un compilateur , la prélecture matérielle nécessite des mécanismes matériels spéciaux.
• La prélecture logicielle ne fonctionne bien qu'avec des boucles où il y a un accès régulier au tableau, car le programmeur doit coder manuellement les instructions de prélecture, tandis que les prélectures matérielles fonctionnent de manière dynamique en fonction du comportement du programme au moment de l'exécution .
• La prélecture matérielle nécessite également moins de ressources CPU que la prélecture logicielle. Cependant, la prélecture logicielle peut atténuer certaines contraintes de la prélecture matérielle, ce qui conduit à des améliorations des performances.

Il existe trois mesures principales pour évaluer la prélecture du cache

La couverture est la fraction du total des échecs qui sont éliminés en raison de la prélecture, c'est-à-dire

où,

La précision est la fraction du total des pré-extractions qui ont été utiles, c'est-à-dire le rapport entre le nombre d'adresses mémoire pré-extraites qui ont été réellement référencées par le programme et le total des pré-extractions effectuées.

Bien qu'il puisse sembler qu'une précision parfaite puisse impliquer qu'il n'y ait aucun échec, ce n'est pas le cas. Les pré-extractions elles-mêmes peuvent entraîner de nouveaux échecs si les blocs pré-extraits sont placés directement dans le cache. Bien que ceux-ci puissent représenter une petite fraction du nombre total d'échecs observés sans aucune pré-extraction, il s'agit d'un nombre d'échecs non nul.

La définition qualitative de la rapidité est la rapidité avec laquelle un bloc est préchargé par rapport au moment où il est réellement référencé. Voici un exemple pour expliquer plus en détail la rapidité :

Considérez une boucle for dans laquelle chaque itération nécessite 3 cycles pour s'exécuter et l'opération de « prélecture » nécessite 12 cycles. Cela implique que pour que les données pré-récupérées soient utiles, le système doit démarrer les itérations de pré-récupération avant leur utilisation afin de maintenir la rapidité.