Architecture des processeurs 6: Mémoire cache

Le processeur ne correspond qu’à la partie opérationnelle du système. Ainsi, pour avoir un système pleinement fonctionnel, il est également nécessaire de l’associer à une ou plusieurs mémoires afin de stocker les différentes instructions et données. Généralement, ces composants sont bien plus lents que le processeur lui-même, ce qui peut impacter les performances de l’ensemble du système.

Sur cette page, nous allon étudier le fonctionnement des mémoires caches, des mémoires intermédiaires permettant de réduire les limitations de la mémoire principale. À l’aide de simulations, nous verrons comment les temps d’accès peuvent varier selon les opérations effectuées. Nous verrons également l’impact du placement des données en mémoire, par exemple lors de la manipulation de tableaux ou matrices.

Analyse en simulation

Pour les différentes analyses des smulations de cette page, nous aurons besoin de retrouver deux types d’informations à partir du chronogramme: le temps d’accès mémoire (utile pour distinguer un hit d’un miss) et l’état d’une ligne de cache.

Temps d’accès mémoire

Afin de mesurer le temps nécessaire pour effectuer un accès mémoire depuis le processeur, le plus simple est de se placer au niveau des ports mémoires (instruction et / ou donnée). Cela permet de s’abstraire de la plupart des autres mécanismes de la microarchitcture pouvant influencer nos mesures. En se plaçant à cet endroit-là, on peut précisément détecter quand une demande est effectuée à la mémoire, et quand la réponse correspondante est reçue.

Sur le chronogramme, vous trouvez les signaux des ports mémoires dans Pipeline, esprectement dans imem et dmem. À l’intérieur, vous trouverez plusieurs groupes de signaux:

• req les signaux pour l’envoi d’une demande du processeur vers la mémoire.
• write les signaux pour l’envoi d’une donnée à écrire du processeur vers la mémoire.
• read les signaux pour la réception d’une donnée lue de la mémoire vers le processeur.

Chaque groupe de signaux est organisé autour d’une transaction en poignée de main (handshake). Pour cela, deux signaux sont toujours présents: valid indique si un envoi est en cours par l’émetteur et ready indique si le récepteur est prêt à la recevoir. Un échange n’est validé que quand les deux signaux sont simultanément à 1 en fin de cycle. Sinon, il est nécessaire de patienter au moins un cycle supplémentaire.

Nous allons ici prendre le cas d’un accès mémoire pour une donnée (port dmem) en lecture réalisé à l’adresse 0x0c000304. Pour connaître le temps d’accès réel, il va donc falloir mesurer la différence de temps (cycles) entre le moment où la requêtes a été acceptée (groupe de signaux req) et le moment où la réponse a été reçue (groupe de signaux read).

Sur l’image ci-dessus, le curseur indique le moment où la requête à l’adresse 0x0c000304 est envoyée par le processeur (valid = 1) et acceptée par la mémoire cache (ready = 1). Le chronogramme nous indique également que cette opération a lieu au cycle 1290.

Cette requête étant une deamnde de lecture, la réponse correspondante sera ici la prochaine donnée reçue par les signauc read. Sur cette nouvelle image, le curseur indique maintenant le moment où la réponse est envoyée par la mémoire (valid = 1) et acceptée par le processeur (ready = 1). Le chronogramme nous indique également que cette opération a lieu au cycle 1313.

Au final, le temps d’accès mémoire a ici duré $1313 - 1290 = 23$ cycles. En sachant qu’un hit devrait mener à un accès d’un seul cycle (aucun ralentissement), on peut donc supposer ici que l’on observe un cache miss.

État d’une ligne de cache

Pour analyser le contenu d’une mémoire cache à un instant donné, il peut être nécessaire de vérifier l’état d’une ligne. Pour cela, le chronogramme rassemble les signaux de chaque ligne en groupe (par exemple Line 0), eux-mêmes rassemblés par sous-ensemble (par exemple set 0) au sein de chaque mémoire cache (par exemple L1D). L’image suivante représente l’évolution des différents signaux pour une seule ligne.

Ces signaux étant propres à l’implémentation simulée. Voici leurs significations:

• valid (tag) indique la validité du tag stocké actuellement. Si le signal est à 1, alors l’emplacement est occupé et le tag est valide. Sinon, l’emplacement est libre. Ce bit est particulièrement utile pour indiquer si une ligne est présente ou non.
• valid (line) indique la validité du contenu de la ligne. Si le signal est à 1, alors le contenu est valide. Sinon, le contenu n’est pas disponible. Ce bit est particulièrement utile pour indiquer que le contenu n’est pas encore prêt, par exemple quand il est en train d’être chargé.
• tag indique le tag de la ligne correspondante.
• line indique le contenu de la ligne entière.
• address indique l’adresse de base de la ligne entière (valeur du tag + numéro du sous-ensemble + décalage à 0). Ce signal n’est présent qu’en simulation pour le debogage: il n’existe pas réellement dans l’implémentation car il serait inutile: le signal de tag suffit.

À partir de ces informations et du chronogramme précédent, on peut donc analyser l’état de ligne ainsi:

1. Avant le cycle 89, valid (tag) est à 0: cela signifie que l’emplacement est libre car aucune ligne n’y est stockée.
2. Au cycle 89, valid (tag) passe à 1: l’emplacement vient d’être alloué pour la ligne ayant le tag 0x0c0000 (soit l’adresse 0x0c000000 ici).
3. Jusqu’au cycle 102, valid (line) reste à 0: cela signifie que les opérations pour charger la ligne depuis le niveau de mémoire supérieur sont toujours en cours.
4. À partir du cycle 102, valid (line) est à 1: le contenu de la ligne est donc valide et disponible dans line.

Accès mémoire

Pour les différentes simulations réalisées sur cette page, nous allons à présent utiliser le langage C. L’intérêt majeur va être de faciliter l’utilisation de structure mémoire telles que des tableaux ou des matrices. Nous allons voir comment le compilateur traduit cela en opérations en langage d’assemblage.

Initialement, la variable var est déclarée ici avec la ligne volatile uint32_t var; Le mot-clé volatile permet d’indiquer au compilateur que la variable associée est susceptible dêtre modifiée par un autre programme ou mécanisme matériel.

Pour les simulations qui suivent, on utilisera cette fonctionalité afin de agrantir que les opérations mémoires seront exécutées par le processeur.

Principe de localité

Le rôle d’une mémoire cache est de conserver à l’intérieur des copies de certaines parties de la mémoire principale afin de les rendre plus rapidement accessibles au processeur. Cependant, de par leurs tailles réduites, ces mémoires ne peuvent copier toute la mémoire principale simultanément. Ainsi, lors d’un accès mémoire passant par une mémoire cache, deux scénarios deviennent donc possibles:

• La donnée demandée est présente dans la mémoire cache. Celle-ci peut donc répondre rapidement: c’est ce qu’on appelle un cache hit.
• La donnée demandée n’est pas,présente dans la mémoire cache. Des opérations supplémentaires sont alors nécessaires pour aller récupérer la donnée dans la mémoire principale avant de répondre à la requête initiale: c’est ce qu’on appelle un cache miss.

Le choix des données placées dans la mémoire cache devient donc essentiel dans le but de réduire les temps d’accès. À partir d’observations générales sur l’exécution des programmes, il est cependant possible de déduire certains comportements liés aux accès mémoires effectués. Dans les faits, ceux-ci ne sont pas entièrement aléatoires et donc des anticipations sont possibles. On regroupe ces observations sous le nom de principe de localité, qui peut être déclinée en deux concepts: la localité temporelle et la localité spatiale.

Localité temporelle

Le concept de localité temporelle est l’observation que lorsque qu’une zone mémoire est utilisée, il y a de plus grandes chances qu’elle soit ré-utilisée dans un futur proche. C’est le cas des instructions placées dans des boucles ou fonctions, ou alors des variables elles-mêmes manipulées par plusieurs opérations. Ce fonctionnement est à l’origine même de l’intérêt des mémoires caches: lorsqu’une donnée est utilisée, celle-ci est copiée afin d’accélérer de futurs utilisations.

Pour les simulations qui suivent, on considèrera qu’aucune opération n’est effectuée dans la fonction func.

Localité spatiale

Le concept de localité spatiale est l’observation que lorsque une zone mémoire est utilisée, il y a de plus grandes chances que les zones mémoires proches le soient également dans un futur proche. C’est le cas des instructions exécutées linéairement (sans redirection du flot d’exécution) mais aussi des données placées dans un même tableau.

Pour tenir compte de ce fonctionnement, les mémoires caches sont conçus pour manipuler des blocs de plusieurs octets de mémoire appelés ligne de cache. Ainsi, lorsqu’un accès est effectué sur un ou plusieurs octets d’une même ligne, c’est l’ensemble de la ligne qui est copiée dans la mémoire cache. De ce fait, les accès dans un futur proche aux autres octets de la ligne seront également accélérés.

Pour les simulations qui suivent, on considèrera qu’aucune opération n’est effectuée dans la fonction func.

Organisation interne

Afin de limiter la latence lors de la vérification des lignes, les mémoires caches sont généralement organisées en interne par ensemble ou sous-ensembles. À partir des bits d’index de l’adresse, l’ensemble correspondant est ensuite sélectionné statiquement: seuls les emplacements qu’il contient doivent être vérifiés.

Politique de remplacement

Une fois tous les emplacements d’une mémoire cache occupés, celle-ci doit pouvoir continuer à s’adapter aux besoin des différents programmes exécutés. Le cache doit donc alors être capable de supprimer d’anciennes lignes pour les remplacer par des nouvelles. Au sein de chaque ensemble d’une même mémoire, le choix de la ligne à remplacer dépend de la politique de remplacement implémentée.

Une politique de remplacement est un algorithme implémenté dans le matériel permettant d’effectuer un choix de ligne. Il existe plusieurs types d’implémentations parmi lesquelles:

• Least-Recently Used (LRU) qui sélectionne la ligne ayant été utilisée le moins récemment. C’est une application directe du principe de localité temporelle.
• Pseudo Least-Recently Used (PLRU) qui vise à se rapprocher d’un fonctionnement en LRU en réduisant le coût matériel.
• First-In First-Out (FIFO) qui sélectionne la première ligne ayant été ramenée dans la mémoire cache.

Ordre des accès

Lorsque l’on effectue de nombreux accès mémoires, les méooires caches peuvent s’avérer insuffisantes pour contenir toutes les données manipulées. Il peut alors être nécessaire de prendre en compte la répartition en mémoire pour limite le nombre de cache miss.

Étude de la mémoire cache L2