Bonjour,

Je débute dans la programmation multithread, et je bloque sur l'implantation du Crible d’Ératosthène.

Tout d'abord voici l'algo séquentiel :

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
#include <iostream>
#include <stdlib.h>
using namespace std;
 
int main(int argc, char **argv)
{
	const int	MAX = atoi(argv[1]);
	bool		tab[MAX+1];
 
	for (int i = 0; i < MAX+1; i++) //Initialisation du Tableau à true
		tab[i] = true;
	tab[0] = false;
	tab[1] = false;
 
	for (int i = 2; i < MAX+1; i++) //Crible d'érastothène
	{
		if (tab[i])
		{
			for (int j = 2*i; j < MAX+1; j = j + i)
				tab[j] = false;
		}
	}
 
        cout << "Nombres premiers jusque " << MAX << " :" << endl; //Affichage du Tableau
	for (int i = 0; i < MAX+1;  i++)
	{
		if (tab[i])
			cout << i << "\t ";
	}
	cout << endl;
 
	return (0);
}
Après réflexion, je pense qu'il est impossible de découper la première boucle en plusieurs Threads sans avoir d'erreur, car le principe du Crible d’Ératosthène est d'éliminer tous les multiples de 2 et ensuite les multiples de 3, 5 etc ... Il y a des chances que le Thread démarre sur un nombre non encore traité par un Thread précédent, donc qu'il débute par un nombre non premier.

Alors j'ai eu l'idée de découper la deuxième boucle, par exemple pour 4 threads et 100 en paramètre, on aurait le premier Thread qui élimine tous les multiples de 2 dans l'intervalle [1,25], le 2nd [26,50], le 3ème [51,75] et enfin le dernier [76,100] et ainsi de suite on fait de même pour 3, 5, 7 etc ...

Pour cela j'ai crée une Structure data :
- Un pointeur pour pointer sur le tableau tab.
- size, l'intervalle sur lequel le Thread va travailler. (ex : 25)
- Le min, c'est à partir de là que le Thread va éliminer les multiples. (ex : 51)
- Le max. (ex : 75)
- i, qui correspond au nombre premier auquel on va éliminer ses multiples (ex : 2, 3, 5, 7 etc ..)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
struct data
{
	bool*			pTab;
	unsigned int	size;
	unsigned int 	i;
	unsigned int	min;
	unsigned int	max;
};
Ensuite le problème c'est que mon programme ne me renvoit pas du tout les nombres premiers, je pense qu'il doit y avoir un problème dans l'attente des threads du nombre premier précédent, du coup l'algo s'enchaine sur un nombre non premier.

Voici mon code du main :
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
int main(int argc, char **argv)
{
	const unsigned int	MAX = atoi(argv[1]);
	pthread_t thtab[NBTHREADS];
	bool * tab = new bool[MAX+1];
 
	for (unsigned int i=0; i<MAX+1; ++i) //Initialisation du tableau à true
		tab[i] = true;
	tab[0] = false;
	tab[1] = false;
 
	unsigned int partSize = MAX / NBTHREADS;
	struct data * myStructs = new struct data[NBTHREADS];
	for (unsigned int i=0; i<NBTHREADS ; ++i)             //Initialisation Structure
	{
		myStructs[i].size 	= partSize;
		myStructs[i].pTab	= tab;
		myStructs[i].i 		= 0;
		if(i > 0)
			myStructs[i].max	= myStructs[i-1].max + partSize;
		else
			myStructs[i].max	= partSize;
		myStructs[i].min	= myStructs[i].max - partSize;
	}
 
	for (unsigned int i = 2; i < MAX+1; i++) //Crible d'érasthotène
	{
		if(tab[i])
		{
			pthread_join(thtab[0], NULL); /*Attente des Threads du Nombre Premier précédent, j'ai mis thtab[0] car juste thtab ne compile, peut-être que le problème vient d'ici.*/
			for (unsigned int th=0; th<NBTHREADS; ++th)
			{
				myStructs[th].i = i;
				pthread_create(&thtab[th], NULL, task, (void*) &myStructs[th]);
			}
		}
	}
 
        cout << "Nombres premiers jusque " << MAX << " :" << endl; //Affichage du Tableau
    	for (unsigned int i = 0; i < MAX+1;  i++)
    	{
    		if (tab[i])
    			cout << i << "\t ";
    	}
    	cout << endl;
 
	delete[] myStructs;
	delete[] tab;
	return (0);
}
Et enfin ma fonction Thread :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void * task(void * _data) 
{
	struct data  * localData = (struct data *) _data; //Pointeur sur ma structure
 
	while ((localData->min)%(localData->i) != 0) //On fait en sorte que le minimum commence à partir d'un nombre multiple.
	{
		localData->min = localData->min + 1;
	}
 
 
       for (unsigned int j = localData->min; j < localData->max; j = j + localData->i) //On élimine les multiples dans l'intervalle [min,max]
			localData->pTab[j] = false;
	return (NULL);
}
Je débute donc il est probable que c'est pas du tout la bonne technique que j’essaie d'employer, peut-être qu'il y a une implémentation plus logique et facile.

Merci d'avance pour votre aide,

Florian.