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