Discussion :

[ganon551]

Bonjour à tous,

Je m'amuse ces derniers temps à implémenter le crible d'Eratosthène en c++/Qt et à améliorer l'algorithme pour aller plus vite. Je précise ça n'a rien à voir avec un exercice ou autre, c'est juste par simple curiosité.

En me baladant sur les sites en traitant, j'ai découvert que certains ont parallélisé leur algo pour aller plus vite, souvent avec OpenMP.

Ni une ni deux je l'inclus et me voilà parti pour les plaisirs du multiThread.

Seulement voilà, tout ne marche pas aussi facilement et je me retrouve avec des choses étranges.

Voici une partie de mon code, celle que je voudrais paralléliser :

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
 
        const ulong const_limite = limite;
	int i = 0;
 
	#pragma omp parallel for schedule(dynamic,3) num_threads(4)
	for(i = 7;i <= const_limite;i+=2)
        {
 
             switch(donnees.tableauStruct.testBit(i))
             {
                        case true:
                        {
                        emit changementBarre(i); 
                        max = nombrePremiers/i;
                        if(((max >> 1)<<1) == max)
                        max--;
                        ulong j=max;
                        const ulong const_i = i;
                        for(; j >= const_i; j-=2)
                        { 
                                switch(donnees.tableauStruct.testBit(j)) 
                                {
                                case true:
                                     {
                                     donnees.tableauStruct.setBit(j*i,false);//On attribue la valeur false au bit en j*i
                                     }
                                     break;
                                }
                        }
                        }
                        break;
             }         
     }

J'ai modifié mon code pour les besoins des tests avec OpenMP, mais globalement c'est le même.

const_limite est ici égal à la racine carrée du nombre entré par l'utilisateur.

Passons au multiThread. Le pragma que j'ai rentré ici ne fait pas planter le programme (c'est déjà bien). Je vais effectivement beaucoup plus vite (je passe de 5s500 à 3s00 jusqu'a 10^9). Toutefois il y a deux problèmes, déjà le programme ne me renvoie pas le bon nombre de premiers, et ce nombre de premiers change à chaque exécution.

Je me suis dit qu'il devait "sauter" des tours de boucle, sinon je ne vois pas comment. J'ai alors pensé que le nombre de boucles imposé dans schedule() était trop bas. J'ai donc mis 2000 à la place. Effectivement avec cette valeur le programme me sort le bon nombre de premiers, mais ça va moins vite qu'en série !

Je précise que cela dépend de la valeur entrée par l'utilisateur. Par exemple si je veux calculer les premiers jusqu'à 10^6, aucun problème. Mais plus on monte, et plus il faut augmenter le nombre de boucles par thread, comme si on devait améliorer la précision.

Autre problème, OpenMP n'aime pas l'HT ? Mon proco est un dual-core avec HT, et si je laisse OpenMP se débrouiller il me lance 4 threads. C'est très bien sauf qu'une fois le programme fermé, le processus ne se ferme pas, et je dois aller dans gestionnaire des tâches pour le supprimer manuellement.

Enfin ce problème me gêne moins, même en forçant le nombre de threads sur 2 j'ai de gros gains, mais encore une fois le nombre de premiers n'est pas le bon (à quelques dizaines près) et change constamment.

J'ai essayé tout ce que je pouvais, les flush, les private, ordered, etc, mais rien n'y fait.

Si une bonne âme peut m'aider, et désolé pour ce pavé

[Ehonn]

Réponse rapide

Paralléliser une boucle avec OpenMP ne veut pas dire que cette boucle est parallèle.
Il faut séparer les données pour qu'elles ne soient pas écrites en même temps par les différents threads (sinon ça fait des collisions et le résultat est faux).
À la lecture rapide du code, j'ai des doutes avec le emit, max donnees.tableauStruct.testBit(j) et donnees.tableauStruct.setBit(j*i,false).
Il faudrait aussi vérifier si OpenMP supporte les break.

Commence peut être par des codes plus simple (pour apprendre) comme une multiplication de vecteurs.
Et ensuite cherche à paralléliser ce code (qui ne peut pas être parallélisé tel quel)

Code :

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

1
2
tab[0] = 1;
for (...) { tab[i] = tab[i-1] * 2; }

Simplifie ton code et utilise juste #pragma omp parallel for sans te soucier du scheduler ou du nombre de thread (concentre-toi sur le résultat).

[ganon551]

Merci pour ta réponse.

En ce qui concerne l'emit j'y ai pensé et je l'avais viré, mais aucun changement.
J'ai aussi essayé sans les breaks, mais toujours pareil.

Je m'étais posé la question pour la variable max, mais quand je la met en private ça ne change rien, de même que j, je m'étais dit que chaque thread devait pouvoir faire des calculs avec son propre j, puisque la seule chose que je veux partager c'est le i.

Je vais essayer de paralléliser le code que tu m'as donné pour voir

Merci encore pour ton aide.

PS : Pour le nombre de threads, je veux bien ne pas m'en soucier mais quand je laisse en auto le programme ne se ferme pas :-/

EDIT : Je galère pas mal avec le code que tu m'as passé. Le problème est qu'il faut l'exécuter en mode séquentiel si on veut avoir le même résultat final. Si on l'exécute en multithread il faudrait que les threads attendent les autres pour faire la multiplication.

Je m'explique, si mon thread1 fait la première opération, tab[1] = tab[0] * 2. Si tab[0] = 1, tab[1] = 2. Si on continue on va afficher comme ça les puissances de 2.

Maintenant si je parallélise, par exemple mon thread 1 fait l'opération précédemment expliquée. Mon thread 2 qui est plus rapide attaque celle d'après avant que thread1 n'ai fini, je me retrouve avec tab[0] = 1, tab[1] = 2, tab[2] = 1.

Du coup le seul moyen c'est d'indiquer aux threads qu'ils doivent attendre les autres. Du coup l'exécution se fera aussi rapidement qu'en série, même moins vite vu qu'on doit créer les threads

[koala01]

Salut,

EDIT : Je galère pas mal avec le code que tu m'as passé. Le problème est qu'il faut l'exécuter en mode séquentiel si on veut avoir le même résultat final. Si on l'exécute en multithread il faudrait que les threads attendent les autres pour faire la multiplication.

Je crois que c'était le but de Ehonn, histoire de t'amener à envisager une "pensée alternative"

Je m'explique, si mon thread1 fait la première opération, tab[1] = tab[0] * 2. Si tab[0] = 1, tab[1] = 2. Si on continue on va afficher comme ça les puissances de 2.

Maintenant si je parallélise, par exemple mon thread 1 fait l'opération précédemment expliquée. Mon thread 2 qui est plus rapide attaque celle d'après avant que thread1 n'ai fini, je me retrouve avec tab[0] = 1, tab[1] = 2, tab[2] = 1.

Du coup le seul moyen c'est d'indiquer aux threads qu'ils doivent attendre les autres. Du coup l'exécution se fera aussi rapidement qu'en série, même moins vite vu qu'on doit créer les threads

Tu as déjà bien compris le problème auquel tu es confronté...

Maintenant, il "n'y a plus qu'à" trouver le moyen de le contourner

Ce qu'il te faut comprendre, c'est que la programmation multi thread impose une dimension supplémentaire à ta logique : le fait que chaque thread peut (doit ) être en mesure de travailler de manière "la plus autonome possible" par rapport aux autres threads.

Dés lors, la question devient :

Si je veux que N threads puissent faire le travail demandé sans s'inquiéter de ce que les autres threads ont fait (ou non), comment faire pour arriver à remplir mon tableau

Et c'est la que la "pensée alternative" intervient, car la réponse à cette question est sans doute proche de

Il faut que chaque thread puisse travailler sur des données qui lui sont propres

Dés lors, pourrais tu envisager de "dérouler" la boucle afin de permettre cela

[ganon551]

Merci pour cette réponse détaillée.

J'ai finalement réussi à paralléliser le calcul.

En fait je crée une variable qui est égal au nombre de thread (il y a une fonction assez simple pour ça sous windows, mais là je ne voulais pas la chercher donc j'ai juste mis le nombre de mes threads en dur dans le code).

Enfin le code parlera de lui même :

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
 
int main()
{        double init = 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001;
 
    double tab[1300] = {init};
 
    int i,j;
 
    int limite = 1300/4, limite2 = 0;
 
 
    for(j = 1; j <= 4; j++)
    {
    limite2 = j*limite;
 
    tab[limite2 - limite] = init * pow(2, limite2 - limite);
 
    for (i = limite2 - limite+1; i < limite2; i++)
    {
        for(int h = 1; h < 100000;h++)
        {
        tab[i] = tab[i-1] * 8192 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2;
        tab[i] = tab[i-1] * log(tab[i-1]) + sin(cos(tan(tab[i] * tab[i-1])));
        tab[i] = tab[i-1] * 8192 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2;
        }
 
    }
 
    }
 
 
    return 0;
}

Bon le code peut sembler très sale, et il l'est, m'enfin le but c'était d'obtenir le même résultat, ce que j'ai fait.

J'ai remplacé le tab[1] par un tab[1^-xxx], simplement parceque si je laisse en tab[1], le résultat est égal à +infini assez rapidement, et que je voulais voir si le résultat final était le même entre ma version multiThread et monoThread. Toutefois le code marche très bien avec les puissances de 2, en plus on peut enlever la multiplication par init et donc gagner du temps.

Ensuite j'ai crée une seconde boucle dans la boucle i, simplement pour que le calcul prenne du temps. Effectivement si je ne met pas cette boucle le calcul prend 0.300s et je ne vois pas la différence entre multiThread et monoThread.

Donc là en multithread je met 22s pour faire le calcul, et en monothread 59s.

Le scaling n'est pas parfait mais en même temps je n'ai que deux coeurs physiques donc ça ne m'étonne pas trop.

Est-ce que c'est ce que tu voulais dire par dérouler la boucle ?

[koala01]

Est-ce que c'est ce que tu voulais dire par dérouler la boucle ?

Oui, c'était bien l'idée

Mais je voulais te mettre sur la voie en te laissant la possibilité de réfléchir par toi même

[ganon551]

D'accord

En tout cas merci c'est agréable de réussir après avoir galéré pas mal de temps sur un problème ^^

Maintenant il faut que j 'arrive à faire pareil avec mes nombres premiers, le problème étant que je ne peux pas diviser mon tableau comme ça, vu que de toute façon chaque thread irait barrer des nombres dans les autres tableaux.

Je vais voir comment je peux faire

Edit : Bon il n'a pas l'air d'aimer quand je met la variable max en private, il plante en cours de calcul.

Est-ce que c'est pertinent de faire un flush sur des variables déclarées private ? J'imagine que non mais je demande au cas où

[koala01]

Hé bien, peut etre faut il continuer avec la pensée alternative

Plutot que de réfléchir à "comment paralléliser l'ensemble de l'algorithme", peut etre est il plus intéressant de réfléchir à "quelle partie de l'algorithme puis-je envisager de paralléliser"

Je vais te laisser réfléchir un peu à cette question, mais tu devrais pouvoir trouver par toi-même de quoi je veux parler

[EDIT] Pour te mettre sur la voie, penses que, pour avoir un résultat effectivement concluant, il faut veiller à ce que le cout de création d'un thread soit compensé par la durée du travail qu'il doit effectuer

[ganon551]

Bon j'ai réussi à paralléliser mais le traitement dure plus longtemps qu'avant.

J'ai fait comme pour l'autre calcul, j'ai entouré ma boucle principale d'une boucle qui va de 1 à 4. Du coup ma boucle interne (celle avec i) s'adapte et chaque thread calcule bien 1/4 de ce que j'ai à calculer.

Dans le gestionnaire des tâches je me retrouve bien à 100 en utilisation processeur, et il me renvoie bien le bon nombre de premiers. Pr contre il met 10% de temps en plus.

En réfléchissant, je pense que ça vient du fait qu'en série, on élimine les premiers au fur et à mesure, et donc le calcul est de plus en plus rapide. Ici comme je sépare en 4, les threads à la fin calculent pratiquement autant de choses que le premier puisque les nombres ne sont pas encore barrés.

Donc au final je ne pense pas pouvoir paralléliser cette partie du code. Le problème c'est que c'est la seule chose que je peux paralléliser

Enfin je vais essayer avec ma boucle interne maintenant je verrais.

[koala01]

Pourrais tu montrer comment tu as fait

Pour de très grands tableaux, tu devrais pouvoir gagner en performances, si tu t'y prend bien

[ganon551]

Erf j'ai supprimé le code du coup. Enfin ça donnait ç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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
int limite_i;
int sub_i = ceil(limite/4); // Où limite est la racine du nombre entré par l'utilisateur
int max;
 
#pragma omp parallel for schedule(dynamic,1) private(i,j,max)
for(int test = 1; test <= 4; test++)
{
 
limite_i = sub_i * test + 7; //Le +7 c'est parce que je veux que i commence à 7, vu que précédemment dans le code j'ai déjà supprimé tous les multiples de 2,3,5.
if(limite_i > limite)
{
limite_i = limite;
i = limite_i - sub_i + 7;//Si limite_i est sup à limite, on ne fait pas le +7, du coup on l'applique ici à i
}
else
{
i = limite_i - sub_i;
}
 
if(i % 2 == 0)
i--
 
for(;i <= limite_i;i+=2)//On parcourt les nombres jusqu'au maximum 2 par 2
     {
 
             switch(donnees.tableauStruct.testBit(i))
             {
                        case true:
                        {
                        emit changementBarre(i); 
                        max = nombrePremiers/i;
                        if(((max >> 1)<<1) == max)
                        max--;
                        ulong j=max;
                        const ulong const_i = i;
                        for(; j >= const_i; j-=2)//On parcourt les nombres de (nombre maximum)/i jusqu'a i. Ici faire la boucle en sens inverse montre de meilleures performances
                        { 
                                switch(donnees.tableauStruct.testBit(j)) 
                                {
                                case true:
                                     {
                                     donnees.tableauStruct.setBit(j*i,false);//On attribue la valeur false au bit en j*i
                                     }
                                     break;
                                }
                        }
                        }
                        break;
             }         
     }
}

Voilà, en gros c'est ça. Avec un tableau d'une taille de 1.000.000.000 je tombe sur le bon résultat, par contre il met 1s de plus qu'en série.
Peut-être que c'est à cause de mes tests avant la boucle "i", mais je ne pense pas vu qu'il ne fait ces tests que 4 fois au final.

Bon le code n'est pas exactement le même, je passe la galère du + 7 qui m'a bien embêté, mais c'est pour que tu vois l'idée.

[koala01]

Héhé... c'est bien ce que je pensais, tu t'es laissé avoir par l'exemple précédent

Le traitement qui consiste à marquer les différents éléments comme "invalides" (car non premier) ne prend presque pas de temps en soi.

C'est parce que tu dois effectuer un (très) grand nombre de fois une toute petite instruction que cela te prend du temps d'effectuer l'ensemble.

J'ai essayé de te mettre sur la voie en te disant que le fait de créer un thread prend, en lui-même, un certain temps, en espérant que tu comprendrait que tu n'aurais aucun intérêt à demander la création d'un trhead pour chaque traitement, mais, visiblement, c'était un peu trop subtile

En fait, ici, il ne s'agit plus de "dérouler" la boucle, mais bien... d'avoir N boucle qui feront chacune 1/N du travail (ou N correspond à ton nombre de thread), en veillant à ce que chaque thread ne travaille que sur des données auxquelles il sera le seul à avoir accès, si possible, en profitant du fait que les éléments d'un tableau sont contigus en mémoire pour éviter d'avoir trop de "cache miss".

Est-ce que cela te met un peu plus sur la voie

[ganon551]

Oui oui je sais bien qu'il ne faut pas créer un thread par opération ^^

Si tu regardes le code, chaque thread fait un tour de boucle extérieure, la boucle qui va de 1 à 4.

Après dans cette boule je fais un nombre d'opérations égal à limite / 4. Donc au final je fais pour 1 000 000 000 : 7906 opérations par thread.

Ce n'est peut être pas assez, mais en même temps je ne peux pas trop augmenter vu que je stocke sur un ulong.

Du coup j'ai bien compris la subtilité

Mais la particularité de ce calcul c'est que plus tu avances, moins ça prend de temps vu qu'on barre au fur et à mesure. Ici j'ai un thread1 qui barre de 7² jusqu'à 7906², pendant ce temps le thread4 barre de 23725² jusqu'à 31624², du coup il tombe sur des bits qui sont à true alors qu'en série ils seraient à false, donc je me retrouve à faire plus de calcul qu'en monothread.

[koala01]

Si tu permets, je vais peut etre commencer par te montrer la logique que j'utiliserais personnellement pour implémenter le crible d'Eratosthène, car il me semble déjà que ta logique n'est pas vraiment des meilleures.

Mais je vais un peu tricher, si tu veux bien : plutôt que de mettre à jour en permanence un tableau qui contient les nombres premiers, je vais utiliser un tableau qui contient un ensemble de (nombre maximal à tester) données qui représenteront le fait que l'indice de cette donnée est considéré comme valide (donc "potentiellement un nombre premier", jusqu'à la fin du traitement) ou non.

Et ce que je vais faire, c'est parcourir tous les indices et, si l'indice est divisible par un nombre donné (qui est celui pour lequel je cherche à savoir s'il s'agit d'un nombre premier), je ferai passer la variable à sa valeur "invalide".

Une fois que j'aurai testés tous les indices inférieurs à la racine carrée du nombre maximal à tester, je n'aurai plus qu'à parcourir une seule fois le tableau pour déterminer les indices qui correspondent encore à une valeur "valide", et le tour sera joué.

Je te montre ici le code que l'on pourrait envisager en considérant que MAX correspond au nombre maximum introduit par l'utilisateur (la limite étant placée à std::numeric_limits<size_t>::max() / 2, pour toute sécurité ), par exemple, 2 000 000 (en dessous de 1 000 000, ca va vraiment trop vite pour qu'il soit possible de constater une différence tangible )

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
/* une valeur arbitraire qui pourrait etre remplacée par une entrée utilisateur
 * les valeurs supérieures à 1 000 000 commencent à se permettre de se faire
 * une idée
 */
static const size_t MAX = 10000000;
void eratosthene(std::vector<char> & potentials, size_t toTest )
{
    for(size_t index  = toTest; index < MAX; ++index )
    {
        // si l'index testé n'est pas la valeur elle-meme et que l'index
        // est divisible par la valeur recherchée, on rend la valeur de
        // l'élément invalide
        if(index!= toTest && index % toTest == 0)
            potentials[index]= 0x0;
    }
}
int main()
{
    std::vector<char> potentials(MAX,0x1);
    size_t square = sqrt(MAX);
    /* Seuls les indices supérieurs à 2 et inférieurs à la racine carrée de MAX
     * nous intéressent, testons donc toutes les valeurs comprises entre 2 et
     * sqrt(MAX)
     */
    for(size_t toTest = 2; toTest < square;++toTest)
    {
        /* ce code peut etre désactivé, mais il permet de se rendre compte que
         * le programme ne s'est pas arrêté en cours de route :D
         */
        if( (toTest %(square / 100)) == 0)
        {
            std::cout<<"working ..."<<toTest /(square/100)<<" % done"<<std::endl;
        }
        eratosthene(potentials, toTest);
    }
  /*  YAPUKA afficher les résultats */
    for(size_t result = 1; result < MAX; ++ result)
    {
        if(potentials[result] == 0x1)
            std::cout<<result<<" est un nombre premier"<<std::endl;
    }
    return 0;
}

Maintenant que nous avons un code propre (n'hésite pas à t'intéresser à mes commentaires, je fais mon possible pour les choisir avec soin ), on peut discuter un peu

Comme tu peux le constater, je ne m'inquiète jamais de savoir si, oui ou non, l'indice testé correspond à une valeur qui a déjà été reconnue comme invalide : si l'index est invalide, je définis la valeur de l'élément de manière à ce qu'elle représente une valeur invalide, et "tant pis si c'était déjà le cas"

En effet, le test prend presque plus de temps que le fait de modifier la valeur, et toute valeur invalide le restera de toutes manières

Maintenant que nous avons des bases "saines" de discussion, parlons un peu de ce qui nous intéresse, à savoir : la parallélisation du code

En fait, je crois que tu es tellement "embourbé" dans ton problème que tu appréhende décidément ce que je veux dire d'une manière erronée, (quoi que je l'exprime peut etre mal).

Pour l'instant, tu as mis toi-même le doigt sur le problème auquel tu est confronté : certains threads doivent travailler beaucoup plus que les autres

Ce qu'il faut impérativement arriver à faire, c'est s'arranger pour faire en sorte de "partager équitablement" la tache entre les différents threads.

Pour y arriver, il faut, tout simplement, essayer de faire en sorte que le nombre de traitement soit équitablement réparti entre chaque thread, tout en évitant de créer des threads trop souvent.

Tel que je te le présente, le code est prêt à une adaptation pour le multi thread :

A vrai dire, j'envisage deux solutions pour y arriver, mais je ne peux absolument pas te dire laquelle sera la meilleure

L'une des solutions passe par l'adaptation du prototype de la fonction eratosthene et la modification de la fonction main(), l'autre passe par la seule modification de la fonction eratosthene, sans rien changer ni à son prototype, ni à la fonction main().

Sauras tu trouver ces solutions, sachant que tu peux parfaitement arriver à ne tester que MAX / nombre de thread éléments dans chaque thread

[ganon551]

Merci pour ce code

Juste, au niveau du temps d'exécution il est tout de même très lent, sur mon ordinateur 10s pour calculer les primes jusqu'à 1000000, sans l'affichage que j'ai supprimé

Enfin ça me permettra au moins de bien remarquer la différence entre le monothread et le multithread.

Le code que j'ai montré ne montre qu'une petite partie de ma logique pour le crible, par exemple j'utilise une roue de factorisation pour l'initialisation, ce qui fait gagner énormément de temps.

Enfin revenons à la parallélisation.

En ce qui concerne le moyen de paralléliser, dans le code que j'ai montré avant je traitais exactement sqrt(MAX) / 4 opérations par thread, ici je vais essayer de paralléliser ton code, mais il ne marche pas vraiment comme le mien, du cou je ne sais pas si je pourrais le reporter.

Enfin on va essayer ! J'ai remplacé l'affichage des premiers par un simple compte pour vérifier que tout va bien quand je passerais en multiThread

[koala01]

En fait, tu peux facilement multiplier la vitesse de traitement par trois (pour 1 000 000 d'éléments) en rajoutant, effectivement, un test sur la valeur indiquée sous la forme de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
void eratosthene(std::vector<char> & potentials, size_t toTest )
{
    for(size_t index  = toTest; index < MAX; ++index )
    {
        // si l'index testé n'est pas la valeur elle-meme et que l'index
        // est divisible par la valeur recherchée, on rend la valeur de
        // l'élément invalide
        if(potentials[index] && index!= toTest && index % toTest == 0)
            potentials[index]= 0x0;
    }
}

Mais l'avantage qu'il peut y avoir à paralléliser une fonction lente est que tu devrait obtenir une différence d'autant plus grande

[ganon551]

Oui il y a pas mal de choses à améliorer pour qu'il soit compétitif, à titre d'exemple le mien met 4ms pour calculer les premiers jusqu'à 1.000.000.

Mais effectivement un algo simple est plus simple à paralléliser et on peux toujours optimiser une fois le parallélisme mis en place

EDIT : Le simple fait de rajouter :

#pragma omp parallel for private(index)

Avant la boucle for dans la fonction eratosthene() me fait déjà gagner 6s sur le calcul, je passe donc de 10s à 4s.

J'essaie l'autre technique, je vais modifier le prototype et faire passer un tableau 4 fois moins grand pour traiter le tableau sur 4 threads.

EDIT2 (oui j'aime éditer ) : Intéressant, avec le pragma d'avant, on peux voir facilement l'impact de la création de threads dans le cas où ils n'ont que peu de calculs à faire. Par exemple si on rajoute un schedule(dynamic,1), il met très longtemps (genre plus d'une minute). Si on met 10000 il met 4s.

[koala01]

Oui il y a pas mal de choses à améliorer pour qu'il soit compétitif, à titre d'exemple le mien met 4ms pour calculer les premiers jusqu'à 1.000.000.

Mais effectivement un algo simple est plus simple à paralléliser et on peux toujours optimiser une fois le parallélisme mis en place

Ben le simple changement que je viens de te proposer fait descendre le calcul pour le premier million en dessous de la barre des 3 secondes

Ceci dit, un algorithme simple n'est pas seulement plus facile à paralléliser, il est aussi beaucoup plus simple a comprendre, à maintenir et à corriger en cas de problème.

Et, comme tu peux le constater, les changements nécessaires à l'amélioration des performances s'avèrent généralement triviaux

Je me demande d'ailleurs si l'on ne pourrait pas encore améliorer les choses en évitant de tester les index dont on sait qu'ils ne sont déjà pas premiers , je vais y jeter un oeil

[koala01]

Comme je m'y attendais plus ou moins, on descend à 0.512 secondes pour le premier million d'éléments avec le code

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
/* une valeur arbitraire qui pourrait etre remplacée par une entrée utilisateur
 * les valeurs supérieures à 1 000 000 commencent à se permettre de se faire
 * une idée
 */
static const size_t MAX = 1000000;
void eratosthene(std::vector<char> & potentials, size_t toTest )
{
    for(size_t index  = toTest; index < MAX; ++index )
    {
        // si l'index testé n'est pas la valeur elle-meme et que l'index
        // est divisible par la valeur recherchée, on rend la valeur de
        // l'élément invalide
        if(potentials[index] && index!= toTest && index % toTest == 0)
            potentials[index]= 0x0;
    }
}
int main()
{
    std::vector<char> potentials(MAX,0x1);
    size_t square = sqrt(MAX);
    /* Seuls les indices supérieurs à 2 et inférieurs à la racine carrée de MAX
     * nous intéressent, testons donc toutes les valeurs comprises entre 2 et
     * sqrt(MAX)
     */
    for(size_t toTest = 2; toTest < square;++toTest)
    {
        /* ce code peut etre désactivé, mais il permet de se rendre compte que
         * le programme ne s'est pas arrêté en cours de route :D
         */
        if( (toTest %(square / 100)) == 0)
        {
            std::cout<<"working ..."<<toTest /(square/100)<<" % done"<<std::endl;
        }
        if(potentials[toTest])
        {
            eratosthene(potentials, toTest);
        }
    }
  /*  YAPUKA afficher les résultats
    for(size_t result = 1; result < MAX; ++ result)
    {
        if(potentials[result] == 0x1)
            std::cout<<result<<" est un nombre premier"<<std::endl;
    } */
    return 0;
}

(affichage de la progression compris )

[ganon551]

Oui pour l'optimisation de cet algo je commence à connaître ^^

Par exemple ce code :

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
 
#include <iostream>
#include <omp.h>
#include <math.h>
#include <vector>
#include <bitset>
#include <cmath>
#include <cstdlib>
 
static const size_t MAX = 1000000;
void eratosthene(std::vector<char> & potentials, size_t toTest )
{
    size_t index;
    #pragma omp parallel for schedule(dynamic, 50000) private(index)
    for(index  = toTest; index < MAX; index+=2 )
    {
        if(potentials[index] && index!= toTest && index % toTest == 0)
            potentials[index]= 0x0;
    }
}
int main()
{
    std::vector<char> potentials(MAX,0x1);
    size_t square = sqrt(MAX);
    /* Seuls les indices supérieurs à 2 et inférieurs à la racine carrée de MAX
     * nous intéressent, testons donc toutes les valeurs comprises entre 2 et
     * sqrt(MAX)
     */
 
    for(size_t result = 0; result < MAX;result+=2)
    {
       potentials[result] = 0x0;
    }
 
    potentials[2] = 0x1;
 
    for(size_t toTest = 3; toTest < square;toTest+=2)
    {
        eratosthene(potentials, toTest);
    }
  /*  YAPUKA afficher les résultats */
  int compteur = 0;
    for(size_t result = 2; result < MAX; ++ result)
    {
        if(potentials[result] == 0x1)
            compteur++;
    }
    std::cout << compteur << std::endl;
    return 0;
}

Calcule les premiers en 1.3s On incrémente de 2 en 2 pour éviter les pairs, et on initialise au début les pairs dans le tableau à 0x0.

Par contre tu as peut-être mal lu, j'ai dit 4ms pour mon programme, pas 4s

Pour la parallélisation je vais faire l'autre et voir laquelle est la mieux
Mais je pense que celle effectuée avant une boucle for, comme celle présente actuellement sur le code, permet de meilleures performances. enfin on va voir