Exemple d'une anomalie d'accélération parallèle

Question

Qu'est-ce qu'un exemple d'anomalie d'accélération parallèle? c'est à dire. Une tâche qui, lorsqu'elle est exécutée sur des processeurs p, entraîne une accélération supérieure à p.

Answer 1

Considérons un algorithme de matrice aux fins de parallélisation est modifié de telle manière que chaque nœud de calcul est attribué une région de la matrice et ne fonctionne que sur cette région. Si avec un nœud la région ne rentre pas dans le cache (parce que c'est la matrice entière) et avec plusieurs nœuds, elle commence à entrer dans le cache (plus il y a de nœuds, plus la région est petite). (mais pas toujours) entraînera une accélération anormale.

Answer 2

voir http://publishing.eur.nl/ir/repub/asset/1438/eur-few-cs-95-05.pdf, page 11, « 5 Anomalies dans le monde réel »

Answer 3

Une zone où l'accélération superlinéaire se produit est pour les problèmes de recherche.

Si la solution est trouvée sur l'un des processeurs supplémentaires, le calcul se termine tôt et une partie de la charge de travail d'origine n'est jamais exécutée.

Bien sûr, on pourrait simuler les n processeurs par des threads parallèles sur un processeur et obtenir le même effet, mais cela n'est généralement pas fait.