Discussion :

[koala01]

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.

Honnêtement, ca, ca ne sert, à mon avis, pas à grand chose...

En effet, tu ne fais que faire "a mano" ce que ton algorithme est sensé faire lors de sa première passe

A partir de là:

1. Dans le meilleurs des cas, tu ne profites pas de la possibilité de paralléliser cette initialisation, ce qui est dommage
2. Tu "triches" un tout petit peu dans tes mesures, étant donné que tu ne compte pas ce passage (qui fait pourtant partie de l'algorithme) dans le temps nécessaire au traitement

Si tu pars dans cette direction, autant le faire jusqu'au bout avec les nombres premiers inférieurs à 100

[ganon551]

C'est en fait ce que font les algo les plus performants avec la factorization wheel, la roue de factorisation. Ils suppriment d'emblée les multiples des premiers premiers. Au final ça n'est pas tricher puisque tu les barres quand même. Par ailleurs je compte le tout dans le temps de traitement

Ce que je fais dans le dernier code n'est pas faire à la main ce qu'est sensé faire le code

Au final je saute les nombres pairs, dont je sais d'emblée qu'ils ne sont pas premiers. Le but étant de ne pas passer par des nombres inutiles

Et au final, on fait bien la même chose, mais en plus vite et avec moins d'opérations de test, donc forcément ça va plus vite. Par contre on ne peux pas faire ça pour tous les premiers, ça finit par être plus lent. Le but est de le faire jusqu'à 7 voire 11 pour certains.

Je vais faire la parallélisation mais je suis en train de jouer à un jeu de cartes

(Par ailleurs ça s'appelle cards vs humanity et je vous le conseille).


EDIT : Bon j'ai fais exactement la même chose qu'avec mon code, soit :

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
 
#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;
 
    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;
 
    size_t limite = 0;
    size_t sub = ceil(square/4);
    size_t toTest;
 
    #pragma omp parallel for schedule(dynamic, 1) private(toTest, limite)
    for(size_t test = 1; test <= 4; test++)
    {
        limite = test * sub + 3;
        for(toTest = limite - sub; toTest < limite;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;
}

J'ai donc crée une boucle externe qui parcours les 4 coeurs et leur assigne chacun un thread faisant square / 4 opérations.

Contre ce que je pensais, le temps d'exécution est en fait plus rapide qu'avec le simple pragma en début de boucle for, dans la fonction eratosthene (donc le code que j'ai mis à la page précédente).

En effet, je trouve les premiers jusqu'à 1 000 000 en 0.8s, contre 1.3 avec la version multiThread de la page d'avant.

Le problème c'est que j'ai testé ça sur mon code et ça l'a ralenti. Peut-être le fait que mon algo est différent ?

EDIT 2 : Petite question, est-il normal de gagner encore du temps en mettant les deux directives pragma ? Celle qui sépare le travail en 4 morceaux et celle qui parallélise la boucle for dans la fonction eratosthene ? Je gagne environ 100ms.

Sinon on peux encore gagner du temps en vérifiant si potentials[toTest] est ur 0x1 avant de lancer la fonction eratothene. En faisant ça on tombe à 0.3s.

On est quand même passé de 10s à 0.3s
C'est prenant l'optimisation

EDIT3 : Bon en modifiant la boucle for dans eratosthene comme suit :

for(index = toTest*toTest; index < MAX; index+=toTest )
{
if(potentials[index] && index!= toTest && index % toTest == 0)
potentials[index]= 0x0;
}

C'est à dire en partant de toTest² et en allant par pas de toTest, on tombe carrément à 50ms pour 1.000.000 et 0.3s pour 10.000.000. Soit par rapport aux 10s du début un facteur de 2000%

[koala01]

En fait, ce que j'aurais envisager, c'est quelque chose comme

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
void eratosthene(std::vector<char> & potentials, size_t toTest )
{
    size_t index;
    size_t dividedSize = potentials.size() / NombreDeThreads ;
    /* la directive pragma viendrait sans doute ici ;) */
   for(int th = 0 ; th< NombreDeThreads ; ++th)
   {
       size_t begin = th * dividedSize;
       /* assurons nous que l'index de début est bel et bien un multiple
        * de toTest, de manière à éviter le test sur le modulo ;)
        */
      begin -= begin % toTest;
       size_t end = (th+1) *dividedSize;
       for(index  = begin; index < end; index+=2 )
       {
           if(potentials[index] && index!= toTest && index)
               potentials[index]= 0x0;
       }
   }
}

De cette manière, il y aura effectivement un thread (le premier) qui fera un peu moins que les autres, mais tu évites au maximum les cache misses, dans le sens ou chaque thread travaille de manière systématique sur un ensemble de données contigues en mémoire

Alors, évidemment, cela signifie que tu vas créer NombreDeThreads threads à chaque fois que tu appelleras fonction, ce qui est, quelque part, dommage, étant donné que ca fera beaucoup de threads à créer au final, et donc beaucoup de temps perdu.

La deuxième solution que j'envisageais est de travailler sur la fonction main, sous une forme proche de

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
/* il faut modifier un peu la fonction pour que ca marche */
void eratosthene(std::vector<char> & potentials, size_t begin, size_t end,
 size_t toTest )
{
    size_t index;
       /* on peut s'éviter le test sur le modulo si l'on est sur que l'index 
        * "begin" est bel et bien un multiple de toTest...
        * cette condition est vérifiée dans main, et nous allons donc "prendre
        * le risque" de faire confiance à la fonction appelante :D
        */
       for(index  = begin; index < end; index+=toTest )
       {
           if(potentials[index] && index!= toTest )
               potentials[index]= 0x0;
       }
   }
}
int main()
{
 
    std::vector<char> potentials(MAX,0x1);
    size_t square = sqrt(MAX);
 
    for(size_t result = 0; result < MAX;result+=2)
    {
       potentials[result] = 0x0;
    }
 
    potentials[2] = 0x1;
    size_t size = potential.size();
    size_t divided = size / 4; // partons du principe de 4 threads ;)
 
    /* 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 index = 2;index < square; ++index)
    {
        /* la directive pragma vient sans doute ici
         * mais je te laisse le soin de trouver comment faire pour que les threads
         * ne soient lancés qu'une fois ;)
         */
        for(int th = 0; th <4; ++ th)
        {
            /* en première approximation, chaque thread travaille sur une
             * part égale des valeurs à tester
             */ 
            size_t begin = th * divided; 
            /* assurons nous que begin est bel et bien un multiple de l'index
             * à tester
            begin -= begin % modulo;
            size_t end = (th+1) * divided;
            if(potential[index]==0x1)
                eratosthene(potentials, begin, end, index);
        }
    } 
    /*...*/
}

Cependant, je dois t'avouer que cette manière d'envisager les choses me laisse un mauvais gout en bouche, car la fonction erastothene part du principe que la fonction appelante fera bien son boulot, sans effectuer la moindre vérification de cette assertion

[ganon551]

Merci pour ta réponse après ce break de fêtes ! Bonne année au passage.

Je viens d'essayer la deuxième solution, pas la première qui effectivement me semble trop gourmande en création de threads.

La seconde solution marche parfaitement, mais n'apporte pas grand chose. Sur un calcul jusqu'à 10^9 je passe de 23s à 19s, le scaling n'est pas excellent.

Je ne comprend pas bien pourquoi d'ailleurs.

Sinon je me suis lancé dans la version du crible segmenté, qui est sensée être plus rapide mais qui pour le moment est beaucoup plus lente

Je vais peut-être essayer l'autre solution de ton post, à voir si la création des threads ne ralentit pas trop.