Loi d’Amdahl : accélération et efficacité

La loi d’Amdahl, formulée par l’architecte informatique Gene Amdahl en 1967, décrit l’accélération théorique obtenue lorsqu’un calcul est parallélisé sur plusieurs processeurs. C’est l’un des principes les plus importants et les plus cités en calcul parallèle, car il fixe une limite supérieure stricte aux gains de performance qu’apporte l’ajout de processeurs, quel que soit leur nombre. La loi part d’une observation simple : tout programme réel comporte deux parties. L’une est intrinsèquement sérielle — elle doit s’exécuter de manière séquentielle, car chaque étape dépend du résultat de la précédente. L’autre est parallélisable — elle peut être divisée en tâches indépendantes et exécutée simultanément sur plusieurs processeurs. La loi d’Amdahl formalise la relation entre ces deux parties. La formule est : S(n) = 1 / (p + (1 − p) / n), où S est l’accélération, p est la fraction du programme qui doit s’exécuter en série (entre 0 et 1), n est le nombre de processeurs et (1 − p) est la fraction parallélisable. Lorsque n tend vers l’infini, le terme (1 − p) / n tend vers zéro et l’accélération tend vers 1/p — l’accélération théorique maximale. Ce maximum dépend entièrement de la fraction sérielle et ne peut pas être dépassé, quel que soit le nombre de processeurs utilisés. Les implications sont fortes. Si 10 % d’un programme doit s’exécuter en série (p = 0.1), l’accélération maximale est 1/0.1 = 10×, peu importe le nombre de processeurs. Si 20 % est sériel, le maximum est 5×. Si 50 % est sériel, le maximum n’est que de 2×. Ajouter davantage de processeurs au-delà d’un certain point produit des rendements décroissants, car la partie sérielle devient le goulet d’étranglement — on parle parfois du « plafond d’Amdahl ». Prenons un exemple concret : un programme prend 3 600 secondes sur un seul cœur, avec 80 % du travail parallélisable (p = 0.2). Avec 8 processeurs, l’accélération est S(8) = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1 / 0.3 = 3.33×. Le temps d’exécution parallèle est de 3600 / 3.33 = 1080 secondes. Avec 16 processeurs, S(16) = 1 / (0.2 + 0.8/16) = 1 / (0.2 + 0.05) = 4×, et le temps tombe à 900 secondes. Doubler de 8 à 16 processeurs n’améliore les performances que de 20 %, car les 20 % sériels dominent. L’efficacité parallèle est l’accélération divisée par le nombre de processeurs, exprimée en pourcentage : E = S(n)/n × 100 %. Elle mesure dans quelle mesure chaque processeur supplémentaire est utilisé. Une efficacité parfaite (100 %) signifierait que chaque processeur est pleinement exploité — un idéal théorique. En pratique, l’efficacité baisse à mesure que l’on ajoute des processeurs, car la fraction sérielle gaspille du temps processeur. Lorsque l’efficacité descend sous 50 %, ajouter des processeurs coûte plus en matériel que cela n’économise en temps. La loi d’Amdahl suppose que la fraction sérielle p reste constante, quelle que soit la taille du problème. La loi de Gustafson (1988) offre une perspective complémentaire : pour des problèmes plus grands, une plus grande fraction du travail devient parallélisable et l’efficacité reste plus élevée à mesure que le nombre de processeurs augmente. Ensemble, ces deux lois donnent une vision complète de la montée en charge parallèle — la loi d’Amdahl est pessimiste mais décrit correctement le cas à taille fixe, tandis que la loi de Gustafson est plus optimiste et s’applique lorsque la taille du problème croît avec le nombre de processeurs. Les applications pratiques de la loi d’Amdahl incluent la conception d’architectures CPU et GPU, l’allocation de ressources dans le cloud, l’analyse d’algorithmes pour le calcul haute performance et l’estimation du retour sur investissement de l’ajout de processeurs à un système existant. Identifier et réduire la fraction sérielle d’un calcul — grâce à de meilleurs algorithmes, à une réduction des coûts de synchronisation ou à une refonte des structures de données — est le moyen le plus efficace de repousser le plafond d’Amdahl.