Fonctionnement d'un ordinateur/Le préchargement

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.

Le préchargement des données

Il faut savoir que le préchargement ne fonctionne pas tout à fait de la même manière pour les données et les instructions. La raison est que l'organisation des données en mémoire diffère de celle des instructions, du moins pour les structures de données usuelles. Les processeurs modernes disposent de prefetchers spécialisés pour les instructions, que nous aborderons dans quelques chapitre, dans le chapitre sur le cache d'instruction. Dans ce chapitre, nous allons nous concentrer sur les prefetchers généraux, capables de précharger des données et/ou des instructions, ainsi que sur les prefetchers spécialisés dans les données.

Notons que le préchargement est fortement influencé par la manière dont les données sont représentées en mémoire. Le point principal est si elles sont regroupées ensemble dans un même bloc de mémoire ou si elles sont dispersées, et comment elles sont regroupées/dispersées. Il existe ainsi des prefetchers qui marchent assez bien pour certaines structures de données spécialisées et très mal sur d'autres. Les prefetchers pour les données sont surtout 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. Ils marchent un peu moins bien pour les autres structures de données, comme les listes chainées ou les arbres, mais il existe des prefetchers spécialisés pour ces dernières.

Les Prefetchers séquentiels

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.

Préchargement séquentiel.

Le préchargement séquentiel ne fonctionne que pour des accès à des adresses consécutives, pour des données avec une bonne localité spatiale. Pour les autres types d'accès, l'utilisation d'un prefetcher séquentiel est généralement contreproductive. Pour limiter la casse, les prefetchers évolués sont capables de distinguer 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 calcule une moyenne du nombre de blocs préchargés qui ont été utiles, à partir des n derniers blocs préchargés. En clair, il calcule 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ête temporairement de précharger. Autre solution : garder un historique des derniers accès mémoires pour vérifier s'ils accèdent à des adresses consécutives. Le processeur peut 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.

Les stream buffers

L'implémentation du préchargement séquentiel peut se faire de nombreuses façons. Mais la plus simple et la plus commune est celle des stream buffers. Elle utilise une mémoire FIFO séparée du cache, appelée le stream buffer, dans laquelle sont préchargés les blocs. Lors d'un défaut de cache, le bloc lu/écrit par le processeur est chargé depuis la mémoire et placé dans le cache. Les blocs suivants sont eux préchargés dans le stream buffer. Le stream buffer permet de précharger un certain nombre de blocs, fixe : 2, 3, 4 blocs, rarement plus. Si le processeur accède à un bloc préchargé, celui-ci sera lu directement depuis le stream buffer, pas depuis la mémoire ou le cache. L'usage de stream buffer est assez simple et n'entraine pas de modifications substantielles du cache, ce qui est un avantage certain. Pas besoin de modifier la politique de remplacement du cache, en cas de préchargement inutile, par exemple. De plus, le processeur peut avoir plusieurs stream buffer, ce qui permet d'effectuer du préchargement pour plusieurs défauts de cache. Un défaut de cache peut remplir un stream buffer, puis un autre défaut en remplir un autre, etc. Les performances sont alors d'autant plus grandes que le nombre et la taille des stream buffer sont élevés.

La toute première technique de ce genre est illustrée ci-dessous. Elle était pensée pour précharger des données dans le cache L1 d'un processeur, que ce soit pour précharger des données de la RAM dans le cache, ou pour précharger des données du cache L2 vers le cache L1. Mais cette technique s'adapte à toute forme de préchargement et à toute hiérarchie mémoire. On peut l'utiliser à tous les niveaux de la hiérarchie mémoire. Une version améliorée précharge les données dans le stream buffer non pas lors d'un défaut de cache, mais lors de chaque accès mémoire : tout accès à une donnée charge la donnée suivante dans le stream buffer. Mais nous en reparlerons plus bas, dans la section sur les évènements qui déclenchent le préchargement.

Technique des stream buffers.

Les accès par enjambées

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.

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.

L'algorithme de gestion des enjambées doit détecter les enjambées, déterminer leur taille de l’enjambée et 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 état où l'instruction n'effectue pas d'accès par enjambées, ainsi qu'un second état pour les instructions qui effectuent des accès par enjambées. 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, la ligne de cache est mise à jour en état "préchargement activé". Le prefetcher considère que la distance entre les deux adresses (celle du premier accès et celle du second) est l'enjambée, cette distance se calculant avec une simple soustraction.

Calcul de l’enjambée.

Néanmoins, cet algorithme voit souvent des accès par enjambées là où il n'y en a pas. Une solution à cela consiste à attendre un troisième accès avant de commencer le préchargement, afin de vérifier si l'enjambée calculée est la bonne. Lorsque l'instruction effectue son premier défaut de cache, l'entrée est initialisée 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.

Le préchargement selon les dépendances

Certaines applications ont besoin de structures de données qui permettent de supprimer ou d'ajouter un élément rapidement. On peut notamment citer les listes, les arbres et les graphes. Dans ces structures de données alternatives aux tableaux, les données sont souvent dispersées dans la 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. Les prefetechers précédents 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, il n'existe des techniques de préchargement adaptées pour ce genre de structures de données.

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. Pour résumer, 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).

Instruction productrice.

Instruction consommatrice.

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. Chaque ligne de celle-ci stocke les adresses du producteur et du consommateur. Reste que ces corrélations ne sortent pas de la 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. 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. À 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.

Le préchargement de Markov

Pour les structures de données plus évoluées, comme des arbres ou des graphes, la technique précédente 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. Pour gérer cette situation, on doit utiliser des prefetchers plus évolués, comme des prefetchers de Markov. Ils fonctionnent comme les précédents, sauf que la table de corrélations permet de mémoriser plusieurs correspondances, plusieurs adresses de successeurs. Dans certains prefetchers, toutes les adresses des successeurs sont préchargées. Mais sur d'autres, le prefetcher se débrouille pour prédire quelle sera la bonne adresse du successeurs. Pour cela, le prefetcher calcule, pour chaque adresse, la probabilité qu'elle soit accédée. À chaque lecture ou écriture, les probabilités sont mises à jour. Seule l'adresse de plus forte probabilité est préchargée.

Vu que la mémoire ne peut précharger qu'une seule donnée à la fois, certaines adresses sont 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é à la table de correspondance. 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.

Le préchargement par distance

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.

Le Tampon d’historique global

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ée de 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 (First In, First Out) 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.

Les variantes du tampon d’historique global

Des variantes du tampon d'historique global ont été 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.

La pollution du cache

Le prefetcher peut se tromper et précharger des données inutilement dans le cache. Et outre l'inutilité de charger des données qui ne servent à rien, cela éjecte aussi 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 permet de tirer parti au maximum de la mémoire cache, reste à savoir comment. Diverses solutions existent.

L'usage d'un Dirty bit

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 (Least Recently Used), on peut la mettre directement dans l'état « utilisée la moins récemment », ou « très peu utilisée ».

L'usage d'un cache spécialisé pour le préchargement

L'autre solution est de précharger les données non pas dans le cache, mais dans une mémoire dédiée au préchargement : un tampon de préchargement, aussi appelé prefetch buffer en anglais. C'est ce qui est utilisé dans le préchargement séquentiel avec les stream buffers, par exemple. Lors d'un accès au cache, on vérifie en parallèle si le tampon de préchargement contient la donnée demandée. 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. Si la donnée est disponible dans le tampon de préchargement, deux solutions sont possibles : on y accède directement dans le stream buffer, ou on la rapatrie dans le cache avant de relancer l'accès dans le cache.

Le filtrage de cache

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.

Le duel d’ensembles

Des chercheurs ont inventé des techniques plus complexes, dont la plus connue est le duel d'ensembles (set dueling). Dans leurs travaux, ils utilisent un cache associatif à plusieurs voies. Les 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 si la ligne chargée est considérée comme la moins récemment utilisée ou la plus récemment utilisée. La décision se fait selon les voies statiques qui ont le plus de défauts de cache : si les voies "moins récemment utilisée" 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.

Quand précharger ?

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.

Le préchargement sur événement

Le préchargement sur événement 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.

• Première solution : précharger le bloc suivant de manière systématique, 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 mémorise 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 dernier est automatiquement mis à zéro au bout d'un certain temps (typiquement au cycle d'horloge suivant). Le prefetcher se contente de charger le bloc qui suit la ligne de cache dont le bit vaut 1.

Préchargement anticipé.

Le préchargement par anticipation du program counter

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 détermine les adresses lues ou écrites par ces instructions anticipées. Les processeurs qui utilisent ce genre de techniques sont redoutablement rares. On trouve quelques articles de recherche sur le sujet, et quelques universitaires travaillent dessus. Mais aucun processeur commercial ne précharge ses données ainsi. Le processeur Rock de la compagnie Sun 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 continue 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û). Les lectures font des accès en avance, ce qui précharge les données accédées. 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 faut éviter que les 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 les écritures dans la mémoire.

Le préchargement par prédiction

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.