Fonctionnement d'un ordinateur/Le préchargement

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

En raison de la localité spatiale, il est avantageux de précharger des données proches de celles chargées il y a peu. Ce préchargement (en anglais, prefetching), peut être effectué par le programmeur, à la condition que le processeur possède une instruction de préchargement. Mais celui-ci peut aussi être pris en charge directement par le processeur, sans implication du programmeur, ce qui a de nombreux avantages. Pour ce faire, le processeur doit contenir un circuit nommé prefetcher. Qui plus est, on peut utiliser à la fois des instructions de préchargement et un prefetcher intégré au processeur : les deux solutions ne sont pas incompatibles.

Préchargement des données[modifier | modifier le wikicode]

Certains prefetchers sont adaptés à l'utilisation de tableaux (des ensembles de données consécutives de même taille et de même type). Ils profitent du fait que ces tableaux sont souvent accédés case par case.

Prefetchers séquentiels[modifier | modifier le wikicode]

Les prefetchers séquentiels préchargent les données immédiatement consécutives de la donnée venant tout juste d'être lue ou écrite. Ils fonctionnent bien lorsqu'on accède à des données consécutives en mémoire, ce qui arrive souvent lors de parcours de tableaux. Dans le cas le plus simple, on précharge le bloc de mémoire qui suit immédiatement la dernière ligne chargée. L'adresse de ce bloc se calcule en additionnant la longueur d'une ligne de cache à la dernière adresse lue ou écrite. Ce qui peut être fait avec un seul bloc de mémoire peut aussi l'être avec plusieurs. Rien n’empêche de charger non pas un, mais deux ou trois blocs consécutifs dans notre mémoire cache. Mais attention : le nombre de blocs de mémoire chargés dans le cache est fixe. Cela fonctionne bien si l'on utilise des données avec une bonne localité spatiale.

Préchargement séquentiel.

Ces prefetchers ne fonctionnent que pour des accès à des adresses consécutives : si ce n'est pas le cas, l'utilisation d'un prefetcher séquentiel est contreproductive. Pour limiter la casse, les prefetchers sont capables de reconnaitre les accès séquentiels et les accès problématiques. Cette détection peut se faire de deux façons. Avec la première, le prefetcher va calculer une moyenne du nombre de blocs préchargés qui ont étés utiles, à partir des n derniers blocs préchargés. En clair, il va calculer le rapport entre le nombre de blocs qu'il a préchargés dans le cache et le nombre de ces blocs qui ont été accédés. Si jamais ce rapport diminue trop, cela signifie que l'on n’a pas affaire à des accès séquentiels : le prefetcher arrêtera temporairement de précharger. Autre solution : garder un historique des derniers accès mémoires et voir s'ils accèdent à des zones consécutives de la mémoire. Si ce n'est pas le cas, le prefetcher ne précharge pas. Le processeur peut même décider de désactiver temporairement le préchargement si jamais le nombre de blocs préchargés utilement tombe trop près de zéro.

Accès par enjambées[modifier | modifier le wikicode]

Certains accès, les accès par enjambées (ou stride access), se font sur des données séparées par une distance constante k. Ils ont comme origine les parcours de tableaux multidimensionnels, et de tableaux de structures/objets. Avec ce genre d'accès, un prefetcher séquentiel charge des données inutiles, ce qui est synonyme de baisse de performances. Mais certains prefetchers gèrent de tels accès à la perfection. Cela ne rend pas ces accès aussi rapides que des accès à des blocs de mémoire consécutifs, vu qu'on gâche une ligne de cache pour n'en utiliser qu'une petite portion, mais cela aide tout de même beaucoup.

Accès par enjambées.

Ces prefetchers conservent un historique des accès mémoires effectués récemment dans un cache : la table de prédiction de références (reference prediction table). Chaque ligne de cache associe à une instruction toutes les informations nécessaires pour prédire quelle sera la prochaine adresse utilisée par celle-ci. Elle stocke notamment la dernière adresse lue/écrite par l'instruction, l’enjambée, ainsi que des bits qui indiquent la validité de ces informations. L'adresse de l'instruction est dans le tag de la ligne de cache.

L'algorithme de gestion des enjambées doit :

  • déterminer la taille de l’enjambée ;
  • détecter les enjambées ;
  • précharger un ou plusieurs blocs.

Détecter les enjambées et déterminer leur taille peut se faire simultanément de différentes manières. La première considère que si une instruction effectue deux défauts de cache à la suite, elle effectue un accès par enjambées. Il s'agit là d'une approximation grossière, mais qui ne fonctionne pas trop mal. Avec cette méthode, une ligne de cache de la table de prédiction de référence peut avoir deux états : un où l'instruction n'effectue pas d'accès par enjambées, qui désactive le préchargement, ainsi qu'un second état pour les instructions qui effectuent des accès par enjambées qui lui l'active. La première fois qu'une instruction effectue un défaut de cache, une entrée lui est allouée dans la table de prédiction de références. La ligne est initialisée avec une enjambée inconnue en état "préchargement désactivé". Lors du second accès, l’enjambée est calculée et la ligne de cache est mise à jour en état "préchargement activé". Le calcul de l’enjambée s'effectue en soustrayant l'adresse précédente de l'adresse en cours.

Calcul de l’enjambée.

Néanmoins, cet algorithme a un petit problème : il arrive très souvent qu'il voie des accès par enjambées là où il n'y en a pas. Une solution à cela consiste à rajouter un état init. Lorsque l'instruction effectue son premier défaut de cache, l'entrée est initialisé dans l'état no prefetch. Lors du défaut de cache suivant, l’enjambée est calculée, mais le préchargement ne commence pas : l'entrée est placée dans l'état init. C'est lors d'un troisième défaut de cache que l’enjambée est recalculée, et comparée avec l’enjambée calculée lors des deux précédents défauts. Si les deux correspondent, un accès par enjambées est détecté, et le préchargement commence. Sinon, l'instruction n'effectue pas d'accès par enjambées : on place l'entrée en état no prefetch.

Calcul amélioré de l’enjambée, partie 2.

On peut améliorer l'algorithme précédent pour recalculer l’enjambée à chaque accès mémoire de l'instruction, et vérifier si celui-ci a changé. Si un changement est détecté, la prédiction avec enjambée est certainement fausse et on ne précharge rien. Pour que cet algorithme fonctionne, on doit ajouter un quatrième état aux entrées : « transitoire » (transient), qui stoppe le préchargement et recalcule l’enjambée.

Recalcul du préchargement à chaque défaut de cache.

Pour prédire la prochaine adresse, il suffit d'ajouter la longueur d’enjambée à l'adresse à lire ou écrire. Cette technique peut être adaptée pour précharger non seulement la prochaine adresse, mais aussi les n adresses suivantes, la énième adresse ayant pour valeur : adresse + n × enjambée. Évidemment, ces adresses à précharger ne peuvent pas être lues ou écrites simultanément depuis la mémoire. On doit donc les mettre en attente, le temps que la mémoire soit libre. Pour cela, on utilise un tampon de préchargement, qui stocke des requêtes de lecture ou d'écriture fournies par l'unité de préchargement.

Préchargement selon les dépendances[modifier | modifier le wikicode]

Certaines applications ont besoin de structures de données qui permettent de supprimer ou d'ajouter un élément rapidement. Pour cela, on doit utiliser des structures de données alternatives aux tableaux, dans lesquelles les données peuvent se retrouver à des endroits très éloignés en mémoire. Pour faire le lien entre les données, chacune d'entre elles sera stockée avec les adresses des données suivantes ou précédentes. On peut notamment citer les listes, les arbres et les graphes. Il va de soi que les méthodes précédentes fonctionnent mal avec ces structures de données, où les données ne sont pas placées à intervalle régulier en mémoire. Cela dit, ça ne veut pas dire qu'il n'existe pas de technique de préchargement adaptée pour ce genre de structures de données. En fait, il existe deux grandes techniques pour ce genre de structures de données, et quelques autres techniques un peu plus confidentielles.

La première de ces techniques a reçu le nom de préchargement selon les dépendances (dependence based prefetching). Elle ne donne de bons résultats que sur des listes. Prenons un exemple : une liste simplement chainée, une structure où chaque donnée indique l'adresse de la suivante. Pour lire la donnée suivante, le processeur doit récupérer son adresse, qui est placée à côté de la donnée actuelle. Puis, il doit charger tout ou partie de la donnée suivante dans un registre. Comme vous le voyez, on se retrouve avec deux lectures : la première récupère l'adresse et l'autre l'utilise. Dans ce qui va suivre, je vais identifier ces deux instructions en parlant d'instruction productrice (celle qui charge l'adresse) et consommatrice (celle qui utilise l'adresse chargée).

Avec le préchargement selon les dépendances, le processeur mémorise si deux instructions ont une dépendance producteur-consommateur dans un cache : la table de corrélations. Celle-ci stocke les adresses du producteur et du consommateur. Reste que ces corrélations ne sortent pas de cuisse de Jupiter : elles sont détectées lors de l’exécution d'une instruction consommatrice. Pour toute lecture, le processeur vérifie si la donnée à lire a été chargée par une autre instruction : si c'est le cas, l'instruction est consommatrice. Reste à mémoriser les adresses lues et l'instruction de lecture associée. Pour cela, le processeur contient une table de correspondances entre la donnée lue et l'adresse de l'instruction (le program counter) : la fenêtre de producteurs potentiels. Lors de l’exécution d'une instruction, il vérifie si l'adresse à lire est dans la fenêtre de producteurs potentiels : si c'est le cas, c'est qu'une instruction productrice a chargé l'adresse, et que l'instruction en cours est consommatrice. L'adresse des instructions productrice et consommatrice sont alors stockées dans la table de corrélations. A chaque lecture, le processeur vérifie si l'instruction est productrice en regardant le contenu de la table de corrélations. Dès qu'une instruction détectée comme productrice a chargé son adresse, le processeur précharge les données de l'instruction consommatrice associée. Lorsqu'elle s’exécutera quelques cycles plus tard, la donnée aura déjà été lue depuis la mémoire.

Préchargement de Markov[modifier | modifier le wikicode]

Pour gérer des structures de données plus évoluées, comme des arbres ou des graphes, la technique vue plus haut ne marche pas très bien. Avec ces types de données, chaque donnée a plusieurs successeurs, ce qui fait qu'une instruction consommatrice ne va pas toujours consommer la même adresse (celle-ci dépendant du successeur). Pour gérer cette situation, on doit utiliser des prefetchers plus évolués, comme des prefetchers de Markov. Ces prefetchers de Markov fonctionnent comme les précédents, sauf que la table de corrélations permet de mémoriser plusieurs correspondances, plusieurs adresses de successeurs. Chaque adresse se voit attribuer une probabilité, qui indique si elle a plus de chance d'être la bonne donnée à précharger que ses voisines. À chaque lecture ou écriture, les probabilités sont mises à jour. Dans certains prefetchers, seule l'adresse de plus forte probabilité. Mais dans d'autres, toutes les adresses de destination sont préchargées. Vu que la mémoire ne peut précharger qu'une seule donnée à la fois, certaines adresses sont alors mises en attente dans une mémoire tampon de préchargement. Lors du préchargement, le program counter de l'instruction qui initiera le préchargement sera envoyé à cette table. Cette table fournira plusieurs adresses, qui seront mises en attente dans le tampon de préchargement avant leur préchargement. L'ordre d'envoi des requêtes de préchargement (le passage de la mémoire tampon au sous-système mémoire) est déterminé par les probabilités des différentes adresses : on précharge d'abord les adresses les plus probables.

Préchargement par distance[modifier | modifier le wikicode]

Le gain apporté par les prefetchers vus auparavant est appréciable, mais ceux-ci fonctionnent mal sur des accès cycliques ou répétitifs, certes rares dans le cas général, mais présents à foison dans certaines applications. Ils apparaissent surtout quand on parcourt plusieurs tableaux à la fois. Pour gérer au mieux ces accès, on a inventé des prefetchers plus évolués, capables de ce genre de prouesses.

Accès mémoire cyclique sans enjambée.

Le préchargement par distance (distance prefetching), une adaptation du prefetcher du Markov, est un de ces prefetchers. Celui-ci n'utilise pas les adresses, mais les différences entre adresses accédées de manière consécutive, qui sont appelées des deltas. Ces deltas se calculent tout simplement en soustrayant les deux adresses. Ainsi, si j'accède à une adresse A, suivie par une adresse B, le préchargement par distance calculera le delta B - A, et l'utilisera pour sélectionner une entrée dans la table de correspondances. La table de correspondances est toujours structurée autour d'entrées, qui stockent chacune plusieurs correspondances, sauf qu'elle stocke les deltas. Cette table permet de faire des prédictions du style : si le delta entre B et A est de 3, alors le delta entre la prochaine adresse sera soit 5, soit 6, soit 7. L'utilité du prefetcher de Markov, c'est que la même entrée peut servir pour des adresses différentes.

Tampon d’historique global[modifier | modifier le wikicode]

Les techniques vues plus haut utilisent toutes une sorte de table de correspondances. L'accès à la table s'effectue soit en envoyant le program counter de l'instruction en entrée (préchargement par enjambées), soit l'adresse lue, soit les différences entre adresses. Ce qui est envoyé en entrée sera appelé l'index de la table, dans la suite de cette partie. Cette table stocke une quantité limitéede données, tirées de l'historique des défauts de cache précédents. En somme, la table stocke, pour chaque index, un historique des défauts de cache associés à l'index. Dans les techniques vues précédemment, chaque table stocke un nombre fixe de défauts de cache par index : le one block lookahead stocke une adresse par instruction, le stride stocke une enjambée et une adresse pour chaque instruction, le préchargement de Markov stocke une ou plusieurs adresses par instruction, etc. Dit autrement, l'historique a une taille fixe.

Vu que cette quantité est fixe, elle est souvent sous-utilisée. Par exemple, le préchargement de Markov limite le nombre d'adresses pour chaque instruction à 4, 5, 6 suivant le prefetcher. Certaines instructions n'utiliseront jamais plus de deux entrées, tandis que le nombre de ces entrées n'est pas suffisant pour d'autres instructions plus rares. La quantité d'informations mémorisée pour chaque instruction est toujours la même, alors que les instructions n'ont pas les mêmes besoins : c'est loin d'être optimal. De plus, le nombre de défauts de cache par index limite le nombre d'instructions ou d'adresses qui peuvent être prédites. De plus, il se peut que des données assez anciennes restent dans la table de prédiction, et mènent à de mauvaises prédictions : pour prédire l'avenir, il faut des données à jour. Pour éviter ce genre de défauts, les chercheurs ont inventé des prefetchers qui utilisent un tampon d’historique global (global history buffer). Celui-ci permet d’implémenter plusieurs techniques de préchargement. Les techniques précédentes peuvent s'implémenter facilement sur ces prefetchers, mais sans les défauts cités au-dessus.

Ces prefetchers sont composés de deux sous-composants. Premièrement, on trouve une mémoire tampon de type FIFO qui mémorise les défauts de cache les plus récents : l'historique global. Pour chaque défaut de cache, la mémoire FIFO mémorise l'adresse lue ou écrite dans une entrée. Pour effectuer des prédictions crédibles, ces défauts de cache sont regroupés suivant divers critères : l'instruction à l'origine du défaut, par exemple. Pour cela, les entrées sont organisées en liste chainée : chaque entrée pointe sur l'entrée suivante qui appartient au même groupe. On peut voir chacune de ces listes comme un historique dédié à un index : cela peut être l'ensemble des défauts de cache associés à une instruction, l'ensemble des défauts de cache qui suivront l'accès à une adresse donnée, etc. Généralement, les instructions sont triées à l'intérieur de chaque groupe dans l'ordre d'arrivée : l'entrée la plus récente contient le défaut de cache le plus récent du groupe. Ainsi, la taille de l'historique s'adapte dynamiquement suivant les besoins, contrairement aux prefetchers précédents où celui-ci tait de taille fixe.

Tampon d’historique global.

Reste que le processeur doit savoir où est l'entrée qui correspond au début de chaque liste. Pour cela, on doit rajouter une table de correspondances d'historiques, qui permet de dire où se trouve l'historique associé à chaque index. Cette table de correspondances (index → historique par index) a bien sûr une taille finie. En somme, le nombre d'entrées de cette table limite le nombre d'index (souvent des instructions) gérées en même temps. Mais par contre, pour chaque instruction, la taille de l'historique des défauts de cache est variable.

Tampon d’historique global avec sa table d’index.

La table de correspondances et l'historique global sont couplés avec un circuit de prédiction, qui peut utiliser chaque historique pour faire ces prédictions. Celui-ci peut aussi bien utiliser la totalité de l'historique global, que les historiques dédiés à un index. Faire une prédiction est simple demande d’accéder à la table de correspondances avec l'index adéquat : l'adresse lue ou écrite, le program counter de l'instruction d'accès mémoire, la distance entre cette adresse et la précédente, etc. Cela va alors sélectionner une liste dans l'historique global, qui sera parcourue de proche en proche par le circuit de prédiction, qui déterminera l'adresse à précharger en fonction de l'historique stocké dans la liste. Dans certains cas, l'historique global est aussi parcouru par le circuit de prédiction, mais c'est plus rare.

Ce tampon d’historique global permet d’implémenter un algorithme de Markov assez simplement : il suffit que la table d'index mémorise une correspondance adresse → début de liste. Ainsi, pour chaque adresse, on associera la liste d'adresses suivantes possibles, classées suivant leur probabilité. L'adresse au début de la liste sera la plus probable, tandis que celle de la fin sera la moins probable. Même chose pour le préchargement par distance : il suffit que l'index soit la distance entre adresse précédemment accédée et adresse couramment accédée. Dans ce cas, la liste des entrées mémorisera la suite de distances qui correspond. L'implémentation d'un préchargement par enjambées est aussi possible, mais assez complexe. Mais de nouveaux algorithmes sont aussi possibles.

Variantes du tampon d’historique global[modifier | modifier le wikicode]

Des variantes du tampon d'historique global ont étés inventées. On pourrait citer celle qui ajoute, en plus de l'historique global, des historiques locaux sous la forme de mémoires FIFO qui mémorisent les derniers accès effectués par une instruction. Plus précisément, si on dispose de n historiques locaux, chacun de ces n historiques mémorise l'historique des n dernières instructions d'accès mémoire les plus récentes. D'autres variantes, et notamment celle du cache d'accès aux données, ont ajouté une seconde table d'index :

  • la première table d'index prend en entrée le program counter de l'instruction à l'origine du défaut de cache ou de l'accès mémoire ;
  • la seconde prend en entrée l'adresse à lire ou écrire.
Cache d'accès aux données.

Préchargement d’instructions[modifier | modifier le wikicode]

Certains processeurs utilisent un prefetcher séparé pour les instructions, chose qui fonctionne à la perfection si le cache d'instruction est séparé des caches de données. Les techniques utilisés par les préfetchers d'instructions sont multiples et nombreux sont ceux qui réutilisent les techniques vues précédemment. Le préchargement séquentiel est notamment utilisé sur certains prefetchers relativement simples, de même que les prefetchers de Markov. Mais certaines techniques sont spécifiques au préchargement des instructions. Il faut dire que les branchements sont une spécificité du flux d'instruction, qui doit être prise en compte par le prefetcher pour obtenir un résultat optimal.

Préchargement séquentiel, le retour ![modifier | modifier le wikicode]

Le préchargement séquentiel est parfaitement adapté au préchargement des instructions d'un programme, vu que ses instructions sont placées les unes après les autres en mémoire. Sur certains processeurs, cette technique est utilisée non seulement pour charger des instructions dans le cache, mais aussi pour charger à l'avance certaines instructions dans le séquenceur. Sur ces processeurs, l'unité de chargement et de décodage sont séparées par une petite mémoire tapon de type FIFO : le tampon d’instructions (instruction buffer). En utilisant du préchargement séquentiel, on peut précharger des instructions dans le tampon d’instructions à l'avance, permettant ainsi de masquer certains accès au cache ou à la mémoire assez longs. Lorsqu'un branchement est décodé, ce tampon d’instructions est totalement vidé de son contenu. Mais un prefetcher purement séquentiel gère mal les branchements.

Branchements et préchargement séquentiel.

Target line prefetching[modifier | modifier le wikicode]

Il serait judicieux de trouver des moyens qui permettent de limiter la casse. Pour ce faire, il faudrait trouver un moyen de savoir où va nous faire atterrir notre branchement, de connaître l'adresse de destination. Néanmoins, le processeur peut supposer que l'adresse de destination est fixe : il suffit de s'en souvenir pour la prochaine fois. C'est ce qu'on appelle le target line prefetching.

Target line prefetching.

Pour implémenter cette technique, le prefetcher incorpore un cache pour stocker les adresses de destination des branchements déjà rencontrés. Plus précisément, ce cache contient les correspondance entre une ligne de cache, et la ligne de cache à charger à la suite de celle-ci. Pour plus d'efficacité, certains processeurs ne stockent pas les correspondances entre lignes de cache consécutives. Si jamais deux lignes de cache sont consécutives, on fera alors face à un défaut de cache dans cette mémoire qui stocke nos correspondances : le prefetcher utilisera alors automatiquement un préchargement séquentiel. Ainsi, la table de correspondances est remplie uniquement avec des correspondances utiles.

Préchargement du mauvais chemin[modifier | modifier le wikicode]

On peut améliorer la technique vue juste avant pour lui permettre de s'adapter au mieux aux branchements conditionnels. En plus de charger les instructions correspondant à un branchement pris, on peut aussi charger les instructions situées juste après le branchement. Comme ça, si le branchement n'est pas pris, les instructions suivantes seront disponibles quand même. On appelle cette technique le préchargement du mauvais chemin (wrong path prefetching).

Préchargement du mauvais chemin.

Pollution de cache[modifier | modifier le wikicode]

Le seul problème avec ces techniques de préchargement, c'est que le prefetcher peut se tromper et précharger des données inutilement dans le cache. On peut se retrouver avec quelques lignes de cache qui contiendront des données qui ne servent à rien, et qui auront éjecté des données potentiellement utiles du cache. C'est le phénomène de pollution de cache. Il va de soi que limiter au maximum cette pollution du cache est une nécessité si on veut tirer parti au maximum de notre mémoire cache, reste à savoir comment.

Dirty bit[modifier | modifier le wikicode]

Avec la première solution, la donnée chargée inutilement sera sélectionnée pour remplacement lors du prochain défaut de cache. Si le cache utilise un algorithme de sélection des lignes de cache de type LRU, on peut la mettre directement dans l'état « utilisée la moins récemment », ou « très peu utilisée ».

Duel d’ensembles[modifier | modifier le wikicode]

Des chercheurs ont inventé des techniques encore plus complexes, dont la plus connue est le duel d'ensembles (set dueling). Dans leurs travaux, ils utilisent un cache associatif à plusieurs voies. Ces voies sont réparties en deux groupes : statiques ou dynamiques. Les voies statiques ont une politique de remplacement fixée une fois pour toutes :

  • dans certaines voies statiques, toute ligne chargée depuis la mémoire est considérée comme la plus récemment utilisée ;
  • dans les autres voies statiques, toute ligne chargée depuis la mémoire est considérée comme la moins récemment utilisée.

Les voies restantes choisissent dynamiquement d'utiliser ou non l'optimisation vue plus haut (la ligne chargée est considérée comme la moins récemment utilisée) suivant les voies statiques qui ont le plus de défauts de cache : si les voies qui appliquent l'optimisation ont plus de défauts de cache que les autres, on ne l'utilise pas et inversement. Il suffit d'utiliser un simple compteur incrémenté ou décrémenté lors d'un défaut de cache dans une voie utilisant ou non l’optimisation.

Cache spécialisé pour le préchargement[modifier | modifier le wikicode]

L'autre solution est de précharger les données non pas dans le cache, mais dans une mémoire séparée dédiée au préchargement : un tampon de flux (stream buffer). Si jamais un défaut de cache a lieu, on regarde si la ligne de cache à lire ou écrire est dans le tampon de flux : on la rapatrie dans le cache si c'est le cas. Si ce n'est pas le cas, c'est que le tampon de flux contient des données préchargées à tort : le tampon de flux est totalement vidé, et on va chercher la donnée en mémoire. Dans le cas où le préchargement utilisé est un simple préchargement séquentiel, le tampon de flux est une simple mémoire FIFO.

Filtrage de cache[modifier | modifier le wikicode]

Une autre solution consiste à détecter les requêtes de préchargement inutiles en sortie du prefetcher. Entre les circuits d'adressage de la mémoire (ou les niveaux de cache inférieurs), et le prefetcher, on ajoute un circuit de filtrage, qui détecte les requêtes de préchargement visiblement inutiles et contreproductives. Les algorithmes utilisés par ce circuit de filtrage de cache varient considérablement suivant le processeur, et les travaux de recherche sur le sujet sont légion.

Quand précharger ?[modifier | modifier le wikicode]

Une problématique importante est de savoir quand précharger des données. Si on précharge des données trop tard ou trop tôt, le résultat n'est pas optimal. Pour résoudre au mieux ce problème, il existe diverses solutions :

  • le préchargement sur événement ;
  • le préchargement par anticipation du program counter ;
  • le préchargement par prédiction.

Préchargement sur événement[modifier | modifier le wikicode]

Une solution consiste à précharger quand certains événements spéciaux ont lieu. Par exemple, on peut précharger à chaque défaut de cache, à chaque accès mémoire, lors de l’exécution d'un branchement (pour le préchargement des instructions), etc. De nos jours, le préchargement est initié par les accès mémoire, de diverses manières.

  • La première solution consiste à précharger le bloc suivant de manière systématique : un préchargement a lieu lors de chaque accès mémoire.
  • Seconde solution : ne précharger que lors d'un défaut de cache. Ainsi, si j'ai un défaut de cache qui me force à charger le bloc B dans le cache, le prefetcher chargera le bloc immédiatement suivant avec.
  • Troisième solution : à chaque accès à un bloc de mémoire dans le cache, on charge le bloc de mémoire immédiatement suivant. Pour cela, on doit mémoriser quelle est la dernière ligne de cache qui a été accédée. Cela se fait en marquant chaque ligne de cache avec un bit spécial, qui indique si cette ligne a été accédée lors du dernier cycle d'horloge. Ce bit vaut 1 si c'est le cas, et vaut 0 sinon. Ce bit est automatiquement mis à zéro au bout d'un certain temps (typiquement au cycle d'horloge suivant). Le prefetcher se contentera alors de charger le bloc qui suit la ligne de cache dont le bit vaut 1.
Préchargement anticipé.

Préchargement par anticipation du program counter[modifier | modifier le wikicode]

Une seconde technique détermine les adresses à précharger en prenant de l'avance sur les instructions en cours d’exécution : quand le processeur est bloqué par un accès mémoire, l'unité de préchargement anticipe les prochaines instructions chargées. Le processeur pourra, à partir de ces prédictions, déterminer les adresses lues ou écrites par ces instructions anticipés. Les processeurs qui utilisent ce genre de techniques sont redoutablement rares à l'heure où j'écris ce tutoriel. On trouve pourtant quelques articles de recherche sur le sujet, et quelques universitaires travaillent dessus. Mais aucun processeur ne précharge ses données ainsi. Il y a bien le processeur Rock de la compagnie Sun, qui aurait pu faire l'affaire, mais celui-ci a été annulé au dernier moment.

La première technique se base sur un lookahead program counter initialisé avec le program counter lors d'un défaut de cache. Il est incrémenté à chaque cycle (et les branchements sont prédits) : ce lookahead program counter est mis à jour comme si l’exécution du programme se poursuivait, mais le reste du processeur est mis en attente. Les adresses fournies à chaque cycle par le lookahead program counter sont alors envoyées aux unités de préchargement pour qu'elles fassent leur travail. On peut aussi adapter cette technique pour que le lookahead program counter passe non d'une instruction à la prochaine à chaque cycle, mais d'un branchement au suivant.

On peut aussi citer le préchargement anticipé (runahead prefetching). Cette technique est utile si un défaut de cache a eu lieu et que le processeur n'est pas conçu pour pouvoir continuer ses calculs dans de telles conditions (pas de caches non bloquants, pas d’exécution dans le désordre, etc.). Dans un cas pareil, le processeur est censé stopper l’exécution de son programme. Mais avec le préchargement anticipé, il va continuer l’exécution des instructions de façon spéculative. Les lectures s’exécutent, mais pas les écritures (pour éviter de modifier des données alors qu'on n'aurait pas dû : cela permet d'effectuer des accès en avance et donc de précharger les données qu'elles manipulent. On continue ainsi jusqu’à ce que l'instruction qui a stoppé tout le processeur ait enfin reçu sa donnée.

Tout doit se passer comme si ces instructions exécutées en avance n'avaient jamais eu lieu. Dans le cas contraire, on a peut-être exécuté des instructions qu'on n’aurait peut-être pas dû, et cela peut avoir modifié des registres un peu trop tôt, ou mis à jour des bits du registre d'état qui n'auraient pas dû être modifiés ainsi. Il faut donc trouver un moyen de remettre le processeur tel qu'il était quand le défaut de cache a eu lieu. Pour cela, le processeur doit sauvegarder les registres du processeur avant d’exécuter spéculativement les instructions suivantes, et les restaurer une fois le tout terminé. Qui plus est, il vaut mieux éviter que ces instructions exécutées en avance puissent modifier l’état de la mémoire : imaginez qu'une instruction modifie une ligne de cache alors qu'elle n'aurait pas dû le faire ! Pour cela, on interdit à ces instructions d'écrire dans la mémoire.

Préchargement par prédiction[modifier | modifier le wikicode]

Certains prefetchers avancés essaient de déduire le moment adéquat pour précharger en se basant sur l'historique des accès précédents : ils en déduisent des statistiques qui permettent de savoir quand précharger. Par exemple, ils peuvent calculer le temps d'accès moyen entre un accès mémoire et un préchargement, et armer des chronomètres pour initialiser le préchargement en temps voulu.