Hello,
Je dispose d'un groupement de boucles imbriquées de la forme suivante:
#pragma omp parallel for for (int a=0; a<h; a++) { int yOffMin = -min(rng,a); int yOffMax = min(rng,(h-a-1)); for (int b=0; b<w; b++) { int xOffMin = -min(rng,b); int xOffMax = min(rng,(w-b-1)); int nbAdd = 0; for (int yOff=yOffMin; yOff<=yOffMax; yOff++) { for (int xOff=xOffMin; xOff<=xOffMax; xOff++) { nbAdd++; for (int c=0; c<nbc; c++) { final[a][b*nbc+c] += rowP[a+yOff][(b+xOff)*nbc+c]; } } } #pragma omp parallel for for (int a=1; a<h-1; a++) { for (int b=1; b<w-1; b++) { for (int c=0; c<nbc; c++) { rowP[a][b*nbc+c] = final[a][b*nbc+c]; } } } }

Les clauses OpenMP fonctionnent là où je les ai placées mais j'aimerais améliorer la parallelisation et j'ai l'impression qu'il manque quelque chose d'évident.

J'avais tenté de régler le schedule en dynamic mais ça n'a rien changé chez moi. Si vous avez des idées de clauses qui améliorent le code je suis preneur !

Merci d'avance

EDIT: Désolé si le code s'affiche mal j'ai l'impression que la balise code ne fonctionne plus

Tes boucles sont imbrique de facon bizare. Tu as une boucle sur int a dans une autre boucle sur int a. Est ce qeu tu peux mettre le code correcte sur pastebin?

On voit mieux le code ici:

https://pastebin.com/BGmQqMaR

Donc j'ai posé les pragmas OMP mais les autres clauses que j'ai rajoutés n'ont fait que ralentir l'execution ou donner le mauvais résultat. Parmi ce que j'ai tenté
collapse: ne marche pas car dépendence entre les indices
schedule(dynamic | guided): aucune difference chez moi
mettre les indices des boucles en private: segfault ou mauvais résultat

Quelques questions:

Les valeures de w, h, et nbc ressemble a quoi?

Tu fais tourner ca sur quel type de machine?

C'est un flou gaussien que tu fais, non ?

Une raison de ne pas utiliser halide pour faire ca ?

Quelques remarques:
La deuxieme boucle for a(ligne 30) est une boucle de memcpy en fait. Je remplacerais les boucles lignes 32 et 34 par un seul memcpy. En supposant que la libc est bien ecrite sur ton systeme.

La premiere boucle sur a (ligne 1) semble completement parallele

Tu peux calcler nbadd a partir des offmin et offmax au lieu de les compter explicitement.

Donne toujours un schedule a ta boucle openmp. Le defaut du compilateur pourrait etre stupide.

Le speedup que tu as ressemble a quoi?

Le 13 septembre 2018 à 22:12:02 godrik a écrit :
Quelques questions:

Les valeures de w, h, et nbc ressemble a quoi?

Tu fais tourner ca sur quel type de machine?

C'est un flou gaussien que tu fais, non ?

Une raison de ne pas utiliser halide pour faire ca ?

Quelques remarques:
La deuxieme boucle for a(ligne 30) est une boucle de memcpy en fait. Je remplacerais les boucles lignes 32 et 34 par un seul memcpy. En supposant que la libc est bien ecrite sur ton systeme.

La premiere boucle sur a (ligne 1) semble completement parallele

Tu peux calcler nbadd a partir des offmin et offmax au lieu de les compter explicitement.

Donne toujours un schedule a ta boucle openmp. Le defaut du compilateur pourrait etre stupide.

Le speedup que tu as ressemble a quoi?

w et h sont entre 2000 et 4500 (dimensions)

La machine est un vieux pentium à 2 coeurs, j'ai pas mieux pour l'instant

C'est un flou gaussien/lisseur effectivement

Je ne connaissais pas halide mais l'algorithme est un pretexte pour m'entrainer sur OMP

Je m'étais fait la même remarque sur les boucles L30 et j'avais tenté un std::copy en vain. j'ai retenté avec un memcpy( rowP[a] , final[a], w*nbc*sizeof *final[a] ) qui ne fonctionne pas non plus mais je n'arrive pas à trouver pourquoi.

Je m'étais concentré sur la boucle de la ligne 1 qui me semble la plus importante et la plus gourmande et j'ai tenté de mettre le plus de variables possibles en private mais pas d'augmentation..

Je rajoute un schedule à chaque pragma selon ton conseil, me conseil tu de laisser le paramètre runtime ou de forcer avec un "dynamic" ou "guided" (par experience les plus efficaces selon moi)

Je n'ai pas encore calculé de speed up, je divise le temps par 2 à vu de nez actuellement. Je sais qu'on ne peut pas faire de magie mais je susi convaincue de pouvoir faire mieux.

Oups pour le memcpy j'avais oublié les références....

Si tu as une machine a 2 coeurs et que tu divise le temps par deux, qu'est ce que tu veux de plus?

je commencerai par du (dynamic, 64) sur un code comme ca.

Peux tu me dire ce qui te pousse à utiliser du dynamique et comment tu as choisi ta taille de chunk?

Je vais abandonner memcpy, en effet rowP est en réalité une instance de classe qui m'empêche d'utiliser memcpy convenablement

C'est quoi comme class? Tu peux vouloir utiliser un tableau directement.

Ca fait 15 ans que je fais du parallelisme, donc j'ai un peu d'intuition.
Mais globalement les raison sont comme ca:
-J'ai rarement vu un avantage important a guided sur dynamic. guided sert juste a eduire le nombre d'appel au scheduler. Mais c'est utile que si tu t'attend a ce que l'overhead soit important. ici, il y a plein de calcul, donc je ne m'y attend pas.
-static ne sert vraiment que quand tu veux forcer l'allocation des iterations sur un thread particulier, mais tu n'as pas l'air de savoir quoi faire avec une propriete comme ca. Et j ene suis pas massivement convaincu que ca va etre utile ici.
-Avec un scheduling dynamic, le cout de l'appel au scheduler est basiquement d'une instruction atomique de type fetch_and_add. Donc c'est pas gratuit, mais en gros c'est de l'ordre d'une 30 aines d'instructions au pire des cas.
-tu dis que w et h sont de l'ordre de 3000. Tu ne m'a pas donner nbc, mais j'imagine que c'est soit 4 si c'est un algo d'imagerie. Soit 32, 64, ou 128, si tu fais de la convolution pour un code de Deep Learning. Donc une iteration de a, va bouger en gros 10kB ou 100kB X la taille de la bande. Ce qui fait qu'une 64 iterations de a va couter un peu de temps, mais pas grand chose comparer a un atomic.
-En meme temps, tu ne veux pas un a trop grand pour eviter de perdre de l'equilibrage de charge, mais si h est dans les 3000, un bloc de 64 va faire de l'ordre de 2%, donc ca va aller cote equilibrage de charge.
-Tu pourrais faire un a plus petit, mais tu veux probablement essayer de reutiliser le cache sur le bandage. Donc tu veux probablement un a qui est plus grand que la bande. On utilise rarement des convolution de plus de 5x5. Donc, une bande va faire en gros 500kB. Ce qui tiens en cache de la plupart des machine. Bon, la tu teste sur une machine antediluvienne (un pentium 2 core, c'est probablement un pentium D, circa 2006), mais il y a quand meme probablement 1MB de cache.
-en supposant une granularite de 64 et une convolution en 5x5, tu perd en gros 2% de la reutilisation de cache de la bande. Donc c'est acceptable.