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 :
J'ai modifié mon code pour les besoins des tests avec OpenMP, mais globalement c'est le 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 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; } }
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é![]()
Partager