11.4.2.2.1 : Introduction
Un programme parallèle ne s'exécutera qu'exceptionnellement $n$ fois plus vite ou mieux noteIl arrive rarement d'observer une accélération supérieure à $n$ en parallèle quand l'algorithme parallèle utilise des ressources processeur partagées comme le cache L3 mieux que son homologue séquentiel. sur une machine à $n$ processeurs. Ce passage à l'échelle parfait avec utilisation optimale des ressources de calcul n'est qu'un idéal vers lequel on doit tendre.
Une des raisons est que le programme parallèle n'utilise pas toutes les ressources de calcul disponibles pendant l'intégralité de son exécution. Par exemple, un schéma de fonctionnement classique est de commencer par une initialisation séquentielle sur un seul cœur CPU, puis de lancer le calcul sur les autres processeurs du système, poursuivre le calcul parallèle jusqu'à ce qu'il soit terminé, et enfin terminer par une phase de finalisation séquentielle exécutée sur un seul cœur telle qu'un envoi des résultats à l'utilisateur. Durant les phases séquentielles, le programme sera limité par la performance d'un processeur unique.
D'autres phénomènes peuvent limiter le passage à l'échelle, par exemple le surcoût lié aux communications entre les tâches parallèles ou l'épuisement de ressources matérielles partagées entre les cœurs de calcul telles que la bande passante de la mémoire, du stockage, et de l'interconnexion réseau.
Une figure de mérite couramment utilisée est la loi de passage à l'échelle, qui relie l'accélération obtenue dans une exécution à $n$ cœurs par rapport à la version séquentielle, au nombre de cœurs $n$ alloués. Cette loi peut être prédite théoriquement dans certains cas idéalisés, que nous allons voir maintenant.