LA MEMOIRE CACHE
ST Magazine N°45 - octobre 1990
Philippe Dorvillier


On en parle de plus en plus, et il fallait bien revenir sur cette notion fondamentale, surtout avec notre numéro spécial sur le TT. Pendant plusieurs années, les constructeurs d'équipements informatiques ont bâti leur cheval de bataille publicitaire autour de la capacité mémoire et de la vitesse de leur machine. Mais on en est arrivé à un point où les processeurs supportent des horloges de 40, voire 50MHz, alors que le temps d ’accès aux mémoires dynamiques n’a pas vraiment évolué ou alors entraîne un important surcoût financier (pour les meilleures 70ns). On a donc vu apparaître un autre type de solution : les systèmes à mémoire-cache.


MAIS LE CACHE, C'EST QUOI ?

C'est une mémoire très rapide, qui peut être intégrée au microprocesseur (et c'est le cas la plupart du temps), et de ce fait les accès mémoires qui prenaient un temps horriblement long ont été fortement raccourcis (merci, Mr Spock !). Par exemple, le cache du MC68030, de chez Motorola, a une capacité de 2x256 octets (256 pour le Cache Instructions et 256 pour le Cache Données). Mais le cache peut aussi être externe (voir ligure 1), en étant réalisé à partir de mémoires statiques très rapides. fig1C'est ainsi que l'on trouve des systèmes avec lA MÉMOIRE CACHE des caches de 1Mo, au temps d'accès de 7 nanosecondes. Le seul problème de ce genre de système, c'est son prix ! En fait, les constructeurs se sont aperçus que dans un programme, lorsque le processeur allait chercher une information (octets, mots, longs mots) en mémoire, il y avait de fortes chances pour que le prochain chargement soit l'information qui est juste derrière la première. Donc, au lieu de charger une information, on en charge plusieurs et on les stocke dans un bloc du cache. Il faut aussi savoir que souvent un processeur utilise la même information plusieurs fois dans le même programme. Si l'information est lue ou écrite 10000 fois dans un programme, cela provoque 10000 accès au bus et, en admettant qu'un cycle bus prenne 4 cycles d'horloge, le processeur aura perdu 40000 cycles d'horloges... Par contre, si l'information est présente dansle cache, il n'y a plus qu’un seul accès au‘ bus pour “cacher" l'information et un pour la remettre dans la mémoire au cas où celle-ci a été modifiée, ce qui procure un gain de 9998 accès au bus. Il y a aussi un autre avantage très important : si, dans un programme, une boucle est effectuée 2000 fois et en admettant qu'elle soit composée de 6 instructions, elle provoque 2000x6 accès au bus. Si les 6 instructions sont cachées, cela réduit les accès au bus au nombre de 6. Les constructeurs ont ainsi réussi à réduire très sérieusement le nombre d'accès au bus.

ET ÇA FONCTIONNE COMMENT ?

Lors d'une extraction d'instruction par le processeur, deux cas se présentent :
 
- dans le premier, l'information est présente dans le cache et le processeur l'obtient immédiatement sans accès au bus ;

— dans le deuxième, l'information est absente du cache et c'est le contrôleur de cache qui va aller chercher l'information dans la mémoire du système, puis la fournir au processeur.

Il faut aussi savoir que certains contrôleurs de cache ne se contentent pas seulement de charger l'information que veut le processeur, mais aussi les x suivantes (x dépendant de la taille d'un bloc du cache). Ainsi, dans le cas où le processeur doit chercher l'information suivante, après le traitement de la première, celle-ci est déjà présente dans le cache. Il existe deux types de contrôleurs, ceux où le bloc d'information est chargé sur ordre logiciel et ceux où cet ordre est géré par le hardware. Voyons maintenant les différents types de caches.

1) LES CACHES ASSOCIATIFS
fig2
Dans ce type de caches, on va mémoriser l'adresse plus l'information contenue à cette adresse. Ainsi, lorsque le processeurveut prendre une donnée en mémoire, le contrôleur de cache va comparer l'adresse fournie par le processeur et les adresses contenues dans sa mémoire. Le nombre de comparaisons dépend donc de la capacité du cache. Si l'une des comparaisons est positive. le contrôleur foumit l'information au processeur. Dans le cas contraire, le contrôleur va chercher l'information dans la mémoire, la foumit au proœsseur et la stocke dans l'un des blocs du cache. Lorsque le contrôleur va placer une information dans la mémoire cache, il faut qu'il détermine quel bloc il peut occuper (donc effacer) sans causer de problèmes, et surtout il ne doit pas prendre un bloc que le processeur a modifié avant d'avoir replacé ce bloc dans la mémoire système. Ce type de cache a l'avantage d'être plutôt facile à mettre en oeuvre, mais du fait des comparaisons d'adresses, il est relativement “lent".


2) LES CACHES À ADRESSAGE DIRECT
fig3
Ici, il suffit d’une seule comparaison pour savoir si l'information est présente dans la mémoire cache. Le cache est découpé en deux zones, la partie adresse et la partie donnée (comme pour le type de cache précédent). Le principe consiste à découper la mémoire du système en x zones égales. Pour prendre un exemple, divisons 16 Mo par 256. cela donne 64 Ko, le résultat de cette opération étant la taille du cache. Il faut aussi savoir que la zone adresse est séparée en deux :
- la zone index qui représente un des blocs parmi les 64 kilos adressables du cache ;
La zone étiquette qui représente un des blocs mémoire parmis les 256

Maintenant, que se passe-t-il lors d'une recherche d'information ? Le contrôleur va séparer en deux parties l'adresse fournie par le processeur (par exemple, pour l'adresse s01 FF40 l'étiquette sera 01 et l'index FF40). Puis il va comparer l'étiquette avec celle qui se trouve à l'endroit pointé par l'index. Si elles sont égales, le contrôleur fournit la donnée au processeur. Dans le cas contraire, le contrôleur prend la donnée en mémoire, la donne au processeur, la place à l'adresse FF4O de la mémoire-cache et modifie l'étiquette à la même adresse en la remplacant par 01.


3) Et enfin, nous trouvons les caches à “adressage direct partiellement associatifs”...
fig4

Si vous avez compris le système de gestion du cache précédent, vous n’aurez pas de mal pour celui-là. En fait, le cache reprend la même structure que le précédent pour l'étiquette et l'index, mais en la répétant x fois. Nous dirons que le cache est divisé en “sous-caches". ll est donc possible d'avoir pour un même index des valeurs différentes, pour l'étiquette et la donnée. De toutes les facons, il est logique que l'étiquette soit différente car, dans le cas contraire, le cache aurait mémorisé deux fois la même information. Lors d'une extraction d'instruction par le processeur, le contrôleur va comparer, comme pour le type de cache n-2, l'étiquette du cache et celle qui lui est donnée par le processeur. Mais ici le contrôleur va faire ça pour tous les sous-caches, le nombre de comparaisons dépend donc directement du nombre de sous-caches. Cette méthode offre un pourcentage de réussite (trouver l'information dans le cache) plus grand que pour les deux autres, mais la complexité du contrôleur de cache est plus élevée. De plus, lorsque la recherche est infructueuse et qu'il faut mettre l'information en provenance de la mémoire dans celle du cache, il faut choisir dans quel sous-cache détruire le bloc :

1) la solution la plus simple étant de prendre un bloc au hasard ;

2) la deuxième serait de prendre le bloc le moins utilisé ;

3) prendre une structure du type FlFO (First In First Out).


Sur le MC68030, la taille du champ de donnée est de 4 mots, c'est-à-dire 16 octets, et pour que le contrôleur puisse charger ces 16 octets à partir de la mémoire vers le cache, Motorola a mis en place un mode de chargement appelé “mode RAFALE" ou “mode BURST”, qui permet le chargement d'un bloc en très peu de temps.

Mais le cache peut aussi poser des problèmes. Par exemple, dans le cas où le processeur est entouré de boîtiers périphériques (gestion série, parallèle, SCSI...), les registres internes du composant gérant le périphérique sont lus de temps en temps par le processeur. A chaque lecture d'un registre, le contrôleur va charger x octets suivant ce registre, ce qui peut poser des problèmes puisqu'il faut savoir que certains registres ne sont accessibles qu'en écriture et vice-versa. De plus, si la valeur du registre est stockée dans le cache, il est fort probable que le boîtier ait modifié la valeur de son registre alors qu'à la prochaine lecture, le processeur va relire la valeur dans le cache sans qu'elle ait été modifiée.

Pour résoudre ce problème, il suffit de regrouper, dans une même partie de la mémoire, les boîtiers dont les informations ne doivent pas être placées dans le cache, et de definir cette partie comme une zone non CACHABLE au niveau de la MMU (voir figure 5). fig5Pour ceux qui auraient un trou de mémoire, la MMU est le composant qui gère la mémoire (Memory Management Unit) et qui permet. entre autres, de définir des zones non-cacnaoles, mais aussi de découper la mémoire pour des problèmes de système multitâche. Mais abandonnons cette digression. et revenons à nos problèmes (NDLR: dans le cas du ST, le composant appelé MMU ne fait rien de tout ça, et a donc un nom quelque peu usurpé, ce qui amène souvent à appeler les vraies MMUs des PMMUs - Paged Memory Management Unit - car elles effectuent une autre opération appellée la pagination, mais ceci sort du cadre de cet article).

Un deuxième problème se pose lorsque le système est en “Multi-prooesseur". Imaginons un instant que le premier processeur charge une partie de la mémoire dans son cache et effectue plusieurs opérations qui vont modifier les valeurs stockées dans le cache, et cela sans que le contrôleur n'ait remplacé ces informations dans la mémoire du système. Maintenant, le deuxième processeur demande le bus au premier et, une fois qu'il est passé maître du bus, transfère la même zone de mémoire dans son cache. Cela provoque alors une erreur de cohérence des caches. ll existe plusieurs possibilités pour régler ce problème :

1) les deux processeurs accèdent à une plage mémoire commune (appelée “mémoire globale"), qui sera définie comme non cachable au niveau des deux MMU (voir figure 6).
fig6
2) la deuxième solution serait d'identifier chaque bloc du cache par un bit indiquant si ses données ont été modifiées. Ainsi, avant de donner le bus au deuxième processeur, le premier devra transférer en mémoire système les blocs qui ont été modifiés.

Voilà. je pense avoir fait un tour d'horizon du fonctionnement des mémoires caches, et il ne s'agit là que d'un premier survol destiné à vous initier sans trop dapprofondissements techniques pour l'instant, d'autant que notre cahier Technologies Avancées vous proposera bientôt une étude complète. Il est sur que dans l'avenir, l'intégration, en matière de composant, permettra l'augmentation de la capacité mémoire des caches.


Philippe Dorvillers