problème performances multithread vs monothread

**lyxthe** · 28/09/2010, 10h53

Bonjour à tous, je reviens encore avec un problème de performance d'un programme que je développe en multithread à l'aide de la librairie boost_thread.

Dans ce programme je lance un thread_group de cette façon là :

Code :

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

1
2
3
4
	for(i=0;i<nbr_proc;i++){
		group.create_thread(boost::bind(fonc_matr,i)); 
	}
	group.join_all();

avec la fonction fonc_matr qui est égale à ça :

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
33
34
void fonc_matr(int num){
	long lig,col,siz,siz_2,deb,fin;
	siz=lis.size();
	siz_2=siz-(siz%nbr_proc);
	deb=(siz_2/nbr_proc)*num;
	if(num+1!=nbr_proc){
		fin=(siz_2/nbr_proc)*(num+1);
	}else{
		fin=siz;
	}
	minm3[num]=inf;
	for(lig=deb;lig<fin;lig++){
		for(col=0;col<siz;col++){
			if(arc(lis[lig],lis[col])){
				Matr[lig][col]=lis[col].cout;
				Matr2[lig][col]=lis[col].cout;
				if((minm3[num]==inf)||(minm3[num]>lis[col].cout)){
					minm3[num]=lis[col].cout;
				}
			}else{
				Matr[lig][col]=inf;
				Matr2[lig][col]=inf;
			}
		}
		if(fin-deb<100){
				cerr <<"calcul matrice " << nummatr << ", thread "<< num+1 << "/" << nbr_proc << " : " << ((lig-deb)*100)/(fin-deb)<<"%" << endl;
		}else{
			if(lig%((int)(fin/100))==0){
				cerr <<"calcul matrice " << nummatr << ", thread "<< num+1 << "/" << nbr_proc << " : " << ((lig-deb)*100)/(fin-deb)<<"%" << endl;
			}
		}
	}
	cerr <<"calcul matrice, thread "<< num+1 << "/" << nbr_proc << " : terminé " <<endl;
}

La donnée nbr_proc est une variable globale que je change selon mes tests. Si elle est de un, un seul thread est créé, sinon plusieurs.

Mon problème est qu'en multithread, j'ai l'impression que les performances que j'obtiens ne sont pas celles auxquelles je pourrais m'attendre.

Pour vous donner une idée j'obtiens ceci dans le visionneur de ressource en mono thread, ce qui me parait correcte :

et voici ce que j'obtiens en multi :

Dans ces graphiques, le carré en haut à gauche signal la charge CPU user des 4 procs, en haut à droite, la charge CPU system, en bas à gauche, la charge CPU inactive.

Ma question est la suivante, est-ce que ça vous parait logique qu'en multi les procs ne soient pas à 100% de charge comme le proc unique qui tourne en monothread?

Au vu de ces informations et du code, pensez vous que je me sois planté quelque part dans la programmation ?

Merci pour ceux qui auront le courage d'avoir lu jusque là, en attendant vos réponses avisées.

**NoIdea** · 28/09/2010, 21h22

Ma réponse est juste une idée. Je vois que tu utilises beaucoup de cout (je suppose que matrice.cout est un cout). Il se peut que les entrées/sorties bloquent le programme (mutex au niveau des fichiers ?, vitesse des bus), ...
Enlève-les et refaits tes test. Si tu as le même résultats, cherche une fonction qui nécessiterais des mutex/semaphores/bus, ...
Bonne chance.

**lyxthe** · 29/09/2010, 03h01

Tout l'intérêt de la parallélisation dans mon cas est justement de ne pas faire de synchronisation entre mes thread, tout est fait pour qu'ils ne lisent pas un emplacement qu'un autre est en train de modifier. Du coup je n'utilise pas de mutex.

Je rajouterai qu'après différent tests, le programme se comporte de la même façon avec pthread qu'avec boost_thread.

Est-il possible que la compilation de mon code donne un programme qui demande aux systèmes des synchronisations régulièrement sans que je l'ai demandé.

J'utilise de nombreuses variable globales, dont l'accès, normalement, n'est pas synchronisé, mais je ne comprend pas pourquoi ma charge CPU système est aussi importante, alors que ma charge CPU user l'est si peu.

De plus le programme tourne beaucoup plus vite en monothread, le comble. J'exécute mes tests ainsi : time ./a.out
le retour de cette commande dans le bash me donne un temps reel, un temps user et un temps système, en mono le temps système est nul alors qu'en multi il est énorme.

Bref je ne comprend pas pourquoi mon programme n'est pas plus rapide en multithread qu'en monothread, et pourquoi diable il donne ces charges CPU.

Help

PS : autant les mutex je vois à peu près ce que c'est, les sémaphore j'en ai une idée très vague, mais les bus, tu es le premier qui m'en parle. Peux-tu m'en dire plus, ou me dire où je peux trouver des infos ?

**Jean-Marc.Bourguet** · 29/09/2010, 09h22

J'ai pas le temps de regarder en detail, mais j'ai quand meme vu qqch. Je ne suis pas sur que ca explique tout ce que tu experimentes. A la place d'utiliser partout minm3[num], utilise une variable locale et assigne dans le tableau juste avant de sortir du thread. Pour plus de details pourquoi, cherche "false sharing".

**lyxthe** · 29/09/2010, 10h50

Merci, apparemment effectivement, avec le peu que j'ai regardé, ça a l'air d'être une bonne piste. Je vais creuser et je reviens vous dire ce qu'il en est

**Astraya** · 29/09/2010, 11h11

Pour allez plus loin, utiliser std::for_each + foncteur pour éviter l'incrémentation de long à chaque boucle.
Ou si tu veux garder les boucles for, utilise ++lig et ++col, tu économise aussi une copie en mémoire du à la post-incrémentation.

**lyxthe** · 29/09/2010, 15h43

J'ai regardé plus en détail ce problème de false sharing, et je suis d'accord que ça pourrait assez bien expliquer les symptômes que je rencontre. Ceci étant dit les quelques modifications que j'ai apporté à mon programme pour remédier au problème n'ont pas l'air de fonctionner (notamment ajouter des buffers dans les structures des tableaux modifiés par les threads).

Du coup je voulais savoir s'il existe un moyen pour être sûr que du false sharing est effectivement commis (en utilisant un outil avec lequel on peut voir les plages mémoires peut être?) si quelqu'un connait plus en détail ce problème, je suis preneur.

Merci

**seeme** · 29/09/2010, 16h00

Je suis tombé ce matin sur ce topic et j'ai regardé un peu le false sharing, par curiosité.

Apparemment, si tu utilises gcc (probable au vu de tes screenshots) avec -O3, les problèmes de false sharing sont gérés par gcc:

http://www.codeguru.com/cpp/misc/mis...cle.php/c17621 à la rubrique "Other thoughts..".

Ca permettra peut-être de voir si le false sharing a un impact sur ton programme (ça ne règle pas le problème, mais ça pourrais orienter tes recherches...)

**zul** · 29/09/2010, 20h41

Sur quelle taille de matrix travailles-tu ? Quelle est le coût de la fonction arc ?
Est ce que le problème ne viendrait pas uniquement du fait que le coût construction / destruction d'un thread est supérieur ou pas de beaucoup inférieur au coût du code que tu execute ?

**lyxthe** · 30/09/2010, 14h05

Les tableaux Matr et Matr2 sont des tableaux de 16000*16000, ou 400000*400000 de short, selon les instances. arc() renvoie un boolean en temps constant :

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
bool arc(vert v1, vert v2){//renvoit vrai si les 11 derniers bits de v1_bin sont égaux aux 11 premiers bits de v2_bin, v1_bin et v2_bin sont des mots de 15 bits, v1.elem et v2.elem sont des long dont la valeur ne dépasse pas 2^15
	bool arctmp=true;
	int i=0;
	std::bitset<nbr>v1_bin(v1.elem);
	std::ostringstream oss;
	oss << v1_bin;
	std::string v1_bin_str = oss.str();
	std::bitset<nbr>v2_bin(v2.elem);
	std::ostringstream oss2;
	oss2 << v2_bin;
	std::string v2_bin_str = oss2.str();
	for(i=3;i<15;i++){
		if(v1_bin_str[i]!=v2_bin_str[i-3]){
			arctmp=false;
		}
	}
	return arctmp;
}

Pour la construction du thread, je pense que dans mon cas c'est tout de même justifié, normalement je pense que si tout se passait bien je devrait gagner beaucoup plus.

Je continue à croire que le problème pourrait effectivement venir de false sharing, mais j'ai toujours pas eu le temps de m'en occuper plus avant, je vous tiens au courent.

**Jean-Marc.Bourguet** · 30/09/2010, 14h26

Envoyé par lyxthe

Les tableaux Matr et Matr2 sont des tableaux de 16000*16000, ou 400000*400000 de short, selon les instances. arc() renvoie un boolean en temps constant :

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
bool arc(vert v1, vert v2){//renvoit vrai si les 11 derniers bits de v1_bin sont égaux aux 11 premiers bits de v2_bin, v1_bin et v2_bin sont des mots de 15 bits, v1.elem et v2.elem sont des long dont la valeur ne dépasse pas 2^15
	bool arctmp=true;
	int i=0;
	std::bitset<nbr>v1_bin(v1.elem);
	std::ostringstream oss;
	oss << v1_bin;
	std::string v1_bin_str = oss.str();
	std::bitset<nbr>v2_bin(v2.elem);
	std::ostringstream oss2;
	oss2 << v2_bin;
	std::string v2_bin_str = oss2.str();
	for(i=3;i<15;i++){
		if(v1_bin_str[i]!=v2_bin_str[i-3]){
			arctmp=false;
		}
	}
	return arctmp;
}

Pour la construction du thread, je pense que dans mon cas c'est tout de même justifié, normalement je pense que si tout se passait bien je devrait gagner beaucoup plus.

Je continue à croire que le problème pourrait effectivement venir de false sharing, mais j'ai toujours pas eu le temps de m'en occuper plus avant, je vous tiens au courent.

Tu es sensible au temps d'execution et tu construits deux ostringstream a l'interieur d'une boucle pour t'amuser a comparer des chars par apres? Il y a comme qui dirait un petit probleme.

Code :

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

1
2
3
4
5
6
7
 
uint_16 const mask11 = (1 << 11) - 1;
bool arc(vert v1, vert v2){
	uint_16 const v1_bin = v1.elem;
        uint_16 const v2_bin = v2.elem;
        return (v1_bin & mask11) == ((v2_bin >> 3) & mask11);
}

devrait faire ce que tu veux. Il faudrait aussi envisager de passer v1 et v2 par reference.

Edit: En passant, on a trouve la cause de tes problemes: les stringstream ou les strings que tu manipules aussi legerement allouent vraisemblablement de la memoire dynamiquement. Il est propable que tu n'utilises pas tes proc a 100% parce qu'ils sont en attente d'un mutex dans l'allocateur.

**lyxthe** · 30/09/2010, 17h08

Cool, je savais pas que les stringstream ou les string allaient faire appel à un mutex. j'ai pourtant bataillé pour vérifier s'il n'y en avait pas des cachés, mais comme je m'y connais pas assez j'avais pas vu. Pour les stringstream je connaissais pas plus que ça, j'avais juste besoin de comparer des longs bit à bit sur 15 bits uniquement, et c'est ce que j'ai trouvé dans la faq c++ du site. J'avoue ne pas m'être posé trop de questions

Par contre mes v1.elem sont des long pas des char, ça va fonctionner quand même ? Bon je vérifie tout ça.

Bref Merci pour tout, je modifie tout ça, fais quelques tests et reviens vous dire si ça marche mieux.

En tout cas encore une fois merci pour votre réaction rapide et adaptée.

**Astraya** · 30/09/2010, 17h13

Cool, je savais pas que les stringstream ou les string allaient faire appel à un mutex.

Euh... les classes de la stl comme string et stringstream ne sont pas thread safe! donc pas de mutex.

**lyxthe** · 30/09/2010, 17h26

ben

Il est propable que tu n'utilises pas tes proc a 100% parce qu'ils sont en attente d'un mutex dans l'allocateur.

ou alors j'ai pas tout compris......j'avoue qu'on rentre dans des discutions qui sont compliquées pour moi.

**lyxthe** · 30/09/2010, 17h40

J'ai un petit problème de compilation avec ton bout de code (que je ne comprend pas trop), y a-t-il une librairie particulière à inclure ?

Code :

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

1
2
3
4
5
6
uint_16 const mask11 = (1 << 11) - 1;
bool arc(vert v1, vert v2){
	uint_16 const v1_bin = v1.elem;
        uint_16 const v2_bin = v2.elem;
        return (v1_bin & mask11) == ((v2_bin >> 3) & mask11);
}

voici les différentes erreurs :

Code :

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

1
2
3
4
5
6
7
expected constructor, destructor, or type conversion before 'const'
'uint_16' was not declared in this scope
expected ';' before 'const'
expected ';' before 'const'
'v1_bin' was not declared in this scope
'mask11' was not declared in this scope
'v2_bin' was not declared in this scope

J'aurais bien besoin d'un peu d'aire .......encore

Juste au cas où, je ne suis pas certain de m'être bien expliqué sur ce à quoi servait ce bout de code. v1.elem et v2.elem sont des long dont la valeur est comprise entre 0 et 2^15 -1 mon but est de vérifier si les 11 premiers bits de v1.elem sont les mêmes que les 11 derniers bits de v2.elem, de renvoyer vrai si c'est le cas, faux sinon.

**Jean-Marc.Bourguet** · 30/09/2010, 17h49

Tu peux remplacer uint_16 par unsigned short.

**lyxthe** · 01/10/2010, 13h47

Effectivement, ce petit bout de code change tout, je suis passé d'une exécution de 25minutes à quelques secondes juste en changeant cette fonction.

Merci beaucoup.

Je ne sais pas reconnaitre ce genre de problèmes, du coup au cas où il m'en reste, si quelqu'un peut me dire si ce petit bout de code ci peut être optimisé :

Code :

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

1
2
3
4
5
6
7
8
9
if(nbr_proc>1){
	for(i=1;i<nbr_proc;i++){
		groupee.create_thread(boost::bind(fonc_multi,i));
	}
}
fonc_multi(0);
if(nbr_proc>1){
	groupee.join_all();
}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
void fonc_multi(int num){
	//long num = (long) p_data;
	long lig,col,siz,siz_2,deb,fin,j;
	siz=lis.size();
	siz_2=siz-(siz%nbr_proc);
	deb=(siz_2/nbr_proc)*num;
	if(num+1!=nbr_proc){
		fin=(siz_2/nbr_proc)*(num+1);
	}else{
		fin=siz;
	}
	minr[num]=inf;
	mind[num].minimum=inf;
	mind[num].somm=inf;
	mind[num].nummatri=nummatr;
	for(lig=deb;lig<fin;lig++){
		for(col=0;col<siz;col++){
			minm3[num]=inf;
			for(j=0;j<siz;j++){
				if((Matr[lig][j]!=inf)&&(Matr2[j][col]!=inf)){
					if((minm3[num]==inf)||(minm3[num]>Matr[lig][j]+Matr2[j][col])){
						minm3[num]=Matr[lig][j]+Matr2[j][col];
					}
				}
			}
			Matr3[lig][col]=minm3[num];
			if((minr[num]==inf)||((minr[num]>minm3[num])&&(minm3[num]!=inf))){
				minr[num]=minm3[num];
			}
			if((lig==col)&&(minm3[num]!=inf)&&((mind[num].minimum==inf)||(mind[num].minimum>minm3[num]))){
 
				mind[num].minimum=minm3[num];
				mind[num].somm=lis[lig].elem;
				mind[num].nummatri=nummatr;
			}
		}
		if(fin-deb<100){
				cerr <<"calcul matrice " << nummatr << ", thread "<< num+1 << "/" << nbr_proc << " : " << ((lig-deb)*100)/(fin-deb)<<"%" << endl;
		}else{
			if(lig%((int)(fin/100))==0){
				cerr <<"calcul matrice " << nummatr << ", thread "<< num+1 << "/" << nbr_proc << " : " << ((lig-deb)*100)/(fin-deb)<<"%" << endl;
			}
		}
	}
}

Mais bon honnetement la dernière aide était vraiment très efficace, donc ça m'a déjà énormément aidé.

Merci à tous

problème performances multithread vs monothread

C++

Discussions similaires

Partager

Partager