Résumé #7: Grande capacité et rapidité: exploiter la hiérarchie de mémoires

À lire: pp. 458 à 479 2/3, 482 4/5 à 491 1/2, 492 1/4 à 496 1/4, 497 1/3 à 502 3/4, 508 2/3 à 519 4/5, 526 1/3 à 528 5/5.

7.1 Introduction

- Objectif de la hiérarchie mémoire = Créer l'illusion d'une mémoire très grande, très rapide et à prix raisonnable.

- Trois types de technologies pour la réalisation de mémoires:

• SRAM (Static RAM): Très rapide mais coûteux.
• DRAM (Dynamic RAM): Un peu moins rapide et moins coûteux.
• Disque: Beaucoup moins rapide mais peu coûteux.

- Stratégie tenant compte des différences de coûts et de temps d'accès = Utilisation d'une hiérarchie de mémoires: les niveaux les plus près du processeur sont plus rapides mais plus petits; ceux plus éloignés sont plus lents mais plus grands.

- Principe fondamental permettant le fonctionnement efficace d'une hiérarchie de mémoires = principe de localité:

• Localité temporelle: Si un objet vient d'être référencé, alors il risque d'être référencé à nouveau très bientôt (e.g., instruction dans une boucle). On conserve donc les objets récemment référencés le plus près possible du processeur.
• Localité spatiale: Si un objet est référencé, alors les objets près de celui-ci risquent d'être référencés très bientôt (e.g., éléments d'un tableau, instructions en séquence). On effectue donc les transferts d'information entre les niveaux par bloc.

- Terminologie pour accès à niveau donné de la hiérarchie:

• Echec = L'objet désiré n'est pas disponible.
• Succès = L'objet désiré est disponible.
• Taux d'échec = Nombre d'échecs / Nombre d'accès.
• Temps de succès = Temps d'accès lorsque l'objet est disponible.
• Coût d'un échec (pénalité) = Temps lorsque l'objet n'est pas présent (= temps pour accéder au niveau inférieur + temps pour mettre à jour les informations du niveau accédé).

7.2 Les caches

- Cache = Niveau de la hiérarchie de mémoires situé entre le processeur et la mémoire principale. Réalisé en SRAM (plus rapide; petite taille coût raisonnable).

- Diverses stratégies de mise en oeuvre:

• Cache à correspondance directe: Chaque bloc ne peut être qu'à une seule position dans le cache. La position est déterminée modulo la taille du cache (i.e., le nombre de blocs). Comme des blocs différents peuvent aller à la même position, le bloc présent est identifié par une étiquette (e.g., partie haute de l'adresse). Désavantage: Des conflits possibles entre blocs allant à la même position peuvent créer un effet ``ping-pong''.
• Cache totalement associatif: Un bloc peut aller n'importe où. Si toutes les positions sont occupées, on éjecte celui qui n'a pas été accédé depuis le plus longtemps (stratégie LRU = Least Recently Used). Plus coûteux à réaliser pcq. nécessite, pour être efficace, une recherche en parallèle des divers blocs.
• Cache associatif par ensemble de n: Compromis entre les deux approches précédentes = Un bloc peut aller n'importe où parmi un sous-ensemble de n blocs.

- Soit un cache contenant K blocs. On a alors les cas suivants:

• Cache à correspondance directe = Cache associatif par ensemble de 1.
• Cache associatif par ensemble de n 1 < n < K.
• Cache totalement associatif = Cache associatif par ensemble de K.

- Localité spatiale et transfert par blocs:

• Pour profiter du principe de localité spatiale, les blocs transférés entre le cache et la mémoire contiennent plusieurs mots à des adresses consécutives.
• Autre avantage des blocs: diminue l'espace relatif occupé par les étiquettes.
• Désavantage: Des blocs très gros augmentent la pénalité en cas de faute de cache (transfert plus long).

- Paramètres influençant le taux d'échec:

• Pour une taille totale de cache donnée, une augmentation du niveau d'associativité entraîne une diminution du taux d'échec.
• Pour une taille totale de cache donnée, des blocs de taille intermédiaire sont préférables: des blocs trop petits augmentent le taux d'échec (localité pas suffisament exploitée) de même que des blocs trop gros (nombre insuffisant de blocs + coût d'échec élevé).

- Traitement des écritures:

• Ecriture simultanée (write-through) = toute écriture dans le cache entraîne immédiatement l'écriture du bloc correspondant dans la mémoire. Solution simple mais entrainant un nombre élevé d'accès mémoire.
• Stratégie de réécriture (write-back) = l'information est écrite dans le cache. L'écriture effective dans la mémoire se fait uniquement lorsque le bloc est éjecté du cache. Un peu plus complexe (nécessite un bit spécial d'écriture + logique correspondante) mais réduit de façon importante le nombre d'accès à la mémoire.

- Performance d'une machine avec cache:

• Pour qu'une machine à pipeline fonctionne efficacement, le temps de succès doit correspondre au temps de cycle du processeur, de façon à ce qu'on puisse obtenir un CPI moyen près de 1.
• En cas d'échec, la machine est suspendue jusqu'à ce que l'accès à la mémoire principale soit complété, entrainant ainsi une augmentation du nombre de cycles requis pour l'exécution de l'accès mémoire. Le taux d'échec et le coût de la pénalité en cas d'échec déterminent donc l'augmentation du CPI moyen.

- Cache à plusieurs niveaux:

• Plusieurs machines récentes utilisent des caches à deux (2) niveaux. La hiérarchie de base:

  cache mémoire disque

  est donc augmentée d'un niveau supplémentaire:

  cache niveau 1 cache niveau 2 mémoire disque

• Différence entre le cache de niveau 1 de celui de niveau 2: le cache de niveau 1 est sur la même puce que le processeur (plus rapide, avec un temps de réponse correspondant au temps de cycle du processeur), alors que celui de niveau 2 est sur une puce différente (temps d'accès plus long mais de taille plus grande donc avec un taux de succès plus élevé).

7.3 La mémoire virtuelle

- Objectifs = Permettre le partage de la mémoire entre programmes (chaque programme possède son espace mémoire indépendant) et donner l'illusion d'une mémoire de très grande taille (équivalente à l'espace d'adressage déterminé par l'architecture du jeu d'instructions, espace généralement plus grand que l'espace mémoire physique).

- Intuition: La mémoire principale (DRAM) est vue comme un cache face au disque.

- Mémoire virtuelle avec pagination:

• L'espace mémoire est décomposé en blocs de taille fixe (appelés pages).
• Une page virtuelle peut être conservée n'importe où en mémoire physique (cache totalement associatif) ou être conservée sur disque.
• Une adresse virtuelle doit être traduite en une adresse physique, indiquant la position où réside la page en mémoire (si présente) ou sa position sur disque (si absente).
• Fonctionne efficacement grâce au principe de localité: durant un intervalle de temps, seul un nombre limité de pages est réellement utilisé par le programme et a besoin d'être conservé en mémoire.

- Processus de traduction des adresses virtuelles pour mémoire paginée:

• Chaque programme possède sa propre table de pages.
• Pour chaque page virtuelle d'un programme, la table de pages indique si la page désirée est en mémoire (succès) ou sur disque (faute de page). Si la page est en mémoire, la table indique le numéro de page physique associée au numéro de page virtuelle.
• En cas d'échec la pénalité est très grande, puisqu'un accès disque doit être effectué. On doit donc minimiser le plus possible les fautes de page.

- Traitement des écritures: Stratégie de réécriture, car l'écriture simultanée serait beaucoup trop coûteuse.

- Stratégie de remplacement des pages: LRU, pour tenter de diminuer le plus possible le taux d'échec (étant donné le coût élevé des échecs).

- Technique pour accélération du processus de traduction d'adresse: Tampon de traduction d'adresse (TLB = Translation Lookaside Buffer).

• Essentiellement, un TLB est un cache dédié à la traduction des adresses (associe une adresse physique à une adresse virtuelle).
• Technique vitale car le processus de traduction peut être très coûteux, nécessitant 2 (ou plusieurs) accès mémoire: 1 accès pour obtenir la table de page (celle-ci pouvant être assez grosse, elle doit aussi être décomposée en pages) + 1 accès pour obtenir l'objet requis. (Certaines machines ont des tables de pages à plusieurs niveaux, e.g., 3 ou 4!)