11.4.4.3 : Algorithmie
Tous les algorithmes ne se prêtent pas à la parallélisation, et ceux qui s'y prêtent ne sont pas forcément parallélisables à toutes les échelles. De même que la parallélisation d'un calcul sur une matrice 5$\times$ 5 n'a pas de sens, alors que sa vectorisation en a, il peut être pertinent pour un programme parallèle d'utiliser une stratégie de parallélisation à l'intérieur d'un nœud très différente de sa stratégie pour la distribution à grande échelle.
Lorsqu'on se lance dans un processus de parallélisation, il est important d'étudier l'état de l'art des structures de données et algorithmes utilisés pour résoudre en parallèle des problèmes similaires. On découvrira alors potentiellement qu'un algorithme séquentiel bien connu, comme mergesort, se décline très facilement en une version parallèle, tandis qu'un autre habituellement considéré comme supérieur en séquentiel, comme quicksort, ne se parallélise que beaucoup plus difficilement.
Cela évitera de partir sur une fausse piste en début de développement, et dans certains cas on y découvrira même une implémentation utilisable de l'algorithme étudié qui économisera de longues heures de développement.
Lorsque cette recherche n'est pas très fructueuse, l'expérimentation sur les infrastructures de calcul les plus fortement parallèles dont on dispose permettra de vérifier si une approche dont on a des raisons théoriques de penser qu'elle passe à l'échelle le fait réellement. En effet, il n'est que trop facile d'oublier dans son raisonnement des coûts matériels cachés, tels que la communication broadcast inhérente à la cohérence de cache en mémoire partagée, qui font qu'une l'implémentation d'un algorithme s'écarte du comportement théoriquement attendu.