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

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

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

ImportantObjectif

Appliquer chaque notion du cours sur des données nouvelles : politiques d’écriture, traces des protocoles MSI et MESI avec leurs latences, false sharing et disposition des données en mémoire, cohérence séquentielle, modèle TSO et barrières mémoire. Durée : une séance de TD.

NoteConventions

Protocoles à espionnage de bus, write-back et write-allocate. Transactions : BusRd, BusRdX (y compris pour écrire depuis S), BusWB. Latences du cours : succès \(1\) cycle ; BusRd ou BusRdX \(100\) cycles ; BusWB \(100\) cycles de plus quand un autre cache détient la ligne en M ; E\(\to\)M en MESI : \(1\) cycle. Colonne « Fournie par » : « Mémoire », le cache qui détenait la ligne en M (après son BusWB), ou « – » quand le demandeur avait déjà une copie valide. Ligne de cache de \(64\) octets ; int de \(4\) octets, long de \(8\) octets (x86-64). Toutes les variables valent \(0\) au départ.

Exercice 1 : politiques d’écriture

Un programme effectue la séquence suivante sur une variable y non présente en cache, puis la ligne de y est évincée :

  1. Write y = 3 ; (2) Read y ; (3) Write y = 8 ; (4) Write y = 6 ; (5) Read y ; (6) éviction.

  1. Compléter le tableau pour les trois configurations : pour chaque accès, succès (S) ou défaut (D) et nombre de transferts mémoire.

    accès WT + no-allocate WB + allocate WT + allocate
    S / D transferts S / D transferts S / D transferts
    (1) Write y = 3
    (2) Read y
    (3) Write y = 8
    (4) Write y = 6
    (5) Read y
    (6) éviction
    total

  2. Donner le total de chaque configuration. Laquelle limite le trafic ? Pourquoi write-through + write-allocate ne gagne-t-il rien ici sur write-through + no-allocate ?

  3. Avec write-back + allocate, à quel moment la mémoire contient-elle la valeur \(6\) ? Que lirait un autre processeur qui irait chercher y en mémoire juste après l’accès (4), en l’absence de protocole de cohérence ?

Exercice 2 : trace MSI à trois processeurs

Trois processeurs P1, P2, P3 et leurs caches C1, C2, C3 utilisent le protocole MSI ; tous les caches sont initialement invalides. Séquence :

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

  1. Compléter le tableau (transaction sur le bus, origine de la donnée, état de chaque cache, sous la forme I\(\to\)S quand l’état change).

    # Action Bus Fournie par C1 C2 C3
    0 Initial – – I I I

  2. À quelles étapes y a-t-il une invalidation ? Quels caches sont invalidés ?

  3. Après quelles étapes la mémoire est-elle périmée ? À quelles étapes redevient-elle à jour, et par quelle transaction ?

  4. Quelle est la latence totale de la séquence (latences du cours) ?

Exercice 3 : trace MESI et latences

Mêmes trois processeurs, protocole MESI, caches initialement invalides. Séquence :

  1. P3 : Read x
  2. P3 : Write x = 8
  3. P1 : Read x
  4. P2 : Read x
  5. P2 : Write x = 4
  6. P2 : Write x = 6
  7. P1 : Write x = 2

  1. Compléter le tableau : transaction, origine de la donnée, états, latence de l’étape et latence cumulée.

    # Action Bus Fournie par C1 C2 C3 Latence Cumul
    0 Initial – – I I I – 0

  2. Refaire le calcul de la latence de chaque étape avec MSI. Quel est le gain de MESI ? À quelle étape est-il obtenu ?

  3. Pourquoi l’écriture (5) coûte-t-elle \(100\) cycles dans les deux protocoles, et l’écriture (6) seulement \(1\) cycle ?

  4. Même travail, sans tableau détaillé, pour la séquence : P1 : Read x ; P2 : Read x ; P3 : Write x = 5 ; P3 : Read x ; P1 : Read x ; P2 : Write x = 1. Donner les états après chaque étape et les deux latences totales. Pourquoi MESI ne gagne-t-il rien ici ? Quelle étape utilise le signal de partage ?

Exercice 4 : false sharing

Le service des statistiques compte les ventes de huit régions (Dakar, Thiès, Kaolack, Saint-Louis, Ziguinchor, Kolda, Matam, Tambacounda) avec huit fils sur huit cœurs ; le fil i incrémente ventes[i] \(500\,000\) fois.

long ventes[8];

/* le fil i execute : */
for (int j = 0; j < 500000; j++) {
    ventes[i]++;
}
  1. Combien d’octets occupe ventes ? Dans combien de lignes de cache, si le tableau commence au début d’une ligne ? Et sinon ?
  2. Donner une borne haute du nombre de transferts de la ligne entre caches. Pourquoi le nombre réel est-il plus petit ?
  3. Écrire une structure rembourrée struct vente_p qui place chaque compteur à \(64\) octets du suivant. Quelle est la taille du rembourrage ? Que vaut sizeof(struct vente_p) ?
  4. La déclaration alignas(64) long ventes[8]; corrige-t-elle le problème ? Proposer une déclaration qui aligne chaque compteur sur une ligne.
  5. Réécrire la boucle avec une variable locale. Combien d’écritures chaque fil fait-il alors dans le tableau partagé ?
  6. Compilée avec gcc -O2, la boucle d’origine devient addq $500000, (%rdx,%rax,8). Que devient le false sharing ? Comment le rendre mesurable dans une expérience ?

Exercice 5 : cohérence séquentielle

Deux fils partagent X et Y, qui valent \(0\) au départ ; r1 et r2 sont des registres du second fil.

Fil 1 Fil 2
(1) X = 1 (3) r1 = Y
(2) Y = 1 (4) r2 = X

  1. Combien d’ordres globaux respectent l’ordre de chaque programme ? Les écrire tous et compléter le tableau.

    n° ordre global r1 r2
    1
    2
    3
    4
    5
    6

  2. Quelles sorties \((r1, r2)\) sont possibles en cohérence séquentielle ? La sortie \((1, 0)\) est-elle possible ? Justifier par un cycle d’ordre.

  3. Ce code sert à « publier » une donnée : X est la donnée, Y un drapeau. Que garantit la réponse de (b) au fil qui lit Y = 1 ?

  4. Sous TSO (x86), la sortie \((1, 0)\) devient-elle possible ? Justifier avec les règles de TSO.

Exercice 6 : vrai ou faux

Dire si chaque affirmation est vraie ou fausse et justifier en une phrase.

  1. En MSI, une ligne en S peut se trouver dans plusieurs caches à la fois.
  2. Une lecture qui trouve sa ligne en M dans son propre cache émet un BusRd.
  3. En MESI, une lecture qui part de I donne toujours l’état E.
  4. Avec write-through et write-no-allocate, une écriture sur une ligne absente ne charge pas la ligne.
  5. Un cache en E qui observe un BusRdX passe en I sans BusWB.
  6. Déclarer deux compteurs voisins volatile supprime le false sharing.
  7. Sous TSO, deux écritures d’un même fil peuvent être vues dans l’ordre inverse par un autre fil.
  8. Une barrière StoreLoad empêche une lecture de dépasser une écriture précédente du même fil.

Exercice 7 (approfondissement) : TSO et barrières

Fil 1 Fil 2
(1) X = 1 (4) Z = 1
(2) Y = 1 (5) r2 = X
(3) r1 = Z
  1. Combien d’ordres globaux respectent l’ordre de chaque programme ? En cohérence séquentielle, la sortie \(r1 = r2 = 0\) est-elle possible ? Justifier sans énumérer tous les ordres.
  2. Sous TSO, décrire une exécution, avec le contenu des tampons d’écriture et de la mémoire à chaque étape, qui donne \(r1 = r2 = 0\).
  3. On place une barrière StoreLoad entre (2) et (3), dans le fil 1 seulement. La sortie \(r1 = r2 = 0\) reste-t-elle possible ? Justifier.
  4. Où faut-il placer des barrières pour interdire cette sortie ? Pourquoi une barrière StoreStore entre (1) et (2) ne sert-elle à rien sous TSO ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet