Fonctionnement d'un ordinateur/Le préchargement

En raison de la localité spatiale, il est avantageux de précharger dans le cache des données/instructions 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, associé au cache, qui charger l'avance des données/instructions susceptibles d’être utilisées dans un avenir proche. 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.

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, séparés des prefetchers spécialisés dans les données. Nous allons ici nous concentrer sur les prefetchers spécialisés dans les données, avec seulement quelques parenthèses sur les prefetchers d'instructions. Il faut dire que parler du préchargement des instructions demande de parler des algorithmes de prédiction de branchement, ce qui fera l'objet d'un chapitre ultérieur.

Les problèmes à résoudre pour précharger une donnée/instruction

Précharger des données/instructions demande de faire plusieurs choses. La première est de prédire à l'avance quelles données/instructions seront utilisées dans le futur. Et cette prédiction d'adresse ne se fait pas de la même manière entre instruction et données.

Pour les instructions, cela revient à prédire quelles instructions seront exécutées dans le futur. Vous vous dites qu'il n'y a rien de plus simple : l'exécution des instruction est séquentielle, les instructions se suivent en mémoire, rien de bien compliqué. Mais il faut prendre en compte les branchements qui peuvent envoyer le programme n'importe où en mémoire. Et résoudre le problème des branchements demande de faire ce qui s'appelle de la prédiction de branchements, qu'on verra dans un chapitre dédié.

Pour les données, tout dépend de la manière dont les structures de données sont parcourues et tout dépend de la structure de donnée. Les tableaux sont la structure de donnée idéale pour le préchargement, comme on le verra plus tard, mais d'autres techniques fonctionnent pour d'autres structures de données.

Le second point est de décider quand précharger des données. Il ne faut pas que le préchargement marche sur les pieds des accès mémoire normaux. Est-ce qu'on précharge les données dès que possible quitte à retarder un accès mémoire normal, où attend-t-on que la mémoire soit libre pour faire le préchargement. Dans le second cas, il faut décider si le préchargement en vaut la peine. Peut-être que la mémoire ne sera libre que trop tard, à un moment où précharger ne fera que gagner quelques cycles, ce qui ne vaut pas le coup comparé aux inconvénients du préchargement. Mais le cas inverse, à savoir un préchargement trop anticipé, peut aussi donner des performances inférieures. Dans le pire des cas, une donnée chargée trop en avance sera évincée du cache avant d'être utilisée. Tout cela fera l'objet d'une section dédiée dans le chapitre.

Enfin, il faut prendre en compte que la donnée préchargée va prendre la place d'une autre donnée dans le cache. Il faut que ce remplacement en vaille la peine. Si la donnée préchargée l'est à tord, elle remplacera une donnée potentiellement plus utile. Il faut absolument éviter cette pollution de cache.

Les algorithmes de préchargement des données

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 tableau ou si elles sont dispersées, et comment elles sont 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.

L’utilisation du préchargement séquentiel pour les instructions

Le préchargement séquentiel est assez 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. Notons que par préchargement des instructions, on veut parler du chargement des instructions dans le cache d'instruction L1, à partir du cache L2. Les niveaux de cache en-dessous n'utilisent pas vraiment de préchargement d'instruction.

Le seul bémol est qu'un prefetcher purement séquentiel gère mal les branchements. Le branchement envoie le programme à une adresse qui peut être n'importe où dans le programme, pas forcément dans la ligne de cache suivante. Les techniques pour résoudre ce problème sont assez complexes, sans compter qu'elles demandent d'utiliser de la prédiction de branchement, chose que nous n'avons pas encore abordé dans ce cours.

Branchements et préchargement séquentiel.

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 prédiction ;
• le préchargement par anticipation du program counter.

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 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.

Le préchargement anticipé (runahead prefetching)

La technique du préchargement anticipé (runahead prefetching) effectue du préchargement sur événement. Elle s'enclenche quand un évènement bloque le processeur, dans le sens où le programme est bloqué à un instant précis. Généralement, il s'agit d'un défaut de cache. Lors de cet évènement, le processeur sauvegarde son état, continue quand même l’exécution de manière spéculative, puis revient à la normale une fois le défaut de cache terminée. Pour le dire autrement, le processeur rentre dans un mode runahead dans lequel il exécute le programme alors qu'il ne devrait pas, avant de revenir à la normale.

Le programme exécuté en mode runahead génère des adresses à lire/écrire, les envoie au cache de données, ce qui précharge les données associées. Tout ce qui a eu lieu pendant le mode runahead est effacé, ce qui fait que l’exécution en mode runahead n'a pas eu d'impact sur les registres ou les unités d’exécution. Du moins, c'est le cas à un détail près : les données et instructions ont été préchargées dans le cache.

Toujours est-il que tout doit se passer comme si ces instructions exécutées en avance n'avaient jamais eu lieu. Pour cela, le processeur sauvegarde les registres à l'entrée du mode runahead, pour les restaurer en sortie, une fois le défaut de cache terminé. Pour éviter tout problème, les lectures s’exécutent en mode runahead, mais pas les écritures (pour éviter de modifier des données alors qu'on n'aurait pas dû).

Un problème qui survient avec cette technique est la gestion des lectures et de leurs dépendances. Généralement, une lecture est suivie d'instruction qui utilisent son résultat, pareil pour certaines écritures. Ainsi, si une lecture déclenche un défaut de cache et démarre un runahead, il se peut que des instructions s’exécutant en mode runahead dépendent du résultat de la lecture fautive. En soi, cela ne pose pas de problèmes d'éxecuter des instructions à tord ou avec des résultats invalides : le pire qui peut arriver est des préchargements inutiles, vu que le processeur restaure son état normal en sortie du mode runahead. Mais il faut quand même gérer la situation.

Une solution possible serait d'interrompre le mode runahead quand le processeur détecte ce genre de situation, mais cela rendrait le mode runahead quasiment inutile tellement ce genre de situation est fréquente. Mais il y a une solution alternative : marquer certains registres comme étant invalides. La lecture qui a déclenché le défaut de cache marque son registre de destination comme invalide. Et cette valeur invalide se propagera d'instruction en instruction. Typiquement, dès qu'une instruction lit un registre invalide, elle marquera le registre de résultat comme invalide. Les adresses marquées comme invalides ne sont pas utilisées pour démarrer des lectures ou écritures, afin d'économiser des préchargements inutiles.

Pour marquer les registres comme invalides, il suffit de leur rajouter un bit invalid qui indique si le résultat est valide ou non. Il faut aussi gérer la propagation du statut invalide d'une instruction à l'autre. Cela ne pose aucun problème pour les instructions dont les opérandes et la destination sont des registres : si une opérande a un statut invalide, la destination l'est aussi. Pour les autres instructions, les règles pour propager les valeurs invalides d'une instruction à l'autre sont assez complexes, surtout quand on prend en compte les écritures. Il faut aussi gérer les branchements et autres, mais passons. L'essentiel est que toutes les instructions qui dépendent de la lecture, directement ou indirectement, soient marquées invalides.

Dans les implémentations les plus simples, les écritures n'ont pas le droit d'écrire quoique ce soit en mémoire dans le mode runahead. Ainsi, si une lecture lit un résultat écrit il y a quelques instructions, elle est marquée comme invalide. Mais les implémentations plus élaborées évitent ce genre de cas. Si une écriture écrit une donnée valide, les lectures qui lisent cette données seront elles aussi marquées comme valides. Pour cela, il faut marquer les lignes de cache comme valides ou invalides, selon les opérandes des écritures. Une lecture marquera son registre de destination comme valide si la ligne de cache lue est valide, comme invalide si elle l'est ou qu'elle déclenche un défaut de cache. Une autre solution est de détourner les écritures dans un cache séparé, spécifique au mode runahead, dans lequel les écritures en mode runahead écrivent.

Notons que cette technique demande dans l'idéal d'utiliser des techniques de prédiction de branchement et les circuits associés, qui sont censés être vus dans les chapitres ultérieurs.

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.