Discussion :

[remya]

Bonjour,

ci dessous un code très bête qui consiste à appeler 10000000 fois la fonction rand() dans 1 thread (pas de seed, le code est stupide mais c'est pour illustrer...)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* to compile: gcc -Wall -fopenmp -o dummy dummy.c */
 
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
 
int main()
{
	int numTH = 1;
	int k,l;
 
	/* Begin parallel region */
	#pragma omp parallel private(k,l) num_threads(numTH)	
	{
		for(k=0;k<10000000;k++) l=rand();
 
	}
 
	return EXIT_SUCCESS;
}

je lance ce code depuis mon shell, avec la fonction time (qui permet de mesurer le temps d'exécution):

time ./dummy

real 0m0.099s
user 0m0.096s
sys 0m0.000s

Faisons la même chose avec 2 threads (dans chaque thread on appelle 10000000 la fonction rand())

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* to compile: gcc -Wall -fopenmp -o dummy dummy.c */
 
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
 
int main()
{
	int numTH = 2;
	int k,l;
 
	/* Begin parallel region */
	#pragma omp parallel private(k,l) num_threads(numTH)	
	{
		for(k=0;k<10000000;k++) l=rand();
 
	}
 
	return EXIT_SUCCESS;
}

je lance ce code depuis mon shell, avec la fonction time:

time ./dummy

real 0m4.753s
user 0m4.080s
sys 0m5.392s

Comme indiqué dans l'en-tête de mes codes, dans les deux cas le code est compilé avec la commande:

gcc -Wall -fopenmp -o dummy dummy.c

Quelqu'un saurait expliquer cette explosion du temps de calcul?
Et surtout comment résoudre ce problème??

Merci d'avance pour vos réponses.
RémyA

[remya]

J'ai l'explication et un début de solution:

La fonction rand() est dite "non-thread-safe", elle définie visiblement une région "atomic" qui protège ses variables "static" des accès simultanés. Ainsi utiliser rand() dans une région parallèle ralenti considérablement le programme.

Une solution (mais elle n'est pas très efficace d'après mes tests) est d'utiliser rand_r() à la place de rand(). rand_r est "thread-safe" elle peut donc être utilisée dans des régions parallèles. Elle prend en argument un pointeur vers une variable d'initialisation. Pour l'utiliser correctement chaque thread doit avoir sa propre variable d'initialisation, et à chaque exécution du programme les variables d'initialisations doivent être différentes (sans quoi on génère toujours les mêmes nombres).

Ainsi je propose le code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
/* to compile: gcc -fopenmp -o dummy2 dummy2.c */
 
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
 
int main()
{
	int numTH = 2;
 
	int k,l,m;
	unsigned int *seed;
 
	/* rand() seed */
	srand((long int) time(NULL));
 
	/* r_rand seed table */
	seed = (unsigned int*)malloc(numTH*sizeof(unsigned int));
	for(k=0;k<numTH;k++) seed[k] = rand();
 
	/* Begin parallel region */
	#pragma omp parallel for private(k,l,m) shared(seed,numTH) num_threads(numTH)	
	for(k=0;k<numTH;k++)
	{
		for(l=0;l<10000000;l++) m =rand_r(&seed[k]); 
	}
 
	/* free memory */
	free(seed);
 
	return EXIT_SUCCESS;
}

Ce code est bien plus satisfaisant en termes de temps d'exécution, voici quelques mesures sur un serveur à 48 processeurs (tous les processeurs étaient disponibles à 100% pendant mes tests):

1 thread >> ~ 140ms
2 threads >> ~ 440ms
5 threads >> ~ 1s
10 threads >> ~ 1.4s
15 threads >> ~ 2.8s
20 threads >> ~ 4s

Bref, c'est moins catastrophique en termes de temps d'exécution, mais ce n'est toujours pas satisfaisant , ça ne devrait pas augmenter comme cela. Certes il faut un peu de temps pour la gestion du fork & join, mais pas autant, ça se vérifie facilement sur des codes simples. De plus le temps perdu à gérer les threads est sensé être kiff-kiff pour 2 threads ou N threads tant que N est inférieur ou égal au nombre de processeurs disponibles.

Quelqu'un a une idée?

[spica314]

Bonjour,

C'est normal vous ne parallelisez pas la boucle en L donc sur 1 procs on a 10M d'appels et sur 2 procs on a 20M d'appels donc au moins deux fois plus de temps.

Ensuite difficile de diviser par x un code qui met 140ms sur 1 procs.

[Ehonn]

Compile avec l'option -O3 (pour activer la plupart des optimisations), tu ne devrais plus avoir de telles différences (mais pas de gain non plus).