Besoin d'aide OpenMP

**ganon551** · 29/12/2012, 19h22

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** · 29/12/2012, 21h15

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** · 29/12/2012, 21h23

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** · 30/12/2012, 10h04

Salut,

Envoyé par ganon551

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** · 30/12/2012, 22h02

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 ?