Hiérarchie de mémoire
Un ordinateur dispose de différents types de mémoires qui se distinguent par leurs vitesses d'accès. Plus la mémoire est rapide plus elle coûte cher et plus la quantité disponible sur l'ordinateur est réduite. Les registres internes entiers ou flottants du micro-processeur constituent la mémoire à laquelle celui-ci accède le plus rapidement mais ils sont en nombre très limité. Il y a ensuite la mémoire vive, les disques durs puis les bandes qui sont très lentes mais qui permettent de stocker des quantités très importantes de données. Les caches sont intermédiaires entre les registres internes du micro-processeur et la mémoires vive. Ils sont faits de mémoire rapide mais ils sont de taille réduite par rapport à la mémoire centrale.
Hiérarchie de mémoire
Quand il est question de vitesse d'accès à la mémoire, il faut distinguer la latence et le débit. La latence est le temps qui s'écoule entre la demande des données et l'arrivée de la première donnée. Le débit mesure ensuite le flux de données transmises pendant le régime stable c'est-à-dire une fois la latence écoulée. Pour un disque dur, le temps de latence est relativement long car la tête de lecture doit être positionnée mécaniquement puis il faut encore attendre que le bon secteur se trouve sous la tête.
Depuis quelques temps, il s'est creusé un fossé entre la vitesse des micro-processeurs et la vitesse des mémoires dynamiques qui sont utilisées comme mémoire centrale des ordinateurs. Les mémoires SDRAM augmentent le débit mais réduisent peu la latence. Pour éviter que le micro-processeur perde du temps à attendre les données de la mémoire, des caches mémoire formés de mémoires statiques plus rapides sont intercalés entre le micro-processeur et la mémoire centrale. Le but est semblable à celui des caches disques permettant d'accélérer les accès aux disques durs.
Principe du cache
Le bon fonctionnement des caches est basé sur le principe de localité qui dit que le code et les données des programmes ne sont pas utilisées de manière uniforme. On constate souvent que 10% du code d'un programme contribue à 90% des instructions exécutées. On distingue deux types de localité. La localité temporelle indique que des éléments auxquels on a eu accès récemment seront probablement utilisés dans un futur proche. La localité spatiale indique que des éléments proches ont tendances à être référencés à des instants proches.
Le cache contient des copies de données qui sont en mémoire centrale. Avant tout accès à la mémoire, le processeur vérifie si les données ne sont pas présentes dans le cache. Auquel cas, le processeur utilise les données contenues dans le cache et n'accède pas à la mémoire. Sinon, il est nécessaire d'aller chercher les données en mémoire centrale.
Le cache est organisé par lignes. Chaque ligne contient une portion de 8 à 512 octets des données en mémoires et une étiquette (tag en anglais) qui est l'adresse de ces données en mémoire. Lorsque le micro-processeur veut accéder à la mémoire, il compare l'adresse avec les étiquettes des lignes du cache. S'il trouve l'adresse parmi les étiquettes, le micro-processeur utilise directement les données du cache. On parle alors de succès de cache. Sinon on parle de défaut de cache ou d'échec de cache (cache miss).
Organisation du cache
La réponse à un défaut de cache dépend de la nature de l'accès aux données. Dans le cas d'une lecture, les données sont chargées de la mémoire centrale dans le cache puis envoyées au micro-processeur. Ce chargement nécessite de libérer au préalable une ligne du cache pour y placer les nouvelles données. Le choix de la ligne à libérer est contrôlé par la politique de remplacement. Le chargement dans le cache des données à partir de la mémoire centrale implique un délai puisque cette dernière est beaucoup plus lente que le cache. Ce délai est parfois augmenté par le fait qu'il faille copier en mémoire le contenu de la ligne libérée.
Dans le cas d'un défaut de cache lors d'une écriture, deux techniques sont utilisées. La première technique est de faire comme pour une lecture en chargeant les données dans le cache puis de laisser le processeur écrire dans le cache. La seconde technique est d'écrire directement les données en mémoire. L'idée est que lors d'une écriture, le processeur n'a pas besoin d'attendre que celle-ci soit terminée pour continuer à travailler. Dans ce cas, les écritures sont mises en attentes dans un buffer afin de permettre à ces écritures de s'effectuer sans ralentir le processeur même en cas de plusieurs écritures consécutives.
Il existe plusieurs façons appelées politiques d'écriture de gérer les écritures dans les caches. La politique appelée write-through consiste à répercuter en mémoire centrale chaque écriture dans le cache. Chaque écriture dans le cache provoque alors une écriture en mémoire centrale. À l'opposé, la politique write-back retarde au maximum les écritures en mémoire centrale. Les données qui ont été écrites dans le cache sont écrites en mémoire centrale au moment où la ligne qui contient ces données est libérée. Pour savoir si cette écriture est nécessaire, chaque ligne contient un bit appelé dirty bit qui indique s'il y a eu au moins une écriture dans cette ligne.
Il existe aussi des politiques intermédiaires. Dans le cas de la politique write-through, les écritures à faire peuvent être mises en attente temporairement dans une file. Plusieurs écritures consécutives à la même adresse peuvent ainsi être répercutées par une seule écriture en mémoire. Ce mécanisme réduit les échanges avec la mémoire centrale. Dans le cas d'une politique write-back, le cache peut anticiper l'écriture en mémoire de certaines lignes modifiées du cache. Il profite de périodes sans échange avec la mémoire pour écrire certaines lignes dont le dirty bit est positionné. Cette technique permet d'éviter l'écriture de la ligne au moment celle-ci est libérée.
Un élément crucial de l'efficacité du cache est de retrouver rapidement si des données à une adresse mémoire sont déjà dans le cache. Afin d'accélérer cette recherche, le nombre de lignes où peuvent être mises les données à une adresse mémoire fixée est souvent réduit. Ce nombre ne dépend pas de l'adresse et il est appelé l'associativité du cache. Lorsque ce nombre est réduit à 1, c'est-à-dire que les données de chaque adresse peuvent être mises dans une seule ligne du cache, on parle de cache direct. Si au contraire l'associativité est égale au nombre de ligne du cache, c'est-à-dire que chaque donnée peut être mise dans n'importe quelle ligne du cache, le cache est dit complètement associatif. Si l'associativité est un entier n, on parle de cache n-associatif (n-way en anglais). Les caches sont très souvent directs, 2-, 3- ou 4-associatifs mais rarement plus. Le cache de niveau 1 de l'Athlon est par exemple 2-associatif.
Dans le cas des caches directs, la ligne où sont placées les données à une adresse sont généralement déterminés par des bits de poids faible de l'adresse. Cette approche a plusieurs avantages. D'une part le numéro de la ligne est très facile à déterminer à partir de l'adresse. D'autre part, les bits utilisés pour déterminer la lignes n'ont pas à être stocker dans l'étiquette, ce qui offre un gains de quelques bits.
Soit un cache direct composé de 256 lignes contenant chacune 16 octets. Comme chaque ligne contient 16 octets, les 4 bits de poids faible de chaque adresse servent uniquement à donner la position (offset) des données dans la ligne. Comme le cache a 256 lignes, les 8 bits suivants déterminent la ligne où les données doivent être placées.
Cache direct
L'avantage des caches directs est de simplifier au maximum la recherche des données dans le cache. Il suffit en effet de comparer l'étiquette de la ligne correspondante avec une partie de l'adresse. Comme la ligne est unique, il est même possible de commencer la lecture du cache pendant la comparaison de l'étiquette avec l'adresse. Si cette comparaison révèle un défaut de cache, cette lecture anticipée du cache est annulée.
Les caches directs souffrent par contre d'un problème. Si un programme utilise simultanément deux parties de la mémoire qui doivent aller dans la même ligne de cache, il peut se produire de nombreux défauts de cache.
Dans le cas des caches n-associatifs, l'organisation du cache est similaires aux caches directs. À chaque adresse correspond n lignes consécutives du cache au lieu d'une. L'indice de la première ligne est encore déterminé par des bits de poids faible de l'adresse. On appelle généralement ensemble les blocs de mémoire ayant même indice.
Pour n égal à 2 ou 4, un cache n-associatif se révèle presqu'aussi performant qu'un cache direct ayant 2 ou 4 fois plus de mémoire. Par contre, au delà de 8, le cache est pénalisé par le temps pris par la recherche des données dans le cache puisqu'il faut comparer une partie de l'adresse avec n étiquettes. On remarque en outre que les caches complètement associatifs ont des performances comparables aux caches 8-associatifs.
Lorsque le cache n'est pas direct et que survient un défaut de cache, les données doivent être placées dans une des lignes du cache déterminées par l'adresse. Il reste alors à choisir quelle ligne libérer pour les nouvelles données. Il existe plusieurs façons de procéder à ce choix qui sont appelées politiques de remplacement. L'objectif de ces politiques est de minimiser le nombre de défauts de cache, en essayant de prévoir au mieux les données qui seront utilisées par le micro-processeur.
Ces différentes politiques de remplacement sont bien sûr un compromis entre leur performance et le surcoût de calculs qu'elles impliquent. Comme ces calculs doivent être réalisés au niveau des circuits du cache, ils sont nécessairement simples. Les politiques favorisent la libération d'une ligne où il n'y a eu aucune écriture. Ce choix économise l'écriture en mémoire centrale des données contenues dans la ligne libérée.
Les deux politiques les plus couramment utilisées sont le tirage aléatoire et la politique dite du moins récemment utilisé (Least Recently Used). Le tirage aléatoire consiste à choisir au hasard une des lignes possibles. L'avantage de cette politique est de minimiser le surcoût de calcul tout en donnant des performances raisonnables. La seconde politique choisit la ligne à laquelle le dernier accès est le plus ancien. L'idée sous-jacente est que cette ligne a une probabilité plus faible d'être utilisée à l'avenir. En particulier, les données qui ne sont plus utilisées par le micro-processeur disparaissent du cache. En fait, ce sont le plus souvent des approximations de cette politique qui sont utilisées en pratique.
Lorsqu'il y a trop de défauts de cache, les performances s'effondrent. Le cache fonctionne alors alors à la vitesse de la mémoire centrale ou même plus lentement en raison des surcoûts de traitement. Beaucoup de recherche a été consacré à la réduction du nombre de défauts de cache. Les défauts de caches sont généralement classés en trois catégories.
Pour un meilleur compromis entre le prix de la mémoire cache et son efficacité, on utilise plusieurs niveaux de cache. On parle alors de hiérarchie de cache. La plupart des ordinateurs performants utilisent 3 à 4 niveaux de cache. Le cache de niveau 1 est le plus près du micro-processeur. Il est petit mais fait de mémoire très rapide. Le cache de niveau 2 est de taille plus grande mais fait de mémoire moins rapide. Le cache de niveau 3 est encore plus grand mais fait de mémoire encore mois rapide. Le cache de niveau 1 est directement intégré au processeur. Le cache de niveau 2 est souvent dans le même boîtier que le micro-processeur ce qui permet un large bus entre les deux. Le bus de niveau 3 est en général sur la carte mère du processeur.
Hiérarchie de caches
Le cache de niveau 1 est souvent organisé en deux caches distincts, un pour les instructions et un autre pour les données. Deux bus permettent alors au micro-processeur d'accéder simultanément aux deux caches. Dans le cas d'une architecture avec un pipeline, cette organisation est indispensable pour éviter certains aléas structurels. En outre, les accès aux instructions ou aux données se comportent de manière assez différente. La séparation des caches autorise des optimisations différentes pour les deux caches.
La figure ci-dessous présente l'architecture à trois niveaux de caches du micro-processeur Alpha 21164.
Hiérarchie de caches du micro-processeur
Alpha 21164