Chapitre 5 - Les Mémoires Caches (PDF)

# Résumé - Chapitre 5: « Les mémoires caches (tampon) » ## Module - ARCH2 - 2CP – S1 ### Evolution des performances - La vitesse des processeurs évolue beaucoup plus vite que la vitesse de la mémoire. - Loi de Moore : « vitesse processeur multipliée par deux tous les 1,5 ans » - La vitesse d'accè...

# Résumé - Chapitre 5: « Les mémoires caches (tampon) » ## Module - ARCH2 - 2CP – S1 ### Evolution des performances - La vitesse des processeurs évolue beaucoup plus vite que la vitesse de la mémoire. - Loi de Moore : « vitesse processeur multipliée par deux tous les 1,5 ans » - La vitesse d'accès aux données n'arrive plus à satisfaire les besoins en données des processeurs. - Il y a des contraintes physiques sur la taille de la mémoire. - Écart de performances entre processeur et mémoire. ### Introduction: Caractéristiques d'une mémoire #### Temps d'accès/latence (Access time/latency) - C'est le temps nécessaire pour effectuer un accès à la mémoire (une lecture ou une écriture) d'un mot mémoire : l'intervalle de temps entre la demande de lecture/écriture et la disponibilité de la donnée sur le bus. #### Temps de cycle mémoire - C'est le temps minimal entre deux accès mémoire successifs. Il concerne les contraintes liées à la mémoire et au bus et non au processeur. - Concept appliqué aux mémoires à accès aléatoire (RAM): - Temps Cycle = Temps d'accès + Temps d'attente avant de pouvoir effectuer une seconde opération - Exemple de temps d'attente : temps nécessaire pour la réécriture de la donnée lue en cas de lecture destructive (dans une DRAM). - Des petites capacités mémoires impliquent des temps d'accès plus courts, donc un plus grand coût par bit. Alors, des plus grandes capacités impliquent de plus faibles coûts par bit, donc des temps d'accès plus élevés. ### Hiérarchie mémoire #### Dilemme - Besoin en capacités mémoires plus importantes, et en mémoires présentant des temps d'accès plus courts (qui sont plus coûteuses et de plus petites tailles !) #### Solution - Ne pas se baser sur un composant ou une technologie mémoire uniques → Utiliser une hiérarchie mémoire. #### Principes d'accélération des accès - Si les mémoires cache permettent d'accroître les performances, c'est en partie grâce à deux principes, appelé « les principes de localité » : - Localité temporelle: l'accès à une zone mémoire à un instant donné a de fortes chances de se reproduire dans la suite du programme. - Localité spatiale: l'accès à une instruction située à une adresse X va probablement être suivi d'un accès à une zone tout proche (voisine) de X. #### Notion d'hiérarchie mémoire - Les mémoires les plus rapides (et plus petites) doivent être placées près de l'UC; - Des mémoires de plus en plus grandes (de moins en moins rapides et de moins en moins coûteuses) sont utilisées au fur et à mesure qu'on s'éloigne de l'UC. ### Principe des mémoires cache #### Rappel - Les DRAM (RAM dynamiques) présentent un taux d'intégration permettant des capacités importantes. Mais, leurs temps d'accès est élevé (≈60ns). - Les SRAM, quant à elles, présentent des temps d'accès très petits (≈10ns). Leur coût rend, cependant, prohibitive la réalisation de mémoires de grandes capacités. #### Problématique - On dispose actuellement d'unité centrale (UC) à base de micro-processeurs capables de fonctionner à des fréquences très élevées (≥ 50KHz). Les mémoires centrales (MC) actuelles, pour es raisons de coût, sont réalisées à base de DRAM qui présentent des temps d'accès élevés. Il apparait donc une grande différence de rapidité entre la mémoire centrale (MC) et l'unité centrale (UC). - Pendant l'exécution d'un programme, l'UC reste inactive chaque fois qu'elle effectue un accès à la MC (recherche d'une instruction ou d'une opérande). Plus grand est la différence du vitesse entre l’UC et la MC, plus grand est le temps d'inaction de l'UC et donc plus grande est la dégradation des performances du calculateur. #### Solution - La solution qui a été adoptée consiste à intercaler une RAM statique de petite taille (faible capacité) entre la mémoire centrale et le processeur. Cette SRAM s'appelle la mémoire tampon (cache) et elle contient une partie des informations de la mémoire centrale (les informations en cours d'utilisation). - La mémoire cache tire son avantage du principe de localité spatiale. #### Fonctionnement général - Lors d'une lecture, l'UC fournit une adresse simultanément à la mémoire tampon (MT) et à la mémoire centrale. Le mot correspondant est d'abord recherché en mémoire cache. En cas de succès cache (cache hit), la mémoire principale n'est pas accédée ; l'UC peut récupérer l'information associée directement de la cache et continuer l'exécution. - Dans le cas contraire d'échec cache (cache miss), la lecture se fait en mémoire centrale et l'information est alors délivrée simultanément au processeur et à la mémoire cache ou elle est stockée ainsi que les informations d'adresses voisines en mémoire centrale (principe de localité spatiale) pour les accès futur. - Un contrôleur s'occupe de la gestion des adresses et de la communication avec le processeur d'une part, et la mémoire centrale d'autre part. ### Organisation des mots en cache et MC #### Principe de calcul des adresses physiques - Pour le processeur, seule l'adresse en mémoire centrale permet d'accéder à une information, que celle-ci soit située en mémoire centrale ou en mémoire cache. Un calcul doit donc être effectué pour localiser l'emplacement en mémoire tampon. Ce calcul dépend évidemment de la technique utilisée pour associer l'adresse mémoire centrale à celle en mémoire cache. Trois techniques d'associativité (organisations des MT) existent : #### 1. Cache Purement associative - Dans ce type d'associativité, Il n'existe aucune relation entre les adresses en RAM et les adresses en tampon, toute information peut donc être rangée à une adresse quelconque en mémoire cache. - Pour cela le contrôleur dispose d'une table d'index qui lui permet d'effectuer la conversion d'adresse. Cette table est implantée dans une mémoire associative dont chaque élément est formé de 2 champs : - Un champ contenant l'adresse en mémoire centrale du mot rangé en mémoire cache. - Un champ contenant l'adresse en mémoire cache du même mot. - L'avantage est que cette méthode offre les meilleurs performances et une grande souplesse d'utilisation. - L'inconvénient, par contre, vient de la complexité de mise en œuvre d'une telle solution (la méthode requiert beaucoup de logique car elle donne accès à de nombreuses possibilités). Ceci explique pourquoi l'associativité complète n'est utilisée que dans les mémoires cache de petite taille. #### 2. Cache à accès direct - La mémoire centrale est divisée en pages de taille égale à celle de la mémoire cache. A chaque emplacement en mémoire centrale correspond un emplacement unique en mémoire cache. Par exemple : le mot d'adresse 0 de chaque page de MC ne peut être chargé qu'à l'adresse 000 en mémoire cache (ceci crée de nombreux défauts de cache conflictuels si le programme accède à des données qui sont rangées sur les mêmes adresses de la cache). - Un index, disposant d'autant d'entrées qu'il y a des mots dans la mémoire cache, contient le numéro de bloc en MC de chaque mot contenu dans la MT. - Pour déterminer si un mot est présent en mémoire cache, le contrôleur accède à l'index, à l'emplacement déterminé par les bits de poids faible de l'adresse, en mémoire centrale, du mot recherché (bits déterminant le déplacement du mot dans le bloc ou il est rangé en MC). Il compare alors le numéro de bloc contenu dans l'index avec celui contenu dans le poids fort de l'adresse. S'il y a concordance, le mot est présent et l'opération peut s'effectuer directement sur la mémoire cache. - L'avantage de cette solution est sa simplicité. Son inconvénient, par contre, est son manque de souplesse dans l'allocation des emplacements en mémoire cache. #### 3. Cache associative par bloc - Cette solution est un compromis entre la première et la seconde. La mémoire cache est divisée en blocs de même taille que ceux de la mémoire centrale. Chaque mot de la MC peut être rangé dans n'importe quel bloc de la mémoire cache. Notons cependant qu'il ne peut être rangé qu'à l'emplacement qui correspond à celui qu'il occupe dans le bloc de la MC (déplacement dans le bloc). Il a donc autant de possibilités qu'il y a de bloc dans la mémoire cache. - Par exemple : le mot d'adresse 0 d'un bloc en MC peut être rangé au premier emplacement du bloc 0 ou du bloc 1 de la MC. - Dans le cas d'un défaut d'information, le contrôleur dispose d'autant de possibilités pour charger le mot lu qu'il y a de blocs dans la mémoire cache. Cet avantage confère plus de souplesse et d'efficacité dans la gestion de la mémoire cache. ### Remplacement d'une information #### Problématique - Avant de charger une nouvelle information de la mémoire centrale à mémoire tampon, on doit d'une part déterminer la taille du bloc à charger en mémoire tampon et d'autre part décider des mots à remplacer. Un critère important des mémoires cache est la taille de ligne; c'est le nombre d'octets que le contrôleur peut simultanément copier de la MC à la MT en cas de défaut d'information dans la cache. - Actuellement, la taille varie de 2 à 64 octets. Ces informations étant transférées en un seul cycle, ceci peut nécessiter un chemin de taille supérieure au bus de données. D'où l'inconvénient de disposer d'une ligne de taille importante. L'avantage, par contre, est au niveau de performance accrue (en termes de vitesse). - Quelle ligne choisir pour la remplacer par la nouvelle information à charger en mémoire cache ? #### Solution - Pour choisir l'information à remplacer, plusieurs techniques existent ; les trois principales sont : - **1. Remplacement aléatoire:** Elle consiste à remplacer l'information de manière aléatoire. L'avantage de cette méthode est la simplicité de sa réaliser mais elle a pour inconvénient un risque élevé de remplacer un bloc encore utile au processeur (une page dont on aura bientôt besoin), augmentant ainsi la probabilité d'avoir des défauts d'informations; in other words : la mise à jour aléatoire ne respecte pas la localité temporelle. - **2. Remplacement direct:** Elle consiste à charger le mot dans l'emplacement qui lui est réservé en mémoire cache (elle est donc valable uniquement pour la cache à placement direct). - **3. Remplacement LRU (Least Recently Used):** Elle consiste à remplacer la ligne qui n'a pas été utilisée depuis le plus longtemps. Le principe de proximité temporelle est utilisé ; une information sur la dernière date d'utilisation des blocs est rajoutée. A chaque remplacement, cette information est testée pour chaque bloc et le moins récemment utilisée est choisi. L'avantage de cette méthode est qu'elle réduit la chance d'éliminer une donnée qui pourrait s'avérer rapidement nécessaire (respect de la localité temporelle, contrairement au remplacement aléatoire, dans les MT de petite taille). Cependant, elle présente un inconvénient; la logique LRU doit toujours maintenir l'instant où la donnée a été référencée la dernière fois ⇒ Son exécution devient complexe à mesure que la taille du cache augmente. #### Comparaison entre remplacement LRU et aléatoire - Il n'y a pas beaucoup de différences dans le taux de succès cache entre le LRU et la technique de remplacement aléatoire lorsque la taille du cache est grande; la technique aléatoire devient plus intéressante du fait de son implémentation plus simple quand le nombre de lignes augmente. ### Écriture en mémoire cache #### Problématique - Lors d'une lecture, l'information récupérée en mémoire cache par l'UC est immédiatement exploitée puis « oubliée ». aucune mise à jour en mémoire centrale n'est nécessaire, la donnée n'ayant pas été altérée. Dans le cas d'une écriture, par contre, le problème de l'intégrité des informations se trouvant simultanément en mémoire cache et en MC peut se poser. La modification d'une donnée se trouvant en cache peut provoquer une incohérence si l'image de cette information en MC n'est pas mise à jour. Le problème est de déterminer l'instant exacte ou il faut réécrire l'information en MC. #### Solution - Trois approches tentent, chacune, de résoudre ce problème : - **1. Écriture immédiate (Write though):** elle consiste à effectuer simultanément la mise à jour dans la mémoire cache et mémoire centrale. C'est la solution la plus simple à mettre en œuvre et évidemment la plus sure; les copies de données sont cohérentes. L'inconvénient d'une telle technique est cependant son influence négative sur les performances de la machine; le temps d'écriture en MT est celui de l'opération en MC ⇒ la cache n'apporte aucun avantage en écriture. - **2. Écriture retardée (Posted write through):** une zone tampon (FIFO) est réservée en mémoire cache qui contiendra les informations à mettre à jour en mémoire centrale. L'écriture se fait dès que le bus est disponible. L'un des avantages de cette solution est le gain de temps, alors que ses principaux inconvénients sont : elle devient inefficace si plusieurs processeurs sont utilisés car chacun a sa propre FIFO. De plus, lors d'une incrémentation en boucle (plusieurs modifications successives de l'information), beaucoup d'écritures inutiles en MC s'effectuent avant la valeur finale. - **3. Écriture différée (Write back):** les accès à la MC ne sont effectués que lorsque cela devient indispensable, c-à-d: au moment où l'emplacement qu'occupe l'information en mémoire tampon doit être libéré et que cette dernière doit être remplacée (on fait l'écriture avant d'écraser l'information du cache). Les accès à la MC sont donc limités au maximum, ce qui est le principal avantage de cette solution. - Cependant, pour appliquer cette méthode, il est nécessaire de disposer d'un indicateur par mot qui est positionné à « 1 » si la donnée est modifiée afin de repérer les mots à réécrire en MC. Le principal inconvénient est donc sa difficulté de mise en œuvre. ### Niveaux de cache - **Cache interne :** elle se trouve dans le micro-processeur : - Niveau L1 : réalisée en technologie SRAM (RAM Statique), rapide, généralement de petite taille - Niveau L2: réalisée en technologie DRAM (RAM dynamique), moins rapide, de plus grande taille que L1. - **Cache externe:** elle se trouve en dehors de micro-processeur (située sur la carte mère): - Niveau L3: réalisée en technologie SRAM (RAM statique), plus rapide que la MC. ### Taille du cache - On pourrait penser que plus la MT est grande, meilleures sont les performances du calculateur puisque la probabilité d'avoir un défaut d'information devient plus faible. Cependant, la taille de cette mémoire est limitée, d'une part du fait de son coût (plus le cache est grand, plus la logique d'adressage est complexe) et d'autre part parce que les résultats des simulations ont montré qu'au-delà d'un certain seuil, l'augmentation de la taille de la MT n'apporte aucune amélioration significative (les programmes ne sont que rarement totalement séquentiels et un défaut d'information survient tôt ou tard). - Il n'existe pas de taille de mémoire cache optimale.