SpeedUp médiocre avec openMP

Bonjour,

Je test ma machine (processeur 6 coeurs+ hyperthreading: donc 12 threads possibles) en programmation openMP et j'ai des speedup plutôt décevant que je ne comprend pas trés bien. Avec l'example ci-dessous mon speedup plafonne entre 3 et 4. J'ai beau augmenter la taille de la boucle,N ,je n'obtient pas mieux. Quelqu'un connaitrait-il des raisons expliquant ces médiocres résultats.
Est-ce du à l'architecture du microprocesseir intel? Ou mes directives openMP ne sont pas obtinmisées.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

double e,*c,*d; int k,N=1e8; c= new double[N]; d= new double[N]; omp_set_num_threads(12); #pragma omp parallel for private(k) reduction(+:e) for (int i=0;i<N;i++) { k=i; d[k]=10.225*(double)i; c[k]=d[k]/1251.5; c[k]+=11.9+d[k]+d[k]/2568+d[k]*0.025; c[k]-=10.36-2.4*d[k]; e=e+cos(c[k]); } delete[] c; delete[] d;

---

Pour info: ne cherchez pas de sens à ce calcul, c'est just un test.
Je travaille en win64 ou Linux64 ubuntu avec gcc4.5

Tout dépend de la taille des blocs, il faudrait faire des chunks (surtout que tu as des accès très proches, il est possible que le proc fasse pas mal de défauts de cache).

Ensuite, c'est quoi le k ? Tu devrais plus avoir un i privé qu'un k !

Merci de ta réponse, le k ne sert à rien, c'est juste histoire de compliquer un peu. Peux-tu etre plus explicites à propos des chunks

OpenMP découpe la boucle en morceaux (taille statique, dynamique, ... ça dépend). Si le morceaux est trop petit, il y a beaucoup d'overhead pour la gestion des morceaux. S'il est assez grand, un morceau va gérer au moins une ligne de cache, et donc très peu de comm et pas de mise à jour à faire entre les coeurs (car ils ne partagent pas les lignes de cahc eL1).

Là aujourd'hui je n'ai qu'une machine 2 processeurs sous la main et visiblement ne pas mettre de schunk semble etre l'optimal, en même temps j'ai bien saisi la doc ci-dessous, mais je ne vois pas diretement le lien avec les performances. A part 'Dynamic' qui semble donner de plus mauvais résultats sur 2 cores, les autres choix ne donnent pas d'amélioreation evidentes. Lundi, je vais faire des testes sur ma machine 12 threads et ainsi peut-etre mettre plus en évidence ce que fait cette directive et peut-etre amméliorer les performances

Code:

---

1 2 3 4 5 6

La clause SCHEDULE spécifie la manière de partager les itérations entre les threads. Au sein de cette clause, chunk est un entier et type peut être : STATIC : SCHEDULE (STATIC,chunk) impose un découpage du nombre d'itérations en blocs de taille chunk. Ces blocs sont attribués aux différentes threads de manière statique en suivant une distribution de type round-robin dans l'ordre des numéros des threads. En l'absence de chunk, les itérations sont réparties parmi les threads en bloc continu. DYNAMIC : SCHEDULE (DYNAMIC,chunk) impose le découpage du nombre d'itérations en blocs de taille chunk. Lorsque chaque thread a fini son bloc, elle reçoit dynamiquement le prochain groupe. Lorsque chunk est omis, la valeur par défaut est 1. GUIDED : SCHEDULE (GUIDED,chunk) impose une décroissance exponentielle de la taille chunk des paquets d'itérations qui sont distribués. Lorsque chunk est omis, la valeur par défaut est 1. RUNTIME : SCHEDULE (RUNTIME) indique que la distribution (type et chunk) des itérations sera effectuée durant l'exécution et ces paramètres seront fixés à l'aide de la variable d'environnementOMP_SCHEDULE. Le paramètre chunk doit être omis.

---

Au passage, e n'est pas initialisée.

Oui, merci c'est uniquement une erreur de recopie.
Bon j'ai fini par faire des tests avec une machine 12 threads, et je n'ai remarqué qu'un certain mieu en utilisant le mode "guided" et pour les petit nombre d'itérations. Sinon le mode "dynamic" agrave les choses. Et quand la boucle devient grande "Guided" devient similaire à "Auto". Je trouve surprenant que quand ma boucle devient trés longue "plusieurs minutes", je n'arrive pas à m'apporcher du speed-up théorique maximum.

Faut voir ce que Parallel Studio te dirait, il te fait des courbes de speedup théoriques avant parallélisation très intéressantes.

Parallele studio est payant et nécessite l'installation de visual que je ne posséde pas. Je travaille uniquement avec GNU gcc

Regarde "false sharing" sur le web (en particulier les articles de Herb Sutter), j'ai l'impression en parcourant rapidement ton code que tu es pile poil dans cette situation.

Citation:

---

Envoyé par uriotcea

Parallele studio est payant et nécessite l'installation de visual que je ne posséde pas. Je travaille uniquement avec GNU gcc

---

Il y a des versions d'évaluation ;) Mais c'est vrai que si tu n'as pas Visual, la version Linux sous Eclipse n'a pas Advisor :(

Citation:

---

Envoyé par JolyLoic

Regarde "false sharing" sur le web (en particulier les articles de Herb Sutter), j'ai l'impression en parcourant rapidement ton code que tu es pile poil dans cette situation.

---

C'est pour ça que je lui avais indiqué de modifier la taille des chunks pour éviter le false sharing (entre autres).

Pour faire ça proprement, il vaudrait mieux changer le mode de stockage des données...Parce qu'autrement, les chunks devraient être plus gros que le cache du processeur pour que ça ait de l'effet, ce qui risque de réduire les possibilités de parallélisation...

Ok, j'ai lu un peu sur le false sharing, je comprend bien le probléme, mais je ne vois pas bien comment mettre ca en evidence dans mon example

Fait un tableau 100* plus gros, et modifie ta boucle pour ne lire qu'une valeur sur 100, et regarde si ça change quelque chose...
Ce n'est certainement pas une solution très propre, mais ça devrait donner une bonne idée si c'est bien le problème.

Une autre façon, mais moins sure (car le compilo optimise peut-être déjà...), serait de remplacer tes c[k] par des variables locales, et ne les écrire que tout à la fin pour minimiser les accès au tableau.

Ok j'ai essayé de multiplier par 100 la taille des tableau comme tu me le suggerais. J'ai essayé 2 types calculs similaires à mon example avec à chaque fois une dégradation légére (Mais présentement, je n'ai qu'un bicore..)

L'explication en viendrait pas du fait que l'hperthreading n'est pas vraiment équiavent à un vrai bi-pro?

Comme tu fais pas mal d'opérations pour les quelques accès mémoire, ça ne devriat pas.

Essaie d'ajouter le mot-clé __restrict sur tes tableaux.

Je ne vois pas à quoi sert ce mot clef. Cela dit, il me génére un message d'erreur à la compilation

error: '__restrict__' qualifiers cannot be applied to 'double'

Le mot clé permet d'indiquer qu'aucun autre pointeur n'accède à la même zone mémoire, donc pas la peine de recharger la donnée à chaque fois, de peur qu'un autre processeur/opération ait modifié l'emplacement.
En revanche, c'est bizarre que ça ne marche pas pour les double :koi: et avec restrict tout court ?

Visiblement ne marche pas non plus avec les int

C'est pour les pointeurs, restrict.

oui oui je parlais des pointeurs

Ok, c'est moi qui faisait faisait pas correctement les choses, j'ai enfin réussi à mettre 'restrick' à mes pointeurs, mais le resultats est le même. Ca ne change pas grand chose.

Bonjour,

Effectivement, ce n'est pas brillant 8O , comme l'atteste le rapport en attachement (il y a un peu de tout, dont le fameux false sharing évoqué auparavant, mais aussi des problèmes de localité spatiale, temporelle).
Il a été généré par un outil nommé ThreadSpotter (sous licence). Vraiment pratique, quelques secondes pour déterminer là où ça ne va pas et quels sont les remèdes à envisager. Pour info, j'ai fait ça à l'arrache sur Windows 7 x86_64 et MSVS 2010 (4 threads).


-SebGR

Bonjour,

Ok je n'y comprend pas grand chose, mais merci de tes indications.
Est ce que cette outil, ThreadSpotter est lié à MSVS.

Non, ThreadSpotter n'est pas adhérent au compilateur. Il fonctionne sous Windows et Linux.


-SebGR

Ok merci, mais il semblerait que ce soit payant !

Oui, c'est payant.

Bonjour,

est-ce qu'il y a un équivalent à ThreadSpotter sous linux gratuit ?

Merci par avance pour vos réponses

Le passage suivant de ce tuto peut peut être t'aider :

http://www.unixgarden.com/index.php/...le-avec-openmp

4.3


Répartition des tâches

Sans spécification particulière, les tâches sont réparties de manière égalitaire entre les différents threads. Les threads traitant le centre de la fractale ont plus de calculs à traiter que les threads chargés de l’extérieur de la fractale. Les threads les plus rapides attendent donc les threads les plus lents avant la finalisation du programme. La répartition des tâches est configurable à la fin de la directive omp parallel for avec la clause schedule. Le découpage peut se faire selon quatre manières différentes.

4.3.1


Répartition statique

Si rien n’est spécifié, la répartition statique est utilisée, elle peut être aussi explicitement choisie en utilisant la clause schedule(static). Le nombre d’itérations de la boucle est divisé par le nombre de threads, tous les threads traitent donc la même quantité de données. Il est possible de fixer le nombre de données traité par chaque thread après la déclaration static, par exemple : schedule(static,32).

4.3.2


Répartition dynamique

Chaque thread traite une quantité de données spécifiée par la taille passée après dans la déclaration dynamic. Dès qu’un thread a terminé son lot de données, il peut reprendre un lot de données à traiter. Les threads n’ont pas d’ordre de passage, certains peuvent être plus longs que d’autres.

Par défaut, un seul élément est traité par chaque thread. Le nombre d’éléments traités peut être fixé après la déclaration dynamic. Sauf si les calculs sont très longs, il doit être initialisé pour prendre une valeur supérieure à la valeur par défaut : schedule(dynamic,32).

4.3.3


Répartition guidée

Cette organisation des tâches est basée sur une taille décroissante des blocs traités. Au départ, les threads traitent une grande quantité de données, puis le nombre d’éléments traités décroît pour optimiser le temps de calcul. Le nombre minimal d’éléments à traiter est fixé par la valeur passée en paramètre.

4.3.4


Répartition à l’exécution

Il est possible de choisir la méthode de répartition des tâches lors de l’exécution du programme. Pour obtenir ce comportement, on utilise la clause schedule runtime. La répartition et ses paramètres sont alors configurés par la variable système OMP_SCHEDULE. La répartition à l’exécution n’est utile que pour le développement afin de tester différentes stratégies de répartition.

4.3.5


Considérations générales pour le choix d’une stratégie

Quelle que soit la solution retenue, la taille des blocs doit être fixée en prenant en compte les deux limites suivantes :

● Si les blocs sont trop gros, le temps de calcul des threads est déséquilibré, certains sont plus lents que d’autres.

● Si les blocs sont trop petits, le temps de changement de contexte (chargement des nouvelles valeurs pour un thread) peut être significatif vis-à-vis du temps de calcul des threads.

Ok merci pour les explications et l'example.
Pour ma part, j'ai un processeur 6 coeurs hyperthreadé, donc à priori 12 threads. Et un peu comme les examples de ton article, j'atteind aprés optimisation, un speed-up relativement linéaire jusqu'à 6 puis un faible gain jusqu'à un maximum de 8.

c'est peut etre tout simplement la faute a Amdhal.
Ton algo est il 100% parallelisable ?