TD — Séance 4 — Architectures distribuées et NUMA
Appliquer chaque notion du cours sur des données nouvelles : latence moyenne d’un programme NUMA, saturation d’un bus espionné, latences et messages du protocole à répertoire, trace complète d’un répertoire, placement des pages, algorithme conscient de NUMA et réduction distribuée. Durée : une séance de TD.
Protocole à répertoire du cours (MSI, nœud home, vecteur de présence complet) : chaque message coûte \(t_r\) sur le réseau, chaque accès à la mémoire du home coûte \(t_m\) ; les invalidations d’une écriture partent en parallèle et le home lit la mémoire pendant ce temps. Le vecteur de présence s’écrit du nœud 0 au dernier nœud (10100 : N0 et N2 ont une copie). Les accès d’un programme ne se recouvrent pas. Pages de \(4\) Kio.
Exercice 1 : latence moyenne d’un programme NUMA
Un programme parcourt un tableau de \(2\) millions de valeurs float64 sur un serveur à \(4\) nœuds. Latences : \(95\) ns en local, \(150\) ns à 1 saut, \(220\) ns à 2 sauts. Les accès se répartissent ainsi : \(45\) % locaux, \(40\) % à 1 saut, \(15\) % à 2 sauts ; chaque accès va en mémoire.
- Quelle est la taille du tableau en Mo ? Calculer la latence moyenne par accès.
- Après un nouveau placement des données, \(85\) % des accès sont locaux et le reste à 1 saut. Calculer la nouvelle latence moyenne, l’accélération et la baisse du temps en pourcentage.
- Calculer le temps total d’un parcours du tableau dans les deux cas.
- Quelle part minimale d’accès locaux (le reste à 1 saut) faut-il pour descendre sous \(110\) ns ?
- Le processeur tourne à \(2{,}5\) GHz. Combien de cycles le cœur attend-il pour un accès local, à 1 saut, à 2 sauts ?
Exercice 2 : un bus espionné trop chargé
Un bus partagé écoule \(300\) millions de transactions par seconde ; chaque cœur en émet \(25\) millions par seconde.
À partir de combien de cœurs le bus est-il saturé ?
Remplir le tableau de la charge du bus (demande divisée par la capacité).
cœurs demande (M/s) charge (%) le bus tient-il la charge ? 8 16 24 Avec \(24\) cœurs, un cœur écrit une donnée qu’ont en copie trois autres cœurs. Combien de caches examinent la transaction
BusRdX? Combien de messages un protocole à répertoire enverrait-il pour la même écriture ? Que deviennent ces deux nombres avec \(64\) cœurs ?
Exercice 3 : latences du protocole à répertoire
Un serveur NUMA a \(8\) nœuds N0 à N7 ; \(t_r=40\) ns par message, \(t_m=110\) ns par accès mémoire. Le bloc Y a son home en N5. Le nœud N2 n’a pas Y dans son cache.
- N2 lit Y, propre en mémoire : écrire la suite des messages, leur nombre et la latence.
- N2 lit Y, modifié par N7 : même travail.
- Comparer les deux latences à un accès local (\(110\) ns) : combien de fois plus lent ?
- Y est maintenant partagé par N1, N3 et N6, et N2 veut l’écrire. Nombre de messages ? Latence si les invalidations partent en parallèle, puis si elles partent l’une après l’autre ? Vecteur de présence après l’écriture ?
Exercice 4 : trace d’un répertoire
Une machine a \(5\) nœuds N0 à N4. Le bloc X a son home en N3 et vaut \(2\) en mémoire ; aucun cache ne l’a. \(t_r=30\) ns, \(t_m=90\) ns. Les opérations suivantes ont lieu dans l’ordre.
Pour chaque opération, donner le cas (succès, lecture d’un bloc propre, lecture d’un bloc modifié, écriture d’un bloc partagé), le nombre de messages, la latence, puis l’état du répertoire, le vecteur de présence et les états MSI des cinq caches après l’opération.
opération cas msg latence état présence caches N0…N4 N0 lit X N2 lit X N1 écrit X = 7 N0 lit X N2 lit X N1 lit X Quelle valeur contient la mémoire du home après la troisième opération ? Après la quatrième ?
Total des messages et des latences de la séquence.
Même séquence avec un bus espionné (MSI) reliant les \(5\) caches : combien de transactions sur le bus, et combien d’examens de transaction par les autres caches ? Même question pour \(64\) caches.
Exercice 5 : placement des pages
Un serveur a \(4\) nœuds reliés en anneau : N0–N1, N1–N3, N3–N2, N2–N0 (N0 et N3 sont à 2 sauts, comme N1 et N2). Latences de l’exercice 1. Un tableau de \(64\) Kio occupe \(16\) pages p0 à p15. Quatre fils, un par nœud (le fil \(i\) sur N\(i\)), lisent chacun un quart contigu : le fil \(i\) lit les pages \(4i\) à \(4i+3\).
Le fil principal, sur N0, initialise tout le tableau. Où sont les pages ? Latence moyenne de chaque fil, puis du programme. Part des accès distants ?
Les pages sont entrelacées (
numactl --interleave=all) : page \(i\) sur le nœud \(i \bmod 4\). Mêmes questions.Chaque fil initialise son quart (premier contact). Mêmes questions.
Pour chaque placement, quelle part des lectures le contrôleur mémoire de chaque nœud sert-il ? Lequel des deux premiers placements est préférable quand le premier contact est impossible ?
placement fil 0 fil 1 fil 2 fil 3 moyenne distants fil principal entrelacé premier contact
Exercice 6 (approfondissement) : un produit de matrices sur quatre nœuds
Le serveur de l’exercice 5 a \(6\) cœurs par nœud. Il faut multiplier deux matrices \(6000\times6000\) de float64. Approche 1 : A et B sur le nœud 0, \(24\) fils répartis sur les quatre nœuds. Approche 2 : A partitionnée en quatre blocs de lignes, un par nœud ; B répliquée sur chaque nœud ; les \(6\) fils d’un nœud calculent avec son bloc.
- Approche 1 : part des accès distants et latence moyenne (chaque fil fait le même nombre d’accès) ?
- Approche 2 : latence moyenne et accélération par rapport à l’approche 1 ?
- Quelle mémoire supplémentaire la réplication de B coûte-t-elle (en Mo) ?
- Variante sans réplication : B entrelacée sur les quatre nœuds, A partitionnée ; la moitié des accès porte sur A, l’autre sur B. Latence moyenne d’un fil du nœud 0 et accélération par rapport à l’approche 1 ?
- Une somme de \(12\) millions de valeurs est répartie sur \(6\) processus. Chaque processus crée sa partition et renvoie un message (indice, somme) de deux nombres de \(8\) octets. Combien d’octets circulent au total ? Combien en circulerait-il si le parent créait les données et les envoyait aux processus ?
Pour cette séance
Le cours
Les slides
À lire en ligne
À télécharger
- Notebooks des labs de la séance 4 (ZIP, 49 Ko)