Exécution ralentie en multithread

**simong** · 04/05/2010, 17h45

Bonjour à tous,
je compile et j'exécute un proto de code C++ multithreadé (je m'appuie sur boost::thread). Mon problème est qu'alors que je m'attendais au global à une réduction du temps de d'exécution de mon programme, celui-ci autmente avec le nombre de threads que je crée ! (4 threads sur un quadricore). Quelqu'un a t-il un avis ? Merci

**3DArchi** · 05/05/2010, 07h23

Salut,
Tu accèdes à une ressource système ou partagée qui nécessite synchronisation (allocation dynamique ?) ?

**simong** · 05/05/2010, 09h37

Salut,
Non pas l'impression et pas de ressource partagée en tout cas :
l'idée est à la base, simplement de balancer en parallèle un traitement (boucle) qui s'exécute en local, sur les processeurs. Mon algo est un random simulator, je souhaite réaliser N simuls, faire à terme en sorte que mon traitement soit réparti sur les n proc. De la machine. Il y aurait ruse particulière? Merci à toi.

**3DArchi** · 05/05/2010, 13h23

C'est possible de voir le code parallélisé ?
Tu peux aussi avoir des impacts de perfs selon la façon dont tu accèdes aux données (pb de cache)

**Joel F** · 06/05/2010, 01h00

t'utilise quoi comme pRNG ? rand() ? si oui rand contient des données statiques en interne qui emepche son usage propre en MT. y a rand_r sinon.

**simong** · 06/05/2010, 18h11

Salut,
On peut effectivement constater des impacts « à la marge) en fonction de comment on adresse les données, j'ai vu ça.
Je n’utilise pas le Rand native de C++, mais boost
La classe que je teste en gros:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Threaded_Sim_Class
{
	private : 
	Rand_Gen	gen;
	size_t nbSimulations;
	bool isMT;
	struct MT_Data
	{
		Rand_Gen gen;
		size_t nbSimulations;
		Result result;
					};
	vector<boost::shared_ptr<MT_Data>> threadData;
	size_t nbThreads;
public :
	Threaded_Sim_Class(size_t _nbSimulations) //monothreading
		:isMT(false),nbSimulations(_nbSimulations),gen()
	{	}
	Threaded_Sim_Class(size_t _nbSimulations,size_t _nbThreads) //multithread si _nbThreads>1
	:nbThreads(_nbThreads),threadData(_nbThreads),nbSimulations(_nbSimulations),gen()
	{
		isMT=(nbThreads>1) ? true : false;
	}
	~Threaded_Sim_Class()
	{}
 
	double Pythagor(double _u)
	{
		return...;
	}
 
	Result getResult()
	{
		Result res;
		if(!isMT)
		{
			for(size_t i=0; i<nbSimulations; ++i)
			{
				double tmp=Pythagor(gen.Next());
				res.mean+=tmp;
				res.var+=tmp*tmp;
			}
			res.mean/=nbSimulations;	res.var=res.var/nbSimulations-(res.mean*res.mean); 
		}
		else
		{
			for(size_t i=0; i<nbThreads; ++i)
			{
				threadData[i]=boost::shared_ptr<MT_Data>(new MT_Data);
				threadData[i]->nbSimulations=nbSimulations/nbThreads;
				threadData[i]->gen.skip(2*i* (nbSimulations/nbThreads));
			}
			boost::thread_group tg;
			for(size_t i=0;i<nbThreads;++i)
			{
	tg.create_thread(boost::bind(&Threaded_Sim_Class::getResult,this,i));
			}
			tg.join_all();
			for(size_t i=0;i<nbThreads;++i)
			{
				res.mean += threadData[i]->result.mean;
				//res.var +=threadData[i]->result.var;
			}
			res.mean/=nbThreads;
		}
		return res;
	}
 
	void getResult(size_t _iThread)
	{
		boost::shared_ptr<MT_Data> td=threadData[_iThread]; //tempo
		for(size_t i=0; i<td->nbSimulations; ++i)
		{
			double tmp=Pythagor(td->gen.Next(),td->gen.Next());
			td->result.mean += tmp;
			td->result.var +=tmp*tmp;
		}
		td->result.mean/=td->nbSimulations;
		td->result.var=td->result.var/nbSimulations-(td->result.mean*td->result.mean); 
	}
	};

J'exécute getResult() dans mon main. Je peux comparer des calculs en monothread et sur plusieurs threads. Mon temps d'exé croît avec le nombre de threads! Je comrpends pas!!!

**3DArchi** · 07/05/2010, 07h03

On va avancer à tâtons....
A quoi ressemble Pythagore ?
Quel est le volume de donnée (combien de boucles ) ? Et quel est le temps en mono thread vs multi thread.
Créés 1 thread de plus que le nb de core (5) et regarde si ça impacte.

**simong** · 07/05/2010, 10h59

Salut, sans problème:
Pythagor : mesure un écart quadratique dans l'idée: return (u*u-M*M), où u tirée aléatoirement avant, est passé à la fonction. Rien comme traitement supplémentaire à l’intérieur.
Volume de données: 10000000 de tirages
Mon impact 9.75s en mono (et 9.5 quand je construis un objet paramétré de façon explicite avec n=1 thread, pour comparer), puis 10.1s sur les 4, 14.7.7 sur 5, 18.7s sur 6, 22.9 sur 7, 26.6s sur 8…
Alors, à la base pas une différence folle entre mono et 4threads mais c’est déjà clairement pas le résultat auquel je me serais attendu. Et puis après, c’est carrément la misère (sans compter que ça a pas l'air très linéaire en impact, tout ça)!

**3DArchi** · 07/05/2010, 23h09

Il n'y aurait pas un mutex sur ton générateur aléatoire ?
Une telle perte de perf me fait quand même penser que les threads se synchronisent ou s'excluent mutuellement régulièrement. Bref, il y a de l'attente quelque part.
Identifie tous tes appels systèmes (y compris allocation, vecteur, liste, flux, trace, etc.) et tous tes appels à des fonctions de bibliothèques tierces.

**simong** · 08/05/2010, 14h18

Salut,
Non aucun mutex nulle part pour l'instant. D'ailleurs il faudra p't^t que je regarde où en mettre c'est vrai... Ma classe de génération aléatoire implémente boost::random, et dans mon main je fais que construire un objet de type Threaded_Sim_Class sur lequel j'appelle la méthode getResult! Je fais aucune autre allocation ou ne traite aucun autre vecteur que ceux que tu vois...
=> "Identifie tous tes appels systèmes (y compris allocation, vecteur, liste, flux, trace, etc.) et tous tes appels à des fonctions de bibliothèques tierces.": Ce serait quoi les précautions à prendre avec ces appels système ?

=> quand tu parles des threads "qui se synchronisent ou s'excluent mutuellement régulièrement", ce serait à rechercher où où dans mon programme???? A+ et merci

**3DArchi** · 08/05/2010, 22h57

Salut,
Prenons le problème autrement : instrumente chacun de tes threads de façon de plus en plus fine pour voir où le temps est consommé (boost.timer peut t'aider je pense pour mesurer le temps écoulé). Une fois que tu as identifié ce qui prend du temps, tu auras probablement la réponse à ton problème

**JeitEmgie** · 09/05/2010, 14h02

Envoyé par 3DArchi

Salut,
Prenons le problème autrement : instrumente chacun de tes threads de façon de plus en plus fine pour voir où le temps est consommé (boost.timer peut t'aider je pense pour mesurer le temps écoulé). Une fois que tu as identifié ce qui prend du temps, tu auras probablement la réponse à ton problème

la lecture du code source permet quand même de déduire quelques petits choses :

a. si c'est un problème de lock caché ce ne peut être que dans

Code :

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

1
2
 
tg.create_thread(boost::bind(&Threaded_Sim_Class::getResult,this,i));

boost::bind ne devant pas jouer directement avec des mutex, create_thread est le suspect, mais ce serait quand même surprenant… à moins qu'il ne crée un mutex sur l'objet passé en paramètre et que l'expansion de boost::bind provoque une situation où l'objet serait toujours le même… mais on rentre dans des hypothèses du genre "bizarre"… éventuellement un effet de bord d'une optimisation du compilateur…
…mais çà reste peu probable… de plus le comportement de l'augmentation du temps de calcul serait plus linéaire…
(encore que pour être certain de cela… il faudrait savoir exactement ce que vous avez mesuré et comment …)

b. si ce n'est pas un problème de mutex lié au threading, alors le suspect principal est :

Code :

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

1
2
 
threadData[i]->gen.skip(2*i* (nbSimulations/nbThreads));

que fait skip() et comment le fait-il ?

PS
petit détail : si le nombre de simulations n'est pas un multiple du nombre de threads le code n'exécutera pas le nombre de simulations espérés… (vous perdez nSimulations modulo nThreads)

NB
si skip() fait "while (toBeSkipped--) next();" alors c'est bien lui le coupable :

avec skip "enabled"

Code :

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

1
2
3
4
5
6
 
benchSimulator  1 threads:  168595199 ns
benchSimulator  2 threads:  529154506 ns
benchSimulator  4 threads:  547437236 ns
benchSimulator 10 threads: 1308146160 ns
benchSimulator 20 threads: 2578868055 ns

avec skip "disabled"

Code :

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

1
2
3
4
5
6
 
benchSimulator  1 threads: 171873820 ns
benchSimulator  2 threads: 466571113 ns
benchSimulator  4 threads: 242895564 ns
benchSimulator 10 threads: 151853600 ns
benchSimulator 20 threads: 146165826 ns

**3DArchi** · 09/05/2010, 19h02

Salut,
@JeitEmgie : le cout de création de thread existe, mais pas au point de passer de 10s à 14s avec 5 threads (ou alors boost.thread est à jeter, ce que je ne crois pas).
Pour gen.skip, il n'est pas présenté. J'ai pensé qu'il s'agissait simplement d'une segmentation de son espace de valeurs selon le nombre de threads. Mais, je n'avais pas pensé que cette fonction pouvait être 'lourde'. C'est vrai que le sur-coût n'est peut être pas dans les fonctions exécutées dans le thread mais dans le travail de préparation avant. En tout cas, je pense qu'instrumenter un peu pour voir où se consomme le temps est peut être une façon rapide d'identifier le ou les lignes problématiques.

**JeitEmgie** · 09/05/2010, 19h34

Envoyé par 3DArchi

Salut,
@JeitEmgie : le cout de création de thread existe, mais pas au point de passer de 10s à 14s avec 5 threads (ou alors boost.thread est à jeter, ce que je ne crois pas).
Pour gen.skip, il n'est pas présenté. J'ai pensé qu'il s'agissait simplement d'une segmentation de son espace de valeurs selon le nombre de threads. Mais, je n'avais pas pensé que cette fonction pouvait être 'lourde'. C'est vrai que le sur-coût n'est peut être pas dans les fonctions exécutées dans le thread mais dans le travail de préparation avant. En tout cas, je pense qu'instrumenter un peu pour voir où se consomme le temps est peut être une façon rapide d'identifier le ou les lignes problématiques.

c'est bien pour cette raison que je parie plus sur le skip()...
les générateurs de nombre aléatoires ne sont pas des fonctions auxquelles ils suffit de passer un index N pour avoir le Nième élément...
la génération du Nième dépend en général des N-1 précédents...
donc çà n'aurait rien d'étonnant à ce qu'il fasse une boucle appelant next()... et dans ce cas inutile d'instrumenter... il est évident que le problème vient de là... d'autant plus que pour chaque "gen" il recalcule certainement depuis le début...

si c'est çà, la solution est de générer les nombre aléatoires avant l'étape du splitsing du travail en threads et de les stocker dans un tableau, chaque accédant en lecture au segment qui le concerne (donc pas de mutex nécessaire...)

ou de changer de générateur de nombre aléatoire (les digits de PI par exemple...) …

en utilisant un tableau contenant les nombres pré-calculés :

Code :

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

1
2
3
4
5
6
 
benchSimulator  1 threads:  70493335 ns
benchSimulator  2 threads: 110037032 ns
benchSimulator  4 threads:  76292946 ns
benchSimulator 10 threads:  62239087 ns
benchSimulator 20 threads:  51807857 ns

(PS ns = nanosecondes... autrement dit l'ensemble des benchmarks va plus vite que ce qu'il a mesuré comme son temps le plus rapide... :
real 0m0.730s
user 0m1.927s
sys 0m0.106s

d'où l'interrogation de ce qui a été mesuré et comment... et l'intérêt d'en savoir un peu plus sur le code qui n'a pas été montré...)

**3DArchi** · 09/05/2010, 20h29

Envoyé par JeitEmgie

la solution est de générer les nombre aléatoires avant l'étape du splitsing du travail en threads et de les stocker dans un tableau

C'est déjà ce qu'il fait (au - en partie), non ? skip est appelé avant la génération des thread :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
for(size_t i=0; i<nbThreads; ++i)
{
    threadData[i]=boost::shared_ptr<MT_Data>(new MT_Data);
    threadData[i]->nbSimulations=nbSimulations/nbThreads;
    threadData[i]->gen.skip(2*i* (nbSimulations/nbThreads));  //// 3DArchi : Skip
}
boost::thread_group tg;
for(size_t i=0;i<nbThreads;++i)
{
    tg.create_thread(boost::bind(&Threaded_Sim_Class::getResult,this,i)); //// 3DArchi : création des threads
}
tg.join_all();

En revanche, c'est peut être dans next :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void getResult(size_t _iThread)
{
    boost::shared_ptr<MT_Data> td=threadData[_iThread]; //tempo
    for(size_t i=0; i<td->nbSimulations; ++i)
    {
        double tmp=Pythagor(td->gen.Next(),td->gen.Next()); //// 3DArchi : Next ou Pythagor ?
        td->result.mean += tmp;
        td->result.var +=tmp*tmp;
    }
    td->result.mean/=td->nbSimulations;
    td->result.var=td->result.var/nbSimulations-(td->result.mean*td->result.mean); 
}

Envoyé par JeitEmgie

et dans ce cas inutile d'instrumenter...

Disons, que l'instrumentation permet de voir tout de suite ce qui prend du temps, d'éviter les conjectures et c'est rapide et facile à mettre en oeuvre.

**JeitEmgie** · 09/05/2010, 21h30

Envoyé par 3DArchi

C'est déjà ce qu'il fait (au - en partie), non ? skip est appelé avant la génération des thread

et alors ? cette partie fait partie du benchmark... qui a priori est sur l'ensemble du calcul...

sauf erreur :

si skip fait une boucle sur next, pour 10.000.000 simulations et 10 threads :
pour le gen du thread n°0 : il appelle 0 fois next()
pour le thread n°1 : il appelle 2 * (nSimul / nThread) = 2.000.000 de next()
pour le thread n°2 : il appelle 4 * (nSimul / nThread) = 4.000.000 de next()
etc.
donc (2 + 4 + 6 + … + 18) = 90 millions de next()…
si au moins il utilisait les résultats du précédent, il n'en ferait que 9 * 2M = 18 millions... dans sa phase préparatoire...
+ les 20 millions implicitement faits dans les threads... (c'est quand même faire 2x le même travail...)

en préparant les nombres aléatoires dans un tableau avant on ne fait que 20 M de next() avant et 0 dans les threads...

Envoyé par 3DArchi

Disons, que l'instrumentation permet de voir tout de suite ce qui prend du temps, d'éviter les conjectures et c'est rapide et facile à mettre en oeuvre.

question de goût : priorité au raisonnement...

**simong** · 10/05/2010, 12h29

Salut,
Merci pour vos contributions, je commence à y voir plus clair Les temps d’exécution présentés sont ceux de l’exécution du « main » sur la base des paramètre que j’annonce (10 millions de tirages, nombre de threads flottant). Skip génère à chaque fois la séquence entière de l'index 0 à l'index i*(nbSimulation/nbThreads) puisqu’il est clair en effet que l’accès à la séquence aléatoire ne se fait pas indépendamment de la séquence déjà tirée, au passage il y a une typo dans la recopie sur le forum de mon source, j'appelle bien sûr Skip sur (i+1)*(nbSimulation/nbThreads) et non 2*(nbSimulations/nbThreads)!
J’ai le code suivant pour Skip:
skip(size_t n)
{
for(size_t i=0; i<n; ++i)
uni();
}
Certes, il y aurait matière à dire sur cette procédure question opimalité mais je ne l’incriminais pas forcément car d’une part aucun aspect de franche dépendance linéaire de mon temps de traitement en fonction des nombres de threads (test effectué par ailleurs) ne se dégageaient réellement et d’autre part, je pensais cette brique de génération globalement peu coûteuse en temps de calcul.
L’approche stockage dans un vecteur préalablement à la distribution sur les threads, je ne l’avais pas retenue (et ai d’ailleurs dû adapté mon code) pour une affaire de portabilité: dépassement de mémoire sur une autre machine que je fais tourner.
Les précautions à apporter en termes de synchro (mutex) ici, y’a matière à? Merci bcp, à +

**JeitEmgie** · 10/05/2010, 13h00

Envoyé par simong

Salut,
Merci pour vos contributions, je commence à y voir plus clair Les temps d’exécution présentés sont ceux de l’exécution du « main » sur la base des paramètre que j’annonce (10 millions de tirages, nombre de threads flottant). Skip génère à chaque fois la séquence entière de l'index 0 à l'index i*(nbSimulation/nbThreads) puisqu’il est clair en effet que l’accès à la séquence aléatoire ne se fait pas indépendamment de la séquence déjà tirée, au passage il y a une typo dans la recopie sur le forum de mon source, j'appelle bien sûr Skip sur (i+1)*(nbSimulation/nbThreads) et non 2*(nbSimulations/nbThreads)!
J’ai le code suivant pour Skip:
skip(size_t n)
{
for(size_t i=0; i<n; ++i)
uni();
}
Certes, il y aurait matière à dire sur cette procédure question opimalité mais je ne l’incriminais pas forcément car d’une part aucun aspect de franche dépendance linéaire de mon temps de traitement en fonction des nombres de threads (test effectué par ailleurs) ne se dégageaient réellement et d’autre part, je pensais cette brique de génération globalement peu coûteuse en temps de calcul.
L’approche stockage dans un vecteur préalablement à la distribution sur les threads, je ne l’avais pas retenue (et ai d’ailleurs dû adapté mon code) pour une affaire de portabilité: dépassement de mémoire sur une autre machine que je fais tourner.
Les précautions à apporter en termes de synchro (mutex) ici, y’a matière à? Merci bcp, à +

vous avez d'autres typos dans le code que vous avez posté :
Pythagor est appelé une fois avec 1 paramètre, l'autre avec 2…
si effectivement il prend 2 paramètres alors le skip avec "2 * …" se comprenait…

et avec un seul paramètre : le (i+1) se justifie comment ? le premier thread (i=0) n'a rien à skipper, non ?

et maintenant vous introduisez "uni()" … "next()" appelle aussi "uni()" ? …

pour ce qui est de votre raisonnement sur le "coût" de skip : je vous ai posté des tests où l'on voir clairement que sa désactivation règle le problème…
ce qui se comprend aisément si l'on considère que selon vos propres explications "pythagor" à très certainement un coût CPU très inférieur à celui de "next()"… (une différence de carrés contre un "rand" ou équivalent…)

bref, ce serait quand même plus simple que vous postiez la totalité du code…

**simong** · 10/05/2010, 16h49

Envoyé par JeitEmgie

vous avez d'autres typos dans le code que vous avez posté :
Pythagor est appelé une fois avec 1 paramètre, l'autre avec 2…
si effectivement il prend 2 paramètres alors le skip avec "2 * …" se comprenait…
Bonjour,
Il sera difficile (impossible) de mettre ici les sources sur lesquelles je travaille.
Les typos résultent de quelques découpes sauvages et empressées , comme je le soulignais, pour soumettre à la lecture de 3DArchi qui m’y avait invité (merci encore), la structure blobale de mon code. Par ailleurs je tenais principalement faire avaliser la mise en place des instructions du threading, (briques sur lesquelles je m’étais déjà bien fais mal à la tête et que je pensais à l’origine de mon pb. J’explore pour la première fois le C++ multithreadé, je ne sais même pas déboguer ça.
et avec un seul paramètre : le (i+1) se justifie comment ? le premier thread (i=0) n'a rien à skipper, non ?
et maintenant vous introduisez "uni()" … "next()" appelle aussi "uni()" ? …
Découpe d’une partie de mon code original là-encore: je réalise dans une « boucle « 1, la construction de mes « index sup » de tirage, puis je j’appelle Skip en consentant à chaque fois et modulo une bidouille pas très propre le « gaspillage » des i premières séquences du tirage pour le tirage courant. Pour moi, le thread 0 tire dans ce cadre une séquence longue de
1*nbSimulation/nbThread éléments?
pour ce qui est de votre raisonnement sur le "coût" de skip : je vous ai posté des tests où l'on voir clairement que sa désactivation règle le problème…
ce qui se comprend aisément si l'on considère que selon vos propres explications "pythagor" à très certainement un coût CPU très inférieur à celui de "next()"… (une différence de carrés contre un "rand" ou équivalent…)

bref, ce serait quand même plus simple que vous postiez la totalité du code

Je tâche de revenir avec un résultat sur les pistes de modifications que vous suggérez au niveau d'un stockage amont de tout le Rand. Merci bien de toute façon.

**3DArchi** · 11/05/2010, 07h26

Envoyé par JeitEmgie

et alors ? cette partie fait partie du benchmark... qui a priori est sur l'ensemble du calcul...

C'est pas pour chipoter, mais tu parlais d'appeler skip avant la génération des threads... Je me suis juste contenté de dire que c'était déjà le cas. Ensuite, que cela fasse partie du benchmark et que cela puisse être très consommateur de temps, c'est effectivement tout à fait probable.

Envoyé par JeitEmgie

question de goût : priorité au raisonnement...

discussion ouverte il y a une semaine. En - d'une demi-journée on instrumente, on mesure et on a matière plus concrète pour raisonner

Envoyé par simong

Les précautions à apporter en termes de synchro (mutex) ici, y’a matière à? Merci bcp, à +

Je rejoint JeitEmgie : à un moment, il va nous falloir un plus de code car là les infos ne sont pas suffisantes.