Configuration de lancement des threads

Version imprimable

15/05/2015, 21h12
mister3957

Configuration de lancement des threads
Bonjour à tous,

Je connais le principe des threads mais ne les ayant jamais appliqués mes connaissances ne sont que théoriques.

J'ai admettons 10 unités (le 10 n'étant connu qu'à l'exécution, ça peut être 5 comme 15 ou 20) et des algorithmes permettent de travailler sur 2 unités en même temps pour les "mélanger" afin d'obtenir un résultat tendant vers un "idéal".

Actuellement les algorithmes tournent en séquentiels sur les unités :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [1 - 2] [1 - 3] [1 - 4] ... [1 - 10] puis [2 - 1] [2 - 3] [2 - 4] ... [2 - 10] puis à la fin [10 - 1] [10 - 2] [10 - 3] ... [10 - 9]
L'ensemble est long à s'exécuter et en faisant un htop on voit qu'il n'y a qu'un processeur logique sur 8 qui est à 100%. Alors l'idée est d'exploiter les performances de la machine un peu mieux en admettant que l'on puisse exécuter les algorithmes [1 - 2], [3 - 4], [5 - 6], [7 - 8] ou [1 - 3], [2 - 4], [5 - 7], [6 - 8] etc. en même temps, mais avant d'exécuter par exemple l'algorithme sur [1 - 3] il faut attendre la fin des threads [1 - 2], [1 - 4], [1 - 5], [1 - 6], [1 - 7], [1 - 8], [2 - 1], [3 - 1], [4 - 1], [5 - 1], [6 - 1], [7 - 1], [8 - 1] car sinon ça va toucher à 1 et 3 qui sont en cours d'exécution. Je vous passe le nombre de combinaisons possibles, et encore plus celui des dépendances.

Le but est d'explorer tous les couples [X - Y] sans que jamais 2 threads travaillent sur X ou Y en même temps.

Donc je pense qu'il faut commencer générer tous les couples [X - Y] possibles, ça ne va pas être compliqué. Ensuite il faut générer les "incompatibilités d'exécution", donc que [X - Y] n'est pas exécutable en même temps que [X - Z], [Y - Z], [Z - X] et [Z - Y], et après je suis perdu pour savoir comment ça peut se traduire avec les threads, les mutex et surtout comment organiser l'ensemble pour que les "compatibles" se lancent en parallèles dont chacun va attendre la fin d'exécution des "non compatibles".

A mon avis il me faut faire une classe qui va fonctionner comme l'une de ces pieuvres que l'on voit dans Men In Black.

Première question : Est-ce que le raisonnement est bon, ou plutôt utopique ?
Deuxième question : Si ça n'est pas utopique, vous auriez une première approche technique en pseudo code ?

Merci à vous,

Bonne soirée et bon weekend,

Kin
16/05/2015, 02h41
bacelar

Vos problème de dépendance montre que votre algorithme n'est pas vraiment conçu pour être parallèle.
Il faut peut-être revoir l'algorithme pour qu'il soit plus parallélisable.
Vous pouvez aussi réduire les dépendances en faisant des copies des données en entrée.
De plus, il serait peut-être plus simple de ne pas résonner sur un nombre fixe de threads.
Il se peut que les dépendances entrainent un nombre plus important de threads possibles en début ou en fin de processus en fonction de l'algorithme choisi.
L'utilisation d'un découpage de l'algorithme en tâches et en utilisant un pool de thread permettrait de mieux adapter la puissance de calcul à parallélisme non constant.
16/05/2015, 08h15
mister3957

Citation:

Envoyé par bacelar

Vos problème de dépendance montre que votre algorithme n'est pas vraiment conçu pour être parallèle. Il faut peut-être revoir l'algorithme pour qu'il soit plus parallélisable.

Je pense que si puisque lorsqu'un algorithme travaille sur les unité 1 et 2, il est cloisonnée aux données des unités 1 et 2, donc un autre peut travailler sur 3 et 4 par exemple.

Citation:

Envoyé par bacelar

Vous pouvez aussi réduire les dépendances en faisant des copies des données en entrée.

Les copies de données sont délicates étant donné que je suis dans un univers de calculs, recherche opérationnelle etc. et la volumétrie étant importante j'aurais peur pour les performances.

Citation:

Envoyé par bacelar

De plus, il serait peut-être plus simple de ne pas résonner sur un nombre fixe de threads. Il se peut que les dépendances entrainent un nombre plus important de threads possibles en début ou en fin de processus en fonction de l'algorithme choisi.

Oui bien sûr, mais y a-t-il une limite au niveau du système ? Est-ce que gérer de nombreux threads consomme beaucoup de CPU ?

Citation:

Envoyé par bacelar

L'utilisation d'un découpage de l'algorithme en tâches et en utilisant un pool de thread permettrait de mieux adapter la puissance de calcul à parallélisme non constant.

C'est déjà pas mal découpé. En fait il n'y a pas un seul algorithmes, mais 9 algorithmes avec des tâches bien spécifiques et qui sont complémentaires entre eux. De plus, pour chaque algorithme on peut leur spécifier leur périmètre d'action en leur imposant de travailler avec tel couple d'unité.

En résumé, on peut lancer AlgoA(u1, u2), AlgoA(u3, u4), AlgoB(u5, u6), AlgoC(u7, u8) en même temps mais pas deux algos (qu'il soient le même ou différent) sur les mêmes unités en même temps, donc on ne peut pas lancer AlgoA(u1, u2) et AlgoB (u2, u3) en même temps.

Aujourd'hui le programme lance les algos les uns à la suite des autres. Chaque algorithme indique s'il a pu améliorer quelque chose permettant potentiellement aux autres algos de trouver à leur tour des améliorations. Le programme s'arrête lorsque plus aucun algo ne peut améliorer la solution. C'est de la recherche combinatoire.

J'ai pensé à une autre solution, ce serait de diviser pour mieux régner en précisant le nombre de division (donc de threads à utiliser) et de manière dégressive. Par exemple pour 10 unité et 4 threads définis, on divise le contexte en :
1 - [u1 -> u3]
2 - [u4 -> u6]
3 - [u7 -> u8]
4 - [u9 -> u10]

Une fois tous les threads exécutés on découpe autrement jusqu'à ce que tous les threads aient travaillés sur les différentes découpes.

Puis on passe à des découpages à 2 threads :
1 - [u1 -> u5]
2 - [u6 -> u10]

Puis 1 thread
1 - [u1 -> u10]

Aujourd'hui ça n'utilise qu'un thread [u1 -> u10] mais avec ce schéma là peut-être que le "diviser pour mieux gérer" aura abouti à une solution déjà bien dégrossit en beaucoup moins de temps que ça ne le mettrait avec un seul thread depuis le début.

Ça fait deux pistes de recherche mais je pense que le mieux serait de construire un arbre des dépendances avec une petite machinerie permettant de dire "toi vas-y, go go go", "toi 2 minutes, on attend lui, lui et lui qu'ils aient terminés" etc. avec un paramètre limitant le nombre de thread à exécuter en même temps s'il y a des restrictions au niveau du système.

Il ne faut pas non plus que cette machinerie pompe trop de performance sinon ça reviendrait à déshabiller Pierre pour habiller Paul.

Je pense qu'il y a moyen de s'amuser ;)
18/05/2015, 00h35
bacelar

Citation:

Les copies de données sont délicates étant donné que je suis dans un univers de calculs, recherche opérationnelle etc. et la volumétrie étant importante j'aurais peur pour les performances.

C'est une histoire de compromis (tradeoff), il faut les évaluer et pas faire des assertions à la serpe.

Citation:

Oui bien sûr, mais y a-t-il une limite au niveau du système ? Est-ce que gérer de nombreux threads consomme beaucoup de CPU ?

En général, oui.
Il n'y a jamais de OUI et de NON absolu => on en revient toujours à un calcul de compromis.

Citation:

C'est déjà pas mal découpé

Découper arbitrairement, cela n'a pas de sens. Il faut découper pour réduire les couplages et donc avoir POTENTIELLEMENT, un meilleur parallélisme.

Il vous faut aussi un algorithme, même pour gérer votre schedulling des thread.
Ce que vous donnez comme indice montre un problème de stabilité, rien n'empêche l'algorithme de travailler pour toujours.(problème de stabilité numérique,etc...).
Votre méta algorithme n'est clairement pas fait pour être parallélisable.

Un thread peut exécuter un "Algo" à un moment et un autre plus tard, etc...

Comme vous avez un nombre limité de "u", vous pouvez faire une gestion "automatique" des dépendances en utilisant des mutex et autres mécanismes de synchronisation.

Le pool de thread permet de réduire "naturellement" le nombre de thread.

Il n'y a pas de solution miracle, vous devez étudier la répartition en temps de calcul des algorithmes en fonction des types d'unité pour chercher à optimiser la répartition du temps de calcul.
18/05/2015, 11h21
white_tentacle

J’aborderai les choses d’une manière différente.

Si j’ai bien compris, les traitements n’ont pas besoin de s’exécuter dans un ordre particulier. Donc, ce que je ferai en première étape, pour n éléments :

- générer la liste des couples à traiter (en simple thread, le nombre est petit de ce que j’ai compris)
- créer n/2 threads, qui vont ensuite « piocher » dans la liste des couples à traiter un couple « disponible ».
- un couple est « disponible » si chacun de ses deux membres est « disponible ».
- quand un couple est choisi par un thread, il marque chacun de ses deux membres comme n’étant plus disponibles (en utilisant, par exemple, un sémaphore)
- si un thread ne trouve pas de couple disponible, il se met en attente (en utilisant, par exemple, une condition variable)
- lorsqu’un thread finit son traitement sur un couple, il rend « disponible » chacun de ses éléments, réveille les autres threads et regarde s’il peut trouver un nouveau couple « disponible » à traiter parmi la liste, etc...
- et ainsi de suite jusqu’à ce que la liste des couples à traiter soit vide.

Cela devrait permettre de bénéficier du parallélisme sans vraiment se préoccuper de la charge répartie à chaque thread : ils prennent en fonction de ce qui est dispo.

Néanmoins, il y a quelque chose qui me chiffonne dans le problème initial :
- le traitement est supposé toucher aux données initiales (sinon, on peut très bien y accéder depuis plusieurs threads)
- l’ordre d’exécution ne serait pas important

Ces deux propriétés sont généralement incompatibles entre elles...
19/05/2015, 08h12
mister3957

Citation:

Envoyé par white_tentacle

J’aborderai les choses d’une manière différente.

Si j’ai bien compris, les traitements n’ont pas besoin de s’exécuter dans un ordre particulier. Donc, ce que je ferai en première étape, pour n éléments :

- générer la liste des couples à traiter (en simple thread, le nombre est petit de ce que j’ai compris)
- créer n/2 threads, qui vont ensuite « piocher » dans la liste des couples à traiter un couple « disponible ».
- un couple est « disponible » si chacun de ses deux membres est « disponible ».
- quand un couple est choisi par un thread, il marque chacun de ses deux membres comme n’étant plus disponibles (en utilisant, par exemple, un sémaphore)
- si un thread ne trouve pas de couple disponible, il se met en attente (en utilisant, par exemple, une condition variable)
- lorsqu’un thread finit son traitement sur un couple, il rend « disponible » chacun de ses éléments, réveille les autres threads et regarde s’il peut trouver un nouveau couple « disponible » à traiter parmi la liste, etc...
- et ainsi de suite jusqu’à ce que la liste des couples à traiter soit vide.

Cela devrait permettre de bénéficier du parallélisme sans vraiment se préoccuper de la charge répartie à chaque thread : ils prennent en fonction de ce qui est dispo.

Néanmoins, il y a quelque chose qui me chiffonne dans le problème initial :
- le traitement est supposé toucher aux données initiales (sinon, on peut très bien y accéder depuis plusieurs threads)
- l’ordre d’exécution ne serait pas important

Ces deux propriétés sont généralement incompatibles entre elles...

Oui je le vois comme ça aussi, mais n'ayant pas beaucoup d'expérience dans ce type de travail je préférais avoir confirmation que l'idée n'était pas mauvaise avant de passer du temps dessus.

Pour les aspects qui te chiffonnent, effectivement l'ordre d'exécution a une importance sur la rapidité avec laquelle on obtiendra les résultats mais ça je le gérerai lorsque j'implémenterai des stratégies évolutives (et / ou génétiques), je dois encore bien saisir le concept avant de plonger les mains dedans.

D'après ce que j'ai compris des stratégies évolutives, il s'agit de collecter des informations durant les opérations afin qu'elles puissent être réutilisées par la suite et éviter de tester des combinaisons (et donc limiter les traitements) dont on sait à l'avance qu'elle ne mèneront à rien. Et comme chaque algorithme a son périmètres définit, la collecte comme la lecture de ces informations ne devraient pas faire l'objet de conflits entre différents threads.

Je vais tenter quelque chose ce weekend, on verra bien ce que ça donnera.

Merci,

A bientôt
19/05/2015, 08h59
white_tentacle

Dans ce cas, je pense qu’il ne faut pas que touches aux données initiales, et que donc tu n’as pas besoin de les protéger. Tu peux en revanche avoir « à côté » une structure dédiée, destinée à stocker tes calculs intermédiaires et les informations qui te permettent d’éviter de calculer certaines branches. C’est du coup seulement cette structure que tu vas devoir protéger en terme d’accès concurrents (ainsi que le résultat).
19/05/2015, 18h40
mister3957

Citation:

Envoyé par white_tentacle

Dans ce cas, je pense qu’il ne faut pas que touches aux données initiales, et que donc tu n’as pas besoin de les protéger. Tu peux en revanche avoir « à côté » une structure dédiée, destinée à stocker tes calculs intermédiaires et les informations qui te permettent d’éviter de calculer certaines branches. C’est du coup seulement cette structure que tu vas devoir protéger en terme d’accès concurrents (ainsi que le résultat).

Oui bien sûr les données initiales ne bougent pas. Un algorithme est chargée de construire une première solution très approximative, lui tournera seul, et ensuite les autres sont chargés d'améliorer la solution avec pour chacun d'entre eux leur spécialité.

Il faut juste que deux threads ne touchent pas à une même donnée de la solution et restent dans leur espace de recherche limité à 2 unités.

Je pense que ça peut le faire, en tout cas sur le papier et si c'est bien fait, y'a pas de raison que ça ne fonctionne pas, même si pour le moment je manque de visibilité quant au code à produire.

Est-ce qu'il faut que les threads "squattent" dans des boucles while(true) avant de tomber et "locker" un cas "libre" ou doit-on utiliser les mutex ? Il y aura au moins une gestion sur une espèce de fonction "EstCompatible ? => Si oui alors lock" pour ne pas que 2 threads effectuent ce test en même temps.

Après le "while(true)" me plait moyen.

Auriez-vous une éboche de pseudo code ?
20/05/2015, 10h35
white_tentacle

Je ne suis pas sûr de bien comprendre les interactions entre la solution et les données initiales, donc tout ce que je dis est à prendre avec des pincettes.

Mais en gros, je vois les choses comme ça :
- le jeu de données initiale est en lecture seule :*tout le monde peut y accéder, aucun problème d’accès concurrents là-dessus
- on ne veut traiter les couples qu’une seule fois. On peut raisonnablement estimer que générer la liste des couples est une tâche rapide, qu’on fera en début de traitement. Une fois cette liste créée, deux options :
* soit le programme principal « dispatche » les couples à traiter à n « threads » (ou en fait, tâches asynchrones avec std::async), et attends qu’ils se terminent : auquel cas, chaque thread ne va faire qu’un traitement et se terminer tranquillement, sans boucle
* soit les threads viennent piocher dans la pile de couples à traiter, auquel cas il faut protéger les accès à cette pile par un mutex, pour éviter les accès concurrents. Auquel cas, chaque thread va avoir une boucle « while obtenirCoupleATraiter() », et s’arrêter lorsqu’il n’y aura plus rien à traiter.

Je pense que la première solution est (un peu) plus simple à mettre en œuvre : le fait de disposer d’un « maître ordonnanceur » simplifie en général la compréhension.

Pour le fait de lire/écrire dans la solution, il n’y a pas le choix : si tout le monde peut lire et écrire, il faut protéger les accès par un mutex. Normalement, puisque les threads de traitement ne communiquent pas entre eux directement, il n’y a pas de risque particulier de se retrouver dans une situation de blocage. La solution que j’emploierai dans ce cas en approche grossière est d’encapsuler la solution dans un objet complètement thread-safe (c’est à dire que chacune de ses méthodes publiques va être protégée par le même mutex, garantissant des accès non-concurrents), qui correspondent aux différents « services » que fournit la solution par rapport aux threads de traitement. L’important est que chaque opération sur la solution que doivent réaliser les threads de traitement soit atomique dans les faits (ta solution ne doit pas être dans un état incohérent).

Bon, je pense que j'ai pigé le principe. Pour tester la logique j'ai fait 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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <vector>
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sstream>
 
#include <boost/thread.hpp>
 
// Simulation du traitement d'un algorithme sur deux unités
bool Algo(int i, int j, boost::mutex& coutMutex)
{
	int iMs = (rand() % 10 + 1) * 1000;
	coutMutex.lock();
	std::cout << "Thread " << boost::this_thread::get_id() << " - Computing " << i << " and " << j << " for " << iMs << " ms" << std::endl;
	coutMutex.unlock();
 
	boost::this_thread::sleep_for(boost::chrono::milliseconds(iMs)); // Attendre entre 1 et 10 secondes
 
	return iMs < 8000; // Dans 20% des cas l'algo indique qu'il n'a pas trouvé de meilleure solution
}
 
// Classe ce coordination des threads
class CExecute
{
public:
	CExecute(int iNumber)
		: m_iN(iNumber)
	{
		// m_pUsed est une liste de flags indiquant si l'unité I est en cours d'utilisation (via m_pUsed[I])
		m_pUsed = new bool[m_iN];
		for (int i = 0; i < m_iN; ++i)
			m_pUsed[i] = false;
 
		// m_pChanged indique si des changements ont été opérés sur l'unité I (via m_pChanged[I])
		// En effet, si l'algo n'a rien amélioré depuis la dernière fois pour ces deux unités, inutile de le relancer
		m_pChanged = new bool[m_iN];
		for (int i = 0; i < m_iN; ++i)
			m_pChanged[i] = true;
 
		// Calculs du nombre de thread à utiliser, il est équivalent au maximum de couple (i, j) pouvant tourner en même temps sans incompatibilité
		m_iNbThreads = (iNumber * (iNumber - 1)) / 6;
	}
 
	// Destructeur -> nettoyage
	~CExecute()
	{
		delete m_pUsed;
		delete m_pChanged;
	}
 
	// Donne un couple (i, j) "libre". Renvoi 0 s'il n'y en a pas, 1 s'il y en a et 2 s'il n'y a plus aucune opération à effectuer sur les unités
	int GetNext(int& i, int&j)
	{
		boost::mutex::scoped_lock lock(m_mutex);
 
		bool b = false; bool bContinue = false;
		for (int p = 0; p < m_iN; ++p)
		{
			bContinue |= (m_pUsed[p] || m_pChanged[p]);
			if (!m_pUsed[p] && (m_pChanged[p] || b)) // i et j doivent être libres, et i ou j doivent avoir changés depuis la dernière exécution du couple
			{
				if (!b) { i = p; b = true; }
				else {
					j = p;
					m_pUsed[i] = true;
					m_pUsed[j] = true;
					return 1;
				}
			}
		}
 
		if (!bContinue)
			return 2;
		return 0;
	}
 
	// Démarrage d'un thread
	void LaunchThread()
	{
		unsigned int lId = 0;
		std::stringstream ss; ss << boost::this_thread::get_id(); ss >> lId;
		srand(lId);
 
		while (true)
		{
			int i; int j; int iRet = 0;
			while (!(iRet = GetNext(i, j))) // On attend une dispo
			{
 
			}
			if (iRet == 1) // S'il y en a une on applique l'algorithme
			{
				bool retAlgo = Algo(i, j, m_CoutMutex);
 
				m_pChanged[i] = retAlgo;
				m_pChanged[j] = retAlgo;
				m_pUsed[i] = false;
				m_pUsed[j] = false;
			}
 
			if (iRet == 2) // S'il n'y en a plus on stoppe le thread
			{
				m_CoutMutex.lock();
				std::cout << "Thread " << boost::this_thread::get_id() << " - Finished !" << std::endl;
				m_CoutMutex.unlock();
				return;
			}
		}
	}
 
	// Lancement des threads
	void Launch()
	{
		std::vector<boost::thread*> vecTh;
 
		for (int i = 0; i < m_iNbThreads; ++i)
			vecTh.push_back(new boost::thread(&CExecute::LaunchThread, this));
		for (int i = 0; i < m_iNbThreads; ++i)
			vecTh[i]->join();
		for (int i = 0; i < m_iNbThreads; ++i)
			delete vecTh[i];
	}
 
private:
	int m_iN;
	bool* m_pUsed;
	bool* m_pChanged;
	int m_iNbThreads;
	boost::mutex m_mutex;
	boost::mutex m_CoutMutex;
};
 
int main(int argc, char *argv[])
{
	CExecute exec(16);
	exec.Launch();
}

La logique semble-t-elle bonne ?

Une autre question : Les algos envoient des messages à un gestionnaire de log.

Est-ce que je dois mettre un mutex dans ce gestionnaire de log qui ne va pas forcément être utilisé dans un contexte multithread ou dois-je plutôt un mutex global encadré de lock / unlock à chaque appel au logger au sein des algorithmes ?

Merci,

A bientôt

20/05/2015, 14h32
white_tentacle

Je vois que tu as choisi la première solution (threads qui sont consommateurs). En lecture rapide, je n’ai rien vu qui me choque particulièrement, à part qu’il manque une protection sur les modifications de m_pChanged et m_pUsed dans LaunchThread. Ce qui m’amène à dire que ta classe fait trop de choses. Crée des classes séparées pour :

- le thread de traitement
- les données partagées
- le lanceur initial (quoique pour lui, l’intérêt d’une classe se discute)

Et protège correctement chacun des services de tes données partagées. Ce découpage t’évitera d’oublier de protéger tes variables à un endroit de ton code.

Sinon, passe toujours par un scoped mutex-locker pour locker tes mutex. Ça ne coûte pas cher et ça t’éviteras bien des ennuis (là il y a des endroits où tu le fais, d’autres non).
20/05/2015, 20h30
mister3957

Citation:

Envoyé par white_tentacle

Je vois que tu as choisi la première solution (threads qui sont consommateurs). En lecture rapide, je n’ai rien vu qui me choque particulièrement, à part qu’il manque une protection sur les modifications de m_pChanged et m_pUsed dans LaunchThread. Ce qui m’amène à dire que ta classe fait trop de choses. Crée des classes séparées pour :

- le thread de traitement
- les données partagées
- le lanceur initial (quoique pour lui, l’intérêt d’une classe se discute)

Et protège correctement chacun des services de tes données partagées. Ce découpage t’évitera d’oublier de protéger tes variables à un endroit de ton code.

Sinon, passe toujours par un scoped mutex-locker pour locker tes mutex. Ça ne coûte pas cher et ça t’éviteras bien des ennuis (là il y a des endroits où tu le fais, d’autres non).

Merci pour ta réponse :)

Ne relevant pas de problème majeur, j'ai intégré ce code de test à mon application et adapté à mon domaine métier.

- Désormais ça n'utilise que des scoped_lock et j'ai sécurisé m_pChanged.
- J'ai réimplémenté les algorithmes pour les sécuriser également, c'était principalement du copier / coller mais avec un mutex que je passe en paramètre à bloquer lorsque ça appelle le gestionnaire de log. Il y a sûrement plus propre mais pour le moment je vais laisser comme ça.
- J'ai préféré conserver les anciens algos et l'ancien fonctionnement pour pouvoir comparer les performances du traitement multi thread et celles du mono thread.
- J'ai gardé le lancer car il doit exécuter un traitement initial et à chaque passe de tous les algos un traitement qui ne peut être parallèle mais dont les résultats influent sur le global, sinon ça va coupler la logique de l'appelant avec celle du dispatcher, donc pas bon mais effectivement pour l'exemple l'intérêt est remis en question

Ça compile et je fera des tests et des benchs probablement ce weekend. Ensuite nettoyage et j'ai vu que certaines options de compilation influençait significativement les performances à l'exécution, donc une passe là dessus ne sera pas de trop ;)

Je vous tiens en courant et en tout cas merci beaucoup pour vos messages
23/05/2015, 09h05
mister3957

Hello,

J'ai fait des tests et résultat, sur un cas de tests, je passe de plus de 10 minutes de traitement à 4 min 30.

Il y a juste que lorsque je lance deux fois le truc, les résultats sont différents alors que ça ne devrait pas l'être, il y a donc un bug sur les conditions d'arrêt de l'ensemble du traitement, je vais investiguer tout ça.

Mais j'ai fait à l'arrach', c'est normal que ça ne soit pas "exact" dès le premier jet.

Dans le cas testé il y a 15 unités, donc potentiellement, il y a (15 * (15 - 1)) / 6 couples qui peuvent être traités en parallèle, ça fait 35 threads. Mais au fur et à mesure que l'algorithme avance, il y a de moins en moins de couples d'unités qui peuvent produire une meilleure solution globale, et je me retrouve à la fin avec 1 thread qui tourne et 34 bloqués dans le GetNext(). Ce genre de situation me paraît contre productive alors je vais déterminer un calcul pour en terminer quelques uns selon le contexte métier.

D'ailleurs j'ai vu qu'il y avait plusieurs façon de gérer la synchronisation, je vais peut-être trouver quelque chose qui soit plus propre et peut-être plus performant.

En tout cas ça confirme que le parallélisme est applicable et que son apport est significatif pour ce type de travail :)

Merci,

Bon weekend