Plan du cours — Architecture et Programmation Parallèles

Plan du cours d’Architecture et Programmation Parallèles : objectifs, prérequis, organisation, conventions et carte des quatre séances.

NoteCe que le cours fait maîtriser

• Expliquer pourquoi la fréquence des processeurs a cessé d’augmenter vers 2005 et pourquoi le gain de performance passe depuis par le parallélisme ; classer une machine selon la taxonomie de Flynn ; calculer une puissance de crête.
• Prévoir, avant d’écrire le code, le gain d’une parallélisation : accélération, efficacité, lois d’Amdahl et de Gustafson, granularité et surcoût, travail et profondeur d’un algorithme.
• Calculer un temps d’accès moyen à la mémoire, décomposer une adresse en étiquette, index et décalage, compter les défauts de cache d’un parcours de tableau ou d’un produit matriciel.
• Dérouler à la main les protocoles de cohérence MSI et MESI sur une trace de plusieurs processeurs, en calculer la latence ; reconnaître et corriger le faux partage ; dire quels résultats un modèle mémoire (cohérence séquentielle, TSO) autorise.
• Écrire du code parallèle correct : repérer une course critique, la corriger par un verrou, un atomique ou une réduction ; prévenir l’interblocage ; choisir un patron (fork-join, pipeline, producteur-consommateur) et une stratégie d’équilibrage.
• Calculer le coût d’un accès dans une machine NUMA et dans un protocole à répertoire ; placer les données près des calculs (premier contact, entrelacement, partition par nœud).

AvertissementPrérequis

Programmation en Python ; notions d’architecture des ordinateurs (processeur, mémoire, caches).

Navigation conceptuelle

Un programme séquentiel ne profite plus des progrès du matériel : depuis le milieu des années 2000, un processeur ne gagne plus en fréquence, il gagne des cœurs. Pour aller plus vite, un programme doit donc répartir son travail entre plusieurs unités de calcul. Ce gain a trois ennemis. Le premier est la part du travail qui reste séquentielle : la loi d’Amdahl dit combien elle coûte. Le deuxième est la mémoire : un accès à la mémoire principale coûte une centaine de cycles, et les caches qui la masquent doivent rester cohérents entre cœurs, au prix de messages, d’invalidations et parfois de faux partage. Le troisième est la coordination : partager une donnée exige de synchroniser, et une synchronisation mal conçue produit des résultats faux (course critique) ou un programme bloqué (interblocage). Les machines à plusieurs processeurs ajoutent une distance : en NUMA, la mémoire d’un autre nœud est plus lente que la mémoire locale, et le placement des données devient une décision du programmeur. Les quatre séances suivent l’ordre où ces idées dépendent les unes des autres : mesurer le gain et comprendre la mémoire (S1), garder les caches cohérents (S2), écrire du code parallèle correct (S3), puis placer les données dans une machine à mémoire répartie (S4).

Identité du cours

Place dans le cursus	Après un cours d’architecture des ordinateurs et un cours de programmation en C. Il éclaire les calculs intensifs des cours de ML et de DL : produit matriciel d’une couche, réduction d’un gradient sur un lot, chargement des données en pipeline.
Volume	Quatre séances de trois heures (S1 à S4), chacune consacrée à un module.
Déroulé type	Environ la moitié de la séance sur le deck (exposé, calculs à la main, traces de protocoles, exercices corrigés en direct), l’autre moitié en TP.
Langue et registre	Français, registre académique impersonnel ; le terme anglais usuel est donné à sa première apparition (antémémoire ou cache, cache miss, false sharing, deadlock).
Outils	Python 3.12 ou plus récent (threading, multiprocessing, concurrent.futures, queue), NumPy, Matplotlib ; sous Linux, lscpu, numactl et perf quand la machine les fournit.

Conventions de notation et valeurs de référence

Objet	Convention
Nombre d’unités de calcul	\(p\) : nombre de processeurs, de cœurs ou de fils d’exécution selon le contexte, toujours précisé. La lettre \(n\) est réservée à la taille du problème (nombre d’éléments, de patients, d’itérations) : c’est la distinction qui rend lisible la loi de Gustafson, où \(n\) grandit avec \(p\). Beaucoup de textes notent \(n\) le nombre de processeurs ; le changement est signalé en S1.
Temps	\(T_1\) temps séquentiel, \(T_p\) temps sur \(p\) unités ; \(T_\infty\) profondeur d’un calcul (span), son temps sur une infinité d’unités.
Mesures du gain	Accélération \(S(p)=T_1/T_p\) (speedup) ; efficacité \(E(p)=S(p)/p\).
Fractions séquentielles	\(f\) : part séquentielle du temps de l’exécution séquentielle (Amdahl) ; \(s\) : part séquentielle du temps de l’exécution parallèle (Gustafson). Les deux ne se confondent pas : S1 donne la conversion.
Granularité	\(G=T_{\text{calcul}}/T_{\text{comm}}\), rapport du calcul utile au temps de gestion (création, synchronisation, communication).
Hiérarchie mémoire	Latences de référence : registre moins d’une nanoseconde ; L1 1 ns ; L2 4 ns ; L3 12 ns ; mémoire locale 80 ns ; mémoire distante à un saut 140 ns, à deux sauts 200 ns.
Caches	Ligne (cache line) de 64 octets ; un int occupe 4 octets, un double 8 ; Ko et Mo désignent ici \(2^{10}\) et \(2^{20}\) octets. Adresse = étiquette | index | décalage. Temps d’accès moyen \(\mathrm{AMAT}=t_{\text{succès}}+m\times t_{\text{pénalité}}\) (average memory access time), \(m\) taux de défaut.
Cohérence	Latences de référence en cycles : succès (hit) 1 ; défaut (miss) 100 ; écriture en retour BusWB 100 ; lecture exclusive BusRdX 100. États M, E, S, I ; requêtes du processeur PrRd, PrWr ; transactions du bus BusRd, BusRdX, BusWB. Dans un tableau de trace, \(\mathrm{I}\to\mathrm{S}\) se lit « passe de I à S ».
Répertoire	Nœud home (propriétaire de l’adresse et de l’entrée du répertoire), demandeur (requestor), possesseur (owner) d’une copie modifiée ; vecteur de présence d’un bit par nœud ; latence réseau de référence 50 ns par message.
Vocabulaire	Cohérence de cache (cache coherence) : accord des copies d’une même adresse ; modèle mémoire ou modèle de consistance (memory consistency model) : ordre dans lequel les accès à des adresses différentes deviennent visibles. Fil d’exécution (thread), course critique (race condition), section critique, verrou (mutex), interblocage (deadlock), famine (starvation), livelock.
Code	Python : threading.Lock, Semaphore, Barrier, queue.Queue, concurrent.futures.
Nombres	Virgule décimale ; espace pour les milliers (\(10\,000\)) ; les valeurs intermédiaires d’un calcul enchaîné sont affichées avec assez de décimales pour qu’un calcul refait à partir des nombres affichés retrouve le résultat affiché.

Architecture du cours

Quatre séances de trois heures et ce que chacune apprend à faire.

Séance	Titre	Questions directrices
S1	Fondements de l’architecture parallèle	Pourquoi les processeurs ne vont-ils plus plus vite ? Pourquoi deux boucles qui font les mêmes calculs diffèrent-elles d’un facteur quatre ? Que gagne-t-on à multiplier les cœurs ?
S2	Cohérence de cache et protocoles	Comment deux caches qui gardent la même donnée restent-ils d’accord ? Pourquoi deux fils qui n’écrivent jamais la même variable se ralentissent-ils ? Dans quel ordre un autre cœur voit-il mes écritures ?
S3	Programmation parallèle avancée	Pourquoi un compteur partagé perd-il des incréments ? Comment un programme correct peut-il se bloquer pour toujours ? Comment faire travailler tous les cœurs jusqu’au bout ?
S4	Architectures distribuées et NUMA	Que devient la cohérence quand le bus ne suffit plus ? Comment placer les données près des cœurs qui les utilisent ?