Discussion:Parallélisation

De Wiki de Calcul Québec
Aller à : Navigation, rechercher

Je ne suis pas d'accord avec une partie du texte au sujet de la loi d'Amdahl. C'est la partie où l'on parle de la linéarité comme étant le cas optimal. En fait, ce n'était pas affirmé dans l'article original d'Amdahl. Il ne tire qu'une conclusion en démontrant la limitation dû au fait qu'une partie d'un code ne peut pas être accélérée.

Sur Wikipedia, on retrouve également un article sur le "speed up". Celui-ci affirme qu'il est possible d'observer du "super linear" speedup. On y parle entre autre de l'effet de mémoire cache. Mais ceci n'est pas un algorithmique. http://en.wikipedia.org/wiki/Speedup

Une raison plus simple pour expliquer la possibilité d'accélération superlinéaire est que la complexité d'un algorithme peut être en loi de puissance en fonction du nombre d'éléments à traiter. Si ces éléments sont distribués parmi les processus, il est évident qu'il est possible d'observer une accélération plus que linéaire.

Par exemple, si le nombre d'opérations O = n^3 où n est le nombre d'éléments à traiter. Il est possible d'imaginer qu'en distribuant ces éléments parmi P processus, que le nombre d'opérations fait pas chaque processus sera de l'ordre de: O' = (n/P)^3 Indiquant une accélération plus que linéaire.


Maxime : Pour moi, l'accélération dû au nombre d'opérations O = n^3 qui est divisé, ce n'est pas une accélération due à la parallélisation, mais due à un changement d'algorithme : dans un cas, tu traites tous les éléments de façon globale, dans l'autre tu en traites plusieurs parties de façon locale. Il n'y a rien qui t'empêcherait de traiter la partie locale de façon séquentielle, un bloc à la fois, sur un seul processeur. En d'autres mots, l'accélération n'est pas due au fait que tu exécutes plusieurs parties de la tâche en parallèle, mais plutôt que tu exécutes la tâche en plusieurs parties (séquentiellement ou parallèlement n'a pas d'importance).


Steve : Je suis d'accord avec toi Maxime. La parallélisation du code, amène parfois à suivre une approche du type "Divide & conquer". Si le nombre de division est fixé par le nombre de processus, on peut en effet voir une accélération supérieur à ce qui est linéaire. Mais c'est dû à la façon que l'algorithme est construit. C'est trompeur. Il semble n'y avoir que les effets de cache et la hiérarchie de mémoire qui peuvent réellement créer une accélération plus que linéaire (si l'on reste avec des bits classiques, je ne parlerai pas des qbits, c'est ta spécialité).

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Ressources de Calcul Québec
Outils
Partager