Discussion :

[CSharpN]

Bonjour,

J'ai actuellement dans un programme une boucle qui prend pas mal de temps qui ressemble á :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
for(i = 1; i< 256; i++)
{
   data = M/i % 256;
   h = HammingWeight(data);
   sum1[i] += h;
   sum2[i] += h*h;
 
   for(k=0; k<1000; k++)
      sum3[i][k] += h* tab[k];
}
// M et tab sont définis avant la boucle.

J'aimerai accelerer ce code en le passant en parallele avec Parallel.For mais je n'arrive pas á m'en sortir a cause des sommes auxquelles on accede en meme temps.

Avec :

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
 
Parralel.For(1, 256, tst =>
{
   i = tst;
   data = M/i % 256;
   h = HammingWeight(data);
 
   lock(this)
   {
      sum1[i] += h;
      sum2[i] += h*h;
 
      for(k=0; k<1000; k++)
         sum3[i][k] += h* tab[k];
   }
});

Je ne gagne pas de temps car le lock l'empeche mais je ne comprend pas comment passer en 3 fonctions, comme je l'ai souvent vu sur le net.
Je voudrais faire qqch qui ressemble á :

Code :

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

1
2
3
4
5
6
int sum = 0;
Parallel.For(0, 100, () => 0, (i,state)=>
{
    if (isPrime(i)) state.ThreadLocalState += i;
},
partialSum => Interlocked.Add(ref sum, partialSum));

Mais qui garde toutes mes sommes et mon tableau de sommes

Est-ce que l'un d'entre vous pourrait m'aider ?

Cordialement.


RQ : J'ai essayer avec un paralle.Invoke et des sommes locales mais je n'y arrive pas non plus.

[antoine.debyser]

Bonjour,

Prenons le cas d'un parcours de somme tous bete, comme tu l'as remarqué, si tu fais un simple lock tu ne gagne pas de temps. La technique pour gagner du temps c'est de faire des sommes partielles puis de locker pour la somme des sommes partielles.

Example (tirer du site de Ben Albahari)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
object locker = new object();
double grandTotal = 0;
 
Parallel.For (1, 10000000,
 
  () => 0.0,                        // Initialize the local value.
 
  (i, state, localTotal) =>         // Body delegate. Notice that it
     localTotal + Math.Sqrt (i),    // returns the new local total.
 
  localTotal =>                                    // Add the local value
    { lock (locker) grandTotal += localTotal; }    // to the master value.
);

Comme tu stockes tes sommes en fonction de l'indice i. Il te faut un tableau temporaire de stockage. Et comme tu veux faire plusieurs somme d'un coup une structure pour stocker tes 3 tableaux temporaires me parait bien.


EDIT:

Voici une ebauche de la chose:

Code :

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

1
2
3
4
5
6
7
 
public class SumsTmp
        {
            public double[] simple;
            public double[] carre;
            public List<double[]> complex;
        }

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
 
Parallel.For(1, 256,
                         () => new SumsTmp(),
                         (i, state, localSum) =>
                             {
                                 double data = M/i%256;
                                 double h = HammingWeight(data);
                                 localSum.simple[i] += h;
                                 localSum.carre[i] += h*h;
 
                                 for (int k = 0; k < 1000; ++k)
                                     localSum.complex[i][k] += h*tab[k];
                                 return localSum;
                             },
                         localSum =>
                             {
                                 lock (_locker)
                                 {
                                     for (int i = 1; i < 256; ++i)
                                     {
                                         final.simple[i] += localSum.simple[i];
                                         final.carre[i] += localSum.carre[i];
 
                                         for (int k = 0; k < 1000; ++k)
                                             final.complex[i][k] += localSum.complex[i][k];
                                     }
                                 }
                             }
                );

Mais l’agrégation des sommes prendras pas mal de temps, le parcours de "tab" est un réel probleme

EDIT2:
J'avais oublier le retour du corps, du coup j'ai passé la struct en class

[CSharpN]

Bonjour,

Merci de me répondre,
Je vais essayer de créer une structure pour les resultats, je n'y avais pas pensé. Par contre, comment je crée ma fonction finale

Code :

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

1
2
3
 
localTotal =>                                    
    { lock (locker) grandTotal += localTotal; }

alors que j'ai une autre boucle pour "les sous sommes" (la boucle en k) ? Mon tableau résultat dépend de l'indice i, existe-t-il encore á ce moment lá ?

[antoine.debyser]

Non ton indice n'existe plus à ce moment là.

Comme je le disais dans mon edit, la boucle en k est un réel problème.
Si la méthode "HammingWeight" est relativement courte, on peut essaye en ne parallélisant que la boucle sur k

[CSharpN]

Bonjour,

Merci pour la réponse, je n'avais pas vu l'edit.

Ce qui me prend du temps c'est la division M/i (car M est un bigInteger) et la boucle k, c'est pourquoi je voulais faire mon parallel.for sur la boucle en i. Je vais essayer votre proposition, si je ne gagne pas de temps j'essaierai seulement sur la boucle k.

Merci beaucoup en tous cas.

Cordialement

[CSharpN]

Bonjour,

Bon alors, voilá j'ai tenté de passer mon localSum comme il avait été proposé mais je me retrouve avec le meme probleme que lorsque j'essaie de faire ma somme pas en local et sans lock : lors de la boucle k : k vaut 1000 et i 256 et j'ai une exception index out of range bien sur.

Je ne comprend pas pourquoi ma condition <1000 et 256 n'est pas vérifiée, auriez vous une idée ?

Cordialement

[antoine.debyser]

Comment initialises tu tes tableaux?

[CSharpN]

Bonjour,

J'ai fais un constructeur qui prend en parametre nb1 et nb2 (ici 256 et 1000) et j'ai declaré :

Code :

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

1
2
3
4
5
6
7
8
9
 
public Sums(int nb1, int nb2)
{
locH = new double[nb1]
locHcarre = new double[nb1]
locCoprod = new doule[nb1][]
for(i=0; i<nb2; i++)
   locCoprod[i] = new double[nb2]
}

Euh, j'ai mis un tableau a 2 dimensions au lieu d'une liste car je suis plus á l'aise avec un tableau, est-ce un probleme ?

[antoine.debyser]

Du coup il y a un petit problème avec "i", il doit varier entre 0 et 255 pour accéder correctement au tableau.

Code :

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

Parallel.For(0, 256,

Code :

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

for (int i = 0; i < 256; ++i)

et du coup il ne faut faire attention a la division

Code :

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

M/(i+1)%256;

Par rapport à ton constructeur, non les tableaux ne sont pas un problème tant qu'ils restent de dimension 1.
Par contre ça devrait pas être

Code :

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

1
2
3
for(i=0; i<nb1; i++)
   locCoprod[i] = new double[nb2];
}

Sinon peux tu indiqué plus précisément ou à lieu l'exception, et quels sont les états des variables "i" et "k"?

[CSharpN]

Bonjour,

Je ne comprend pas pourquoi il y a un probleme avec le i, je veux bien le faire varier de 1 á 255. (par contre pour la suite de mon programme je l'utilise parfois de 0 a 255 auquel cas je mets une boucle de 0 a 255)

Oui bien sur c'est

Code :

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

1
2
3
 
for(i=0; i<nb1; i++)
   locCoprod[i] = new double[nb2];

mauvaise recopie de mon code

Sinon mon erreur apparait comme ceci :

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
Parallel.For(1, 256,
                         () => new SumsTmp(),
                         (i, state, localSum) =>
                             {
                                 double data = M/i%256;
                                 double h = HammingWeight(data);
                                 localSum.simple[i] += h;
                                 localSum.carre[i] += h*h;
 
                                 for (int k = 0; k < 1000; ++k)
                                     localSum.complex[i][k] += h*tab[k];
                                 return localSum;
                             },
                         localSum =>
                             {
                                 lock (_locker)
                                 {
                                     for (int i = 1; i < 256; ++i)
                                     {
                                         final.simple[i] += localSum.simple[i];
                                         final.carre[i] += localSum.carre[i];
 
                                         for (int k = 0; k < 1000; ++k)
                                             final.complex[i][k] += localSum.complex[i][k];
                                     }
                                 }
                             }
                );

avec IndexOutOfRangeException, i = 256 et k = 1000.

Je ne comprend pas comment i et k peuvent prendre ces valeurs. J'ai essayé de débuguer mais le mode parallele rend ca trop compliqué (du moins pour moi).

[antoine.debyser]

"i" ne peux pas valoir 256.
"k" ne peux pas valoir 1000.
Es-tu sur que "tab" est correctement initialisé? Es tu sur de ne pas avoir déclarer "i" ou "k" a l'exterieur de lambda expression.

J'ai fais un test chez moi, et tous est bon.

[CSharpN]

En effet j'avais déjá déclaré i et k avant ma boucle (je n'avais pas compris qu'ils devaient etre locaux )

Par contre maintenant les resultats des sommes sont faux

Ceci dit ca prend beaucoup plus de temps qu'avant donc je pense que je vais laisser tomber l'idée.

Je prend quand meme les conseils si qqn sait pourquoi les resultats sont faux.

Merci antoine.debyser pour ta patience !

[antoine.debyser]

Je n'ai aucune idée de la performance du truc. Mais voici les conditions de mon test.
M = factoriel(125)
La valeurs d'une case de "tab" est égale à son index.
Sur un quad-core à 2.6Ghz (Q8400 pour être précis), le temps de calcul total est de 8 ms.
Les résultats semblent correct à première vu.

[CSharpN]

Pardon je me suis mal fait comprendre :
les resultats des sommes sont faux, je ne trouve plus les meme choses qu'avec la boucle for classique.

Par rapport aux performances, je vois bien que mes 8 coeurs sont utilisés contrairement á précédemment mais le temps est multiplié par 4... J'aurais espéré gagner un peu de temps mais bon je vais chercher une autre solution.