Séance 2 — Cohérence de cache et protocoles

bleutitreSéance 2 : Cohérence de cache et protocoles

Séance 2 d’Architecture et Programmation Parallèles : cohérence de cache et protocoles.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Introduction : Le problème de cohérence de cache

Dans un processeur multicœur, chaque cœur garde dans son cache sa propre copie des données qu’il utilise. La question de cette séance : comment s’assurer que tous les cœurs voient une vue cohérente de la mémoire quand chacun a sa propre copie en cache ?

La nécessité de la cohérence de cache

Dans un système multicœur moderne, chaque cœur possède ses propres caches (L1, L2) pour améliorer les performances. Mais cela crée un problème fondamental :

NoteDéfinition

Le problème de cohérence de cache survient quand plusieurs caches peuvent contenir des copies d’une même donnée, et qu’une modification dans un cache doit être visible par tous les autres de manière cohérente.

  1. P1 lit \(x\)

  1. P2 lit \(x\)

  1. P1 écrit \(x=5\)

  1. P2 relit \(x\) : \(0\)
Figure 1: Le problème de cohérence : deux copies d’une même donnée, caches write-back, aucun protocole. Cadre rouge : copie modifiée à l’étape ; flèche verte : donnée lue en mémoire. À l’étape 4, P2 trouve sa copie (succès) et lit 0.

Exemple concret : Variable partagée x = 0 en mémoire

  1. Cœur 1 lit x → copie dans Cache 1 : x = 0
  2. Cœur 2 lit x → copie dans Cache 2 : x = 0
  3. Cœur 1 écrit x = 5 → Cache 1 : x = 5
  4. Cœur 2 lit x → Que lit-il ? 0 ou 5 ?

Sans mécanisme de cohérence, le Cœur 2 lirait toujours 0 depuis son cache ! La Figure 1 suit ces quatre étapes (le Cœur 1 est P1, le Cœur 2 est P2) : après l’écriture, la copie de C2 est périmée et la mémoire aussi, et rien ne prévient C2.

Les défis de la cohérence

Chaque cache garde des copies des données les plus utilisées. Quand une donnée est modifiée, trois questions se posent :

  • comment informer tous les caches qui en détiennent une copie ?
  • faut-il détruire (invalider) les anciennes copies, les mettre à jour, ou seulement les signaler obsolètes ?
  • comment limiter les communications entre caches que cela coûte ?

Les protocoles de cohérence sont les règles qui régissent ces décisions. Les protocoles de cette séance (MSI, MESI) invalident les autres copies.

Rappels : Opérations de cache

Latences de référence

AvertissementAttention

Pour tout le cours, nous utiliserons ces valeurs de référence cohérentes :

  • Cache hit : 1 cycle
  • Cache miss : 100 cycles
  • Write-back (BusWB) : 100 cycles
  • BusRdX (lecture exclusive) : 100 cycles

Ces valeurs sont arrondies pour faciliter les calculs : sur un processeur actuel, une lecture en mémoire principale coûte plutôt 180 à 300 cycles (Séance 1), et un transfert d’un cache à l’autre coûte moins qu’un accès à la mémoire.

Types d’accès mémoire

NoteDéfinition

Opérations du processeur :

  • PrRd (Processor Read) : Le processeur lit une donnée
  • PrWr (Processor Write) : Le processeur écrit une donnée

Transactions sur le bus :

  • BusRd (Bus Read) : Demande de lecture sur le bus
  • BusRdX (Bus Read Exclusive) : Demande de lecture exclusive pour modification
  • BusWB (Bus Write Back) : Écriture des données modifiées en mémoire

La Figure 2 situe ces opérations : PrRd et PrWr circulent entre un processeur et son cache ; BusRd, BusRdX et BusWB passent sur le bus, que tous les caches observent.

Figure 2: Opérations du processeur et transactions sur le bus. Ici P1 lit \(x\) : son cache émet un BusRd, la mémoire fournit la ligne (flèche verte), C2, qui a une copie valide, examine la transaction sans changer d’état (cadre orange) ; C3, invalide, n’est pas concerné.

Politiques d’écriture

Write-Through vs Write-Back

NoteDéfinition

Write-Through : Chaque écriture est propagée sans attendre à la mémoire principale.

  • Avantage : Mémoire toujours à jour
  • Inconvénient : Beaucoup de trafic sur le bus

Write-Back : Les écritures sont effectuées uniquement dans le cache. La mémoire est mise à jour lors de l’éviction de la ligne.

  • Avantage : Moins de trafic sur le bus
  • Inconvénient : contrôleur plus élaboré (une marque « modifiée » par ligne), mémoire pas toujours à jour

Write-Allocate vs Write-No-Allocate

NoteDéfinition

Write-Allocate : En cas de write miss, la ligne est d’abord chargée dans le cache, puis modifiée.

  • Avantage : Exploite la localité temporelle
  • Inconvénient : Trafic supplémentaire pour le chargement
  • Utilisé typiquement avec Write-Back

Write-No-Allocate : En cas de write miss, l’écriture va directement en mémoire sans charger la ligne dans le cache.

  • Avantage : Moins de pollution du cache
  • Inconvénient : Pas d’exploitation de la localité
  • Utilisé typiquement avec Write-Through
AstuceÉnoncé

Un programme effectue la séquence suivante sur une variable non présente en cache :

  1. Write x = 10
  2. Write x = 20
  3. Read x
  4. Write x = 30

Comparez le nombre de transferts mémoire avec : a) Write-Through + Write-No-Allocate b) Write-Back + Write-Allocate

AstuceCorrection
Afficher la correction

a) Write-Through + Write-No-Allocate :

  1. Write x=10 : Miss → écriture directe en mémoire (1 transfert)
  2. Write x=20 : Miss → écriture directe en mémoire (1 transfert)
  3. Read x : Miss → lecture depuis mémoire, mise en cache (1 transfert)
  4. Write x=30 : Hit → écriture cache + mémoire (1 transfert)

Total : 4 transferts mémoire

b) Write-Back + Write-Allocate :

  1. Write x=10 : Miss → lecture ligne (1), puis écriture en cache seulement
  2. Write x=20 : Hit → écriture en cache seulement
  3. Read x : Hit → lecture depuis cache
  4. Write x=30 : Hit → écriture en cache seulement

Total : 1 transfert (+ 1 write-back à l’éviction)

Conclusion : Write-Back + Write-Allocate est beaucoup plus efficace pour les accès répétés !

La Figure 3 montre l’état final des deux configurations après les quatre accès et l’éviction de la ligne.

Figure 3: Les quatre accès de l’exercice, puis l’éviction de la ligne. À gauche, chaque écriture va en mémoire : 4 transferts. À droite, 1 chargement et 1 write-back : 2 transferts. Cadre rouge : modifié à l’étape (ici l’éviction).

Le protocole MSI

Les trois états MSI

Le protocole MSI est le protocole d’invalidation de base : MESI et les protocoles suivants l’enrichissent.

NoteDéfinition

Le protocole MSI définit trois états possibles pour chaque ligne de cache :

  • M (Modified) : La ligne est modifiée et présente uniquement dans ce cache. Le cache est responsable de la donnée.
  • S (Shared) : La ligne est valide et peut être présente dans d’autres caches. Lecture seule.
  • I (Invalid) : La ligne n’est pas valide ou n’est pas présente dans le cache.
AstuceIntuition

Pensez aux états MSI comme des permissions sur un fichier :

  • Modified = Vous avez l’unique copie modifiable (accès exclusif en écriture)
  • Shared = Vous avez une copie en lecture seule (d’autres peuvent aussi lire)
  • Invalid = Vous n’avez pas le droit d’accéder au fichier

Diagramme de transitions MSI

Mécanisme de snooping

NoteDéfinition

Le bus snooping (espionnage de bus) est un mécanisme où chaque cache surveille toutes les transactions sur le bus et réagit selon son état actuel et le type de transaction observée.

Figure 4: Diagramme d’états du protocole MSI : transitions initiées par le processeur au-dessus (trait plein), par le bus au-dessous (tirets bleus)

Notation : Action/Réaction

  • Avant la barre (/) : Action observée (PrRd, PrWr, BusRd, BusRdX)
  • Après la barre (/) : Action entreprise (BusRd, BusRdX, BusWB, ou – pour aucune action)

Les transitions principales sont :

  • I → S : PrRd/BusRd (lecture depuis Invalid → transaction BusRd)
  • I → M : PrWr/BusRdX (écriture depuis Invalid → transaction BusRdX)
  • S → M : PrWr/BusRdX (écriture depuis Shared → transaction BusRdX pour invalider les autres ; la copie locale est déjà valide, certains processeurs utilisent ici une transaction sans données, BusUpgr)
  • M → S : BusRd/BusWB (autre processeur lit → write-back et partage)
  • M → I : BusRdX/BusWB (autre processeur écrit → write-back et invalidation)
  • S → I : BusRdX/– (autre processeur écrit → invalidation seule)
NoteDéfinition

Les trois règles de MSI :

  1. Pour lire une donnée, il faut au minimum être en S.
  2. Pour écrire, il faut être en M (exclusivité obligatoire).
  3. Quand un cache veut écrire, il émet un BusRdX qui invalide toutes les autres copies.

Exemple détaillé du protocole MSI

Suivons une séquence d’opérations avec le protocole MSI :

Trace d’exécution MSI avec trois processeurs
Action Bus Tr Fournit C1 C2 C3
Initial - - I I I
P1: PrRd x BusRd Mem I→S I I
P2: PrRd x BusRd Mem S I→S I
P1: PrWr x=5 BusRdX - S→M S→I I
P3: PrRd x BusRd C1(WB) M→S I I→S
P2: PrWr x=10 BusRdX Mem S→I I→M S→I

Ligne 3, C1 possède déjà la donnée : le BusRdX sert à invalider la copie de C2, d’où « - » dans la colonne Fournit. Ligne 4, C1 est en M : il intercepte le BusRd, écrit la ligne en mémoire (BusWB) et la fournit à P3. Ligne 5, C2 est en I : son BusRdX doit ramener la ligne, et la mémoire, à jour depuis le BusWB, la fournit. La Figure 5 montre l’état des caches après chaque ligne.

Les deux questions de la fiche d’exercice (lignes 1 à 4) :

  1. À quelle étape y a-t-il une invalidation d’un autre cache ? Pourquoi ? À l’étape 3 : pour écrire, P1 doit obtenir l’exclusivité ; son BusRdX force C2, qui était en S, à passer en I.
  2. À l’étape 4, d’où vient la donnée lue par P3 ? Pas de la mémoire, qui est périmée : C1, en M, fait un BusWB et fournit la donnée la plus récente.

Ligne 1 : P1 lit

Ligne 2 : P2 lit

Ligne 3 : P1 écrit 5

Ligne 4 : P3 lit (BusWB de C1)

Ligne 5 : P2 écrit 10

Figure 5: La trace MSI, ligne par ligne. Flèche bleue : transaction émise ; verte : donnée fournie par la mémoire ; violette : BusWB ; cadre rouge : état modifié ; cadre orange : copie valide examinée par l’espionnage, sans changement d’état.
AstuceType examen

Soit un système à trois processeurs utilisant le protocole MSI. Les caches sont initialement invalides. Tracez les états pour la séquence :

  1. P1: Read x
  2. P3: Read x
  3. P3: Write x = 20
  4. P2: Read x
  5. P1: Read x

Complétez le tableau avec états et transactions bus.

AstuceCorrection
Afficher la correction
Action Bus Tr Fournit par C1 C2 C3
Initial - - I I I
P1: PrRd x BusRd Mémoire I→S I I
P3: PrRd x BusRd Mémoire S I I→S
P3: PrWr x=20 BusRdX - S→I I S→M
P2: PrRd x BusRd C3 (WB) I I→S M→S
P1: PrRd x BusRd Mémoire I→S S S

Points clés :

  • Ligne 3 : P3 invalide toutes les autres copies pour obtenir l’exclusivité
  • Ligne 4 : P3 doit faire un BusWB car il a la donnée modifiée
  • Ligne 5 : La donnée vient de la mémoire (après write-back) : en MSI, les copies en S ne fournissent pas la donnée

Le protocole MESI

L’état Exclusive

Pour améliorer les performances du protocole MSI, MESI ajoute un quatrième état :

NoteDéfinition

Le protocole MESI ajoute l’état :

  • E (Exclusive) : La ligne est présente uniquement dans ce cache et est identique à la mémoire (propre). Le cache peut la modifier sans transaction sur le bus.

Les quatre états MESI sont donc :

  • M (Modified) : Exclusive et modifiée (dirty)
  • E (Exclusive) : Exclusive et propre (clean)
  • S (Shared) : Partagée et propre
  • I (Invalid) : Invalide
NoteAnalogie

L’état Exclusive est comme emprunter un livre à la bibliothèque :

  • Shared = Consulter le livre dans la salle de lecture (d’autres peuvent aussi)
  • Exclusive = Emprunter le livre chez vous (personne d’autre ne l’a, mais intact)
  • Modified = Emprunter et annoter le livre (vous devez le rendre modifié)

L’avantage : passer de Exclusive à Modified ne nécessite aucune communication !

Diagramme de transitions MESI

Figure 6: Diagramme d’états du protocole MESI. Les transitions au-dessus (trait plein) sont initiées par le processeur, celles au-dessous (tirets bleus) par le bus. La transition E→M en vert est le gain principal de MESI

Transitions clés de MESI :

  • I → E : PrRd/BusRd quand aucun autre cache n’a la ligne (signal de partage négatif)
  • I → S : PrRd/BusRd quand un autre cache signale qu’il a la ligne
  • E → M : PrWr/– (pas de transaction bus ! C’est LE gain MESI)
  • E → S : BusRd/– quand un autre processeur lit
  • E → I : BusRdX/– quand un autre processeur écrit
  • S → M : PrWr/BusRdX (doit invalider les autres copies)
  • S → I : BusRdX/– (invalidation par un autre processeur)
  • M → S : BusRd/BusWB (partage après write-back)
  • M → I : BusRdX/BusWB (invalidation après write-back)
AvertissementAttention

La transition E→M est LE gain principal de MESI : une écriture sur une donnée exclusive ne génère AUCUNE transaction bus, donc latence minimale (1 cycle) !

Calcul de latence avec MESI

AstuceType examen - Calcul de latence

Soit un système MESI avec les latences suivantes :

  • Cache hit : 1 cycle
  • Cache miss : 100 cycles
  • Write-back (BusWB) : 100 cycles
  • BusRdX : 100 cycles

Calculez la latence totale pour :

  1. P0: Read x (cache vide, personne n’a x)
  2. P0: Write x = 10
  3. P1: Read x
  4. P1: Write x = 20
AstuceCorrection
Afficher la correction

Analyse détaillée de chaque étape :

Action P0 État P1 État Transaction Latence
Initial I I - -
P0: Read x I→E I BusRd (miss) 100 cycles
(pas de partage)
P0: Write x=10 E→M I Aucune ! 1 cycle
(transition locale) (hit)
P1: Read x M→S I→S BusRd + BusWB 100 + 100
(P0 write-back) = 200 cycles
P1: Write x=20 S→I S→M BusRdX 100 cycles
(invalidation)
Latence totale : 401 cycles
  1. Étape 1 : P0 obtient l’état E car personne n’a x
  2. Étape 2 : Transition E→M locale, AUCUN bus ! C’est le gain MESI
  3. Étape 3 : P0 doit write-back ses données modifiées (coûteux : 200 cycles)
  4. Étape 4 : BusRdX pour obtenir l’exclusivité et invalider P0

Comparaison avec MSI : Avec MSI, l’étape 2 aurait nécessité un BusRdX (100 cycles au lieu de 1). Gain MESI : 99 cycles dans ce scénario ! Les étapes 1, 3 et 4 coûtent la même chose dans les deux protocoles (MSI : \(100+100+200+100=500\) cycles, MESI : \(100+1+200+100=401\) cycles).

  1. P0 lit : I→E

  1. P0 écrit : E→M, sans bus

  1. P1 lit : BusWB de P0

  1. P1 écrit : BusRdX
Figure 7: La trace MESI de l’exercice, étape par étape. L’étape 2 ne fait aucune transaction (pas de flèche sur le bus).

Impact sur la programmation : False Sharing

Le problème du false sharing

NoteDéfinition

Le false sharing se produit quand deux processeurs modifient des variables différentes qui se trouvent dans la même ligne de cache (typiquement 64 octets). Cela provoque des invalidations mutuelles constantes.

// Structure problématique
struct shared_data {
    int counter1;  // Utilisé par Thread 1
    int counter2;  // Utilisé par Thread 2
} data;

// Les deux compteurs sont dans la même ligne de cache !
// Chaque modification invalide le cache de l'autre thread
// Structure corrigée
struct shared_data {
    int counter1;           // Thread 1
    char padding[60];       // Force nouvelle ligne cache
    int counter2;           // Thread 2
} data;

// Maintenant, chaque compteur est dans sa propre ligne

Avec gcc sur x86-64, sizeof(struct shared_data) vaut 8 et counter2 est au décalage 4 ; dans la structure corrigée, sizeof vaut 68 et counter2 est au décalage \(4+60=64\). Les deux compteurs sont alors à 64 octets l’un de l’autre : ils ne peuvent pas tomber dans la même ligne, quelle que soit l’adresse de data (Figure 8). Le rembourrage ne protège que les deux compteurs entre eux : d’autres variables placées juste avant ou juste après data peuvent encore partager leurs lignes.

Figure 8: Une ligne de 64 octets découpée en cases de 4 octets, data placé au début d’une ligne. En haut, les deux compteurs dans la même ligne ; en bas, avec padding[60], chacun dans la sienne.

La Figure 9 suit deux fils qui incrémentent chacun leur compteur. Chaque incrémentation est une écriture : la ligne doit être en M dans le cache de celui qui écrit, et elle quitte donc l’autre cache à chaque changement de fil.

Figure 9: False sharing en MSI. En haut, après quatre incrémentations alternées : trois invalidations, la ligne fait des allers-retours. En bas, la même séquence avec le rembourrage : chaque compteur a sa ligne, aucune invalidation.
AstuceÉnoncé

Un programme a 4 threads, chacun incrémente son compteur 1 million de fois.

int counters[4];  // Tableau de compteurs

// Thread i exécute :
for(int j = 0; j < 1000000; j++) {
    counters[i]++;
}

Si une ligne de cache fait 64 octets et un int fait 4 octets :

  1. Tous les compteurs sont-ils dans la même ligne de cache ?
  2. Combien d’invalidations de cache cela génère-t-il ?
  3. Proposez deux solutions.
AstuceCorrection
Afficher la correction

  1. Oui ! 4 entiers × 4 octets = 16 octets < 64 octets → Tous dans la même ligne de cache

  2. Jusqu’à environ 4 millions de transferts de la ligne ! Il y a \(4 \times 1\,000\,000\) incrémentations, et chacune peut trouver la ligne dans un autre cache, en M : l’écriture émet alors un BusRdX, le cache qui détenait la ligne fait un BusWB et s’invalide. C’est une borne haute : en M, une seule copie existe, donc chaque transfert invalide une copie (et non trois), et un fil enchaîne souvent plusieurs incrémentations avant de perdre la ligne. Le programme devient plusieurs fois plus lent : avec deux fils et des compteurs volatile, sur une machine virtuelle x86-64 à deux cœurs, la boucle va de 4 à 9 fois moins vite selon les essais qu’avec des compteurs dans des lignes séparées (le Lab 3 fait mesurer un effet voisin, un compteur partagé).

  3. Solutions :

    // Solution 1 : Padding
struct {
    int value;
    char pad[60];  // 64 - 4 = 60
} counters[4];     // 64 octets par element

// Solution 2 : Alignement du champ
// (C11 : #include <stdalign.h>)
struct compteur {
    alignas(64) int value;
} counters[4];     // sizeof = 64

// Solution 3 : Variables locales
int local_counter = 0;
for(int j = 0; j < 1000000; j++)
    local_counter++;
counters[i] = local_counter;  // Une seule écriture
AvertissementAttention

alignas(64) int counters[4]; n’aligne que le début du tableau : sizeof vaut 16 et les quatre compteurs restent dans la même ligne. Il faut aligner chaque élément, en plaçant alignas(64) sur le champ d’une structure (solution 2) : chaque élément occupe alors 64 octets et commence une ligne (Figure 10).

Autre piège : compilée avec gcc -O2, la boucle de l’exercice devient une seule addition (addl $1000000) et le false sharing disparaît de ce programme. Il se mesure avec -O0, des compteurs volatile ou atomiques, ou quand la boucle fait un vrai travail entre deux écritures.

Figure 10: Disposition des quatre compteurs relevée avec gcc 13 (x86-64) : tableau d’entiers, tableau aligné, tableau de structures alignées.

Cohérence séquentielle

Modèle de cohérence

NoteDéfinition

La cohérence séquentielle garantit que :

  1. Les opérations de chaque processeur apparaissent dans l’ordre du programme
  2. Il existe un ordre global unique des opérations vu par tous les processeurs
AstuceType examen - Cohérence séquentielle

Deux threads exécutent le code suivant (A et B initialement à 0) :

Thread 1:

(1) A = 1
(2) print(B)

Thread 2:

(3) B = 1
(4) print(A)
  1. Donnez trois exécutions possibles et leurs résultats
  2. Quelle sortie est impossible en cohérence séquentielle ?
AstuceCorrection
Afficher la correction

Exécutions possibles :

  1. (1)→(2)→(3)→(4) : Thread1 affiche 0, Thread2 affiche 1
  2. (3)→(4)→(1)→(2) : Thread1 affiche 1, Thread2 affiche 0
  3. (1)→(3)→(2)→(4) : Thread1 affiche 1, Thread2 affiche 1
  4. (3)→(1)→(4)→(2) : Thread1 affiche 1, Thread2 affiche 1

Sortie impossible : Les deux threads affichent 0

Explication : Si Thread1 affiche 0, alors (2) précède (3). Si Thread2 affiche 0, alors (4) précède (1). Mais cela créerait un cycle : (2)→(3)→(4)→(1)→(2), impossible en cohérence séquentielle !

Il existe en tout six entrelacements qui respectent l’ordre de chaque programme ; la Figure 11 les donne tous avec leurs sorties.

Figure 11: Les six ordres globaux possibles en cohérence séquentielle et ce qu’affiche chaque fil.

Modèles de cohérence relâchée

Introduction aux modèles relâchés

La cohérence séquentielle est intuitive mais limite les optimisations. Les modèles relâchés permettent certains réordonnancements pour améliorer les performances.

NoteDéfinition

Les modèles de cohérence relâchée assouplissent les contraintes d’ordonnancement. Le plus répandu sur les PC et les serveurs est TSO (Total Store Order), celui des processeurs x86 ; les processeurs ARM et RISC-V autorisent davantage de réordonnancements.

TSO (Total Store Order)

NoteDéfinition

Le modèle TSO (x86) permet uniquement le réordonnancement W→R :

  • Les écritures peuvent être bufferisées et retardées
  • Les lectures peuvent dépasser les écritures précédentes (vers des adresses différentes)
  • L’ordre des lectures est préservé
  • L’ordre des écritures est préservé

Exemple TSO :

// Thread 1              // Thread 2
A = 1;                   B = 1;
r1 = B;                  r2 = A;

// Sous TSO, possible d'avoir r1 = 0 et r2 = 0
// Car les écritures peuvent être bufferisées

Chaque cœur range ses écritures dans un tampon d’écriture (store buffer) et continue sans attendre ; une lecture vers une autre adresse peut alors passer avant que l’écriture précédente n’atteigne la mémoire. La Figure 12 montre l’exécution qui donne \(r1 = r2 = 0\) : les deux écritures attendent dans les tampons quand les deux lectures vont en mémoire.

Figure 12: TSO : après les deux lectures, \(A = 1\) et \(B = 1\) sont encore dans les tampons, la mémoire contient toujours \(A = 0\) et \(B = 0\) ; les deux fils ont lu \(0\).

Barrières mémoire

NoteDéfinition

Les barrières mémoire forcent l’ordre des opérations :

  • StoreLoad : Empêche W→R (la plus coûteuse)
  • StoreStore : Empêche W→W
  • LoadLoad : Empêche R→R
  • LoadStore : Empêche R→W

Sous TSO, seule la barrière StoreLoad est utile (les trois autres ordres sont déjà garantis). Dans l’exemple précédent, une barrière StoreLoad (mfence sur x86) entre A = 1 et r1 = B, et de même dans le second fil, oblige chaque fil à vider son tampon avant de lire : la sortie \(r1 = r2 = 0\) devient impossible.

Métriques et optimisations

Métriques de performance

NoteDéfinition

Métriques clés pour la cohérence :

  • Hit rate : Pourcentage d’accès trouvés en cache
  • Coherence miss : Miss causés par invalidations de cohérence
  • False sharing rate : Invalidations dues au false sharing

Tableau récapitulatif des transitions

Transition Transaction Latence MSI MESI
Read miss (excl.) BusRd 100 cycles I→S I→E
Write après read excl. BusRdX/Aucune 100/1 cycles S→M E→M
Write miss BusRdX 100 cycles I→M I→M
Invalidation autre BusRdX - S/M→I S/M→I
Write-back BusWB 100 cycles M→S/I M→S/I

Techniques d’optimisation

  1. Minimiser le partage : Variables locales, réduction finale
  2. Aligner les données : Padding, structure dont le champ porte alignas(64)
  3. Batching : Grouper les modifications
  4. Prefetching : Anticiper les besoins futurs

Synthèse et points clés

Comparaison des protocoles

Caractéristique MSI MESI Gain MESI
Nombre d’états 3 4 -
État Exclusive Non Oui Permet E→M local
Write sur donnée exclusive BusRdX Aucun bus 99 cycles (100 → 1)
Signal de partage sur le bus Non Oui Choix de E ou S
Trafic bus Plus élevé Réduit Selon le programme

Le gain de trafic de MESI dépend du programme : il porte sur les données lues puis écrites par un seul cœur (une transaction BusRdX en moins à chaque fois) et disparaît quand les données sont réellement partagées.

Points à retenir

  1. La cohérence est essentielle dans les systèmes multicœurs modernes
  2. L’espionnage du bus (snooping) permet la cohérence par surveillance du bus
  3. MSI : 3 états (Modified, Shared, Invalid)
  4. MESI : Ajoute Exclusive pour permettre E→M sans bus (gain majeur)
  5. BusWB : Write-back des données modifiées vers la mémoire
  6. False sharing : des variables indépendantes dans une même ligne ; la ligne fait des allers-retours
  7. Cohérence séquentielle : Modèle mental intuitif mais restrictif
  8. TSO (x86) : permet W→R ; barrière StoreLoad pour l’interdire
  9. Optimisations : Padding, alignement, variables locales
  10. Latences types : Hit=1, Miss=100, BusWB=100, BusRdX=100 cycles

Questions de révision

AstuceÉnoncé

QCM - Cochez les affirmations vraies :

□ L’état Modified peut être dans plusieurs caches simultanément

□ MESI élimine tous les cache miss

□ E→M ne génère pas de transaction bus

□ Write-allocate charge la ligne avant modification

□ BusWB transfère les données modifiées vers la mémoire

□ False sharing affecte des variables logiquement indépendantes

□ TSO permet le réordonnancement W→R

□ L’état Exclusive garantit qu’aucun autre cache n’a la ligne

AstuceCorrection
Afficher la correction

☑ E→M ne génère pas de transaction bus ✓

☑ Write-allocate charge la ligne avant modification ✓

☑ BusWB transfère les données modifiées vers la mémoire ✓

☑ False sharing affecte des variables logiquement indépendantes ✓

☑ TSO permet le réordonnancement W→R ✓

☑ L’état Exclusive garantit qu’aucun autre cache n’a la ligne ✓

Explications des erreurs :

  • Modified est exclusif à un seul cache
  • MESI ne supprime aucun défaut de lecture ni d’écriture sur une ligne absente ; il supprime l’« upgrade » (BusRdX) d’une écriture sur une ligne en E

Prolongements et références

  • Prochaine séance : Séance 3, programmation parallèle avancée (synchronisation)
  • TD associé : TD de la Séance 2 (politiques d’écriture, traces MSI et MESI avec calculs de latence, false sharing, cohérence séquentielle et TSO)
  • Lab Python : Lab 3, la mémoire : lecture par lignes de cache, copies envoyées aux processus, écritures concurrentes dans une même mémoire, calcul local et fusion à la fin, tableau partagé sans copie
  • Lecture recommandée : Hennessy & Patterson, Computer Architecture: A Quantitative Approach, chapitre 5
  • Références : M. S. Papamarcos et J. H. Patel, A Low-Overhead Coherence Solution for Multiprocessors with Private Cache Memories, ISCA 1984, p. 348-354 (MESI, protocole Illinois) ; L. Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Transactions on Computers, C-28(9), 1979, p. 690-691 (cohérence séquentielle)

Pour cette séance

Les slides

À lire en ligne

À télécharger

Retour au sommet