Séance 1 — Fondements de l’architecture parallèle
bleutitreSéance 1 : Fondements de l’architecture parallèle
Objectifs
- Expliquer l’arrêt de la montée en fréquence par \(P=C\,V^2f\), et ce que plusieurs cœurs apportent.
- Classer une architecture selon Flynn : SISD, SIMD, MISD, MIMD.
- Situer registres, caches et mémoire principale en cycles ; suivre une ligne de cache, un succès, un défaut.
- Calculer l’accélération et l’efficacité d’un programme parallèle.
- Appliquer les lois d’Amdahl et de Gustafson, et dire laquelle convient à un problème.
- Choisir une granularité selon le surcoût et le nombre de processeurs.
Les ordres de grandeur matériels sont datés : tendances des processeurs de 1971 à 2021 d’après les données de K. Rupp (50 Years of Microprocessor Trend Data), latences et capacités typiques des processeurs de bureau des années 2020. Dans les figures, un cadre orange signale un élément examiné sans changement, un cadre rouge un élément modifié à l’étape.
Introduction : la nécessité du parallélisme
L’idée du parallélisme informatique est de répartir un travail : au lieu d’un processeur qui fait tout, l’une après l’autre, plusieurs processeurs travaillent ensemble pour accomplir la tâche plus vite. Pour comprendre pourquoi cette idée, ancienne, est devenue incontournable, il faut revenir à la façon dont les processeurs ont gagné en vitesse pendant cinquante ans.
L’évolution des processeurs : du séquentiel au parallèle
Le processeur exécute les instructions. Sa fréquence d’horloge (en hertz) donne le nombre de cycles par seconde : un processeur à 3 GHz bat 3 milliards de cycles par seconde.
Un cycle d’horloge est un « battement » de l’horloge du processeur, l’unité de temps minimale qui rythme toutes ses opérations. Une instruction prend un ou plusieurs cycles selon sa complexité. À 3 GHz, un cycle dure \(1/3\) ns, soit environ \(0{,}33\) ns.
Pendant des décennies, le nombre de transistors par puce a doublé environ tous les deux ans (loi de Moore), et les performances des processeurs ont progressé presque au même rythme. Cette amélioration venait de trois sources :
- l’augmentation de la fréquence d’horloge (des MHz aux GHz) ;
- la miniaturisation des transistors ;
- l’amélioration de l’architecture séquentielle.
Un programme écrit une fois allait donc plus vite à chaque génération de processeurs, sans être modifié. La Figure 1 montre pourquoi ce n’est plus le cas.
Chaque point est un processeur. Les transistors (en gris) suivent une droite sur l’échelle logarithmique : de quelque \(2\,300\) en 1971 à près de \(58\) milliards en 2021, soit un doublement tous les deux ans environ. La fréquence (en bleu) monte aussi, un peu moins vite, jusqu’au milieu des années 2000, puis plafonne à quelques GHz. Le nombre de cœurs (en rouge) reste à un jusque-là, puis augmente : à partir de 2005, les transistors supplémentaires servent à multiplier les cœurs, et non plus à accélérer un cœur unique.
Le mur de la fréquence : un problème de physique
Vers 2004, une limite physique est atteinte :
- la fréquence maximale plafonne vers 3 à 4 GHz (Pentium 4 à \(3{,}8\) GHz en novembre 2004 ; Intel renonce alors au modèle à 4 GHz) ;
- la chaleur à évacuer devient un problème : la puissance dissipée vaut \(P = C \times V^2 \times f\), où \(C\) est la capacité commutée, \(V\) la tension et \(f\) la fréquence ;
- la consommation électrique devient prohibitive ;
- les transistors nanométriques laissent passer des courants de fuite.
Pour faire monter la fréquence, il faut en général monter aussi la tension. Avec l’hypothèse d’école d’une tension proportionnelle à la fréquence, la puissance varie comme \(f^3\) : la Figure 2 en tire les conséquences.
Un cœur ralenti à \(0{,}8\,f\) fait \(0{,}8\) fois le travail mais ne dissipe plus que \(0{,}8^3=0{,}512\) fois la puissance. Deux cœurs à \(0{,}8\,f\) font donc \(1{,}6\) fois le travail d’un cœur à \(f\), pour \(2\times0{,}512=1{,}024\) fois sa puissance. La solution est le parallélisme : au lieu d’un processeur très rapide, plusieurs processeurs (cœurs) travaillent ensemble.
Paradigme séquentiel et paradigme parallèle
La Figure 3 compare les deux façons d’exécuter huit tâches indépendantes, T1 à T8, de même durée \(t\). Un seul processeur les enchaîne et termine à \(8t\). Quatre processeurs identiques en prennent deux chacun et terminent ensemble à \(2t\) : le travail va quatre fois plus vite. Le gain suppose que les tâches soient indépendantes : une tâche qui attend le résultat d’une autre ne peut pas s’exécuter en même temps qu’elle.
Un processeur mono-cœur de 2004 fonctionne à \(3{,}6\) GHz. Un processeur moderne a 8 cœurs à \(2{,}4\) GHz chacun.
Question : quel est le gain théorique maximal de performance ?
Afficher la correction
- Processeur 2004 : \(1 \times 3{,}6 = 3{,}6\) GHz de capacité de calcul.
- Processeur moderne : \(8 \times 2{,}4 = 19{,}2\) GHz de capacité de calcul théorique.
- Gain théorique maximal : \(19{,}2 / 3{,}6 = \mathbf{5{,}33}\).
Hypothèse : les deux processeurs exécutent le même nombre d’instructions par cycle ; le produit cœurs \(\times\) fréquence ne mesure alors que la capacité de calcul.
Note importante : ce gain n’est atteint que si le programme utilise parfaitement les 8 cœurs. En pratique, c’est rarement le cas à cause de la partie séquentielle du code (loi d’Amdahl, section Section 8). Un programme séquentiel, lui, n’utilise qu’un cœur : il va \(2{,}4/3{,}6=0{,}67\) fois aussi vite, il ralentit.
Taxonomie de Flynn
Michael Flynn a proposé en 1966 une classification des architectures selon deux critères : le nombre de flux d’instructions (Single ou Multiple) et le nombre de flux de données (Single ou Multiple) traités simultanément.
La taxonomie de Flynn classe les architectures en quatre catégories selon le nombre de flux d’instructions et de données traités simultanément.
| Single Data | Multiple Data | |
|---|---|---|
| Single Instruction | SISD | SIMD |
| Multiple Instruction | MISD | MIMD |
La Figure 4 dessine les quatre classes avec les mêmes éléments : une unité de contrôle (UC) par flux d’instructions, qui décode les instructions et commande ; une unité de traitement (UT) qui calcule ; les données (D) qu’elle lit et écrit.
SISD (Single Instruction, Single Data)
Architecture séquentielle classique, où une seule instruction est exécutée sur une seule donnée à la fois. C’est le modèle de von Neumann traditionnel.
Une instruction traite une donnée à la fois. Exemples : Intel 8086, ARM Cortex-M0, microcontrôleur d’une carte Arduino Uno. Utilisation : microcontrôleurs, petits systèmes embarqués.
SIMD (Single Instruction, Multiple Data)
Architecture où une même instruction s’applique simultanément à plusieurs données. Idéal pour le traitement vectoriel et les opérations sur des tableaux.
La Figure 5 montre l’effet d’une instruction vectorielle : là où un processeur scalaire exécute quatre instructions d’addition, une seule instruction additionne les quatre paires de nombres rangées côte à côte dans des registres larges. Exemples : instructions SSE et AVX (Intel), NEON (ARM), GPU (que NVIDIA appelle SIMT, une variante de SIMD). Utilisation : traitement d’images, calcul scientifique, apprentissage profond.
MISD (Multiple Instruction, Single Data)
Architecture où plusieurs instructions différentes traitent la même donnée. Très rare en pratique, utilisée principalement pour la redondance.
Exemple : systèmes redondants pour la tolérance aux fautes. Utilisation : systèmes critiques (spatial, nucléaire). Beaucoup d’auteurs rangent ces systèmes en MIMD.
MIMD (Multiple Instruction, Multiple Data)
Architecture où plusieurs processeurs exécutent des instructions différentes sur des données différentes. C’est l’architecture la plus flexible et la plus courante aujourd’hui.
Exemples : processeurs multicœurs, grappes de machines (clusters). Utilisation : serveurs, stations de travail, supercalculateurs.
Un processeur multicœur est MIMD entre ses cœurs ; chacun de ses cœurs exécute aussi des instructions SIMD (AVX). Une machine réelle relève souvent de plusieurs classes à des niveaux différents.
Classer les architectures suivantes selon Flynn :
- un GPU qui exécute la même opération sur 1024 pixels ;
- un processeur à quatre cœurs où chaque cœur exécute un programme différent ;
- le microcontrôleur d’une carte Arduino Uno ;
- un pipeline de vérification où 3 unités vérifient le même calcul.
Afficher la correction
- SIMD : une instruction (la même opération) sur plusieurs données (1024 pixels).
- MIMD : instructions multiples (programmes différents) sur données multiples.
- SISD : architecture séquentielle classique.
- MISD : instructions multiples (3 vérifications) sur une même donnée.
Hiérarchies mémoire
Le problème de la vitesse mémoire
Un processeur moderne peut exécuter plusieurs instructions par cycle d’horloge (environ \(0{,}3\) ns à 3 GHz). Mais un accès à la mémoire principale prend environ 60 à 100 ns : c’est environ 200 à 300 fois plus lent (180 à 300 cycles). Plus une mémoire est proche du processeur et rapide, plus elle est chère et limitée en taille ; d’où une organisation en niveaux.
La hiérarchie mémoire est une organisation en niveaux de stockage, du plus rapide (et cher) au plus lent (et économique). Chaque niveau sert de cache pour le niveau inférieur.
La Figure 6 place chaque niveau sur une échelle logarithmique de cycles : à 3 GHz, 1 ns vaut 3 cycles. Un accès aux registres prend moins d’un cycle, au cache L1 3 à 6 cycles, au L2 9 à 15, au L3 30 à 60, à la mémoire principale 180 à 300. Ces valeurs sont des ordres de grandeur ; à titre d’exemple daté, l’AMD Zen 4 (2022) a 32 Kio de cache L1 de données et 1 Mio de L2 par cœur, un L2 qui répond en 14 cycles et un L3 de 32 Mio qui répond en 50 cycles.
Les types de mémoire
Les registres sont les emplacements mémoire les plus rapides, directement intégrés au processeur. Ils stockent les données en cours de traitement.
Temps d’accès : moins d’un cycle (moins de \(0{,}3\) ns). Capacité : quelques dizaines (32 à 64 registres en général). Utilisation : variables temporaires, pointeurs, résultats intermédiaires.
La SRAM utilise 6 transistors par bit pour stocker l’information. Elle est très rapide mais coûteuse en surface de silicium.
Temps d’accès : 1 à 2 ns. Coût : de l’ordre de cent fois celui de la DRAM par gigaoctet. Capacité typique : quelques Mio. Utilisation : caches L1, L2, L3. Avantage : pas besoin de rafraîchissement.
La DRAM utilise 1 transistor et 1 condensateur par bit. Plus dense, elle nécessite un rafraîchissement périodique.
Temps d’accès : 60 à 100 ns. Coût : quelques dollars le gigaoctet (le prix varie fortement d’une année à l’autre). Capacité typique : 8 à 32 Gio. Utilisation : mémoire principale (RAM). Inconvénient : le rafraîchissement périodique (d’où « dynamique »).
Un processeur a les caractéristiques suivantes :
- fréquence : 3 GHz (cycle de \(1/3\) ns, soit environ \(0{,}33\) ns) ;
- cache L1 : temps d’accès de 1 ns ;
- mémoire principale : temps d’accès de 100 ns.
- Combien de cycles pour un accès au cache L1 ?
- Combien de cycles pour un accès à la mémoire principale ?
- Quel est le ralentissement sans cache ?
Afficher la correction
- Cycles pour le cache L1 : \(1~\text{ns} \times 3~\text{cycles/ns} = \mathbf{3}\) cycles.
- Cycles pour la mémoire : \(100~\text{ns} \times 3~\text{cycles/ns} = \mathbf{300}\) cycles.
- Ralentissement : \(300 / 3 = \mathbf{100}\) fois plus lent sans cache.
Piège d’arrondi : diviser par \(0{,}33\) au lieu de multiplier par 3 donne 303 cycles et un rapport de 101 ; l’écart vient seulement de l’arrondi de \(1/3\).
Conclusion : le cache est indispensable aux performances. Sans lui, le processeur passerait 99 % de son temps à attendre la mémoire.
Introduction aux caches
Principe de fonctionnement
Le cache garde près du processeur les données qu’il vient d’utiliser, ainsi que leurs voisines ; quand il est plein, il évince celles qui servent le moins. Il exploite deux propriétés des programmes.
Localité temporelle : si une donnée est utilisée, elle le sera probablement à nouveau bientôt.
Localité spatiale : si une donnée est utilisée, ses voisines en mémoire le seront probablement aussi.
La Figure 7 suit les seize accès de la boucle \(s \leftarrow s + t[i]\) pour \(i\) de 0 à 7, avec un tableau t d’entiers de 4 octets. Les lectures de t montent d’adresse en adresse, à 4 octets d’écart : les huit tombent dans le même bloc de 64 octets (localité spatiale). La variable s revient à la même adresse à chaque tour (localité temporelle). Le cache garde les données récemment utilisées et charge des blocs entiers de données voisines : c’est ainsi qu’il tire parti des deux.
Organisation du cache : la ligne de cache
Le cache est organisé en lignes de cache (ou blocs) :
- taille typique : 64 octets, soit 16 entiers de 32 bits ;
- unité de transfert entre le cache et la mémoire ;
- c’est ainsi que le cache exploite la localité spatiale.
La mémoire est vue comme une suite de blocs de 64 octets : le bloc \(k\) couvre les octets \(64k\) à \(64k+63\). Un tableau t d’entiers de 4 octets rangé à partir de l’adresse 0 place donc 16 entiers par bloc, t[0] à t[15] dans le bloc 0, t[16] à t[31] dans le bloc 1, et ainsi de suite. L’entier t[50] est à l’adresse \(4\times50=200\) ; son bloc est \(\lfloor 200/64\rfloor=3\), qui couvre les octets 192 à 255, soit t[48] à t[63].
Une adresse et son bloc : t[50], adresse 200, bloc 3
Ce que charge un défaut sur t[50] : le bloc 3 entier
Un défaut sur t[50] ne charge pas 4 octets mais le bloc entier : les 64 octets du bloc 3 sont copiés dans une ligne du cache, avec les 16 entiers t[48] à t[63]. Les quinze voisins de t[50] sont désormais en cache : une lecture de t[51] sera servie sans aller en mémoire.
Succès et défaut de cache
Un succès (cache hit) se produit quand la donnée demandée est présente dans le cache. Un défaut (cache miss) se produit quand elle n’y est pas et doit être chargée depuis la mémoire.
Quand le processeur demande une donnée :
- le gestionnaire de cache vérifie si la donnée est présente ;
- succès : la donnée est dans le cache, l’accès est rapide (quelques cycles, 3 à 6 en L1) ;
- défaut : la donnée n’est pas dans le cache ; il faut charger la ligne complète depuis la mémoire, attendre plus de 100 cycles (pénalité de défaut) et, éventuellement, évincer une ligne existante.
Le cache L1 dessiné ici n’a que quatre lignes (un cache L1 de 32 Kio en a 512) ; elles contiennent les blocs 9, 12, 1 et 6, le bloc 1 étant le moins récemment utilisé. Le processeur demande t[50], à l’adresse 200, donc dans le bloc 3.
Étape 1 : la demande, le cache L1 est examiné
Étape 3 : la mémoire envoie le bloc 3, qui remplace le bloc 1
Étape 5 : la demande suivante, t[51], est un succès
Le bloc 3 n’est dans aucune ligne : c’est un défaut, et la demande passe à la mémoire principale (étape 2). La mémoire envoie le bloc entier, 64 octets, en environ 300 cycles (100 ns à 3 GHz) ; il remplace la ligne la moins récemment utilisée, celle du bloc 1, qui est évincée (étape 3). La donnée t[50] est alors transmise au processeur, qui a attendu pendant tout ce temps (étape 4). La demande suivante, t[51] à l’adresse 204, tombe dans le même bloc : c’est un succès, servi en environ 3 cycles (1 ns), cent fois moins qu’un défaut.
Un programme accède séquentiellement à un tableau de 100 entiers de 4 octets chacun.
- ligne de cache : 64 octets ;
- temps d’un succès : 1 ns ;
- temps d’un défaut : 100 ns.
Question : calculer le temps total d’accès aux 100 entiers.
Afficher la correction
Analyse :
- une ligne de cache \(= 64\) octets \(= 16\) entiers ;
- 100 entiers occupent \(100/16 = 6{,}25\), donc 7 lignes de cache ;
- le premier accès à chaque ligne est un défaut ;
- les accès suivants dans la même ligne sont des succès.
Calcul détaillé :
- 7 défauts \(\times\) 100 ns \(=\) 700 ns ;
- 93 succès \(\times\) 1 ns \(=\) 93 ns ;
- total \(=\) 793 ns.
Sans cache : \(100 \times 100\) ns \(= 10\,000\) ns : le cache divise le temps par \(12{,}6\).
Observation : grâce à la localité spatiale, il n’y a que 7 % de défauts. La septième ligne ne contient que 4 entiers utiles sur 16.
Le programme suivant compte les succès et les défauts du parcours : cache est l’ensemble des lignes déjà chargées, et t[i], à l’adresse \(4i\), est dans la ligne \(\lfloor 4i/64\rfloor\) : la ligne désigne ici le numéro du bloc chargé.
cache = set()
defauts, succes = 0, 0
for i in range(100):
ligne = (4 * i) // 64
if ligne in cache:
succes += 1
else:
defauts += 1
cache.add(ligne)
temps = 100 * defauts + succes
print(defauts, succes, temps)Après \(i=0\)
Après \(i=1\)
Après \(i=16\)
Fin du programme
Pour \(i=0\), t[0] est à l’adresse 0, dans la ligne 0, absente : défaut, et la ligne entière (t[0] à t[15]) est chargée. Pour \(i=1\), l’adresse 4 est toujours dans la ligne 0, présente : succès. Les quinze accès suivants à la ligne 0 sont des succès ; à \(i=16\), l’adresse 64 ouvre la ligne 1 : deuxième défaut, et le motif se répète toutes les 16 itérations. À la fin, 7 lignes ont été touchées : 7 défauts et 93 succès, et la ligne 6 n’a servi qu’à 4 entiers sur 16. La ligne 10 calcule \(7\times100+93\times1=793\) ns.
Sortie :
7 93 793Métriques de performance
Temps d’exécution
Le temps d’exécution d’un programme parallèle dépend de \(T_s\), le temps de la partie séquentielle (non parallélisable), de \(T_p\), le temps de la partie parallélisable, et de \(n\), le nombre de processeurs (les labs le notent \(p\)) : \[T(n) = T_s + \frac{T_p}{n} + T_{\text{surcoût}}\] où \(T_{\text{surcoût}}\) représente le surcoût de la parallélisation (synchronisation, communication).
La Figure 8 montre ce que chaque terme devient quand \(n\) augmente. La partie séquentielle (violet) reste sur un seul processeur et garde ses 10 s ; la partie parallélisable (bleu) se partage en \(n\) morceaux égaux ; le surcoût (gris), ici 1 s par processeur dès que \(n\ge2\), pour créer et synchroniser les processus, s’ajoute. Avec 4 processeurs, le programme dure \(10+22{,}5+4=36{,}5\) s.
Accélération (speedup)
L’accélération (speedup) mesure le gain de performance obtenu par la parallélisation : \[S(n) = \frac{T(1)}{T(n)} = \frac{T_s + T_p}{T_s + \frac{T_p}{n}}\] où \(T(1)\) est le temps séquentiel et \(T(n)\) le temps avec \(n\) processeurs ; la seconde égalité néglige le surcoût.
Sur l’exemple de la Figure 8, \(S(4)=100/36{,}5=2{,}74\), alors que la formule sans surcoût donne \(100/32{,}5=3{,}08\). L’accélération idéale est \(S(n)=n\) : le programme irait \(n\) fois plus vite avec \(n\) processeurs. En pratique, \(S(n)<n\) à cause de :
- la partie séquentielle ;
- le surcoût de la parallélisation ;
- les conflits d’accès à la mémoire ;
- le déséquilibre de charge.
Sur la Figure 9, chaque courbe part de l’idéal puis s’en écarte et plafonne à \(1/f\) (pointillés) : avec \(f=10~\%\) de séquentiel, 16 processeurs donnent \(6{,}40\), et la courbe ne dépassera jamais 10. La section Section 8 établit la formule de ces courbes.
Efficacité
L’efficacité mesure l’utilisation des processeurs : \[E(n) = \frac{S(n)}{n} = \frac{T(1)}{n \times T(n)}\] Elle représente la part du travail des \(n\) processeurs réellement utile.
- \(E(n) = 1\) : utilisation parfaite (100 %) ;
- \(E(n) = 0{,}5\) : utilisation à 50 % ;
- \(E(n) < 0{,}5\) : généralement considéré comme inefficace.
Par exemple, un programme de 100 s qui dure 30 s sur 4 processeurs a une accélération \(S=100/30=3{,}33\) et une efficacité \(E=3{,}33/4=0{,}83\) : chaque processeur a travaillé utilement 83 % du temps, le reste est perdu en attente et en coordination.
L’efficacité dépasse 100 % dans les cas d’accélération superlinéaire : en découpant les données, chaque part tient dans le cache de son cœur, et l’ensemble va plus de \(n\) fois plus vite. C’est l’exception, pas la règle.
Un programme s’exécute en 120 secondes en séquentiel. Avec 4 processeurs, il s’exécute en 40 secondes. Calculer :
- l’accélération ;
- l’efficacité ;
- la fraction séquentielle approximative ;
- puis commenter les résultats.
Afficher la correction
- Accélération : \(S(4) = 120/40 = 3\).
- Efficacité : \(E(4) = 3/4 = 0{,}75\), soit 75 %.
- Fraction séquentielle : la loi d’Amdahl (section Section 8), lue à l’envers, donne \[3 = \frac{1}{f + \frac{1-f}{4}} \;\Rightarrow\; f + \frac{1-f}{4} = \frac{1}{3} \;\Rightarrow\; 4f + 1 - f = \frac{4}{3} \;\Rightarrow\; 3f = \frac{1}{3} \;\Rightarrow\; f = \frac{1}{9} \approx 11~\%.\]
- Analyse : accélération de 3 au lieu de 4 (idéal) ; efficacité de 75 %, correcte mais perfectible ; 11 % de code séquentiel limitent déjà nettement l’accélération. Causes possibles : synchronisation, accès à la mémoire partagée.
Loi d’Amdahl
Énoncé de la loi
La loi d’Amdahl donne l’accélération maximale en fonction de la fraction séquentielle. Soit \(f\) la fraction séquentielle du programme (\(0 \le f \le 1\)) : \[S(n) = \frac{1}{f + \frac{1-f}{n}}\] Accélération maximale (\(n \to \infty\)) : \(S_{\max} = \dfrac{1}{f}\).
La formule vient du temps d’exécution de la section précédente, sans surcoût, en prenant le temps séquentiel pour unité : \(T(1)=1\), \(T_s=f\) et \(T_p=1-f\), d’où \(T(n)=f+(1-f)/n\) et \(S(n)=1/T(n)\).
La loi d’Amdahl dit une vérité fondamentale : on ne peut pas paralléliser ce qui est intrinsèquement séquentiel. C’est comme une chaîne de production : peu importe le nombre d’ouvriers, si une étape doit être faite par une seule personne, elle devient le goulot d’étranglement.
Interprétation : si 5 % du programme est séquentiel (\(f = 0{,}05\)), l’accélération maximale est 20, même avec un million de processeurs.
Un programme dure 100 s sur un processeur, dont 10 % de partie séquentielle (\(f=0{,}1\)) : \(T(n)=10+90/n\) et \(S(n)=100/T(n)\).
\(n=8\) : le tableau des quatre premiers cas et la frise à huit processeurs
\(n\to\infty\) : il reste la partie séquentielle
Avec 2 processeurs, seule la partie parallèle se partage : \(10+90/2=55\) s, \(S(2)=100/55=1{,}82\). Avec 4, \(10+22{,}5=32{,}5\) s et \(S(4)=3{,}08\) : la partie séquentielle fait déjà près du tiers du temps. Avec 8, \(10+11{,}25=21{,}25\) s et \(S(8)=4{,}71\) ; doubler \(n\) ne fait plus gagner que \(11{,}25\) s. Quand \(n\) tend vers l’infini, la part de chaque processeur tend vers 0 : il reste les 10 s séquentielles, et l’accélération plafonne à \(100/10=10=1/f\).
Exemples pratiques
| \(f\) (séq.) | \(S(2)\) | \(S(10)\) | \(S(100)\) | \(S(\infty)\) |
|---|---|---|---|---|
| 0 % | 2,00 | 10,00 | 100,00 | \(\infty\) |
| 5 % | 1,90 | 6,90 | 16,81 | 20 |
| 10 % | 1,82 | 5,26 | 9,17 | 10 |
| 20 % | 1,67 | 3,57 | 4,81 | 5 |
| 50 % | 1,33 | 1,82 | 1,98 | 2 |
Calcul d’une case, pour \(f=5~\%\) et \(n=100\) : \(S(100)=1/(0{,}05+0{,}95/100)=1/0{,}0595=16{,}81\). Avec 5 % de séquentiel, 100 processeurs ne donnent que \(16{,}81\), à peine 17 % de l’idéal : les petites fractions séquentielles coûtent cher dès que \(n\) grandit.
Un programme a une partie séquentielle de 15 %.
- Calculer l’accélération avec 4 processeurs.
- Calculer l’accélération avec 16 processeurs.
- Quelle est l’accélération maximale possible ?
- Combien de processeurs faut-il pour atteindre 90 % de l’accélération maximale ?
- Doubler le nombre de processeurs double-t-il l’accélération ?
Afficher la correction
Avec \(f = 0{,}15\) :
- \(S(4) = \dfrac{1}{0{,}15 + \frac{0{,}85}{4}} = \dfrac{1}{0{,}15 + 0{,}2125} = \dfrac{1}{0{,}3625} = \mathbf{2{,}76}\).
- \(S(16) = \dfrac{1}{0{,}15 + \frac{0{,}85}{16}} = \dfrac{1}{0{,}15 + 0{,}053125} = \dfrac{1}{0{,}203125} = \mathbf{4{,}92}\).
- \(S_{\max} = \dfrac{1}{0{,}15} = \mathbf{6{,}67}\).
- 90 % de \(6{,}67\) valent \(0{,}9 \times \frac{1}{0{,}15} = 6\). Il faut \(\dfrac{1}{0{,}15 + \frac{0{,}85}{n}} = 6\), donc \(0{,}15 + \dfrac{0{,}85}{n} = \dfrac{1}{6}\), \(\dfrac{0{,}85}{n} = \dfrac{1}{6} - 0{,}15 = \dfrac{1}{60}\) et \(n = 0{,}85 \times 60 = \mathbf{51}\) processeurs. Le calcul se fait en fractions : arrondir \(1/6\) à \(0{,}167\) donnerait 50.
- Non. De 4 à 8 processeurs, \(S(8) = 3{,}90\) : \(+41~\%\) seulement. De 8 à 16 processeurs, \(S(16) = 4{,}92\) : \(+26~\%\) seulement. Les rendements sont décroissants.
Loi de Gustafson
Une vision plus optimiste
La loi d’Amdahl suppose que la taille du problème est fixe. Gustafson (1988) propose une vision différente : quand on a plus de processeurs, on traite des problèmes plus grands. Les deux lois ne posent pas la même question. Amdahl demande : avec \(n\) processeurs, en combien de temps ce problème est-il résolu ? Gustafson demande : avec \(n\) processeurs, quelle taille de problème est traitée dans le même temps ?
La loi de Gustafson considère le temps d’exécution fixe. Si \(s\) est la fraction du temps passé en séquentiel sur \(n\) processeurs : \[S(n) = s + n(1-s) = n - s(n-1)\] Cette loi mesure combien de travail supplémentaire on peut accomplir avec plus de processeurs.
Différence clé :
- Amdahl : taille du problème fixe, donc accélération limitée ;
- Gustafson : temps d’exécution fixe, donc problème plus grand ;
- Amdahl est pessimiste, Gustafson est optimiste.
Les deux lois partent du même programme : \(0{,}1\) de séquentiel et \(0{,}9\) de parallélisable, pour une durée de 1 sur un processeur.
\(n=2\)
\(n=8\)
À gauche, Amdahl garde le problème et partage le \(0{,}9\) : avec 2 processeurs, la durée tombe à \(0{,}55\) et \(S=1{,}82\) ; avec 4, \(0{,}325\) et \(S=3{,}08\) ; avec 8, \(0{,}2125\) et \(S=4{,}71\), et la partie séquentielle (violet) pèse de plus en plus. À droite, Gustafson garde la durée 1 et donne à chaque processeur \(0{,}9\) de travail : avec 2 processeurs, \(0{,}1+2\times0{,}9=1{,}9\) unités de travail, que l’exécution sur un seul processeur mettrait \(1{,}9\) fois plus de temps à faire, d’où \(S=1{,}9\) ; avec 4, \(3{,}7=4-0{,}1\times3\) ; avec 8, \(7{,}3=8-0{,}1\times7\). La partie parallèle grossit avec \(n\) : le séquentiel ne pèse plus que \(0{,}1/7{,}3\approx1{,}4~\%\) du travail.
Comparaison des deux lois
Avec 10 % de code séquentiel et 16 processeurs :
- calculer l’accélération selon Amdahl ;
- calculer l’accélération selon Gustafson ;
- expliquer la différence ;
- dans quel contexte chaque loi est-elle pertinente ?
Afficher la correction
- Loi d’Amdahl, \(f = 0{,}1\) : \(S(16) = \dfrac{1}{0{,}1 + \frac{0{,}9}{16}} = \dfrac{1}{0{,}1 + 0{,}05625} = \dfrac{1}{0{,}15625} = \mathbf{6{,}4}\).
- Loi de Gustafson, \(s = 0{,}1\) : \(S(16) = 16 - 0{,}1 \times (16-1) = 16 - 1{,}5 = \mathbf{14{,}5}\).
- Explication : Amdahl parallélise un problème de taille fixe, et l’accélération plafonne (ici \(6{,}4\)). Gustafson utilise les 16 processeurs pour traiter, dans le même temps, un problème \(14{,}5\) fois plus grand ; il est plus optimiste parce qu’il suppose que la taille du problème suit les ressources disponibles.
- Contextes : Amdahl est pertinent pour les traitements de taille fixe (compilation d’un projet, rendu d’une vidéo donnée) ; Gustafson pour la simulation scientifique et l’apprentissage automatique, où plus de données donnent de meilleurs résultats.
Granularité et surcoût
Granularité des tâches
La granularité est le rapport entre le temps de calcul et le temps de communication et de synchronisation d’une tâche. Elle détermine la taille des unités de travail parallèle : \[G = \frac{T_{\text{calcul}}}{T_{\text{communication}}}\] où \(T_{\text{calcul}}\) est le temps de calcul utile et \(T_{\text{communication}}\) le temps de gestion (création, synchronisation, communication).
Types de granularité :
- fine (\(G < 1\)) : petites tâches, beaucoup de communication ;
- moyenne (\(1 \le G < 100\)) : équilibre entre calcul et communication ;
- grosse (\(G \ge 100\)) : grandes tâches, peu de communication.
La granularité, c’est comme organiser un déménagement avec des amis.
- Granularité fine : chaque personne porte un livre à la fois ; beaucoup d’allers-retours (le surcoût), beaucoup de coordination, et un embouteillage dans les escaliers.
- Granularité moyenne : chaque personne porte une boîte de livres ; effort et coordination s’équilibrent.
- Granularité grosse : chaque personne s’occupe d’une pièce entière ; peu de coordination, mais un déséquilibre si les pièces sont de tailles différentes, et celui qui finit en avance ne peut guère aider les autres.
La Figure 10 montre les trois cas. Un million de tâches de 1 \(\mu\)s avec 10 \(\mu\)s de surcoût chacune : un processeur passe \(10/11=91~\%\) de son temps en surcoût. Mille tâches de 1 ms avec \(0{,}1\) ms de surcoût : \(0{,}1/1{,}1=9~\%\) seulement. Quatre tâches de 250 ms sur 16 processeurs : 12 processeurs restent inactifs, et l’efficacité tombe à \(4/16=25~\%\). Trop fin, le surcoût mange le calcul ; trop gros, il ne reste pas assez de tâches pour occuper tous les processeurs, et les plus lentes retardent la fin.
Le surcoût du parallélisme
Le surcoût est le temps supplémentaire nécessaire pour gérer le parallélisme, qui n’existe pas dans la version séquentielle. Il représente le coût de la parallélisation.
Le surcoût comprend :
- la création et la destruction des processus ou des fils d’exécution (jusqu’à plusieurs millisecondes) ;
- la synchronisation : attentes, verrous, barrières (cycles perdus) ;
- la communication entre processus (latence du réseau, copies en mémoire) ;
- le déséquilibre de charge (processeurs inactifs) ;
- la contention mémoire (accès concurrents au bus).
Le Lab 2 mesure ce surcoût : il fait payer le prix des tâches trop petites confiées à plusieurs processus.
Un calcul matriciel peut être découpé de deux façons :
- option A : 1000 tâches de 1 ms chacune, surcoût de \(0{,}1\) ms par tâche ;
- option B : 10 tâches de 100 ms chacune, surcoût de 1 ms par tâche.
Avec 4 processeurs, quelle option est la meilleure ? Et avec 100 processeurs ?
Afficher la correction
Avec 4 processeurs. Option A : \(1000 \times 1 = 1000\) ms de calcul et \(1000 \times 0{,}1 = 100\) ms de surcoût, soit 1100 ms de travail ; réparti également, \(1100/4 = \mathbf{275}\) ms par processeur. Granularité : \(G = 1/0{,}1 = 10\) (moyenne).
Option B : \(10 \times 100 = 1000\) ms de calcul et \(10 \times 1 = 10\) ms de surcoût, soit 1010 ms de travail. Dix tâches ne se partagent pas également entre quatre processeurs : au mieux, deux processeurs font 3 tâches (\(3\times101=303\) ms) et deux en font 2 (202 ms). Le temps total est celui du plus lent : 303 ms. Granularité : \(G = 100/1 = 100\) (grosse).
Conclusion avec 4 processeurs : l’option A est meilleure (275 ms contre 303 ms).
Avec 100 processeurs. Option A : \(1100/100 = \mathbf{11}\) ms par processeur, une répartition excellente. Option B : seulement 10 tâches pour 100 processeurs ; 90 processeurs restent inactifs et le temps total est celui d’une tâche, 101 ms.
Conclusion avec 100 processeurs : l’option A est largement meilleure (11 ms contre 101 ms).
Leçon : la granularité optimale dépend du nombre de processeurs.
Le programme suivant simule la répartition : chaque tâche va au processeur (cœur) libre le plus tôt, celui dont la date de fin fin[k] est la plus petite (ligne 4). Les lignes 7 et 9 traitent le découpage B, les lignes 8 et 10 le découpage A.
def rep(n, d, s, p):
fin = [0] * p
for t in range(n):
k = fin.index(min(fin))
fin[k] += d + s
return round(max(fin))
print(rep(10, 100, 1, 4))
print(rep(1000, 1, 0.1, 4))
print(rep(10, 100, 1, 100))
print(rep(1000, 1, 0.1, 100))Ligne 7, découpage B sur 4 cœurs
Ligne 8, découpage A sur 4 cœurs
Lignes 9 et 10, les deux découpages sur 100 cœurs
Pour B, la tâche 1 va au cœur 0, qui finit à \(100+1=101\) ms ; les tâches 2 à 4 vont aux cœurs 1 à 3, puis les tâches 5 à 8 font un deuxième tour (fin vaut alors \([202, 202, 202, 202]\)). Il ne reste que deux tâches pour quatre cœurs : les cœurs 0 et 1 en font 3 et finissent à 303 ms, les cœurs 2 et 3 en font 2 et attendent dès 202 ms. C’est la répartition \(3/3/2/2\) de la correction. Pour A, chaque cœur reçoit 250 tâches de \(1{,}1\) ms et finit à 275 ms, sans attente. Sur 100 cœurs, B n’occupe que 10 cœurs pendant 101 ms, alors que A donne 10 tâches à chacun et finit en 11 ms.
Sortie :
303
275
101
11Synthèse
À retenir
- Le parallélisme est nécessaire : les processeurs n’augmentent plus en fréquence (mur thermique, \(P=C\,V^2f\)) ; les transistors servent à multiplier les cœurs.
- Taxonomie de Flynn : SISD, séquentiel classique ; SIMD, vectoriel (GPU) ; MISD, rare (redondance) ; MIMD, multicœurs modernes.
- Hiérarchie mémoire : le cache est indispensable aux performances ; il charge des lignes de 64 octets et exploite la localité temporelle et spatiale ; rapport d’environ 1 à 100 entre cache et RAM.
- Métriques : \(T(n)=T_s+T_p/n+T_{\text{surcoût}}\) ; accélération \(S(n) = T(1)/T(n)\) (gain de vitesse) ; efficacité \(E(n) = S(n)/n\) (utilisation des ressources).
- Loi d’Amdahl : le séquentiel limite l’accélération, \(S_{\max} = 1/f\).
- Loi de Gustafson : à temps fixé, on traite plus avec plus de ressources, \(S(n)=n-s(n-1)\).
- Granularité : l’équilibre entre calcul et communication décide de l’efficacité, et dépend du nombre de processeurs.
- Un processeur SIMD peut exécuter plusieurs programmes différents simultanément.
- La SRAM est plus rapide mais plus chère que la DRAM.
- Avec 10 % de code séquentiel, l’accélération maximale est 10 (Amdahl).
- La granularité fine est toujours préférable.
- Le cache exploite la localité temporelle et spatiale.
- Gustafson est plus optimiste qu’Amdahl.
- L’efficacité peut être supérieure à 100 %.
Afficher la correction
- Faux : SIMD exécute la même instruction sur plusieurs données, pas plusieurs programmes.
- Vrai.
- Vrai : \(S_{\max}=1/0{,}1=10\).
- Faux : la granularité fine génère trop de surcoût (la communication dépasse le calcul).
- Vrai.
- Vrai.
- Vrai, rarement : dans les cas d’accélération superlinéaire, chaque part des données tient dans le cache de son cœur, et l’ensemble va plus de \(n\) fois plus vite. C’est l’exception, pas la règle.
Prochaine séance
Séance 2 : cohérence de cache et protocoles. Chaque cœur a ses propres caches ; quand deux cœurs utilisent la même donnée, il faut garantir qu’ils en voient la même valeur : protocoles MSI et MESI, false sharing (faux partage), cohérence séquentielle. Le Lab 3 (mémoire) l’accompagne.
TD et labs associés
TD de la Séance 1 (Flynn, mémoire et cache, accélération, Amdahl, Gustafson, granularité). Lab 0 : prise en main de l’environnement (Anaconda, Jupyter, fonctions, lambda et map, mesure du temps, NumPy, fils et processus). Lab 1 : penser parallèle (map, reduce, tâches indépendantes, comptage de mots avec plusieurs processus). Lab 2 : plusieurs cœurs (multiprocessing, accélération mesurée, prix des tâches trop petites, loi d’Amdahl confrontée à la mesure, \(\pi\) par Monte-Carlo).
Références
- Hennessy, J. L., Patterson, D. A. Computer Architecture: A Quantitative Approach, 6e éd., Morgan Kaufmann, 2017 : ch. 1 (tendances, puissance, loi d’Amdahl), ch. 2 et annexe B (hiérarchie mémoire et caches), ch. 4 (SIMD).
- Pacheco, P. S., Malensek, M. An Introduction to Parallel Programming, 2e éd., Morgan Kaufmann, 2022 : ch. 2 (Flynn, caches, accélération, efficacité, lois d’Amdahl et de Gustafson).
- Grama, A., Gupta, A., Karypis, G., Kumar, V. Introduction to Parallel Computing, 2e éd., Addison-Wesley, 2003 : ch. 3 et 5 (granularité, surcoût).
- Flynn, M. J. Very high-speed computing systems. Proceedings of the IEEE, 54(12), 1966. Amdahl, G. M. Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Conference Proceedings, 1967. Gustafson, J. L. Reevaluating Amdahl’s law. Communications of the ACM, 31(5), 1988.
- Données des processeurs : K. Rupp, 50 Years of Microprocessor Trend Data, 1971 à 2021, licence CC BY 4.0. Chiffres matériels : Intel (Pentium 4 570J, \(3{,}8\) GHz, novembre 2004) ; AMD, présentation de l’architecture Zen 4, août 2022.
Pour cette séance
Les slides
À lire en ligne
- TD — Séance 1 — Fondements de l’architecture parallèle
- Lab 0 — Prise en main : Anaconda, Jupyter et les outils Python des labs
- Lab 1 — Penser parallèle : map, reduce et tâches indépendantes
- Lab 2 — Plusieurs cœurs : multiprocessing, granularité et loi d’Amdahl
À télécharger
- Notebooks des labs de la séance 1 (ZIP, 147 Ko)