OpenMP ralentit au lieu de booster

[rAyyy]

Hello,

J'ai fait un programme graphique que je souhaite optimiser. Je me suis donc intéresse à OpenMP (pour dire que j'y connais pas grand chose).

Voila la partie du code que j'ai parallélisé:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
void incrementation(Planete* A, int nmb)
{
  int i;
  int l;
float truc1;
float truc2;
float truc3;
float distance;
 
 
for(l=0;l<=nmb-1;l++)
{
    truc1=0;
    truc2=0;
    truc3=0;
    distance=0;
 
#pragma omp parallel for
    for(i=0;i<=nmb-1;i++)
    {
 
        if(!(i==l))
        {
            distance=(A[i].x_now-A[l].x_now)*(A[i].x_now-A[l].x_now)+(A[i].y_now-A[l].y_now)*(A[i].y_now-A[l].y_now)+(A[i].z_now-A[l].z_now)*(A[i].z_now-A[l].z_now);
 
            truc1=truc1+(G*A[i].masse*(A[i].x_now-A[l].x_now))/((distance+1)*sqrt(distance));
            truc2=truc2+(G*A[i].masse*(A[i].y_now-A[l].y_now))/((distance+1)*sqrt(distance));
            truc3=truc3+(G*A[i].masse*(A[i].z_now-A[l].z_now))/((distance+1)*sqrt(distance));
 
        }
 
    }
 
A[l].x_after= truc1*PAS*PAS - A[l].x_past + 2*A[l].x_now;
A[l].y_after= truc2*PAS*PAS - A[l].y_past + 2*A[l].y_now;
A[l].z_after= truc3*PAS*PAS - A[l].z_past + 2*A[l].z_now;
 
}
 
 
#pragma omp parallel for
for(l=0;l<=nmb-1;l++)
{ 
    A[l].x_past=A[l].x_now;
    A[l].y_past=A[l].y_now;
    A[l].z_past=A[l].z_now;
 
    A[l].x_now=A[l].x_after;
    A[l].y_now=A[l].y_after;
    A[l].z_now=A[l].z_after;
 
    A[l].x_after=0;
    A[l].y_after=0;
    A[l].z_after=0;
 
}
 
}

Le problème c'est que au final à part avoir monté le pourcentage du processus utilisé de 25% à 96% (mon processeur a 4 coeur) la parallélisation n'a eut aucun effet sur la vitesse d’exécution du programme. Ça la même ralenti: j'ai une baisse de 3 ou 4 FPS par rapport au même code sans les : #pragma omp parallel for . De plus il y a aussi plus d'erreur de calcul( c'est moins stable).

Donc ma question c'est est ce que OpenMP est vraiment utile ou est ce que c'est moi qui ne sais pas l'utilisé?

Merci d'avance.

[gbdivers]

Bonsoir

Hum, difficile comme question. Allez, je tente une réponse... le problème vient peut être de toi ?

Plus sérieusement, le problème avec OpenMP est que cela permet de faire du multithread facilement. Le problème avec ceux qui utilisent OpenMP est qu'ils croient que le multithreading est facile. En pratique, tout n'est pas parallélisable. Et rien n'est parallélisable n'importe comment.

Faudra regarder en détail ton code, ton algo pour voir le problème, mais pas le temps ce soir

[Iradrille]

Hello,

Appeler une variable l ou O c'est assez troublant, la confusion avec 1 ou 0 est vite arrivée, et c'est pas facile à relire du coup :p

Mais sinon le morceau de code
truc1 += ...;
truc2 += ...;
truc3 += ...;
me semble pas safe, si 2 threads accèdent en même temps à truc1 / truc2 / truc3, tu peux perdre la valeur d'un des threads.

[rAyyy]

Merci pour vos réponses.

à gbdivers
Je me doutai bien que ça venais de moi mais bon on a toujours espoir que l'on est sans reproche ^^
Je vais essayer de trouver des cours pour mieux comprendre openMP alors

à Iradrille
Ça doit être pour ça que je trouve que c'est moins stable quand j'utilise le multi-threading :/
Quelqu'un aurait une idée pour savoir comment éviter ce problème?

[Trademark]

Salut,

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
for(l=0;l<=nmb-1;l++)
{
    truc1=0;
    truc2=0;
    truc3=0;
    distance=0;
 
#pragma omp parallel for
    for(i=0;i<=nmb-1;i++)
    {
 
        if(!(i==l))
        {
            distance=(A[i].x_now-A[l].x_now)*(A[i].x_now-A[l].x_now)+(A[i].y_now-A[l].y_now)*(A[i].y_now-A[l].y_now)+(A[i].z_now-A[l].z_now)*(A[i].z_now-A[l].z_now);
 
            truc1=truc1+(G*A[i].masse*(A[i].x_now-A[l].x_now))/((distance+1)*sqrt(distance));
            truc2=truc2+(G*A[i].masse*(A[i].y_now-A[l].y_now))/((distance+1)*sqrt(distance));
            truc3=truc3+(G*A[i].masse*(A[i].z_now-A[l].z_now))/((distance+1)*sqrt(distance));
 
        }
 
    }
 
A[l].x_after= truc1*PAS*PAS - A[l].x_past + 2*A[l].x_now;
A[l].y_after= truc2*PAS*PAS - A[l].y_past + 2*A[l].y_now;
A[l].z_after= truc3*PAS*PAS - A[l].z_past + 2*A[l].z_now;
 
}

Dans ce code, la deuxième boucle ne peut pas être parallélisée… En effet comment veux-tu paralléliser quelque chose qui, à l'itération i, a besoin de données de l'itération i-1 ?

Par contre la première boucle peut être parallélisée vu que chaque itération est indépendante l'une de l'autre (a première vue).

À part ça, je n'aime pas trop tes notations de variable (truc notamment). Et l<=nmb-1 == i < nmb mais bon ça c'est plus du style qu'autre chose.

J'ai retrouvé un petit lien sur la prog parallèle qui te donnera quelques bases (section Manycore) http://www.intel-software-academic-p...ses/index.html

[rAyyy]

à Trademark
Tu veut dire mettre #pragma omp parallel for sur la boucle en l ?
Comme cela?

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#pragma omp parallel for
for(l=0;l<=nmb-1;l++)
{
    float truc1=0;
    float truc2=0;
    float truc3=0;
    float distance=0;
 
    for(i=0;i<=nmb-1;i++)
    {
 
        if(!(i==l))
        {
            distance=(A[i].x_now-A[l].x_now)*(A[i].x_now-A[l].x_now)+(A[i].y_now-A[l].y_now)*(A[i].y_now-A[l].y_now)+(A[i].z_now-A[l].z_now)*(A[i].z_now-A[l].z_now);
 
            truc1=truc1+(G*A[i].masse*(A[i].x_now-A[l].x_now))/((distance+1)*sqrt(distance));
            truc2=truc2+(G*A[i].masse*(A[i].y_now-A[l].y_now))/((distance+1)*sqrt(distance));
            truc3=truc3+(G*A[i].masse*(A[i].z_now-A[l].z_now))/((distance+1)*sqrt(distance));
 
        }
 
    }
 
A[l].x_after= truc1*PAS*PAS - A[l].x_past + 2*A[l].x_now;
A[l].y_after= truc2*PAS*PAS - A[l].y_past + 2*A[l].y_now;
A[l].z_after= truc3*PAS*PAS - A[l].z_past + 2*A[l].z_now;
 
}
 
for(l=0;l<=nmb-1;l++)
{ 
    A[l].x_past=A[l].x_now;
    A[l].y_past=A[l].y_now;
    A[l].z_past=A[l].z_now;
 
    A[l].x_now=A[l].x_after;
    A[l].y_now=A[l].y_after;
    A[l].z_now=A[l].z_after;
 
    A[l].x_after=0;
    A[l].y_after=0;
    A[l].z_after=0;
 
 
 printf("////////////////////////////////////  x %f y %f z %f \n",A[l].x_now,A[l].y_now,A[l].z_now);
 
}

J'ai essayer mais ça me donne quelque chose de très bizarre. Enfaite ça marche pendent un certain nombre d'itération (une cinquantaine) puis ça "explose".
Voila ce que j'ai en réponse à une certaine itération (qui doit être la première où ça bug):

//////////////////////////////////// x -1.#IND00 y -1.#IND00 z -1.#IND00
//////////////////////////////////// x 1.173992 y 1.173772 z 0.830448
//////////////////////////////////// x 0.000324 y 1.709239 z 0.855267
//////////////////////////////////// x -0.991069 y 0.991448 z 0.697652
//////////////////////////////////// x -1.532580 y 0.000020 z 0.767228
//////////////////////////////////// x -1.191267 y -1.191673 z 0.843637
//////////////////////////////////// x 0.000533 y -1.104066 z 0.553131
//////////////////////////////////// x 1.137536 y -1.137083 z 0.804880
//////////////////////////////////// x 1.794373 y 0.000017 z 0.897442
//////////////////////////////////// x -0.005192 y -0.000273 z -0.010508

J'ai jamais vu ces -1.#IND00 qu'est ce qu'ils signifient ? Erreur de calcul? Dépassement de capacité?

[bretus]

Envoyé par rAyyy

Ça doit être pour ça que je trouve que c'est moins stable quand j'utilise le multi-threading :/
Quelqu'un aurait une idée pour savoir comment éviter ce problème?

Avant de faire du multi-threading avec une bibliothèque comme OpenMP, il faudrait peut-être que tu comprennes les difficultés liées aux threads.

Là, tu fais des accès concurrent sur truc1, truc2, truc3 (reduction?) et tu as des accès concurrent sur distance (private?)

Essaye de prendre un cours OpenMP et de faire le tour des instructions, elles sont la solution à des problèmes, tu connaîtras donc ces problèmes. Si tu t'arrêtes à

Code :

#pragma omp parallel for

sans ce qui va derrière, tu ne t'en sortiras pas.

J'aurais tendance à te conseiller de commencer par des choses simples pour te faire la main :
* Somme de vecteur (pas de concurrence)
* Min/max sur vecteur (accès concurrent sur le résultat)
* Produit scalaire (réduction d'une somme)

Tu auras moins de mal qu'en t'attaquant directement à des boucles imbriquées.

[Aleph69]

Salut,

pour paralléliser ton code avec OpenMP, il faut que tu apprennes les concepts d'OpenMP (Lapalisse n'aurait pas dit mieux) et notamment :
1. les notions de données partagées et privées
2. la notion de synchronisation
3. la notion de réduction dans une boucle parallèle.
Sans ça, tu n'y arriveras jamais. Avec ça, tu vas y arriver très facilement et très rapidement. Encore merci Lapalisse!

Je t'invite à regarder le cours de l'IDRIS qui est très bien fait :
http://www.idris.fr/data/cours/paral...choix_doc.html
Si tu cherches les cours en C++ et que tu ne les trouves pas... c'est normal, ils sont bien en fortran! C'est très facile de les traduire en C++ et ce n'est pas cela qui importe. Je te conseille vivement de faire les TPs qui sont progressifs et introduisent bien les concepts.

Pour te motiver un peu : ton code est réellement très simple à paralléliser, tu vas tomber sur la même problématique dans les TPs!

@gbdivers : joli troll!

[Médinoc]

Ce code fait ce qu'on appelle une réduction puisqu'il fait une somme cumulative en boucle.

Je sais qu'il y a un pragma pour OpenMP qui gère ça.

[rAyyy]

à Aleph69:
c'est vrai que le cour explique bien mais les instructions openMP en fortran et en C++ sont très différentes donc j'arrive pas à le mettre en pratique mais bon je vais chercher d'autre cours. Merci quand même.

[bretus]

Bonsoir,

Si ça peut t'aider, voici un exemple simple de produit scalaire :

Code :

1
2
3
4
5
6
7
8
9
 
double dot( const std::vector< double >& a, const std::vector< double >& b ){
	double result = 0.0 ;
	#pragma omp parallel for reduction(+:result)
	for ( size_t i = 0; i < a.size(); i++ ){
		result += a[i] * b[i] ;
	}
	return result ;
}

Dans ton cas, le réduction devrait ressembler à

Code :

reduction(+:truc1,truc2,truc3)

si j'ai bien compris ("openmp reduction multiple variables c++" dans l'ami google)

++

Autres exemples :

Réduction et autres

http://people.sc.fsu.edu/~jburkardt/...mp/openmp.html

[Aleph69]

Salut,

Envoyé par rAyyy

les instructions openMP en fortran et en C++ sont très différentes

Je dirais plutôt qu'elles sont très ressemblantes mais bon...

Voici un résumé des commandes openmp pour le C/C++
http://openmp.org/mp-documents/OpenMP3.1-CCard.pdf
et pour le fortran
http://openmp.org/mp-documents/OpenM...ortranCard.pdf

[rAyyy]

Je dirais plutôt qu'elles sont très ressemblantes mais bon...

Lol t'a raison c'est moi qui extrapole trop.
C'est juste que je pouvais pas deviner comme ça par quoi il fallait remplacer.
Merci pour tes liens.

openmp reduction multiple variables c++" dans l'ami google

Je n'ai pas eu vraiment le temps de m'y mettre à fond dernièrement (fin de semestre)

J'ai essayer

Code :

#pragma omp parallel for reduction(+:truc1,truc2,truc3)

Comme ceci

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void incrementation(Planete* A, int nmb)
{	
  int i;
  int l;
 
for(l=0;l<=nmb-1;l++)
{
    float truc1=0;
    float truc2=0;
    float truc3=0;
    float distance=0;
 
   #pragma omp parallel for reduction(+:truc1,truc2,truc3)
    for(i=0;i<=nmb-1;i++)
    {
        if(!(i==l))
        {
            distance=(A[i].x_now-A[l].x_now)*(A[i].x_now-A[l].x_now)+(A[i].y_now-A[l].y_now)*(A[i].y_now-A[l].y_now)+(A[i].z_now-A[l].z_now)*(A[i].z_now-A[l].z_now)+1;
 
            truc1=truc1+(G*A[i].masse*(A[i].x_now-A[l].x_now))/((distance)*sqrt(distance));
            truc2=truc2+(G*A[i].masse*(A[i].y_now-A[l].y_now))/((distance)*sqrt(distance));
            truc3=truc3+(G*A[i].masse*(A[i].z_now-A[l].z_now))/((distance)*sqrt(distance));
 
        }
    }
 
A[l].x_after= truc1*PAS*PAS - A[l].x_past + 2*A[l].x_now;
A[l].y_after= truc2*PAS*PAS - A[l].y_past + 2*A[l].y_now;
A[l].z_after= truc3*PAS*PAS - A[l].z_past + 2*A[l].z_now;
 
}

Ça a le même effet sur mon rendu que

Code :

#pragma omp parallel for

Cad perte de fps et on voit que ça fait des choses bizarre(qu'il doit y avoir des calculs qui sautent ou des erreurs; je ne sais pas)

[Aleph69]

Bon, il faut vraiment que tu prennes le temps de regarder un cours sur OpenMP. Je te donne quelques points d'entrée pour que tu démarres.

Quand tu parallélises, chaque processus possède une mémoire qui lui est propre. Un autre processus ne peut ni lire ni écrire dans cette mémoire. Les variables stockées dans cette mémoire sont dites privées. Par ailleurs, tous les processus partagent une autre quantité de mémoire dans laquelle chacun peut y lire et y écrire. Les variables stockées dans cette mémoire sont dites partagées. Quand on utilise une directive OpenMP, on spécifie si les variables sont privées ou partagées, ce que tu ne fais pas.

Par défaut, une variable est souvent partagée mais ce n'est pas toujours le cas. On va considérer ta variable distance pour illustrer. Comme tu n'as rien précisé, elle est partagée. Ce qui veut dire que chaque processus met à jour sa valeur à la ligne

Code :

distance=(A[i].x_now-A[l].x_now)*(A[i].x_now-A[l].x_now)+(A[i].y_now-A[l].y_now)*(A[i].y_now-A[l].y_now)+(A[i].z_now-A[l].z_now)*(A[i].z_now-A[l].z_now)+1;

Ce n'est pas souhaitable. Imagine que le premier processus calcule distance mais le temps qu'il arrive par exemple à

Code :

truc3=truc3+(G*A[i].masse*(A[i].z_now-A[l].z_now))/((distance)*sqrt(distance));

le deuxième processus a peut-être eu le temps de modifier lui aussi distance et là... c'est le drame. Tous tes calculs sont faux.

Prend vraiment le temps de lire un cours, au moins jusqu'au principe de la réduction.

Petite remarque au passage : si tu veux de la performance, il faut paralléliser la boucle la plus externe dans la mesure où c'est possible. Cela demande parfois de modifier l'ordre des boucles ou ce qui y est fait dedans.

[bretus]

Bonsoir,

Envoyé par rAyyy

Cad perte de fps et on voit que ça fait des choses bizarre(qu'il doit y avoir des calculs qui sautent ou des erreurs; je ne sais pas)

Tu as la distance qui est partagée par les différents thread dans ta boucle... Essaye voir ça stp (sans garantie) :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
void incrementation(Planete* A, int nmb)
{	
	for( int l=0; l < nmb; l++ )
	{
		float truc1=0.0f;
		float truc2=0.0f;
		float truc3=0.0f;
 
		float Alx_now = A[l].x_now ;
		float Aly_now = A[l].y_now ;
		float Alz_now = A[l].z_now ;
 
		#pragma omp parallel for reduction(+:truc1,truc2,truc3)
		for( int i=0; i < nmb; i++ )
		{
			if( i != l )
			{
				float dx = A[i].x_now - Alx_now ;	
				float dy = A[i].y_now - Aly_now ;
				float dz = A[i].z_now - Alz_now ;
				float m  = A[i].masse ; 
 
				float distance = dx*dx + dy*dy + dz*dz + 1.0f ;
 
				float factor = 1.0f / ((distance)*sqrt(distance)) ; 
 
				truc1 += ( G * m * dx ) * factor ;
				truc2 += ( G * m * dy ) * factor ;
				truc3 += ( G * m * dz ) * factor ;
			}
		}
		A[l].x_after= truc1*PAS*PAS - A[l].x_past + 2*A[l].x_now;
		A[l].y_after= truc2*PAS*PAS - A[l].y_past + 2*A[l].y_now;
		A[l].z_after= truc3*PAS*PAS - A[l].z_past + 2*A[l].z_now;
	}
}

[rAyyy]

Quand tu parallélises, chaque processus possède une mémoire qui lui est propre. Un autre processus ne peut ni lire ni écrire dans cette mémoire. Les variables stockées dans cette mémoire sont dites privées. Par ailleurs, tous les processus partagent une autre quantité de mémoire dans laquelle chacun peut y lire et y écrire. Les variables stockées dans cette mémoire sont dites partagées. Quand on utilise une directive OpenMP, on spécifie si les variables sont privées ou partagées, ce que tu ne fais pas.

Par défaut, une variable est souvent partagée mais ce n'est pas toujours le cas. On va considérer ta variable distance pour illustrer. Comme tu n'as rien précisé, elle est partagée. Ce qui veut dire que chaque processus met à jour sa valeur à la ligne

J'avais compris ça du cour que tu m'avais passer mais comme tu le dit je me suis pas assez penché dessus. Je n'ai pas pris assez de recule sur ce que j'ai fait par rapport à ce cours. Je vais regardé tout ce que vous m’avais passer comme lien quand j'aurai un peu plus de temps.

à bretus

Essaye voir ça stp (sans garantie)

tu m'a mâché le travaille que Aleph69 voulais que je fasse ^^
J'ai essayé et ça marche. Ça reste stable. L'histoire des fps c'est que enfaite pour 10 "planètes" je passe de 1800 fps (sans openMP) à 1400 fps (avec openMP). Mais pour 500 planètes je passe de 40 fps (sans openMP) à 60fps (avec openMP).
Donc j'imagine que la boucle doit être suffisamment importante pour que ça vaut le coup.

Petite remarque au passage : si tu veux de la performance, il faut paralléliser la boucle la plus externe dans la mesure où c'est possible. Cela demande parfois de modifier l'ordre des boucles ou ce qui y est fait dedans.

Je vais essayer de faire ça alors. Ça me permettra de m'entrainer. J'imagine que c'est un peu plus compliquer étant donnée qu'il y a plus de variable et surtout qu'il y a une autre boucle.
(Ne m'aider pas , enfin pour l'instant )

En tout cas merci beaucoup pour vos réponses.

[Aleph69]

Quand tu regarderas d'un peu plus près ta documentation, profites-en pour bien regarder la notion de barrière et la clause nowait, cela t'aidera à gagner en performances si besoin.

Surtout ne parallélise pas les deux boucles : c'est soit l'une soit l'autre.
Conserve bien les deux versions pour comparer.
Pense aussi que tu es en fait en train de manipuler une matrice de distances.
Je pense que ce serait une bonne chose que tu fasses sauter ton instruction conditionnelle, soit en faisant un peu plus de calculs, soit en procédant à une fission de ta boucle interne en deux boucles.

Au fait, tu as combien de coeurs? Tu peux faire de l'hyperthreading?

[bretus]

Heureux que tu sois ravy!

Envoyé par rAyyy

tu m'a mâché le travaille que Aleph69 voulais que je fasse ^^

Ma bonté me perdra.

Envoyé par rAyyy

J'ai essayé et ça marche. Ça reste stable. L'histoire des fps c'est que enfaite pour 10 "planètes" je passe de 1800 fps (sans openMP) à 1400 fps (avec openMP). Mais pour 500 planètes je passe de 40 fps (sans openMP) à 60fps (avec openMP).
Donc j'imagine que la boucle doit être suffisamment importante pour que ça vaut le coup.

Démarrer des threads coûte moins cher que de démarrer un processus, mais ça à quand un coût.

Avec 10 planètes, tes traitements ne sont pas assez long pour que ça vaille le coup.

Je vais essayer de faire ça alors. Ça me permettra de m'entrainer. J'imagine que c'est un peu plus compliquer étant donnée qu'il y a plus de variable et surtout qu'il y a une autre boucle.

Je ne m'y suis pas risqué pour ne pas réfléchir (A[i] peut correspondre à un A[l] en cours de modification, mais après relecture, c'est x_after, y_after et z_after qui sont modifiés)

[rAyyy]

J'ai un Intel i5 3570K 4coeur à 3.4GHz.
De ce que je voit la
http://ark.intel.com/products/65520/...up-to-3_80-GHz
mon proc n'est pas capable de faire de l'hyperthreading.

Mais il a une puce graphique(et j'ai une carte graphique). Du coup au début je pensai utiliser OpenCL mais je me suis dit que ça serai plus simple pour commencer avec OpenMP.

[Aleph69]

Avec 4 coeurs tu devrais voir quelque chose c'est bon.
Tu as raison de laisser OpenCL de côté pour le moment, c'est mieux.
Le GPGPU est très à la mode mais c'est dû à un marketing agressif de Nvidia qui n'est pas très honnête sur ses benchmarks...
Tu pourras tester avec par la suite mais ne t'attends pas à un speed-up de 400 même si on te promet le contraire sur le papier!