Mesurer l'accélération — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 15)

Mesurer l'accélération

Threads · niveau 3 (difficile)

Énoncé

On calcule $\sum_{i = 0}^{N - 1} i$ pour $N = 4 \times 1 0^{8}$ avec $k$ fils, chacun sur une tranche.

Écrire le programme, et mesurer le temps pour $k = 1, 2, 4, 8$ . Calculer l'accélération $t_{1} / t_{k}$ .
Pourquoi l'accélération n'atteint-elle pas $k$ ?
Pourquoi faut-il faire tourner le calcul une première fois avant de mesurer ?

Corrigé

Le découpage est celui de l'exercice 15.3, avec un tableau double[] partiel des sommes partielles. Sur la machine de l'auteur (14 cœurs) :


1 fil(s) : 0.291 s, accélération 1.00  (somme 5.333333e+12)
2 fil(s) : 0.158 s, accélération 1.84  (somme 5.333333e+12)
4 fil(s) : 0.105 s, accélération 2.77  (somme 5.333333e+12)
8 fil(s) : 0.050 s, accélération 5.79  (somme 5.333333e+12)

(La somme vaut environ $\frac{2}{3} N^{3/2} \approx 5, 33 \times 1 0^{12}$ .)

Créer et attendre les fils a un coût ; tous les cœurs ne sont pas identiques ni toujours libres (le système et d'autres programmes tournent) ; la mémoire est partagée ; enfin le fil le plus lent détermine la durée totale. L'accélération idéale $k$ n'est jamais atteinte, et elle plafonne au nombre de cœurs.
Au début, la JVM interprète le code ; elle ne le compile en code machine (compilation « à la volée ») qu'après l'avoir vu tourner. La première mesure serait donc faussée. On « échauffe » la JVM par un premier calcul non mesuré.