11.4.4.1 : Passage à l'échelle
Le problème de performance le plus fréquemment rencontré dans les programmes parallèles est une inaptitude à tirer parti des ressources d'exécution disponibles.
En particulier, tous les mécanismes de synchronisation qui sont basés sur l'attente (mutexes, communications bloquantes... ) réduisent intrinsèquement le niveau de parallélisme puisqu'ils amènent une tâche à attendre qu'une autre progresse avant de pouvoir continuer son exécution. Si ces mécanismes de synchronisation causent beaucoup d'attente sur un chemin critique pour la performance du programme, le programme ne passera pas à l'échelle.
Dans ce cas, les approches suivantes peuvent être considérées, étant entendu qu'elles sont triées par ordre de priorité décroissante~:
- Élimination de la synchronisation. Si une donnée ne varie pas au cours de l'exécution parallèle, sa synchronisation n'est pas nécessaire. Si elle varie peu et est de petite taille, il peut être acceptable d'en conserver une copie au sein de chaque tâche qui ne sera synchronisée qu'occasionnellement.
- Synchronisation à grain plus fin. Par exemple, au lieu de synchroniser l'accès à l'ensemble d'un tableau, on peut synchroniser l'accès à des éléments individuels. Cette approche réduit les conflits lorsque chaque tâche n'accède qu'à un sous-ensemble presque disjoint des données synchronisées, mais elle augmente souvent le coût de synchronisation et n'est donc pas applicable quand les accès sont fréquents.
- Synchronisation non bloquante. Il existe des techniques permettant de synchroniser deux tâches sans qu'elles ne s'attendent les une les autres à aucun moment (algorithmes lock-free, communications asynchrones... ). En dernier recours, ces techniques peuvent réduire ou éliminer la perte de parallélisme liée à la synchronisation, mais cela se fait souvent au prix d'un surcoût sur une autre ressource (mémoire, CPU... ) et d'une augmentation de la complexité du code.
En dehors de l'attente, une autre classe de problèmes à éviter est l'excès de communication. Les interconnexions qui portent ces communications (qu'il s'agisse du bus interne portant la cohérence de cache CPU ou du réseau explicitement commandé en calcul distribué) ont une certaine latence et une bande passante finie. Toute communication introduit donc des surcoûts qui écartent le programme parallèle du passage à l'échelle parfait. Et lorsque la bande passante d'une interconnexion est épuisée, on ne peut plus augmenter le niveau de parallélisme associé.
Cela implique, en particulier, qu'il faut se méfier de tous les mécanismes qui permettent à un thread ou plus de communiquer avec tous les autres threads du système. Quand une communication collective s'avère nécessaire, elle doit si possible se produire entre des groupes de threads de taille réduite, quitte à produire ensuite un résultat global par plusieurs passes de communication hiérarchique.
Les synchronisations de type "barrière", où l'on attend qu'un groupe de threads ait terminé un travail avant de continuer, combinent à la fois une synchronisation basée sur l'attente et une communication entre de nombreux threads. Elles ne doivent donc être employées qu'avec la plus extrême parcimonie.
Enfin, le passage à l'échelle en parallèle passera aussi souvent par une optimisation individuelle de chaque tâche séquentielle, afin de réduire l'empreinte de chacune d'entre elle sur les ressources matérielles partagées dont l'épuisement empêche tout passage à l'échelle. La parallélisation se situera donc idéalement après l'optimisation séquentielle dans le processus de développement.