Comparez avec des benchmarks et passez à l'échelle

Le script d’agrégation des ventes tourne maintenant en Parquet. L’équipe veut aller plus loin : louer une machine à 16 cœurs, ou même une grappe de 64. Un fournisseur promet « des performances 30 % supérieures » sur son benchmark maison. Deux questions se posent alors : comment comparer honnêtement deux machines, et jusqu’où peut-on accélérer un programme en ajoutant des processeurs ?

Ce chapitre répond aux deux, avec deux outils : la bonne façon de résumer un benchmark, et les lois d’Amdahl et de Gustafson.

Les benchmarks

Un benchmark (banc d’essai) est une charge de travail standardisée, exécutée sur plusieurs systèmes pour les comparer. On en distingue plusieurs familles :

• les micro-benchmarks mesurent une opération élémentaire : une addition, un accès mémoire, un appel système, une lecture de fichier ;
• les noyaux (kernels) isolent le cœur d’un calcul fréquent : un produit de matrices, une transformée de Fourier ;
• les benchmarks applicatifs exécutent des programmes réalistes : SPEC CPU (programmes de calcul), TPC-C (transactions de base de données), MLPerf (entraînement et inférence de modèles d’apprentissage).

Plus un benchmark est proche de votre charge réelle, plus il est pertinent pour vous. Un excellent score SPEC ne dit rien d’une application limitée par le disque.

Attention

Les micro-benchmarks sont piégeux. Un compilateur peut supprimer une boucle dont le résultat n’est jamais utilisé : vous mesurez alors… rien du tout. Et dès qu’un benchmark devient une référence commerciale, les constructeurs optimisent spécifiquement pour lui. Lisez toujours les conditions de mesure.

Résumer plusieurs résultats : quelle moyenne ?

Un benchmark comporte souvent plusieurs programmes. Pour résumer, on est tenté de faire une moyenne. Mais laquelle ? Prenons deux machines A et B et trois programmes (durées en secondes) :

Programme	Machine A	Machine B	B normalisé par A	A normalisé par B
P1	2	4	2,0	0,5
P2	50	25	0,5	2,0
P3	10	10	1,0	1,0
Moyenne arithmétique			1,17	1,17
Moyenne géométrique			1,00	1,00

Normalisé par A, B semble 17 % plus lente. Normalisé par B, c’est A qui semble 17 % plus lente ! La moyenne arithmétique de ratios fait dépendre la conclusion du choix de la référence. La moyenne géométrique, $\left(\prod_{j=1}^{n} x_j\right)^{1/n}$, n’a pas ce défaut : le classement ne dépend pas de la machine de référence. C’est pourquoi SPEC l’utilise pour agréger ses ratios.

Mais attention, la moyenne géométrique répond à une question précise : « en moyenne, d’un facteur combien un programme est-il plus rapide ? ». Si votre vraie charge consiste à exécuter les trois programmes une fois chacun, la bonne métrique est la durée totale : 62 s pour A, 39 s pour B. B est alors nettement meilleure, parce que le programme P2, le plus long, y va deux fois plus vite.

La moyenne arithmétique des ratios vaut 1,17 quelle que soit la référence : chaque machine « perd » à tour de rôle. La moyenne géométrique reste à 1. Sur la durée totale, B l'emporte nettement.

Pour résumer…	utilisez
des durées, quand la charge réelle exécute chaque programme	la somme ou la moyenne arithmétique des durées (éventuellement pondérée)
des débits (tâches/s) sur une même quantité de travail	la moyenne harmonique
des ratios normalisés par une référence	la moyenne géométrique

Les jeux de ratios

On appelle jeu de ratios (ratio game) l’art de présenter des chiffres exacts pour leur faire dire ce qu’on veut. À repérer :

• choisir la base qui arrange, comme dans le tableau ci-dessus ;
• choisir une métrique ratio plutôt qu’une métrique absolue : « deux fois plus de requêtes par watt » peut cacher un débit divisé par deux ;
• comparer des gains relatifs : « +50 % » sur un temps de 2 ms ne pèse rien face à « +5 % » sur un temps de 10 s ;
• calculer des pourcentages dans des conditions différentes (autre charge, autre version, autre machine).

Piège

Faire la moyenne arithmétique de performances normalisées. Selon la référence choisie, chacune des deux machines peut « gagner ». Utilisez la moyenne géométrique pour des ratios, ou, mieux encore, revenez à la métrique qui correspond à votre charge réelle.

Accélération et efficacité

Passons au parallélisme. On mesure l’accélération d’un programme parallèle par le speedup :

$$S(n) = \frac{t_1}{t_n}$$

où $t_1$ est la durée de la meilleure implémentation séquentielle, et $t_n$ la durée de la version parallèle sur $n$ processeurs. L’efficacité mesure la fraction du temps où chaque processeur travaille utilement :

$$E(n) = \frac{S(n)}{n} = \frac{t_1}{n \, t_n}$$

Idéalement, $S(n) = n$ et $E(n) = 1$. En pratique, les communications, les synchronisations et la partie non parallélisable font baisser l’efficacité.

Exemple

Le script d’agrégation, parallélisé avec des processus, a donné les durées suivantes :

$n$	1	2	4	8	16
$t_n$ (s)	120	63	34	20	14
$S(n)$	1	1,90	3,53	6,00	8,57
$E(n)$	1	0,95	0,88	0,75	0,54

Avec 16 processus, chaque cœur n’est utile qu’un peu plus de la moitié du temps. Payer le double pour passer de 8 à 16 cœurs ne fait gagner que 30 % de temps.

Les mesures s'écartent de plus en plus de la droite idéale et suivent la loi d'Amdahl ; l'efficacité tombe à 0,54 sur 16 processus.

Attention

$t_1$ doit être la durée de la meilleure version séquentielle, pas celle de la version parallèle lancée sur un seul processeur. Cette dernière contient souvent des surcoûts (verrous, découpage des données) qui gonflent artificiellement le speedup.

La loi d’Amdahl : la partie séquentielle plafonne tout

Pourquoi l’efficacité s’effondre-t-elle ? Parce qu’une partie du programme reste séquentielle : lire la configuration, répartir le travail, fusionner les résultats. Notons $f$ cette fraction séquentielle du temps d’exécution sur un processeur. Avec $N$ processeurs, la partie parallélisable, $1 - f$, est divisée par $N$, mais pas la partie séquentielle :

$$t_N = \left( f + \frac{1 - f}{N} \right) t_1 \qquad \Rightarrow \qquad S(N) = \frac{1}{f + \dfrac{1 - f}{N}} \leq \frac{1}{f}$$

• $f$ est la fraction séquentielle du travail (mesurée sur l’exécution séquentielle) ;
• $1 - f$ est la fraction parallélisable ;
• $N$ est le nombre de processeurs.

C’est la loi d’Amdahl. Sa conclusion est brutale : quel que soit le nombre de processeurs, le speedup ne dépassera jamais $1/f$. Avec 5 % de code séquentiel, le speedup plafonne à 20 ; avec 10 %, à 10.

Exemple

Pour le script d’agrégation, le speedup mesuré de 6 sur 8 processus correspond à une fraction séquentielle $f$ telle que $1/6 = f + (1 - f)/8$, soit $f = (1/6 - 1/8)/(1 - 1/8) \approx 0{,}048$. Environ 5 % du temps est séquentiel, et Amdahl prédit un plafond de 20, quel que soit le nombre de cœurs. Sur 64 cœurs, on n’obtiendrait qu’environ $1/(0{,}05 + 0{,}95/64) \approx 15{,}4$.

Calculer ainsi $f$ à partir de chaque mesure (c’est la métrique de Karp-Flatt) donne 0,050, 0,044, 0,048 et 0,058 pour 2, 4, 8 et 16 processus. La valeur reste proche de 5 %, ce qui confirme le modèle d’Amdahl ; sa légère hausse à 16 processus trahit des surcoûts de coordination qui grandissent avec $n$.

La loi d’Amdahl s’applique en fait à toute amélioration partielle, pas seulement au parallélisme. Si l’inférence d’un modèle représente 60 % du temps d’une requête et que vous l’accélérez d’un facteur 4, le gain global vaut $1/(0{,}4 + 0{,}6/4) \approx 1{,}82$. Même une inférence infiniment rapide ne ferait gagner qu’un facteur $1/0{,}4 = 2{,}5$.

La loi de Gustafson : et si le problème grandissait ?

Amdahl raisonne à taille de problème fixe : on veut traiter le même travail plus vite. Mais souvent, quand on dispose de plus de processeurs, on traite un plus gros problème dans le même temps : plus de données, un maillage plus fin, un modèle plus grand. La partie séquentielle (lire la configuration, fusionner) reste à peu près constante, tandis que la partie parallèle grandit avec $N$.

Mesurons sur la machine parallèle : $t_N = t_s + t_p$, où $t_s$ est le temps séquentiel et $t_p$ le temps de la partie parallèle. Sur un seul processeur, le même problème prendrait $t_1 = t_s + N t_p$. En notant $\varphi = t_s/(t_s + t_p)$ la fraction séquentielle mesurée sur l’exécution parallèle, on obtient le speedup à l’échelle (scaled speedup) :

$$S(N) = \frac{t_1}{t_N} = \varphi + (1 - \varphi)\, N$$

C’est la loi de Gustafson-Barsis. Le speedup croît alors linéairement avec $N$ : avec $\varphi = 10$ %, on obtient 7,3 sur 8 processeurs et 57,7 sur 64.

À taille fixe (Amdahl), seule la partie parallèle rétrécit et la partie séquentielle finit par tout occuper. À durée fixe (Gustafson), chaque processeur ajouté apporte son travail parallèle et le speedup reste presque proportionnel à N.

	Amdahl	Gustafson-Barsis
Hypothèse	taille du problème fixe	temps d’exécution fixe, problème qui grandit
Fraction séquentielle	$f$, mesurée sur l’exécution séquentielle	$\varphi$, mesurée sur l’exécution parallèle
Speedup	$1/(f + (1 - f)/N)$, plafonné à $1/f$	$\varphi + (1 - \varphi) N$, non plafonné
Question posée	« combien plus vite ? »	« combien plus gros, dans le même temps ? »
Passage à l’échelle	fort (strong scaling)	faible (weak scaling)

Les deux lois ne se contredisent pas : elles ne mesurent pas la fraction séquentielle au même endroit. Avec $\varphi = 10$ % sur 8 processeurs, la partie séquentielle ne représente que $0{,}1/(0{,}1 + 8 \times 0{,}9) \approx 1{,}4$ % du travail total mesuré en séquentiel, et Amdahl avec $f = 1{,}4$ % redonne bien 7,3.

À retenir

Amdahl (taille fixe) : $S(N) = 1/(f + (1 - f)/N) \leq 1/f$ ; la partie séquentielle plafonne l’accélération. Gustafson-Barsis (problème qui grandit) : $S(N) = \varphi + (1 - \varphi) N$ ; si le travail parallèle grandit avec les processeurs, l’accélération reste presque linéaire. Toujours préciser laquelle des deux situations on étudie.

def amdahl(f, N):
    return 1 / (f + (1 - f) / N)

def gustafson(phi, N):
    return phi + (1 - phi) * N

for N in (2, 8, 64, 1024):
    print(f"N = {N:4d} : Amdahl(5 %) = {amdahl(0.05, N):5.2f}   "
          f"Gustafson(10 %) = {gustafson(0.10, N):7.1f}")

En entretien

« La loi d’Amdahl dit que si 5 % d’un programme est séquentiel, on ne l’accélérera jamais plus de 20 fois, même avec mille cœurs : il faut donc d’abord réduire la partie séquentielle. Gustafson rappelle qu’en pratique on profite souvent des cœurs supplémentaires pour traiter plus de données dans le même temps, et là le gain reste presque linéaire. »

En résumé

• Un benchmark compare des systèmes sur une charge standard : micro-benchmark, noyau ou benchmark applicatif (SPEC CPU, TPC-C, MLPerf). Il n’a de valeur que s’il ressemble à votre charge.
• Pour des ratios normalisés, utilisez la moyenne géométrique ; la moyenne arithmétique fait dépendre le classement de la référence. Méfiez-vous des jeux de ratios.
• Speedup $S(n) = t_1/t_n$ (avec la meilleure version séquentielle), efficacité $E(n) = S(n)/n$.
• Amdahl : $S(N) = 1/(f + (1 - f)/N) \leq 1/f$ ; elle s’applique à toute amélioration partielle.
• Gustafson-Barsis : $S(N) = \varphi + (1 - \varphi) N$, quand la taille du problème grandit avec $N$.
• Passage à l’échelle fort (problème fixe) contre faible (problème qui grandit) : précisez toujours lequel vous mesurez.

Exercices

Exercice · Speedup et efficacité

facile

Un entraînement de modèle dure 400 min sur un GPU et 70 min sur 8 GPU.

1. Calculez le speedup et l’efficacité.
2. En supposant la loi d’Amdahl, quelle est la fraction séquentielle $f$ ? Quel est le speedup maximal possible ?

Voir la solution

1. $S(8) = 400/70 \approx 5{,}71$ et $E(8) = 5{,}71/8 \approx 0{,}71$.
2. $1/S = f + (1 - f)/8$ donne $f = (1/S - 1/8)/(1 - 1/8) = (0{,}175 - 0{,}125)/0{,}875 \approx 0{,}057$. Le speedup maximal vaut $1/f \approx 17{,}5$.

En code

Python

t1, t8, n = 400, 70, 8                     # durées (min) sur 1 et 8 GPU

S = t1 / t8                                # speedup
E = S / n                                  # efficacité
f = (1 / S - 1 / n) / (1 - 1 / n)          # fraction séquentielle (Amdahl, Karp-Flatt)
print(round(S, 2), round(E, 2))            # 5.71 0.71
print(round(f, 4), round(1 / f, 1))        # 0.0571 17.5 : speedup maximal

R

t1 <- 400; t8 <- 70; n <- 8                # durées (min) sur 1 et 8 GPU

S <- t1 / t8                               # speedup
E <- S / n                                 # efficacité
f <- (1 / S - 1 / n) / (1 - 1 / n)         # fraction séquentielle (Amdahl, Karp-Flatt)
round(c(S = S, E = E, f = f, S_max = 1 / f), 4)   # 5.7143  0.7143  0.0571  17.5

Exercice · Où investir ?

moyen

Une requête à une API de recommandation se décompose ainsi : 30 % de lecture en base, 50 % d’inférence, 20 % de sérialisation et de réseau. Deux options :

• (a) un GPU qui rend l’inférence 5 fois plus rapide ;
• (b) un cache qui rend la lecture en base 10 fois plus rapide.

Calculez le gain global de chaque option, puis des deux combinées.

Voir la solution

• (a) $1/(0{,}5 + 0{,}5/5) = 1/0{,}6 \approx 1{,}67$.
• (b) $1/(0{,}7 + 0{,}3/10) = 1/0{,}73 \approx 1{,}37$.
• Les deux : la nouvelle durée relative vaut $0{,}3/10 + 0{,}5/5 + 0{,}2 = 0{,}03 + 0{,}1 + 0{,}2 = 0{,}33$, soit un gain de $1/0{,}33 \approx 3{,}03$.

Le GPU rapporte plus, car il touche la plus grande part du temps. Une fois les deux appliqués, la sérialisation et le réseau représentent $0{,}2/0{,}33 \approx 61$ % du temps restant : c’est le nouveau goulot.

En code

Python

parts = {"base": 0.3, "inférence": 0.5, "réseau": 0.2}   # fractions du temps d'une requête

def gain(accelerations):
    """Amdahl généralisée : chaque part est divisée par son facteur d'accélération."""
    nouvelle = sum(p / accelerations.get(nom, 1) for nom, p in parts.items())
    return round(nouvelle, 3), round(1 / nouvelle, 2)

print(gain({"inférence": 5}))                  # (0.6, 1.67)   option (a), le GPU
print(gain({"base": 10}))                      # (0.73, 1.37)  option (b), le cache
duree, g = gain({"inférence": 5, "base": 10})
print(duree, g, round(0.2 / duree, 2))   # 0.33 3.03 0.61 : le réseau pèse 61 %

R

parts <- c(base = 0.3, inference = 0.5, reseau = 0.2)   # fractions du temps d'une requête

# Amdahl généralisée : chaque part est divisée par son facteur d'accélération
gain <- function(acc) {
  facteurs <- c(base = 1, inference = 1, reseau = 1)
  facteurs[names(acc)] <- acc
  nouvelle <- sum(parts / facteurs)
  c(duree = nouvelle, gain = 1 / nouvelle)
}
gain(c(inference = 5))                      # 0.60  1.67   option (a), le GPU
gain(c(base = 10))                          # 0.73  1.37   option (b), le cache
g <- gain(c(inference = 5, base = 10))
c(g, part_reseau = 0.2 / g[["duree"]])      # 0.33  3.03  0.61 : le réseau pèse 61 %

Exercice · Amdahl ou Gustafson ?

difficile

Une simulation météo dure 1 heure sur 64 processeurs. On mesure pendant cette exécution 3 minutes de partie séquentielle (lecture des données et écriture des résultats).

1. Quel est le speedup à l’échelle selon Gustafson-Barsis ?
2. Quelle serait la fraction séquentielle $f$ au sens d’Amdahl, pour ce même problème exécuté sur un seul processeur ? Vérifiez que la loi d’Amdahl redonne le même speedup.
3. Le centre de calcul double le nombre de processeurs. Que peut espérer l’équipe si elle garde la même taille de problème ? Et si elle double la résolution (deux fois plus de calcul parallèle) ?

Voir la solution

1. $\varphi = 3/60 = 0{,}05$, donc $S(64) = 0{,}05 + 0{,}95 \times 64 = 60{,}85$.
2. Sur un processeur : $t_1 = 3 + 64 \times 57 = 3\,651$ min. La fraction séquentielle vaut $f = 3/3\,651 \approx 0{,}000\,82$. Amdahl : $S = 1/(0{,}000\,82 + 0{,}999\,18/64) \approx 60{,}85$. Les deux lois donnent bien le même chiffre, elles ne mesurent simplement pas $f$ au même endroit.
3. Même problème sur 128 processeurs (Amdahl, $f \approx 0{,}000\,82$) : $S \approx 1/(0{,}000\,82 + 0{,}999\,18/128) \approx 115{,}9$, soit une durée de $3\,651/115{,}9 \approx 31{,}5$ min (le temps séquentiel de 3 min, plus $64 \times 57/128 = 28{,}5$ min de calcul parallèle). Résolution doublée sur 128 processeurs (Gustafson) : la partie parallèle double et se répartit sur deux fois plus de processeurs, donc la durée reste d’environ 1 heure, pour un problème deux fois plus gros, avec un speedup à l’échelle de $0{,}05 + 0{,}95 \times 128 = 121{,}65$.

En code

Python

t_seq, t_tot, N = 3, 60, 64                # minutes de partie séquentielle, durée, processeurs

phi = t_seq / t_tot                        # fraction séquentielle mesurée en parallèle
S_gustafson = phi + (1 - phi) * N
t1 = t_seq + N * (t_tot - t_seq)           # même problème sur un seul processeur (min)
f = t_seq / t1                             # fraction séquentielle au sens d'Amdahl
amdahl = lambda f, N: 1 / (f + (1 - f) / N)
print(round(S_gustafson, 2), t1, round(f, 5), round(amdahl(f, N), 2))
# 60.85 3651 0.00082 60.85 : les deux lois donnent le même speedup

S128 = amdahl(f, 128)                      # même problème sur 128 processeurs
print(round(S128, 1), round(t1 / S128, 1), round(phi + (1 - phi) * 128, 2))
# 115.9 31.5 121.65 : 31,5 min à taille fixe, ou 1 h pour un problème deux fois plus gros

R

t_seq <- 3; t_tot <- 60; N <- 64           # minutes de partie séquentielle, durée, processeurs

phi <- t_seq / t_tot                       # fraction séquentielle mesurée en parallèle
S_gustafson <- phi + (1 - phi) * N
t1 <- t_seq + N * (t_tot - t_seq)          # même problème sur un seul processeur (min)
f <- t_seq / t1                            # fraction séquentielle au sens d'Amdahl
amdahl <- function(f, N) 1 / (f + (1 - f) / N)
c(S_gustafson, t1)                         # 60.85  3651
c(f, amdahl(f, N))                         # 0.00082  60.85 : même speedup

S128 <- amdahl(f, 128)                     # même problème sur 128 processeurs
round(c(S128, t1 / S128, phi + (1 - phi) * 128), 2)   # 115.90  31.50  121.65